670 Maximum Swap

思路：先把整數分解成一個一個的數，從0-n放著從最低位到最高位的數字。例如2376變成數組[6,7,3,2]。假設要替換的是最高位n-1,從0到n-2中查找是否有比nums[n-1]大的元素；如果有則替換，否則繼續考慮替換n-2位。比較的時候一定要從0位開始，因為如果 第1,2下標元素相同，把第1位的元素換到高位數字更大。樣例數據1993，替換以后是9913。
學習：首先，記錄0-9這十個數字在num中的最低位數。其次，遍歷每個位置，找一找從9到digits[i]+1這幾個數字中是不是存在可以替換的數值。
代碼

289 Game of Life

思路：這個題目的難點是既要根據數組情況修改board[i][j]的新狀態，還要能作為鄰居找到board[i][j]原來的狀態。可以使用如下策略：
live->die 2
live->live 1
die->die 0
die->live 3
最后再遍歷一次，把所有值%2。
代碼

792 Number of Matching Subsequences

思路：暴力方法不再敘述。
學習：把words的第一個字符以<character,string><character,string><script type="math/tex" id="MathJax-Element-1"></script>的數據結構存儲，接著遍歷S中的每一個字符，找到在該字符下的words，刪除words的字符，更新word。當word的長度為1時，表示匹配成功，計數。這里使用雙向列表是一個技巧之處。（參考）
學習2：第二種思路是：s的長度為n，計算每個位置i之后 [a-z]首次出現的位置。這樣，當檢查每一個word的時候，只要查看位置就可以。
例如 s=”abcde”。
指針在位置0（也就是a前面），那么a、b、c、d、e首次出現的位置分別為1，2,3,4,5。
在遇到’a’以后，a、b、c、d、e首次出現的位置分別為-1，2,3,4,5，如此循環下去。
在匹配單詞bb的時候，首先指針在0，b的位置是2。指針在2，b的位置是-1.所以找不到。
代碼

11 Container With Most Water

思路：根據題意，我們知道取兩條邊中最小的值*底長得到面積，找到最大面積。用暴力枚舉是可以算得的，但會超時。
學習：減少循環的核心思路是省去沒有必要的遍歷，并且確保所需的答案一定能被遍歷到。
算法描述是：假設現在有一個容器，則容器的盛水量是由容器的底和高共同決定的。則我們可以從最大的底入手。設兩個指針一個在最右邊，一個在最左邊。接著移動較小值的指針，左指針右移，右指針左移。直到兩指針相遇。遍歷結束。計算出最大值。
算法證明：首先解釋為什么移動較小值的指著。假設left值小于right值。如果移動right，底肯定會變小，如果移動之后：
1 新的right<<<script type="math/tex" id="MathJax-Element-2"><</script>left，那么高也變小，容量變小；
2 新的right>=>=left，那么高不變，底變小，容量變小。
所以移動值比較大的指針沒有意義。（ps：移動值小的指針，可以認為我們是在枚舉高度）。
其次證明這種移動方式肯定會經過容量最大的點。假設容量最大的時候指針分別為p_left和p_right。根據題設，遍歷的時候左指針先到達p_left，右指針還沒有到達p_right，假設右指針在p_right+n。這個時候會移動的條件是p_left<(p_right+n)p_left<(p_right+n)。如果是這樣最大面積就不是p_left,p_right兩指針。因為p_left?([p_right+n]?p_left)的底>p_left?(p_right?p_left)的底p_left?([p_right+n]?p_left)的底>p_left?(p_right?p_left)的底。這與假設矛盾。所以一定會經過容量最大的點。
學習2：不但要能想到算法描述，更需要證明算法正確。

參考
代碼

713 Subarray Product Less Than K

思路：首先肯定想到暴力枚舉，超時。接著考慮有哪些計算是重復的。以nums=[10, 5, 2,6]為例。
計算i=0,遍歷j=0,1,2,3；計算i=1，遍歷j=1,2,3；如果[0,2]符合要求，那么[1,2]一定是符合要求的，進一步考慮[0],[0,1],[0,2],[1,2]都是符合要求的。當然我思考到這里就進行不下去了。
學習：slide window的思想。
10:count+1
10*5<100:count+2，因為[5],[10,5]
10*5*2=100:count+2 因為：[2],[5,2]
5*2*6<100:count+3 因為[6][6,2][6,2,5]
需要保持最大的乘積<<<script type="math/tex" id="MathJax-Element-6"><</script>k的窗口；
每次向右移動一個數值nums[j]；如果右移后乘積>=>=k，就增加i，減少左邊的數值，直到乘積＜k;
每一步都會新增(j-i+1)個子數組。
這種滑動窗口，或者說每一步增加一個元素，考慮是否改變數組起止位置的思想與795 Number of Subarrays with Bounded Maximum很類似。如果能從一步計算中推出多個結論，就可以減少計算次數。降低復雜度。
代碼

33 Search in Rotated Sorted Array

