力扣刷到现在题做了不少，感觉遗忘速度与做题速度相当了，是时候总结一下了。思索了一下，按照tag来总结应该是个还不错的主意，第一篇就从数组入手吧，列出一些有代表性的题目，并且以题带知识点，顺便巩固一下基础的数据结构等知识。
1.两数之和（twoSum）
题目描述：给定一个数组和一个目标值，找出数组中和为目标值的两个整数，并且返回数组下标。
上榜理由：这道题是力扣开篇第一题欸，意义相当于单词书里的abandon，怎么能少了它呢~
做法回顾：这道题我当时用了三种解法来做它。其实也是很有意义的学习过程。
①使用暴力解法，两次循环，两个指针i，j初始值分别为0和i+1,当nums[i]+nums[j] == target时，返回i，j的值。这无疑是最简单的思路，但时间复杂度为O(n^2)，提交后无法通过，这给了我一个启示，就是在力扣做题是要考虑时间空间复杂度的，暴力解法还是往后放吧。
回顾题目要求，找出数组中的目标值的索引。通过值找索引最快的方法是什么，当然是哈希表了。所以后两种解法分别运用了两次哈希表和一次哈希表，解法类似。
②仍旧两次迭代，第一次将数组元素存入哈希表中，值为key，数组标号为value。第二次迭代过程，用containsKey来找目标值减去每个元素的值是否存在于数组当中，存在即返回该值的value，也就是下标。
③一次迭代，在插表的同时完成查找过程。
注：哈希表的key不能重复，但此处根据题意“假设每种输入只会对应一个答案”，实际上规避了这种情况。
知识回顾：哈希表是基于哈希函数建立的一种查找表，将key作为自变量，通过哈希函数计算出的值即是元素的存储地址。哈希表中存储的是键值对（key-value），Java中的HashMap()继承的是Map接口。常用的方法有get()，remove()，put(key,value)，containsKey()，containsValue()，isEmpty()，size()等。
详见：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. 删除排序数组中的重复项（removeDuplicates）
题目描述：给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
上榜理由：使用了快慢指针，具有一定的代表性。
做法回顾：其中i是慢指针，j是快指针。只要nums[i] == nums[j]，就j++跳过重复项。当遇到nums[j] != nums[i]时，i++，交换两个指针指向的值，接着重复相同的过程，直到 j 到达数组的末尾为止。nums[i]代表去掉重复元素的新数组，i+1即为移除后的数组长度。
解题：
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）
问题描述：给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
上榜理由：分治法代表（动态规划解法代码量大大减小，详见https://www.jianshu.com/p/68577a67fecf
）
做法回顾：分析该题，一个数组的最大子序和，要么出现在该数组的左半部分，要么出现在右半部分，要么横框左右，称之为中间部分。通过分治法分而治之的思想，将问题的规模不断缩小，将求解最大子序和分为三个部分，左最大，右最大和中最大，比较三个的值返回最大值作为单次递归的结果。递归的结束条件是数组长度为1时，返回它本身。
解题：
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);
//注意子序和要求为数组连续段的和
//思想：由中间开始向左加，为正则更新左最大子序和，否则继续向左加
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）
题目描述：给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。最高位数字存放在数组的首位， 数组中每个元素只存储一个数字。你可以假设除了整数 0 之外，这个整数不会以零开头。
上榜理由：力扣萌新的做法：遍历数组转化为整数来做。经过这道题终于领悟了力扣的测试用例有多么的庞大，这样的做法不可取啊，其实本质来说是没有理解题意。
做法回顾：0-8不用进位，直接末位加1，返回退出循环；末位为9，末位变零，循环继续，前面的位数逐位加1，不再进位则直接退出循环，若每一位均进位直到遍历到digits[0]，循环结束，则答案一定是1000...（最后三行代码的由来，大神做法，好妙啊）
解题：
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. 合并两个有序数组
问题描述：给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得num1 成为一个有序数组。
上榜理由：我最开始的想法是先合并再排序，这样的做法固然最朴素简单，但是时间复杂度方面不够好，为O((n+m)log(n+m))。通过双指针法从后往前合并，可以获得O(n+m)的复杂度，学习学习。
做法回顾：将nums1作为基数组，双指针从后往前，取大的数字放到nums1，数字被取到的数组的指针向前滑，当某一指针达到头后，退出循环，若nums2还有比较后被剩下的数字（说明此时剩下的比nums1的0位置数字更小），则补齐到基数组。
知识回顾：System.arraycopy(array1,0,array2,0,10)字符串拷贝，将array1从0位置拷贝到array2的0位置，拷贝长度为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. 杨辉三角
问题描述：给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
上榜理由：谁没有在初学编程的时候被杨辉三角摁在地上摩擦过呢？
做法回顾：用List里套List来存储杨辉三角（[ [ ],[ ].. ]），最外层循环i表示当前正在构造的杨辉三角的行数，因为上下两行存在数学关系，curList表示当前构造行，preList表示上一行。j==0||j==i表示每一行的两端为1，其他时候根据上一行的左上方和右上方的数相加之和。
解题：
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.买卖股票的最佳时机
问题描述：给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
上榜理由：除了暴力解法还有没有更有思考的解法呢？这道题给人启示在于力扣上的很多算法题如果能使用数学思想进行分析和简化，就可以优化编程思路，要多加练习这方面。
做法回顾：最简单的解法当然是暴力法，遍历找到所有买进卖出股票的方法，找到获得最大利润的时刻，这种解法的时间复杂度为O(n^2)。而通过分析可知，我们的目的是要找到股价走势图中最低的谷之后最大的峰，其差值就是我们要找的最大利润。所以我们可以维持minprice和maxprice两个变量。此解法的时间复杂度为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道简单题的数组tag题就总结到这儿了，我也终于走出了对抗艾宾浩斯遗忘曲线的第一步 XD，keep fighting！
网友评论