刷題（day01）

1、leetcode485.最大連續1的個數

給定一個二進制數組?nums?，計算其中最大連續?1?的個數。

示例 1：
輸入：nums = [1,1,0,1,1,1]
輸出：3
解釋：開頭的兩位和最后的三位都是連續 1 ，所以最大連續 1 的個數是 3.
示例 2:
輸入：nums = [1,0,1,1,0,1]
輸出：2
提示：

1 <= nums.length <= 10^5
nums[i]?不是?0?就是?1.

① 常規思路：遍歷數組，記錄連續1的個數，比較是否是當前最大個數。

public class Solution {public int findMaxConsecutiveOnes(int[] nums) {int count = 0;int result = 0;for (int i = 0; i < nums.length; i++) {if(nums[i] == 1){count ++;}else{result = Math.max(count,result);count = 0;}result = Math.max(count,result);}return result;}
}

② 滑動窗口思路：

當輸出或比較的結果在原數據結構中是連續排列的時候，可以使用滑動窗口算法求解。

將兩個指針比作一個窗口，通過移動指針的位置改變窗口的大小，觀察窗口中的元素是否符合題意。

初始窗口中只有數組開頭一個元素。
當窗口中所有元素為1時，右指針向右移動，擴大窗口。
當窗口中存在 0 時，計算連續序列長度，左指針指向右指針。