思路：這是要在一個有旋轉的排序數組中查找。
學習：一種思路是找到旋轉點的位置每次找mid，找到的是(mid+ratedIdx)%n的位置
學習2：使用最大值、最小值使得數組有序。我理解的不太好。查看網頁。文中提到的If nums[mid] and target are “on the same side” of nums[0], we just take nums[mid].這句話意思是：nums[0]<nums[mid]?&&?nums[0]<targetnums[0]<nums[mid]?&&?nums[0]<target 或者 nums[0]>nums[mid]?&&?nums[0]>targetnums[0]>nums[mid]?&&?nums[0]>target
代碼
學習3：因為rotate的緣故，當我們切取一半的時候可能會出現誤區，所以我們要做進一步的判斷。具體來說，假設數組是A，每次左邊緣為l，右邊緣為r，還有中間位置是m。在每次迭代中，分三種情況：
（1）如果target==A[m]target==A[m]，那么m就是我們要的結果，直接返回；
（2）如果A[m]<A[r]A[m]<A[r]，那么說明從l到m一定是有序的，同樣只需要判斷target是否在這個范圍內，相應的移動邊緣即可。
根據以上方法，每次我們都可以切掉一半的數據，所以算法的時間復雜度是O(logn)，空間復雜度是O(1)。(原文鏈接)

81 Search in Rotated Sorted Array II

學習：本題和上一題唯一的區別是這道題目中元素會有重復的情況出現。不過正是因為這個條件的出現，出現了比較復雜的case，甚至影響到了算法的時間復雜度。原來我們是依靠中間和邊緣元素的大小關系，來判斷哪一半是不受rotate影響，仍然有序的。而現在因為重復的出現，如果我們遇到中間和邊緣相等的情況，我們就丟失了哪邊有序的信息，因為哪邊都有可能是有序的結果。假設原數組是{1,2,3,3,3,3,3}，那么旋轉之后有可能是{3,3,3,3,3,1,2}，或者{3,1,2,3,3,3,3}，這樣的我們判斷左邊緣和中心的時候都是3，如果我們要尋找1或者2，我們并不知道應該跳向哪一半。解決的辦法只能是對邊緣移動一步，直到邊緣和中間不在相等或者相遇，這就導致了會有不能切去一半的可能。所以最壞情況（比如全部都是一個元素，或者只有一個元素不同于其他元素，而他就在最后一個）就會出現每次移動一步，總共是n步，算法的時間復雜度變成O(n)。（來自網頁）
代碼

209 Minimum Size Subarray Sum

思路：這道題目與713很類似。一個是求子數組的和，一個是求子數組的乘積。都可以使用滑動窗口的思想。這里要求得到的是子數組和>=s>=s的最小長度。兩指針，一個指向窗口的開始位置，一個指向窗口的結束位置。（參考網頁）
學習：二分查找。輸入的數組沒有順序，而且也不能排序，那怎么用二分查找呢？sum[i]表示從下標0到i-1區間元素的和。因為輸入的元素是正整數，所以sum[i]是一個遞增函數。最短的數組長度，也就是找sum[i,j]的和。sum[i,j]=sum[0,j]?sum[0,i?1]>=ssum[i,j]=sum[0,j]?sum[0,i?1]>=s。對于每個sum[0,i-1]找到>sum[0,i?1]+s>sum[0,i?1]+s的最小的值，更新數組長度。
代碼

228 Summary Ranges

思路：這道題目簡單。只要判斷前后元素差距不等于1，就斷開。需要注意的是[2147483648,-2147483647,2147483647]這樣的數組。
代碼

56 Merge Intervals

思路：合并。用每一個Interval和其他所有Interval去比較合并。
學習：改進思路是按照Interval的start升序排列。這樣就不需要和每個Interval比較。
代碼

16 3Sum Closest

思路：找三個數的和最近接一個目標值。首先想到三個數的和可能大于，也可能小于目標值。其次，枚舉其中某一個值，然后使用兩指針從頭、尾開始相加。當然數組要求是排序了的。
代碼

55 Jump Game

思路：初看是一道非常簡單的題目。但是沒有正確理解題意。第一點：每一個nums[i]表示最多能跳多少個元素，而不是必須跳那么多個元素；第二點：如果能夠到達最后一個元素位置就返回true。有時候按照最遠的跳，可能超過最后一個元素了，也是可以的。當然第一點理解正確了，第二點也就正確的。第三：如果輸入[0]，那么初始化的時候就已經到了最后一個元素的位置了。我按照遞歸的代碼實現了一版，超時。

public boolean canJump(int[] nums) {return jump(nums,nums.length-1);}private boolean jump(int[] nums,int idx){if(idx<0){return false;}if(idx==0){return nums[idx]>0 || nums.length==1;}for(int i=idx-1;i>=0;i--){if(nums[i]>=idx-i){if(jump(nums,i)){return true;}}}return false;}

思路2：用數組表示是否能夠到達i的結果保存起來，用dp[i]表示。發生棧溢出。遞歸改為迭代？失敗，沒有完成。
學習1：基本事項是：在每一步，記錄下當前能夠達到的最遠的下標。我們循環遍歷每一個下標，如果發現當前下標是不可到達的，也就是說(當前idx>reachableIdx)，那就退出循環，返回false。
學習2：參考網頁

169 Majority Element

思路：最開始的思路，一定是用個map記錄每個元素出現次數。最后返回次數最多的那個元素。
學習：因為主元素的出現次數比其他所有元素出現次數的總和還要多1，或者相同，那么就用元素相同次數加1，元素不同次數減1，來過濾掉最后剩下的元素。Moore voting algorithm摩爾投票算法。
學習2：排序后，直接返回nums[nums.length/2]位置的元素。
學習3：位運算。一個元素的二進制表示是相同的。所有元素，計算二進制位置每個位置出現次數。
代碼

229 Majority Element II

學習：229是169的升級版，摩爾投票算法的一般情況。
代碼

總結

以上是生活随笔為你收集整理的array专题8的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。