本文共 7215 字，大约阅读时间需要 24 分钟。
一、LeetCode 350题 求两个集合中的差值
1.1 题目分析
我们先来看一道题目： 第350题：两个数组的交集
需求：给定两个数组，编写一个函数来计算它们的交集。 实例代码输入: nums1 = [1,2,2,1], nums2 = [2,2]输出: [2,2]
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]输出: [4,9]
根据实例代码分析：
- 输出的结果应该与给定的两个集合共同出现的次数是相同的。
- 我们这里不考了排序的问题
- 首先拿着这个题目的时候，我们首先应该想到使用map的方式进行映射，为什么可以这样看那，因为我们需要找出两个数组中交集的元素，同时应与两个数组中出现的次数一直，这样导致我们需要制每个值串的次数，所以映射关系就成了<元素，元素出现的次数>
1.2 题目讲解
根据分析，假设我们有两个数组分别为； nums1=[1,2,2,2] ， nums2=[2,2]
首先我们定义一个map用来存其中一个数组中的数据，进行循环向数组中输入数据
第一次map中没有这个元素所以value为1
第二、三次map中如有这个元素value+1后面依次类推，就像使用map计算wordCount 
首先我们需要进行判断map中是否这个数据，如果有则进行相加(后面的逻辑就是一样的了) 
第二阶段 首先定义一个空的数组。我们现在获取到了map之后，map中就存储了我们每个元素及他们出现的个数，接下来我们在遍历nums2这个数组，拿着每个元素去map中get数据如果get到了数据value次数减1,将这个key复制给空的数组。
1.3 代码分析
public static int[] intersect(int[] nums1, int[] nums2) { // 判空操作 if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) { return new int[0]; } //1.定义一个map用来存储一个数组中的出现的值 value存储出现的个数 HashMap map = new HashMap<>(); for (int i = 0; i < nums1.length; i++) { Integer integer = map.get(nums1[i]); if (integer == null) { map.put(nums1[i], 1); } else { map.put(nums1[i], integer + 1); } } int k = 0; for (int i = 0; i < nums2.length; i++) { Integer integer = map.get(nums2[i]); if (integer != null) { if (integer > 0) { nums2[k] = nums2[i]; map.put(nums2[i], integer - 1); k++; } } } return Arrays.copyOfRange(nums2, 0, k); } 1.4 题目进阶（优化）
前提:我们首先我们需要将两个数组进行排序
如果给定的数组已经排好序呢？你将如何优化你的算法？我们分析一下，假如两个数组都是有序的，分别为： nums1=[1,2,2,2] ， nums2=[2,2]
<2>如果两个元素相同，则两个指针同时后移 
<3> 直到任意一个数组终止。 
1.5 代码分析
public static int[] intersect2(int[] nums1, int[] nums2) { if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) { return new int[0]; } int i = 0, j = 0, k = 0; Arrays.sort(nums1); Arrays.sort(nums2); while (i < nums1.length && j < nums2.length) { if (nums1[i] > nums2[j]) { j++; } else if (nums1[i] < nums2[j]) { i++; } else { nums2[k] = nums1[i]; i++; j++; k++; } } return Arrays.copyOfRange(nums2, 0, k); } 二、LeetCode 14 最长公共前缀
2.1 题目分析
我们先来看一道题目： 第14: 最长公共前缀
需求：编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，则返回"" 实例代码输入: ["flower","flow","flight"]输出: "fl"
输入: ["dog","racecar","car"]输出: ""
题目分析：
我们要想寻找最长的公共前缀，那么首先这个前缀是公共的，我们可以从任意一个元素中找到他。假定我们现在就从一个数组中寻找最长公共前缀，那么首先，我们可以将第一个元素设置为基准元素x0。假如数组为[“flow”,“flower”,“flight”]，flow就是我们的基准元素x0。
然后我们只需要依次将基准元素和后面的元素进行比较（假定后面的元素依次为x1,x2,x3…），不断更新基准元素，直到基准元素和所有元素都满足最长公共前缀的条件，就可以得到最长公共前缀。
对比流程：
- 如果strs[i].indexOf(x0,x) == 0，则直接跳过（因为此时x就是x1的最长公共前缀），对比下一个元素。（如flower和flow进行比较）
- 如果strs[i].indexOf(x0,x) != 0, 则截取掉基准元素x的最后一个元素，再次和x1进行比较，直至满足strs[i].indexOf(x0,x) == 0，此时截取后的x为x和x1的最长公共前缀。（如flight和flow进行比较，依次截取出flow-flo-fl，直到fl被截取出，此时fl为flight和flow的最长公共前缀）
2.2 图解分析
2.3 代码分析
public static String longestCommonPrefix(String[] strs) { if (strs.length==0 || strs[0].length()==0){ return ""; } String mondel = strs[0].substring(0, strs[0].length() - 1); for (int i = 0; i < strs.length; i++) { if (mondel.length()==0){ return ""; } if (strs[i].indexOf(mondel)!=0){ while (true){ mondel=mondel.substring(0,mondel.length()-1); if (mondel.length()==0){ break; } if (strs[i].indexOf(mondel)==0){ break; } } } } return mondel==null? "":mondel; } 三、LeetCode 买卖股票的最佳时机（I、II）
面试时出现的频率非常的高。稍微改一改条件，就让我们防不胜防。那我们如何攻克这一类的问题那？我们从最贱的一道开始看起。
3.1 121题 买卖股票的最佳时机 I
3.1.1 题目分析
我们先来看一道题目： 第121题：买卖股票的最佳时机 I
需求：给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。
示例1：输入: [7,1,5,3,6,4]输出: 5
解释： 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意：注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。 示例 2:输入: [7,6,4,3,1]输出: 0
解释： 在这种情况下, 没有交易完成, 所以最大利润为 0。
3.2.2 图解分析
执行流程 
3.1.3 代码分析
public static int maxProfit(int[] prices) { int maxProfit = 0, fi = 0, maxV = 0; for (int i = 1; i < prices.length; i++) { fi = Math.max(maxProfit + prices[i] - prices[i - 1], 0); maxV = Math.max(fi, maxV); maxProfit = fi; } return maxV; } 3.2 122题 买卖股票的最佳时机 II
3.2.1 题目分析
我们先来看一道题目： 第122题：买卖股票的最佳时机 II
需求：给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意： 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）
示例1输入: [7,1,5,3,6,4]输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。 示例 2:输入: [1,2,3,4,5]输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。 因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。示例三
输入: [7,6,4,3,1]输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
3.2.2 图解分析
假设我们的数据是：[7, 1, 5, 3, 6, 4]
从上图中，我们可以观察到 A+B+C的和等于差值 DD 所对应的连续峰和谷的高度之差。 3.2.3 代码分析
public int maxProfit(int[] prices) { int maxProfit=0; for (int i = 1; i < prices.length ; i++) { if (prices[i] > prices[i - 1]) { maxProfit += prices[i] - prices[i - 1]; } } return maxProfit; } 四、LeetCode 189 旋转数组
4.1 题目分析
我们先来看一道题目： 第189 题：旋转数组
需求：给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数 示例 1:输入: [1,2,3,4,5,6,7] 和 k = 3输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5] 向右旋转 3 步: [5,6,7,1,2,3,4]
示例 2:
输入: [-1,-100,3,99] 和 k = 2输出: [3,99,-1,-100]
解释:
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]
注意：
尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。 要求使用空间复杂度为 O(1) 的 原地 算法。4.2 图解分析
假设我们的数组为[1,2,3,4,5,6],I=6 且 k=3
通过观察我们可以得到，我们要得到最终的结果。我们只需要将所有元素反转，然后反转前 k 个元素，再反转后面l-k个元素，就能得到想要的结果。 
4.3代码分析
public static void rotate(int[] nums, int k) { revers(nums, 0, nums.length); revers(nums, 0, k % nums.length); revers(nums, k % nums.length, nums.length); } public static void revers(int[] nums, int start, int end) { int length = end - start; for (int i = 0; i < length / 2; i++) { int num = nums[start + i]; nums[start + i] = nums[start + length - i - 1]; nums[start + length - i - 1] = num; } System.out.println(Arrays.toString(nums)); } 转载地址：http://qokzi.baihongyu.com/