public class Solution {public int findMaxConsecutiveOnes(int[] nums){int length = nums.length;int left = 0;int right = 0;int maxSize = 0;while(right < length){//當滑動窗口所有元素為 1 時，右指針向右移，擴大窗口if(nums[right++] == 0){//當窗口中存在 0 時，計算連續序列長度，左指針指向右指針maxSize = Math.max(maxSize,right - left - 1);left = right;}}//因為最后一連續序列在循環中無法比較，所以在循壞外進行比較return Math.max(maxSize,right - left);}
}

?2、leetcode26.刪除有序數組中的重復項

給你一個?非嚴格遞增排列?的數組?nums?，請你?原地?刪除重復出現的元素，使每個元素?只出現一次?，返回刪除后數組的新長度。元素的?相對順序?應該保持?一致?。然后返回?nums?中唯一元素的個數。

考慮?nums?的唯一元素的數量為?k?，你需要做以下事情確保你的題解可以被通過：

更改數組?nums?，使?nums?的前?k?個元素包含唯一元素，并按照它們最初在?nums?中出現的順序排列。nums?的其余元素與?nums?的大小不重要。
返回?k?。

判題標準:

系統會用下面的代碼來測試你的題解:
int[] nums = [...]; // 輸入數組
int[] expectedNums = [...]; // 長度正確的期望答案
int k = removeDuplicates(nums); // 調用
assert k == expectedNums.length;
for (int i = 0; i < k; i++) {assert nums[i] == expectedNums[i];
}
如果所有斷言都通過，那么您的題解將被?通過。

示例 1：
輸入：nums = [1,1,2]
輸出：2, nums = [1,2,_]
解釋：函數應該返回新的長度 2 ，并且原數組 nums 的前兩個元素被修改為 1, 2 。
不需要考慮數組中超出新長度后面的元素。
示例 2：
輸入：nums = [0,0,1,1,1,2,2,3,3,4]
輸出：5, nums = [0,1,2,3,4]
解釋：函數應該返回新的長度 5， 并且原數組 nums 的前五個元素被修改為 0, 1, 2, 3, 4。不需要考慮數組中超出新長度后面的元素。
提示：

1 <= nums.length <= 3 * 10^4
-10^4?<= nums[i] <= 10^4
nums?已按?非嚴格遞增?排列

① 解題思路：雙指針

首先注意數組是有序的，那么重復的元素一定會相鄰，要求刪除重復，實際上就是將不重復的元素移到數組的左側。考慮用到 2 個指針，一個在前記作 i，一個在后記作 j。

比較 i 和 j 位置的元素是否相等，如果相等，i 后移 1 位，如果不相等，將 i 位置的元素復制到 j + 1 位置上，j 后移 1 位，i 后移 1 位重復上述過程，知道 i 等于數組長度。返回 j + 1，即為新數組長度。

class Solution {public int removeDuplicates(int[] nums) {if(nums == null || nums.length == 0) return 0;int n = nums.length;int j = 0;for(int i = 0;i < n;i ++){if(nums[i] != nums[j]){nums[++j] = nums[i];}}return j + 1;}
}

3、leetcode283.移動零

給定一個數組?nums，編寫一個函數將所有?0?移動到數組的末尾，同時保持非零元素的相對順序。

請注意?，必須在不復制數組的情況下原地對數組進行操作。

示例 1:
輸入: nums = [0,1,0,3,12]輸出: [1,3,12,0,0]示例 2:
輸入: nums = [0]輸出: [0]
提示:

1 <= nums.length <= 10^4
-231?<= nums[i] <= 231?- 1?

① 兩次遍歷

思路：我們創建兩個指針 i 和 j，第一次遍歷的時候指針 j 用來記錄當前有多少非0 元素。即遍歷的時候每遇到一個非0 元素就將其往數組左邊挪，每一次遍歷完后，j 指針的下標就指向了最后一個非0 元素下標。第二次遍歷的時候，起始位置就從 j 開始到結束，將剩下的這段區域內的元素全部置為0。

class Solution {public void moveZeroes(int[] nums) {if(nums==null) return;//第一次遍歷的時候，j指針記錄非0的個數，只要是非0的統統都賦給nums[j]int j = 0;for(int i=0;i<nums.length;++i) {if(nums[i]!=0) {nums[j++] = nums[i];}}//非0元素統計完了，剩下的都是0了//所以第二次遍歷把末尾的元素都賦為0即可for(int i=j;i<nums.length;++i) {nums[i] = 0;}}
}

②一次遍歷

如下所示，我們可以將 j 移動到自身右側第一個元素為 0 的位置，將 i?移動到 j?右側第一個元素非 0 的位置，然后交換元素。

?然后再執行上一步驟，循環下去，直至 i 抵達邊界。

class Solution {public void moveZeroes(int[] nums) {if(nums==null) {return;}//兩個指針i和jint j = 0;for(int i=0;i<nums.length;i++) {//當前元素!=0，就把其交換到左邊，等于0的交換到右邊if(nums[i]!=0) {int tmp = nums[i];nums[i] = nums[j];nums[j++] = tmp;}}}
}

4、leetcode27.移除元素

給你一個數組?nums?和一個值?val，你需要?原地?移除所有數值等于?val?的元素。元素的順序可能發生改變。然后返回?nums?中與?val?不同的元素的數量。

假設?nums?中不等于?val?的元素數量為?k，要通過此題，您需要執行以下操作：

更改?nums?數組，使?nums?的前?k?個元素包含不等于?val?的元素。nums?的其余元素和?nums?的大小并不重要。
返回?k。

用戶評測：

評測機將使用以下代碼測試您的解決方案：
int[] nums = [...]; // 輸入數組
int val = ...; // 要移除的值
int[] expectedNums = [...]; // 長度正確的預期答案。// 它以不等于 val 的值排序。int k = removeElement(nums, val); // 調用你的實現assert k == expectedNums.length;
sort(nums, 0, k); // 排序 nums 的前 k 個元素
for (int i = 0; i < actualLength; i++) {assert nums[i] == expectedNums[i];
}
如果所有的斷言都通過，你的解決方案將會?通過。

示例 1：
輸入：nums = [3,2,2,3], val = 3
輸出：2, nums = [2,2,_,_]
解釋：你的函數函數應該返回 k = 2, 并且 nums 中的前兩個元素均為 2。
你在返回的 k 個元素之外留下了什么并不重要（因此它們并不計入評測）。
示例 2：
輸入：nums = [0,1,2,2,3,0,4,2], val = 2
輸出：5, nums = [0,1,4,0,3,_,_,_]
解釋：你的函數應該返回 k = 5，并且 nums 中的前五個元素為 0,0,1,3,4。
注意這五個元素可以任意順序返回。
你在返回的 k 個元素之外留下了什么并不重要（因此它們并不計入評測）。
提示：

0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100

?① 拷貝覆蓋

思路：遍歷數組 nums，在遍歷過程中如果出現數字與需要移除的值不相同時，則進行拷貝覆蓋，如果相同的時候，則跳過該數字不進行拷貝覆蓋，最后 j 即為新的數組長度

這種思路在移除元素較多時更適合使用，最極端的情況是全部元素需要移除，遍歷一遍結束即可。

class Solution {public int removeElement(int[] nums, int val) {int j = 0;for(int i = 0;i < nums.length;i ++) {if(nums[i] != val) {nums[j ++] = nums[i];}}return j;}
}

② 交換移除

思路：遍歷數組 nums，在遍歷過程中如果出現數字與需要移除的值不相同時，則 i 自增 1，繼續下一次遍歷，如果相同的時候，則將 nums[i] 與 nums[ans - 1] 交換，即當前數字和數組最后一個數字進行交換，交換后就少了一個元素，故而 ans 自減 1

這種思路在移除元素較少時更適合使用，最極端的情況是沒有元素需要移除，遍歷一遍結束即可。

class Solution {public int removeElement(int[] nums, int val) {int j = nums.length;for (int i = 0; i < nums.length;) {if (nums[i] == val) {nums[i] = nums[-- j];             } else {i++;}}return j;}
}