#561 Array Partition I#
思路：題目要求數(shù)組中所有數(shù)字配對(duì)后，每一對(duì)中最小值加和sum，sum要盡可能大。我的第一反應(yīng)就是暴力枚舉。下標(biāo)為0的數(shù)值可能匹配的下標(biāo)有：1,2,3…n-1；接著計(jì)算下標(biāo)為1的數(shù)值可能匹配的下標(biāo)有哪些。不斷匹配，直到數(shù)組中所有數(shù)字配對(duì)完成。求和，保存和最大的值。可以得出結(jié)果，時(shí)間復(fù)雜度O(n^n)。n的n次冪。因?yàn)橛衝步，每步有n種情況。
學(xué)習(xí)：先排序數(shù)組，然后相鄰的做paire。原因是這樣的。如果一個(gè)數(shù)組已經(jīng)排序好，則有a0,a1,a2…a(2n-1)。所求和最大的應(yīng)該是a0+a2+…a+(2n-2) ，這是因?yàn)?a0,a1),(a2,a3)…；最小的和是 a0+a1+a2+…+a(n-1)，這是因?yàn)?a0,an),(a1,a(n+1))這樣匹配。還有另外一種解釋。要想讓和最大，則需要每個(gè)數(shù)值盡可能大。觀察：如果一次配對(duì)，當(dāng) (1,4) 與 (1,2)比較的時(shí)候就會(huì)發(fā)現(xiàn)(1,2)pair 要比(1,4)pair 要好。因?yàn)?這個(gè)數(shù)字可能與其他數(shù)字配對(duì)被保留下來(lái)。而(1,4)配對(duì)，那4一定被舍棄。所以，能夠看出配對(duì)的兩個(gè)數(shù)字要盡可能接近。這里的時(shí)間復(fù)雜度主要是排序的時(shí)間復(fù)雜度O(nlogn)。
學(xué)習(xí)2：上面的主要時(shí)間耗在排序，其實(shí)排序還有一種思路是桶排序。就是把相同的數(shù)字放在一個(gè)桶里面。在配對(duì)的時(shí)候還是把盡可能相同的數(shù)字放在一起配對(duì)。
參考：網(wǎng)頁(yè)1；網(wǎng)頁(yè)2；網(wǎng)頁(yè)3
我學(xué)習(xí)到的就是做題目除了依賴直覺(jué)，還需要靠觀察。從觀察中總結(jié)規(guī)律，進(jìn)而提高算法效率。
代碼

#566 Reshape the Matrix
思路：這道題是一道真正的easy級(jí)別，按照題目描述直接寫(xiě)代碼即可。
學(xué)習(xí)：這里學(xué)習(xí)到的一點(diǎn)是對(duì)下標(biāo)的巧妙利用。當(dāng)然，這不影響算法的時(shí)間復(fù)雜度。二維數(shù)組變一維數(shù)組 M[i][j]=M[i*n+j],n是列數(shù)；一維變二維 M[i] = M[i/n][i%n],n是列數(shù)；

public int[][] matrixReshape(int[][] nums, int r, int c) {if(nums ==null) return nums;int initRow = nums.length;if(initRow==0) return nums;int initCol = nums[0].length;if(r*c!=initRow * initCol) return nums;int[][] result = new int[r][c];for(int i=0;i<r*c;i++){result[i/c][i%c] = nums[i/initCol][i%initCol];}return result;}

#775 Global and Local Inversions
思路：按照題目要求，分別計(jì)算全局反轉(zhuǎn)次數(shù)與局部反轉(zhuǎn)次數(shù)。這樣會(huì)產(chǎn)生O(n^2)的時(shí)間復(fù)雜度。
學(xué)習(xí)：題目中提到了一個(gè)很重要的信息，We have some permutation A of [0, 1, …, N - 1], where N is the length of A。這說(shuō)明正常的A=[0,1,2,3,…N-1]，也就是說(shuō)A[i] = i , $0<=i<N$。
進(jìn)一步分析得到：
1 每個(gè)local inversion 也是一個(gè)global inversion
2 如果想要 localCount = globalCount，也就是說(shuō)只有l(wèi)ocal inversion，沒(méi)有其余的global inversion
3 如果只有l(wèi)ocal inversion，那么當(dāng)遇到inversion的時(shí)候，只要交換A[i]和A[i+1]的位置，那么數(shù)組從0到i+1就有序了。
例如A = [1,0,2]。當(dāng)i=1的時(shí)候，$A[1]<A[0]$，那么交換A[1]和A[0]之后，A=[0,1,2]，那么A[0]=0，A[1]=1，符合A[i] = i的要求。那這數(shù)組從0到1是有序的，這是一次local inversion。
例如A = [2,0,1]。當(dāng)i=1的時(shí)候，$A[1]<A[0]$，那么交換A[1]和A[0]之后，A=[0,2,1]，那么A[0]=0，A[1]=2，A[1]不符合A[1]=1的要求。那這樣就可以立即返回false。

代碼

