• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

Leetcode刷题计划1

互联网 diligentman 2周前 (04-30) 8次浏览

刷题目标:

刷题计划:

  • 前TOP100,学习java解题,每天2道题,先刷2遍,和小姐妹互相监督(自己刚搭建好的博客)。
  • 数组-> 链表-> 哈希表->字符串->栈与队列->树->回溯->贪心->动态规划->图论->高级数据结构,从简单刷起,再慢慢做中等、困难题目。
  • 尽量不要用暴力!!!

内容:

数组

1. 两数之和

Leetcode刷题计划1
Leetcode刷题计划1

class Solution {
    public int[] twoSum(int[] nums, int target) {
 	if (nums == null || nums.length == 0) return new int[0];
    // 数据预处理
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) { // O(n)
        map.put(nums[i], i);
    }

    for (int i = 0; i < nums.length; i++) { // O(n)
        int x = nums[i];
        // 哈希查找 - O(1)
        if (map.containsKey(target - x)) {
            int index = map.get(target - x);
            // i 和 index 不是同一个元素,同一个元素不能使用两次
            if (i != index) return new int[]{i, index};
        }
    }
    return new int[0];
    }
}

53. 最大子序和

Leetcode刷题计划1
Leetcode刷题计划1

解题思路
对于含有正数的序列而言,最大子序列和肯定是正数,所以头尾肯定都是正数;
我们可以从第一个正数开始算起,每往后加一个数便更新一次和的最大值;
当前子序列和为负数时,则表明此前序列无法为后面提供最大子序列和,因此必须重新确定序列首项。

class Solution {
    public int maxSubArray(int[] nums) {
        int sum=0;
        int ans=nums[0];
        for(int i=0;i<nums.length;i++){
            if(sum>0){
                sum+=nums[i];
            }else{
                sum=nums[i];//记录前一个数
            }
            if(ans<=sum){
                ans=sum;
            }
        }
        return ans;
    }
}

121. 买卖股票的最佳时机

Leetcode刷题计划1
Leetcode刷题计划1

public class Solution {
    public int maxProfit(int prices[]) {
        int minprice = Integer.MAX_VALUE;
        int maxprofit = 0;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minprice) {
                minprice = prices[i];//历史最低点
            } else if (prices[i] - minprice > maxprofit) {
                maxprofit = prices[i] - minprice;
            }
        }
        return maxprofit;
    }
}

169. 多数元素

Leetcode刷题计划1

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }
}

283. 移动零

Leetcode刷题计划1

先统计非零元素个数,再将非零的紧凑的重新分配到数组,剩下的直接赋值0。

class Solution {
    public void moveZeroes(int[] nums) {
        int cnt=0;//记录非零元素个数
        for(int i=0;i<nums.length;i++){
            if(nums[i]!=0) cnt++;
        }
        int index=0;
        for(int i=0;i<nums.length;i++){
            if(nums[i]!=0) {
                nums[index]=nums[i];
                index++;
            }
        }
        for(int i=index;i<nums.length;i++){
            nums[i]=0;
        }
    }
}

448. 找到所有数组中消失的数字

Leetcode刷题计划1

遍历数组,将每个数字交换到它理应出现的位置上,下面情况不用换:
当前数字本就出现在理应的位置上,跳过,不用换。
当前数字理应出现的位置上,已经存在当前数字,跳过,不用换。
再次遍历,如果当前位置没对应正确的数。

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        //利用数组与索引建立关系
        List<Integer> res = new ArrayList<>();
        int num;//记录索引下的值
        for(int i = 0 ; i < nums.length ; i++){
            num = Math.abs(nums[i])-1;
            if(nums[num] > 0){ //索引下的值在理应位置是一个其余大于0的值,变为负数
                nums[num] *= -1;
            }
        }
        for(int i=0 ; i < nums.length ; i++){
            if(nums[i] > 0){//若最后在理应位置不是负数,说明这个数在其他位置重复,理应的数又没出现
                res.add(i+1);//不存在的存入
            }
        }
        return res;
    }
}

总结:

  1. 复习了java一些语法,忘性太快了。
  2. 在做题时,总是用暴力简单思维,以后多学习题解中动规,dp,容器巧妙解决的思路吧。
  3. 自律不行他律!

程序员灯塔
转载请注明原文链接:Leetcode刷题计划1
喜欢 (0)