LeetCode通關：數組十七連，真是不簡單
- 2021 年 8 月 7 日
- 筆記
- leetcode, LeetCode通關
分門別類刷算法，堅持，進步！
大家好，我是老三，一個刷題困難戶，接下來我們開始數組類型算法的刷題之旅！
數組基礎
數組基本上是我們最熟悉的數據結構了，剛會寫「Hello World」不久，接着就是「楊輝三角」之類的練習。
數組基本結構
- 數組是存放在連續內存空間上的相同類型數據的集合
上圖是一個字符數組的例子。
因為內存空間連續，所以可以直接通過下標獲取對應的元素。
但是刪除就麻煩一點，相當於填坑，一個元素被移走，留下的坑，需要其它元素來填上。
在Java中，多維數組的存儲本質上也是一個行優先的一維數組。
數組是引用傳遞
我們都知道，在Java中的 「=」 用在基本數據類型上，是值傳遞，用在引用數據類型上，是引用傳遞。
這一塊展開可以寫一篇文章，我們只簡單看個例子：
public class ArrayTest {
public static void main(String[] args) {
int[] array = {1, 2, 3};
int[] newArray = array;
newArray[1] = 0;
//結果： 1 0 3
printArray(array);
//結果： 1 0 3
printArray(newArray);
}
static void printArray(int[] data) {
for (int d : data) {
System.out.print(d + " ");
}
System.out.println();
}
}
大家可以看到，newArray改變了，array也跟着變了。
為什麼呢？
在Java中，數組是引用數組類型。array、newArray都是存儲在棧中的引用，它們指向堆中真正存儲的數組對象。
所以改變了newArray，實際是改變了newArray指向的數組。
這一點是我們刷題需要注意的，複製數組需要在循環中一個個複製。
好了，接下來，讓我們愉快地開始刷題吧！
二分查找
LeetCode704. 二分查找
☕ 題目：704. 二分查找 (//leetcode-cn.com/problems/binary-search/)
❓ 難度：簡單
📕 描述：
給定一個 n 個元素有序的（升序）整型數組 nums 和一個目標值 target ，寫一個函數搜索 nums 中的 target，如果目標值存在返回下標，否則返回 -1。
💡 思路：
二分查找可以說我們都很熟了。
因為數組是有序的，所以定義三個指針，low、high、mid，每次與中間指針指向的元素nums[mid]比較，
-
相等，命中
-
比nums[mid]大，目標元素就在(mid,high]區間；
-
比 nums[mid]小，目標元素就在 [low,mid)區間
/**
* 704. 二分查找
*
* @param nums
* @param target
* @return
*/
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (target == nums[mid]) {
return mid;
} else if (target > nums[mid]) {
//target在(mid,high]區間
//右移
left = mid + 1;
} else if (target < nums[mid]) {
//target 在[low,mid)區間
//左移
right = mid - 1;
}
}
return -1;
}
但是這個代碼還有一處問題，在哪呢？
int mid = (left + right) / 2;
這個地方可能會因為left和right數值太大導致內存溢出，所以應該寫為 int mid = left + ((right - left) >> 1);
修改之後代碼如下：
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid=left+((right-left)>>1);
if (target == nums[mid]) {
return mid;
} else if (target > nums[mid]) {
//target在(mid,high]區間
//右移
left = mid + 1;
} else if (target < nums[mid]) {
//target 在[low,mid)區間
//左移
right = mid - 1;
}
}
return -1;
}
⏰ 時間複雜度：O(logn)
LeetCode35. 搜索插入位置
☕ 題目：35. 搜索插入位置 (//leetcode-cn.com/problems/search-insert-position/)
❓ 難度：簡單
📕 描述：
給定一個排序數組和一個目標值，在數組中找到目標值，並返回其索引。如果目標值不存在於數組中，返回它將會被按順序插入的位置。
請必須使用時間複雜度為 O(log n) 的算法。
💡 思路：
二分查找比較簡單，但寫對還要費點功夫，再做一道基本一樣的題鞏固一下。
這道題基本一樣，插入的位置可能有四種情況：
- target<nums[0] : 在最左側插入
- target>nums[length-1] :在最右側插入
- target=nums[i] : 和數組中元素相同，插入位置i
- nums[i]<target<nums[i+1] :在i位置之後插入
代碼如下：
/**
* 35. 搜索插入位置
*
* @param nums
* @param target
* @return
*/
public int searchInsert(int[] nums, int target) {
int left = 0, right = nums.length - 1;
//target小於最左側，或者大於最右元素
if (target < nums[left]) {
return 0;
}
if (target > nums[right]) {
return right + 1;
}
while (left <= right) {
int mid=left+((right-left)>>1);
if (target == nums[mid]) {
//和數組元素相等
return mid;
} else if (target > nums[mid]) {
//右側
left = mid + 1;
} else if ((target < nums[mid])) {
//左側
right = mid - 1;
}
}
// 在某個元素之後插入
//因為退出條件是left==right，所以返回left或者right都可以
return left;
}
⏰ 時間複雜度：O(logn)
LeetCode34. 在排序數組中查找元素的第一個和最後一個位置
☕ 題目：34. 在排序數組中查找元素的第一個和最後一個位置 (//leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/)
❓ 難度：中等
📕 描述：
給定一個按照升序排列的整數數組 nums，和一個目標值 target。找出給定目標值在數組中的開始位置和結束位置。
如果數組中不存在目標值 target，返回 [-1, -1]。
進階：
- 你可以設計並實現時間複雜度為 O(log n) 的算法解決此問題嗎？
💡 思路：
看到時間複雜度 O(log n) ，數組有序，我們知道，二分查找該上場了。
但是這道題有點不一樣，它需要尋找邊界。
那我們怎麼辦呢？
這就引入了尋找邊界的二分查找。
這道題的思路是什麼呢？
我們分別用二分查找來尋找左邊界和右邊界。
一般的二分查找：
if (nums[mid] == target) {
return mid;
}else if (nums[mid] < target) {
left = mid + 1;
}else if (nums[mid] > target) {
right = mid - 1;
}
注意，我們這裡的返回條件是 nums[mid] == target，但是尋找邊界的時候就不能這樣了，因為我們不能確定mid是不是我們的邊界。
以尋找左邊界為例，條件是 target <= nums[mid]的時候，我們接着往左移動。
尋找右邊界也類似。
代碼如下：
public int[] searchRange(int[] nums, int target) {
//左邊界
int leftBound = leftBound(nums, target);
//右邊界
int rightBound = rightBound(nums, target);
//不存在情況
if (rightBound < leftBound) {
return new int[]{-1, -1};
}
return new int[]{leftBound, rightBound};
}
/**
* @return int
* @Description: 求左邊界
*/
int leftBound(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
//往左移動
if (target <= nums[mid]) {
right = mid - 1;
} else if (target > nums[mid]) {
//向右移動
left = mid + 1;
}
}
return left;
}
/**
* @return int
* @Description: 求右邊界
*/
int rightBound(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
//往右移動
if (target >= nums[mid]) {
left = mid + 1;
} else if (target < nums[mid]) {
//往左移動
right = mid - 1;
}
}
return right;
}
⏰ 時間複雜度：O(logn)
雙指針
LeetCode27. 移除元素
☕ 題目：27. 移除元素 (//leetcode-cn.com/problems/remove-element/)
❓ 難度：簡單
📕 描述：
給你一個數組 nums 和一個值 val，你需要 原地 移除所有數值等於 val 的元素，並返回移除後數組的新長度。
不要使用額外的數組空間，你必須僅使用 O(1) 額外空間並 原地 修改輸入數組。
元素的順序可以改變。你不需要考慮數組中超出新長度後面的元素。
說明:
為什麼返回數值是整數，但輸出的答案是數組呢?
請注意，輸入數組是以「引用」方式傳遞的，這意味着在函數里修改輸入數組對於調用者是可見的。
你可以想像內部操作如下:
// nums 是以「引用」方式傳遞的。也就是說，不對實參作任何拷貝
int len = removeElement(nums, val);
// 在函數里修改輸入數組對於調用者是可見的。
// 根據你的函數返回的長度, 它會打印出數組中 該長度範圍內 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
💡 思路
暴力解法
暴力解法沒什麼好說的，和上道題類似，找到要刪除的元素，把它後面的元素全部向前移動一位。
這裡有兩點需要注意：
-
需要先定義變量 length 獲取數組長度，因為後面我們的返回的數組長度是改變的
-
每找到一個需要刪除的值的時候，需要 i–，防止出現多個需要刪除的值在一起的情況，然後漏刪
代碼如下：
public int removeElement(int[] nums, int val) {
int length = nums.length;
int i = 0;
for (; i < length; i++) {
if (nums[i] == val) {
for (int j = i; j < length - 1; j++) {
nums[j] = nums[j + 1];
}
//防止漏刪
i--;
//數組長度減一
length--;
}
}
return length;
}
⏰ 時間複雜度：O(n²)。
雙指針法
雙指針法，是數組和鏈表題中非常常用的一種方法。
這道題用雙指針法怎麼解決呢？
定義兩個指針，一個前，一個後。沒有找到目標的時候front和after一起移動，找到目標的時候，after停下來，front接着移動，把front指向的值賦給after指向的值。
這樣一來，雙指針就通過一個循環完成了雙循環完成的事情。
代碼如下：
public int removeElement(int[] nums, int val) {
//定義前後指針
int front = 0;
int after = 0;
for (; front < nums.length; front++) {
if (val != nums[front]) {
nums[after] = nums[front];
after++;
}
}
return after;
}
⏰ 時間複雜度：O(n)。
LeetCode26. 刪除有序數組中的重複項
☕ 題目：27. 移除元素 (//leetcode-cn.com/problems/remove-element/)
❓ 難度：簡單
📕 描述：
給你一個有序數組 nums ，請你 原地 刪除重複出現的元素，使每個元素 只出現一次 ，返回刪除後數組的新長度。
不要使用額外的數組空間，你必須在 原地 修改輸入數組 並在使用 O(1) 額外空間的條件下完成。
說明:
為什麼返回數值是整數，但輸出的答案是數組呢?
請注意，輸入數組是以「引用」方式傳遞的，這意味着在函數里修改輸入數組對於調用者是可見的。
你可以想像內部操作如下:
// nums 是以「引用」方式傳遞的。也就是說，不對實參做任何拷貝
int len = removeDuplicates(nums);
// 在函數里修改輸入數組對於調用者是可見的。
// 根據你的函數返回的長度, 它會打印出數組中 該長度範圍內 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
💡 思路
趁着上一道題勁兒還沒緩過來，趕緊做一道基本一樣的鞏固一下。
直接上代碼：
public int removeDuplicates(int[] nums) {
int front = 1;
int after = 1;
for (; front < nums.length; front++) {
if (nums[front] != nums[front - 1]) {
nums[after] = nums[front];
after++;
}
}
return after;
}
⏰ 時間複雜度：O(n)。
LeetCode283. 移動零
☕ 題目：283. 移動零 (//leetcode-cn.com/problems/move-zeroes/)
❓ 難度：簡單
📕 描述：
給定一個數組 nums，編寫一個函數將所有 0 移動到數組的末尾，同時保持非零元素的相對順序。
示例:
輸入: [0,1,0,3,12]
輸出: [1,3,12,0,0]
說明:
- 必須在原數組上操作，不能拷貝額外的數組。
- 盡量減少操作次數
💡 思路
繼續沿着上一道題的思路。
- 第一步：我們可以把為零的元素先給它刪掉，怎麼刪呢？就是LeetCode26的兩個指針的刪除方式
- 第二步：但是我們這是將零移動到末尾，怎麼辦呢？我們把通過移動方式刪除，導致數組末尾的坑用零填上就行了。
代碼如下：
/**
* @return void
* @Description: 283. 移動零
* @author 三分惡
* @date 2021/7/30 7:44
*/
public void moveZeroes(int[] nums) {
int after = 0;
int front = 0;
//移動元素
for (; front < nums.length; front++) {
if (nums[front] != 0) {
nums[after] = nums[front];
after++;
}
}
//將末尾元素置為0
for (; after < nums.length; after++) {
nums[after] = 0;
}
}
⏰ 時間複雜度：O(n)。
LeetCode977. 有序數組的平方
☕ 題目：977. 有序數組的平方 (//leetcode-cn.com/problems/squares-of-a-sorted-array/)
❓ 難度：簡單
📕 描述：
給你一個按 非遞減順序 排序的整數數組 nums，返回 每個數字的平方 組成的新數組，要求也按 非遞減順序 排序。
💡 思路
暴力排序法
這道題一看，最直觀的做法是什麼呢？
先求數字平方的數組，然後再把新數組排序。
代碼也好寫：
/**
* @return int[]
* @Description: 977. 有序數組的平方-暴力法
* @author 三分惡
* @date 2021/7/30 8:03
*/
public int[] sortedSquares(int[] nums) {
for (int i = 0; i < nums.length; i++) {
nums[i] *= nums[i];
}
//快排，時間複雜度O(nlogn)
Arrays.sort(nums);
return nums;
}
⏰ 時間複雜度：遍歷時間複雜度O(n)，快排時間複雜度O(nlogn)，所以時間複雜度O(n+nlogn)。
💡 思路
雙指針法
我們連寫幾道雙指針了，這道題能不能用雙指針實現呢？
我們分析一下，這個數組在取平方之前，是有序的，那麼它絕對值最大的數一定是在兩端的。
所以我們可以定義兩個指針，一個指向最左端，一個指向最右端，比較兩者平方的大小，大的平方放入結果數組，並移動指針。
代碼如下：
/**
* @return int[]
* @Description: 977. 有序數組的平方-雙指針法
* @author 三分惡
* @date 2021/7/30 8:29
*/
public int[] sortedSquares(int[] nums) {
int left = 0;
int right = nums.length - 1;
int[] result = new int[nums.length];
int r = nums.length - 1;
while (left <= right) {
int leftRes = nums[left] * nums[left];
int rightRes = nums[right] * nums[right];
//右邊大
if (leftRes <= rightRes) {
result[r] = rightRes;
right--;
} else {
//左邊大
result[r] = leftRes;
left++;
}
r--;
}
return result;
}
⏰ 時間複雜度：O(n)。
兩數之和
LeetCode1. 兩數之和
☕ 題目：1. 兩數之和 (//leetcode-cn.com/problems/two-sum/)
❓ 難度：簡單
📕 描述：給定一個整數數組 nums 和一個整數目標值 target，請你在該數組中找出 和為目標值 target 的那 兩個 整數，並返回它們的數組下標。
你可以假設每種輸入只會對應一個答案。但是，數組中同一個元素在答案里不能重複出現。
你可以按任意順序返回答案。
💡 思路：
暴力解法
上來我們先來個最簡單的暴力解法，大家應該都知道冒泡排序吧，類似的兩層循環。
代碼寫起來也很簡單：
public int[] twoSum(int[] nums, int target) {
int[] result = new int[2];
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
result[0] = i;
result[1] = j;
return result;
}
}
}
return result;
}
⏰ 時間複雜度：看到這個雙循環，就知道時間複雜度O(n²)。
哈希輔助法
時間複雜度O(n²)多少有點過了，這道題的重點是兩個元素相加之和的判斷。
我們可以用一個Hash集合把元素存起來，這樣一來遍歷一遍就夠了，例如目標和9，當前元素2，只需要判斷集合里是否有元素7就行了。
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<>(16);
int[] result = new int[2];
for (int i = 0; i < nums.length; i++) {
//目標元素
int goal = target - nums[i];
if (map.containsKey(goal)) {
result[0] = map.get(goal);
result[1] = i;
return result;
}
//將數組值作為key,下標作為value
map.put(nums[i], i);
}
return result;
}
⏰ 時間複雜度：從Hash查詢和取值時間複雜度都是O(1)，所以整體時間複雜度是O(1)。
LeetCode15. 三數之和
☕ 題目：15. 三數之和 (//leetcode-cn.com/problems/3sum/)
❓ 難度：簡單
📕 描述：
給你一個包含 n 個整數的數組 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？請你找出所有和為 0 且不重複的三元組。
注意：答案中不可以包含重複的三元組。
💡 思路：
哈希法
做完兩數之和以後，我們首先想到的就是哈希法。
兩層循環，取到a，b，再通過 0-(a+b) 來確定c。
但是這裡還有一個問題，答案中不可以包含重複的三元組。
所以，我們還要想辦法去掉Hash里的重複元素。
可以加入一個約束，第三個數的索引大於第二個數才存入。
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>(16);
if (nums.length < 3) {
return result;
}
//排序
Arrays.sort(nums);
HashMap<Integer, Integer> map = new HashMap<>();
//將元素存入hash表
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], i);
}
Integer c;
int target = 0;
for (int a = 0; a < nums.length; a++) {
target = -nums[a];
//去重
if (a > 0 && nums[a] == nums[a - 1]) {
continue;
}
for (int b = a + 1; b < nums.length; b++) {
//去重
if (b > a + 1 && nums[b] == nums[b - 1]) {
continue;
}
//從hash表獲取c
if ((c = map.get(target - nums[b])) != null) {
//c下彪必須大於b
if (c > b) {
result.add(new ArrayList<>(Arrays.asList(nums[a], nums[b], nums[c])));
} else {
break;
}
}
}
}
return result;
}
⏰ 時間複雜度：雙循環，O(n²)。
雖然這麼也寫出來了，但是，說實話，很難寫出沒有問題的代碼。
我們寫了這麼多雙指針，那麼有沒有可能用雙指針的方式呢？
雙指針法
首先對數組進行排序，然後遍曆數組。
然後再在當前節點後面取左右指針，判斷左右指針的值是否等於0-nums[i]，然後分別左右移動。
怎麼去重呢？
滿足條件時，看左指針的值是否和前一個位置相等，右指針的值是否和和它後一個位置的值相等。
代碼如下：
public static List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>(16);
if (nums.length < 3) {
return result;
}
//排序
Arrays.sort(nums);
//遍歷
for (int i = 0; i < nums.length-2; i++) {
//如果當前元素大於0，三數之和一定大於0
if (nums[i] > 0) {
break;
}
int left = i + 1;
int right = nums.length - 1;
int count = 0 - nums[i];
//去重
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
result.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right])));
//去重,注意去重邏輯要放在找到第一個三元組之後
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
//找到結果，雙指針同時移動
left++;
right--;
} else if (sum < 0) {
//左指針右移
left++;
} else if (sum > 0) {
//右指針左移
right--;
}
}
}
return result;
}
⏰ 時間複雜度：O(n²)
LeetCode18. 四數之和
☕ 題目：18. 四數之和 (//leetcode-cn.com/problems/4sum/)
❓ 難度：簡單
📕 描述：
給定一個包含 n 個整數的數組 nums 和一個目標值 target，判斷 nums 中是否存在四個元素 a，b，c 和 d ，使得 a + b + c + d 的值與 target 相等？找出所有滿足條件且不重複的四元組。
注意：答案中不可以包含重複的四元組。
💡 思路：
我們延續三數之和的思路，在三數之和外面再套一層循環。
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<>(16);
if (nums.length < 4) {
return result;
}
//排序
Arrays.sort(nums);
for (int i = 0; i < nums.length - 3; i++) {
//去重
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
for (int j = i + 1; j < nums.length - 2; j++) {
//去重
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
int left = j + 1;
int right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[j] + nums[left] + nums[right];
if (sum == target) {
result.add(new ArrayList<>(Arrays.asList(nums[i], nums[j], nums[left], nums[right])));
//去重
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
left++;
right--;
} else if (sum > target) {
right--;
} else if (sum < target) {
left++;
}
}
}
}
return result;
}
⏰ 時間複雜度：O(n³)
滑動窗口
LeetCode209. 長度最小的子數組
☕ 題目：209. 長度最小的子數組(//leetcode-cn.com/problems/minimum-size-subarray-sum/)
❓ 難度：中等
📕 描述：
給定一個含有 n 個正整數的數組和一個正整數 target 。
找出該數組中滿足其和 ≥ target 的長度最小的 連續子數組 [numsl, numsl+1, …, numsr-1, numsr] ，並返回其長度。如果不存在符合條件的子數組，返回 0 。
💡 思路
這道題是一道經典的滑動窗口問題[4]。
- 使用start、end指針，分別表示滑動窗口的起始、終止位置
- 移動end指針，擴大窗口，直到子數組達到目標值target
- 移動start指針，縮小窗口，直到子數組不再滿足>=target
代碼如下：
public int minSubArrayLen(int target, int[] nums) {
int result = Integer.MAX_VALUE;
//起、止指針
int start = 0, end = 0;
//總和
int sum = 0;
while (end < nums.length) {
//sum添加，end右移
sum += nums[end++];
while (sum >= target && start < end) {
//因為end++，所以序列長度end - start
result = Math.min(result, end - start);
//移動start
sum -= nums[start++];
}
}
return result == Integer.MAX_VALUE ? 0 : result;
}
⏰ 時間複雜度：O(n)，雖然循環里套循環了，但是starrt和end各自被移動了n次，所以時間複雜度是O(n)。
LeetCode219. 存在重複元素 II
☕ 題目：219. 存在重複元素 II (//leetcode-cn.com/problems/contains-duplicate-ii/)
❓ 難度：簡單
📕 描述：
給定一個整數數組和一個整數 k，判斷數組中是否存在兩個不同的索引 i 和 j，使得 nums [i] = nums [j]，並且 i 和 j 的差的 絕對值 至多為 k。
💡思路：
上面我們做了一道滑動窗口的題，我們接着再做一道也可以用滑動窗口解決的問題。
這道題的滑動窗口略有區別，上一道題的窗口是活動的，這個是固定的滑動窗口,維護一個長度為k的固定窗口，如果窗口內含有目標值，返回。如果窗口進入新的元素，就需要把頭部的元素移除掉，保持窗口的長度。
代碼如下：
public boolean containsNearbyDuplicate(int[] nums, int k) {
HashSet<Integer> set = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
if (set.contains(nums[i])) {
return true;
}
set.add(nums[i]);
if (set.size() > k) {
set.remove(nums[i - k]);
}
}
return false;
}
⏰ 時間複雜度：O(n)。
LeetCode1052. 愛生氣的書店老闆
☕ 題目：1052. 愛生氣的書店老闆(//leetcode-cn.com/problems/grumpy-bookstore-owner/)
❓ 難度：中等
📕 描述：
今天，書店老闆有一家店打算試營業 customers.length 分鐘。每分鐘都有一些顧客（customers[i]）會進入書店，所有這些顧客都會在那一分鐘結束後離開。
在某些時候，書店老闆會生氣。 如果書店老闆在第 i 分鐘生氣，那麼 grumpy[i] = 1，否則 grumpy[i] = 0。 當書店老闆生氣時，那一分鐘的顧客就會不滿意，不生氣則他們是滿意的。
書店老闆知道一個秘密技巧，能抑制自己的情緒，可以讓自己連續 X 分鐘不生氣，但卻只能使用一次。
請你返回這一天營業下來，最多有多少客戶能夠感到滿意。
示例：
輸入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
輸出：16
解釋：
書店老闆在最後 3 分鐘保持冷靜。
感到滿意的最大客戶數量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.
💡思路：
這道題是一道固定窗口的問題。
整體思路就是把不生氣的部分作為固定窗口，固定窗口把customers分成了三部分，最後求三部分的最大和。
public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
// 窗口值總和
int winSum = 0;
//左區間總和
int leftSum = 0;
//右區間總和
int rightSum = 0;
int len = customers.length;
//窗口位於起點
for (int i = 0; i < minutes; i++) {
winSum += customers[i];
}
//窗口位於起點時右區間的值
for (int i = minutes; i < len; i++) {
//不生氣
if (grumpy[i] == 0) {
rightSum += customers[i];
}
}
//窗口左右-開始移動窗口
int left = 1;
int right = minutes;
int maxSum = winSum + leftSum + rightSum;
//移動
while (right < len) {
//重新計算左區間的值
if (grumpy[left - 1] == 0) {
leftSum += customers[left - 1];
}
//重新計算右區間的值
if (grumpy[right] == 0) {
rightSum -= customers[right];
}
//窗口值
winSum = winSum - customers[left - 1] + customers[right];
//最大總和
maxSum = Math.max(maxSum, leftSum + winSum + rightSum);
//移動固定窗口
left++;
right++;
}
return maxSum;
}
⏰ 時間複雜度：O(n)。
🏠 空間複雜度： O(1)。
原地置換
面試題3. 數組中重複的數字
☕ 題目：面試題3. 數組中重複的數字 (//leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/)
❓ 難度：複雜
📕 描述：
找出數組中重複的數字。
在一個長度為 n 的數組 nums 里的所有數字都在 0～n-1 的範圍內。數組中某些數字是重複的，但不知道有幾個數字重複了，也不知道每個數字重複了幾次。請找出數組中任意一個重複的數字。
示例 1：
輸入：
[2, 3, 1, 0, 2, 5, 3]
輸出：2 或 3
💡思路：
哈希法
這種找重複的數字問題，我們腦子裡第一下就想起來，用Hash存儲元素，然後進行比對。
代碼實現也很簡單：
public int findRepeatNumber(int[] nums) {
HashSet<Integer> set = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
if (set.contains(nums[i])) {
return nums[i];
}
set.add(nums[i]);
}
return 0;
}
⏰ 時間複雜度：O(n)。
🏠 空間複雜度：O(n)
但今天的主角不是它，而是👇
原地置換法
我們注意到一個條件所有數字都在 0～n-1 的範圍內,那就在這方面進行操作，我們可以把元素放到它的值對應的下標的位置。
例如 num[2]=1，那我們就把它放到下標1的位置。
接着遍歷，元素髮現它應該待的坑已經被它的雙胞胎兄弟給佔了，它就知道，它是多餘的那個。
代碼如下：
public int findRepeatNumber(int[] nums) {
if (nums.length == 0) {
return -1;
}
for (int i = 0; i < nums.length; i++) {
while (nums[i] != i) {
//判斷位置是否被占
int index = nums[i];
if (nums[index] == nums[i]) {
return nums[i];
}
//交換位置
int temp = nums[i];
nums[i] = nums[index];
nums[index] = temp;
}
}
return -1;
}
⏰ 時間複雜度：O(n)。
🏠 空間複雜度：O(1)
LeetCode41. 缺失的第一個正數
☕ 題目：41. 缺失的第一個正數 (//leetcode-cn.com/problems/first-missing-positive/)
❓ 難度：複雜
📕 描述：
給你一個未排序的整數數組 nums ，請你找出其中沒有出現的最小的正整數。
請你實現時間複雜度為 O(n) 並且只使用常數級別額外空間的解決方案。
💡 思路
輔助數組
這道題有一個非常巧妙地的辦法！[1]
可以引入一個輔助數組，從1開始，在對應的位置存入原數組對應的元素。如原數組num[0]=1，那麼這個元素就應該存入輔助數組 helper[1]。
然後遍歷輔助數組，發現的第一個坑就是缺失的第一個正數。
代碼如下：
public int firstMissingPositive(int[] nums) {
if (nums.length == 0) {
return 1;
}
//輔助數組
int[] helper = new int[nums.length + 1];
//將數組正數元素存入輔助數組中
for (int n : nums) {
if (n > 0 && n < helper.length) {
helper[n] = n;
}
}
//遍歷查找，找到不一樣元素
for (int i = 1; i < helper.length; i++) {
if (helper[i] != i) {
return i;
}
}
return helper.length;
}
⏰ 時間複雜度：O(n)。
🏠 空間複雜度：O(n)。
原地置換法
我們上面用了原地置換法解決了一個問題，降低了空間複雜度，我們這道題是不是也可以呢？
原地置換沒法修改數組長度，我們肯定不能nums[i] 存 i 了，我們左移一下，num[i-1]存i。
代碼實現如下：
public int firstMissingPositive(int[] nums) {
if (nums.length == 0) {
return 1;
}
//原地置換
for (int i = 0; i < nums.length; i++) {
//將正數填入對應位置
//需要考慮指針移動情況，大於0，小於len+1，不等與i+1，兩個交換的數相等時，防止死循環
while (nums[i] > 0 && nums[i] < nums.length + 1 && nums[i] != i + 1 && nums[i] != nums[nums[i] - 1]) {
//下標
int index = nums[i] - 1;
//交換
int temp = nums[index];
nums[index] = nums[i];
nums[i] = temp;
}
}
//遍歷置換後的數組
for (int j = 0; j < nums.length; j++) {
if (nums[j] != j + 1) {
return j + 1;
}
}
return nums.length + 1;
}
⏰ 時間複雜度：O(n)。
🏠 空間複雜度：O(1)。
螺旋矩陣
LeetCode54. 螺旋矩陣
☕ 題目：54. 螺旋矩陣 (//leetcode-cn.com/problems/spiral-matrix/)
❓ 難度：中等
📕 描述：
給你一個 m 行 n 列的矩陣 matrix ，請按照 順時針螺旋順序 ，返回矩陣中的所有元素。
💡 思路
這道題，思路比較容易想，就是上右下左四個方向順時針遍曆數組。
但是這道題的細節是魔鬼。
有兩種，一種是一圈遍歷完成，上下左右的位置移動，遍歷是左閉右開[的條件。
我們採用的是第二種，每遍歷完一條邊，就移動對應的位置，遍歷就是左閉右閉的條件。
還有一點細節就是值得注意的是，遍歷過程中可能會出現出現 top > bottom || left > right ，其中一對邊界彼此交錯了。
這意味着此時所有項都遍歷完了，如果沒有及時 break ，就會重複遍歷。
代碼如下：
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> result = new ArrayList<>(16);
//邊界
int left = 0, right = matrix[0].length - 1;
int top = 0, bottom = matrix.length - 1;
int size = matrix.length * matrix[0].length;
//遍歷
while (result.size() != size) {
//上層遍歷
for (int i = left; i <= right; i++) {
result.add(matrix[top][i]);
}
top++;
if (top > bottom) break;
//右層遍歷
for (int i = top; i <= bottom; i++) {
result.add(matrix[i][right]);
}
right--;
if (left > right) break;
//下層遍歷
for (int i = right; i >= left; i--) {
result.add(matrix[bottom][i]);
}
bottom--;
if (top > bottom) break;
//左層遍歷
for (int i = bottom; i >= top; i--) {
result.add(matrix[i][left]);
}
left++;
if (left > right) break;
}
return result;
}
🚗 時間複雜度：O(mn)，其中 m 和 n 分別是輸入矩陣的行數和列數。
LeetCode59. 螺旋矩陣 II
☕ 題目：59. 螺旋矩陣 II (//leetcode-cn.com/problems/spiral-matrix-ii/)
❓ 難度：中等
📕 描述：
給你一個正整數 n ，生成一個包含 1 到 n2 所有元素，且元素按順時針順序螺旋排列的 n x n 正方形矩陣 matrix 。
💡 思路
和上面一道題基本一模一樣，我們往裏面套就行了。
代碼如下：
public int[][] generateMatrix(int n) {
int[][] res = new int[n][n];
int left = 0, right = n - 1;
int top = 0, bottom = n - 1;
int x = 1;
while (x <= n * n) {
//上
for (int i = left; i <= right; i++) {
res[top][i] = x;
x++;
}
top++;
if (top > bottom) break;
//右
for (int i = top; i <= bottom; i++) {
res[i][right] = x;
x++;
}
right--;
if (left > right) break;
//下
for (int i = right; i >= left; i--) {
res[bottom][i] = x;
x++;
}
bottom--;
if (left > right) break;
//左
for (int i = bottom; i >= top; i--) {
res[i][left] = x;
x++;
}
left++;
if (left > right) break;
}
return res;
}
🚗 時間複雜度：O(n²)
劍指 Offer 29. 順時針打印矩陣 也是一道類似的題目。
總結
寫了個順口溜總結一下：
簡單事情重複做，重複事情認真做，認真事情創造性地做！
我是三分惡，一個能文能武地全棧開發。
點贊、關注不迷路，咱們下期見！
博主是個算法練習生，路線和思路參考如下大佬！建議關注！
參考：
[1].//github.com/chefyuan/algorithm-base
[2].//github.com/youngyangyang04/leetcode-master/
[3].//www.zhihu.com/question/31203609