#495 Teemo Attacking
思路： 根據(jù)題目含義，這是要處理重復(fù)線段的問(wèn)題。 例如[1,2], 2；第一次起始時(shí)間是1，結(jié)束時(shí)間是3（或者2s的末尾）；第二次起始時(shí)間是2，結(jié)束時(shí)間是4（或者3s的末尾）。 用第一次的結(jié)束時(shí)間-第二次的起始時(shí)間，就是重復(fù)的時(shí)間。
代碼
#62 Unique Paths
思路：在每個(gè)位置(i,j)有兩種走向：向右走到達(dá)(i+1,j)，向下走到達(dá)(i,j+1)。暴力搜索每種情況。處理邊界條件。這樣會(huì)超時(shí)。
思路二：動(dòng)態(tài)規(guī)劃思想：dp[i][j]表示到達(dá)(i,j)位置，有幾種走法。初始條件是第一行、第一列的每個(gè)位置只有一種走法所以dp[0][] = 1,dp[][0]=1；遞歸條件 dp[i][j] = dp[i-1][j]+dp[i][j-1]。時(shí)間復(fù)雜度O(m*n)
學(xué)習(xí)：排列組合思想:表格是m行，n列，robot需要向下移動(dòng)m-1次，向右移動(dòng)n-1次。如果用D表示向下，R表示向右。例如在3x7的表格中，需要2次D，6次R。這樣可以是任意組合例如D,D,R,R,R,R,R,R或者D,R,D,R,R,R,R,R。這樣只需要計(jì)算(m-1)+(n-1)的組合數(shù)。
代碼

#442 Find All Duplicates in an Array
思路：題目要求不用額外的空間，在O(n)時(shí)間內(nèi)完成，這樣就要非常注重一個(gè)前提1 ≤ a[i] ≤ n (n = size of array)，數(shù)組內(nèi)的元素是在長(zhǎng)度范圍內(nèi)的。這樣就可以將數(shù)組的下標(biāo)與數(shù)組的值建立映射關(guān)系。這里建立映射的關(guān)系是把nums[i]放在nums[i]-1 的位置上。如果nums[nums[i]-1]已經(jīng)等于nums[i]了，那說(shuō)明是重復(fù)的。（nums[i] = -1 就說(shuō)明是缺失的值）
學(xué)習(xí)：不用交換數(shù)值，只需要將對(duì)應(yīng)位置修改為負(fù)數(shù)即可。

public List<Integer> findDuplicatesV2(int[] nums) {List<Integer> list = new ArrayList<Integer>();for(int i=0;i<nums.length;i++){int val = Math.abs(nums[i]);if(nums[val-1]<0){list.add(val);}else{nums[val-1] = - nums[val-1];}}return list;}

代碼

#63 Unique Paths II
思路：與62類(lèi)似，用動(dòng)態(tài)規(guī)劃解決。注意條件判斷即可。
問(wèn)題：沒(méi)有找到更快的方法。
代碼

287 Find the Duplicate Number

學(xué)習(xí)思路一：Floyd龜兔法
學(xué)習(xí)思路二：二分法
代碼

15 3Sum

思路：三個(gè)數(shù)相加和為0，轉(zhuǎn)為固定一個(gè)數(shù)nums[i]，求兩個(gè)數(shù)的和為0-nums[i]。將nums排序后，用兩個(gè)指針從最前面和最末尾開(kāi)始移動(dòng)。
代碼

18 4Sum

思路：可以基于3Sum，將一個(gè)數(shù)固定nums[i]，再剩余數(shù)組中查找三個(gè)數(shù)和為target-nums[i]。三個(gè)數(shù)的和再轉(zhuǎn)為2個(gè)數(shù)的和。
思路2：可以使用map，將兩兩數(shù)的和存起來(lái)放在map中，再循環(huán)nums，得到兩個(gè)下標(biāo)。這樣做的最大難題是去重。參考discuss的代碼
代碼

#73 Set Matrix Zeroes
思路：看起來(lái)比較簡(jiǎn)單的一道題。難點(diǎn)是注意修改和判斷不能相互影響。例如matrix[2][3]=0，則matrix[2][]=0,matrix[][3] = 0。那么在判斷第三行的時(shí)候，只能依據(jù)修改前的matrix[3][3]來(lái)判斷是為0，而不能依據(jù)修改后的。我的思路是先遍歷一遍找，分別找到需要置0的行和列，放入list中。然后再遍歷這些行，每一列設(shè)置為0；遍歷這些列，每一行的該列設(shè)置為0。
學(xué)習(xí)1：遍歷如果某一行包含元素0，則修改matrix[i][0] =0;如果某一列包含元素0，則修改matrix[0][j]=0;但是第0行和第0列會(huì)共享同一個(gè)空間matrix[0][0]，則需要添加一個(gè)變量col0，col0=0表示第0列為0；matrix[0][0]=0則表示第0行為0。
代碼

總結(jié)

以上是生活随笔為你收集整理的array专题5的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。