力扣刷到現(xiàn)在題做了不少，感覺(jué)遺忘速度與做題速度相當(dāng)了，是時(shí)候總結(jié)一下了。思索了一下，按照tag來(lái)總結(jié)應(yīng)該是個(gè)還不錯(cuò)的主意，第一篇就從數(shù)組入手吧，列出一些有代表性的題目，并且以題帶知識(shí)點(diǎn)，順便鞏固一下基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)等知識(shí)。
1.兩數(shù)之和（twoSum）
題目描述：給定一個(gè)數(shù)組和一個(gè)目標(biāo)值，找出數(shù)組中和為目標(biāo)值的兩個(gè)整數(shù)，并且返回?cái)?shù)組下標(biāo)。
上榜理由：這道題是力扣開篇第一題欸，意義相當(dāng)于單詞書里的abandon，怎么能少了它呢~
做法回顧：這道題我當(dāng)時(shí)用了三種解法來(lái)做它。其實(shí)也是很有意義的學(xué)習(xí)過(guò)程。
①使用暴力解法，兩次循環(huán)，兩個(gè)指針i，j初始值分別為0和i+1,當(dāng)nums[i]+nums[j] == target時(shí)，返回i，j的值。這無(wú)疑是最簡(jiǎn)單的思路，但時(shí)間復(fù)雜度為O(n^2)，提交后無(wú)法通過(guò)，這給了我一個(gè)啟示，就是在力扣做題是要考慮時(shí)間空間復(fù)雜度的，暴力解法還是往后放吧。
回顧題目要求，找出數(shù)組中的目標(biāo)值的索引。通過(guò)值找索引最快的方法是什么，當(dāng)然是哈希表了。所以后兩種解法分別運(yùn)用了兩次哈希表和一次哈希表，解法類似。
②仍舊兩次迭代，第一次將數(shù)組元素存入哈希表中，值為key，數(shù)組標(biāo)號(hào)為value。第二次迭代過(guò)程，用containsKey來(lái)找目標(biāo)值減去每個(gè)元素的值是否存在于數(shù)組當(dāng)中，存在即返回該值的value，也就是下標(biāo)。
③一次迭代，在插表的同時(shí)完成查找過(guò)程。
注：哈希表的key不能重復(fù)，但此處根據(jù)題意“假設(shè)每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案”，實(shí)際上規(guī)避了這種情況。
知識(shí)回顧：哈希表是基于哈希函數(shù)建立的一種查找表，將key作為自變量，通過(guò)哈希函數(shù)計(jì)算出的值即是元素的存儲(chǔ)地址。哈希表中存儲(chǔ)的是鍵值對(duì)（key-value），Java中的HashMap()繼承的是Map接口。常用的方法有get()，remove()，put(key,value)，containsKey()，containsValue()，isEmpty()，size()等。
詳見(jiàn)：https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html
解題（解法③）：
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap();
for(int i = 0; i<nums.length; i++) {
int complement = target - nums[i];
if(map.containsKey(complement)) {
return new int[] {i, map.get(complement)};
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}
}
26. 刪除排序數(shù)組中的重復(fù)項(xiàng)（removeDuplicates）
題目描述：給定一個(gè)排序數(shù)組，你需要在原地刪除重復(fù)出現(xiàn)的元素，使得每個(gè)元素只出現(xiàn)一次，返回移除后數(shù)組的新長(zhǎng)度。
上榜理由：使用了快慢指針，具有一定的代表性。
做法回顧：其中i是慢指針，j是快指針。只要nums[i] == nums[j]，就j++跳過(guò)重復(fù)項(xiàng)。當(dāng)遇到nums[j] != nums[i]時(shí)，i++，交換兩個(gè)指針指向的值，接著重復(fù)相同的過(guò)程，直到 j 到達(dá)數(shù)組的末尾為止。nums[i]代表去掉重復(fù)元素的新數(shù)組，i+1即為移除后的數(shù)組長(zhǎng)度。
解題：
class Solution {
public int removeDuplicates(int[] nums) {
if (nums.length == 0)
return 0;
int i = 0;
for (int j = 1; j < nums.length; j++) {
if (nums[j] != nums[i])
i++;
nums[i] = nums[j];
}
return i + 1;
}
}
53. 最大子序和（maxSubArray）
問(wèn)題描述：給定一個(gè)整數(shù)數(shù)組 nums ，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素），返回其最大和。
上榜理由：分治法代表（動(dòng)態(tài)規(guī)劃解法代碼量大大減小，詳見(jiàn)http://www.itdecent.cn/p/68577a67fecf
）
做法回顧：分析該題，一個(gè)數(shù)組的最大子序和，要么出現(xiàn)在該數(shù)組的左半部分，要么出現(xiàn)在右半部分，要么橫框左右，稱之為中間部分。通過(guò)分治法分而治之的思想，將問(wèn)題的規(guī)模不斷縮小，將求解最大子序和分為三個(gè)部分，左最大，右最大和中最大，比較三個(gè)的值返回最大值作為單次遞歸的結(jié)果。遞歸的結(jié)束條件是數(shù)組長(zhǎng)度為1時(shí)，返回它本身。
解題：
class Solution {
public int maxSubArray(int[] nums) {
if (nums.length == 0 || nums == null) {
return -1;
}
return maxSubArray(nums, 0, nums.length - 1);
}
public int maxSubArray(int[] nums, int left, int right) {
if (left == right) {
return nums[left];
}
int mid = (left + right) / 2;
int maxLeft = maxSubArray(nums, left, mid);
int maxRight = maxSubArray(nums, mid + 1, right);
//注意子序和要求為數(shù)組連續(xù)段的和
//思想：由中間開始向左加，為正則更新左最大子序和，否則繼續(xù)向左加
int sumLeft = 0, maxSumLeft = nums[mid];
for (int i = mid; i >= left; i--) {
sumLeft = sumLeft + nums[i];
if (sumLeft > maxSumLeft) {
maxSumLeft = sumLeft;
}
}
int sumRight = 0, maxSumRight = nums[mid + 1];
for (int i = mid + 1; i <= right; i++) {
sumRight = sumRight + nums[i];
if (sumRight > maxSumRight) {
maxSumRight = sumRight;
}
}
int result = maxLeft > maxRight ? maxLeft : maxRight;
int maxMid = maxSumLeft + maxSumRight;
result = result > maxMid ? result : maxMid;
return result;
}
}
66. 加一（plusOne）
題目描述：給定一個(gè)由整數(shù)組成的非空數(shù)組所表示的非負(fù)整數(shù)，在該數(shù)的基礎(chǔ)上加一。最高位數(shù)字存放在數(shù)組的首位， 數(shù)組中每個(gè)元素只存儲(chǔ)一個(gè)數(shù)字。你可以假設(shè)除了整數(shù) 0 之外，這個(gè)整數(shù)不會(huì)以零開頭。
上榜理由：力扣萌新的做法：遍歷數(shù)組轉(zhuǎn)化為整數(shù)來(lái)做。經(jīng)過(guò)這道題終于領(lǐng)悟了力扣的測(cè)試用例有多么的龐大，這樣的做法不可取啊，其實(shí)本質(zhì)來(lái)說(shuō)是沒(méi)有理解題意。
做法回顧：0-8不用進(jìn)位，直接末位加1，返回退出循環(huán)；末位為9，末位變零，循環(huán)繼續(xù)，前面的位數(shù)逐位加1，不再進(jìn)位則直接退出循環(huán)，若每一位均進(jìn)位直到遍歷到digits[0]，循環(huán)結(jié)束，則答案一定是1000...（最后三行代碼的由來(lái)，大神做法，好妙?。?/p>
解題：
class Solution {
public int[] plusOne(int[] digits) {
for (int i = digits.length - 1; i >= 0; i--) {
if(digits[i] != 9){
digits[i]++;
return digits;
}
digits[i] = 0;
}
digits = new int[digits.length + 1];
digits[0] = 1;
return digits;
}
}
88. 合并兩個(gè)有序數(shù)組
問(wèn)題描述：給定兩個(gè)有序整數(shù)數(shù)組 nums1 和 nums2，將 nums2 合并到 nums1 中，使得num1 成為一個(gè)有序數(shù)組。
上榜理由：我最開始的想法是先合并再排序，這樣的做法固然最樸素簡(jiǎn)單，但是時(shí)間復(fù)雜度方面不夠好，為O((n+m)log(n+m))。通過(guò)雙指針?lè)?/em>從后往前合并，可以獲得O(n+m)的復(fù)雜度，學(xué)習(xí)學(xué)習(xí)。
做法回顧：將nums1作為基數(shù)組，雙指針從后往前，取大的數(shù)字放到nums1，數(shù)字被取到的數(shù)組的指針向前滑，當(dāng)某一指針達(dá)到頭后，退出循環(huán)，若nums2還有比較后被剩下的數(shù)字（說(shuō)明此時(shí)剩下的比nums1的0位置數(shù)字更小），則補(bǔ)齊到基數(shù)組。
知識(shí)回顧：System.arraycopy(array1,0,array2,0,10)字符串拷貝，將array1從0位置拷貝到array2的0位置，拷貝長(zhǎng)度為10。
解題：
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
// two get pointers for nums1 and nums2
int p1 = m - 1;
int p2 = n - 1;
// set pointer for nums1
int p = m + n - 1;
// while there are still elements to compare
while ((p1 >= 0) && (p2 >= 0))
// compare two elements from nums1 and nums2
// and add the largest one in nums1
nums1[p--] = (nums1[p1] < nums2[p2]) ? nums2[p2--] : nums1[p1--];
// add missing elements from nums2
System.arraycopy(nums2, 0, nums1, 0, p2 + 1);
}
}
118. 楊輝三角
問(wèn)題描述：給定一個(gè)非負(fù)整數(shù) numRows，生成楊輝三角的前 numRows 行。
上榜理由：誰(shuí)沒(méi)有在初學(xué)編程的時(shí)候被楊輝三角摁在地上摩擦過(guò)呢？
做法回顧：用List里套List來(lái)存儲(chǔ)楊輝三角（[ [ ],[ ].. ]），最外層循環(huán)i表示當(dāng)前正在構(gòu)造的楊輝三角的行數(shù)，因?yàn)樯舷聝尚写嬖跀?shù)學(xué)關(guān)系，curList表示當(dāng)前構(gòu)造行，preList表示上一行。j==0||j==i表示每一行的兩端為1，其他時(shí)候根據(jù)上一行的左上方和右上方的數(shù)相加之和。
解題：
class Solution {
public List<List<Integer>> generate1(int numRows) {
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < numRows; i++) {
List<Integer> curList = new ArrayList<>();
List<Integer> preList = new ArrayList<>();
if (i > 0) {
preList = res.get(i - 1);
}
for (int j = 0; j <= i; j++) {
if (j == 0 || j == i) {
curList.add(1);
} else {
curList.add(preList.get(j - 1) + preList.get(j));
}
}
res.add(curList);
}
return res;
}
}
121.買賣股票的最佳時(shí)機(jī)
問(wèn)題描述：給定一個(gè)數(shù)組，它的第 i 個(gè)元素是一支給定股票第 i 天的價(jià)格。如果你最多只允許完成一筆交易（即買入和賣出一支股票），設(shè)計(jì)一個(gè)算法來(lái)計(jì)算你所能獲取的最大利潤(rùn)。
上榜理由：除了暴力解法還有沒(méi)有更有思考的解法呢？這道題給人啟示在于力扣上的很多算法題如果能使用數(shù)學(xué)思想進(jìn)行分析和簡(jiǎn)化，就可以優(yōu)化編程思路，要多加練習(xí)這方面。
做法回顧：最簡(jiǎn)單的解法當(dāng)然是暴力法，遍歷找到所有買進(jìn)賣出股票的方法，找到獲得最大利潤(rùn)的時(shí)刻，這種解法的時(shí)間復(fù)雜度為O(n^2)。而通過(guò)分析可知，我們的目的是要找到股價(jià)走勢(shì)圖中最低的谷之后最大的峰，其差值就是我們要找的最大利潤(rùn)。所以我們可以維持minprice和maxprice兩個(gè)變量。此解法的時(shí)間復(fù)雜度為O(n)。
解法：
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;
}
}
??????)??
??????)??
前120道簡(jiǎn)單題的數(shù)組tag題就總結(jié)到這兒了，我也終于走出了對(duì)抗艾賓浩斯遺忘曲線的第一步 XD，keep fighting！
