刷題目標：

刷題計劃：

• 前TOP100，學習java解題，每天2道題，先刷2遍，和小姐妹互相監督（自己剛搭建好的博客），
• 陣列-> 鏈表-> 哈希表->字串->堆疊與佇列->樹->回溯->貪心->動態規劃->圖論->高級資料結構，從簡單刷起，再慢慢做中等、困難題目，
• 盡量不要用暴力！！！

內容：

陣列

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. 最大子序和

解題思路
對于含有正數的序列而言，最大子序列和肯定是正數，所以頭尾肯定都是正數；
我們可以從第一個正數開始算起，每往后加一個數便更新一次和的最大值；
當前子序列和為負數時，則表明此前序列無法為后面提供最大子序列和，因此必須重新確定序列首項，

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. 買賣股票的最佳時機

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. 多數元素

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

283. 移動零

先統計非零元素個數，再將非零的緊湊的重新分配到陣列，剩下的直接賦值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. 找到所有陣列中消失的數字

遍歷陣列，將每個數字交換到它理應出現的位置上，下面情況不用換：
當前數字本就出現在理應的位置上，跳過，不用換，
當前數字理應出現的位置上，已經存在當前數字，跳過，不用換，
再次遍歷，如果當前位置沒對應正確的數，

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. 自律不行他律！