和233酱一起刷leetcode系列
为什么要刷leetcode
引用 左耳朵耗子 耗子叔的一段话：
““
Leetcode这个网站上的题都是一些经典的公司用来面试应聘者的面试题，很多人通过刷这些题来应聘一些喜欢面试算法的公司，比如：Google、微软、Facebook、Amazon之类的这些公司，基本上是应试教育的功利主义。
我做这些题目的不是为了要去应聘这些公司，而是为了锻炼一下自己的算法和编程能力。因为我开始工作的时候基本没有这样的训练算法和编程的网站，除了大学里的“算法和数据结构”里的好些最基础最基础的知识，基本上没有什么训练。所以，当我看到有人在做这些题的时候，我也蠢蠢欲动地想去刷一下。
于是，我花了3-4个月的业余时间，我把Leetcode的154道题全部做完了。（这也是最近我没有太多的时间来写博客的原因，你可以看到我之前做的那个活动中有几个算法题来自于Leetcode）有人说我时间太多了，这里声明一下，我基本上都是利用了晚上10点以后的时间来做这些题的。
LeetCode的题大致分成两类：
1）基础算法的知识。这些题里面有大量的算法题，解这些题都是有套路的，不是用递归（深度优先DFS，广度优先BFS），就是要用动态规划（Dynamic Programming），或是拆半查找（Binary Search），或是回溯（Back tracing），或是分治法（Divide and Conquer），还有大量的对树，数组、链表、字符串和hash表的操作。通过做这些题能让你对这些最基础的算法的思路有非常扎实的了解和训练。对我而言，Dynamic Programming 是我的短板，尤其是一些比较复杂的问题，在推导递推公式上总是有思维的缺陷（数学是我的硬伤），通过做了这些题后，我能感到我在DP的思路上有了很大的收获。
2）编程题。比如：atoi，strstr，add two num，括号匹配，字符串乘法，通配符匹配，文件路径简化，Text Justification，反转单词等等，这些题的Edge Case, Corner Case有很多。这些题需要你想清楚了再干，只要你稍有疏忽，就会有几个case让你痛不欲生，而且一不小心就会让你的代码会写得又臭又长，无法阅读。通过做这些题，可以非常好的训练你对各种情况的考虑，以及你对程序代码组织的掌控（其实就是其中的状态变量）。还记得我在《函数式编程》中说的，程序中的状态是你程序变得复杂难维护的直接原因。
我觉得每个程序员都应该花时间和精力做这些题，因为你会从这些题中得到很大的收益。做完这些题后你一定会明白下面几个道理：
1）想清楚了再干。这个观点我以前就在《多些时间可以少些代码》说过。如果你拿到题就上去直接写代码的话，你一定会被各种case打回来了。然后呢，你一着急，你就会进入那种我在《开发团队的效率》中说的那种毫无效率case by case的开发模式，而你也进入了“平庸模式”。于是你就会出现下图那样的情况。
Case-by-Case Developement
2) 编程是脑力劳动，急不得。这个事情在这做这些题的时候你就会发现，要么是脑子转不过来了，要么就是明明就差一点了，但程序怎么都调不对。如果你越着急的话，你就会发现你会离目标越远，而花的时间也会更多。另外，你会发现这些题基本上都是50行代码内就可以搞定的，但是为了这50行以内的代码，你要花好多时间和精力。coding 50行代码在我们的日常工作中分分钟就完成，而Leetcode里的50行代码却没那么简单，也许，用这个你就可以区别什么是码农，什么是程序员了。
3）加班要不得。因为我总是在晚上10点以后做题，所以，基本上都是在加班状态中工作。这种状态过上两三天，你就会发现，整个大脑已经不转了，而且不但不转，还会犯很多低级错误，很多事情都想不清楚，一个晚上都在和程序的状态控制做搏斗，代码写得越来越乱，越来越没条理。于是这种时候，我都会休息几天，不做题了，然后再做题的时候，就觉得非常地清楚。可见加班 是编程最致命的敌人！
””
如何刷leetcode
leetcode难刷是因为初刷时处处是自己的难度题，一个人孤军奋战，很容易被劝退。但是刷题是有套路的，我们需要搞清楚每道题背后所对应的一类问题的套路，学会套路才是目的。
氛围和坚持
233酱也想和大家一起攻克这个难关。我想和大家一起营造一个刷题氛围，互帮互助，每日至少坚持搞懂一道题，早日赢娶白富美：）
如何更简单的明白套路
人接受讯息的难度文字要难于视频，但是文字相比视频留给人更多的思考时间。此外针对性的相互交流也更加容易获得帮助。我们需要多管齐下。
233酱想免费提供的一条龙服务：
公众号文章题解 -> 私信答疑 -> 刷题群答疑 -> 视频讲解
我们的目的是搞懂每道题背后的套路，成为套路王～
嘿嘿，关注公众号：【码农知识点】，加 233酱 微信好友，备注 加刷题群 就完成了一大步 (友情提示：不允许频繁水群哦，先劝退一波 :)
至于233的视频讲解，目前我还没学会如何拍视频。废话，拍不美拍什么鬼视频。。但这并不妨碍... 大饼要先画，牛逼要先吹～只能说快了快了 (>▽<)
口嗨完毕，leetcode1-5， Let's do it :)
leetcode1.两数之和
题目描述：
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
题目示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]解题思路:
- 当顺序遍历数组时，假设当前遍历的数是
secondNum，我们关心的是firstNum =target - curr是否在数组nums中出现。 只要我们记录下来secondNum之前遍历过的数的一个集合，判断其中firstNum是否存在，即可获取到答案。 - 套路：
hash映射可将查找firstNum的时间复杂度降为O(1)，用hashmap解决。 - 整体时间复杂度：O(n)。 遍历
secondNum:O(n),判断firstNum是否存在：O(1)
Java版本
class Solution {
public int[] twoSum(int[] nums, int target) {
//key:数组中已遍历过的数字 value:数字在数组中的下标
Map<Integer,Integer> existMap = new HashMap<>();
for(int i = 0;i<nums.length;i++){
int secondNum = nums[i];
Integer firstNum = target - secondNum;
if(existMap.containsKey(firstNum)){
return new int[]{existMap.get(firstNum),i};
}
existMap.put(secondNum,i);
}
throw new IllegalArgumentException("No two sum solution");
}
}leetcode2. 两数相加
题目描述： 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
题目示例:
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807解题思路:
- 和我们学数字加法的思路一样。假设A+B=C，注意C是否有下一数字位的条件是：
A对应数字位不为空 || B对应数字位不为空 || 上次运算的进位不为空 - 套路：
加法运算&单链表的插入，明确单链表节点ListNode的结构，调整好链表的指针就不会出错了。
小技巧：构造一个头节点dummyNode，可将结果链表的头节点和之后节点的逻辑保持一致，不然头节点就需要判断结果链表是否为空。
Java版本
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummyNode = new ListNode(-1);
ListNode tailNode = dummyNode;
int progress = 0;
while(l1 != null || l2 != null || progress > 0){
int sum = progress;
if(l1 != null){
sum += l1.val;
l1 = l1.next;
}
if(l2 != null){
sum += l2.val;
l2 = l2.next;
}
int result = sum % 10;
progress = sum / 10;
tailNode.next = new ListNode(result);
tailNode = tailNode.next;
}
return dummyNode.next;
}
}leetcode3. 寻找不重复子串的长度
题目描述： 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
题目示例:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。解题思路: 需要解决的问题是：我们需要从所有的子串中获得最长子串的长度。高效的做法是不需要遍历所有的子串。
- 假设子串l->r(l,r是输入字符串的字符下标)是最长无重复子串，当我们从左到右遍历输入串的字符，在找子串l->r时，r所对应的l值至少是在和r所对应的字符串相同的上一个下标的右边一位。我们同样可以用hash结构来存储每个已出现字符出现的最大下标位置。
l 和 r 满足单调性，也就是说 l 和 r的值只会向右前进，不会倒退。我们可以用反证法证明这个结论。
这样我们只需要遍历一次输出串，每次都修改当前 l 和 r对应的值，和最大子串长度max对比下是否需要更新max就好了。
- 套路：
滑动窗口。左右指针的滑动满足单调性，只会前进，不会后退。 - 时间复杂度：O(n)
小技巧：因为是ASCII字符，最多有256个，通过初始化好一个 int[256] 数组，而不是用hashmap来装每个字符对应的最大下标位置，可提高执行效率。
Java版本
class Solution {
public int lengthOfLongestSubstring(String s) {
int[] m = new int[256];
Arrays.fill(m, -1);
int res = 0, left = -1;
for (int i = 0; i < s.length(); ++i) {
left = Math.max(left, m[s.charAt(i)]);
m[s.charAt(i)] = i;
res = Math.max(res, i - left);
}
return res;
}
}leetcode4. 求两个有序数组的中位数
题目描述： 给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。 请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。 你可以假设 nums1 和 nums2 不会同时为空。
题目示例:
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0解题思路:
这道题可转换为求两个有序数组中第k个有序的数:
假设total=nums1.length + nums2.length,当total为奇数时， k = total/2 + 1;当total为偶数时，中位数 = （第total/2个有序的数 + 第total/2 + 1个有序的数）/2.0
因为时间复杂度要求为O(log(m + n))，看到log级别我们就可以往二分法上去思考。因为我们不知道这第k个数分别是由nums1数组和nums2数组中的哪些数组成，但我们可以保守的知道一定会包含哪些部分。
假设取nums1数组的前k/2个数 和 nums2数组的前k/2个数 ，假设：
- nums1[k/2] < nums2[k/2] :则说明这前k个数中一定包含nums1的前k/2个数，那我们可以从nums1的 k/2 + 1 之后 和 nums2的整个数组中继续寻找剩下的前k/2个数，此时折半单位就是k/4.直到触发边界条件：
剩下前k个数未找到的数只有一个 or nums1[k/2] = nums2[k/2] or 较短的数组已经遍历完了等条件，可结束折半处理，做对应的边界处理。 - nums1[k/2] > nums2[k/2] :同理。
- 套路：二分查找，每次可去掉一半的数。待查找的数：k -> k/2 -> k/4... -> 1 or 0个
Java版本
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int total = nums1.length + nums2.length;
if(total %2 == 0){
//偶数个数，中位数是中间两个数的平均数
int left = find(nums1,0,nums2,0,total/2);
int right = find(nums1,0,nums2,0,total/2 + 1);
//注意：必须除以2.0才是小数运算
return (left + right)/2.0;
}
//中位数是第total/2+1个数
return find(nums1,0,nums2,0,total/2+1);
}
/**
*
* @param nums1: 有序数组nums1
* @param i：有序数组nums1的起始查找下标位置
* @param nums2：有序数组nums1
* @param j：有序数组nums2的起始查找下标位置
* @param k：待查找的k个数
* @return：待查找的第k个数的值
*/
public int find(int[] nums1,int i,int[] nums2,int j,int k){
if((nums1.length - i) > (nums2.length - j)){
//将nums1定义为长度较短的有序数组，方便后面边界条件代码的简洁
return find(nums2,j,nums1,i,k);
}
if(k == 1){
//待查找的数只剩下一个
if(nums1.length == i) return nums2[j];
return Math.min(nums2[j],nums1[i]);
}
//nums1 查找完了
if(nums1.length == i) return nums2[j+k-1];
//下一次二分nums1的下标位置
int next_i = Math.min(nums1.length,i+k/2);
//下一次二分nums2的下标位置
int next_j = j+k-k/2;
if(nums1[next_i-1] > nums2[next_j-1]){
//此时应该丢弃的是nums2的 next_j - j 个数
return find(nums1,i,nums2,next_j,k-(next_j-j));
}else{
//此时应该丢弃的是nums1的 next_i - i 个数
return find(nums1,next_i,nums2,j,k-(next_i-i));
}
}
}leetcode5. 最长回文子串
题目描述： 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
题目示例:
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。解题思路: 题目是找出一个最长回文子串。和leetcode3思路一样，高效的做法 不需要遍历所有子串。还是利用滑动窗口的左右指针来及时止损。
字符串s 的最大长度为 1000，说明O(n^2) 的时间复杂度可以通过。这个题有多种解法，如动态规划。但是动态规划的时间复杂度和空间复杂度都是O(n^2)。比我们下面这种中心扩展算法要占空间，所以我们看一下中心扩展算法的解法：
回文子串的特点是左右对称，我们以中心为轴向左右两边扩散。确定最终最长的回文子串左右指针的位置。遍历输入串s中的每个字符，每个字符作为中心位置向左右两侧寻找回文子串，记录下每次比较后的最长回文子串的左右指针位置，就得到了答案。
回文子串的中心位置包含两种情况：
1.长度为奇数：如aba,则以b为中心左右对称。假设b处的下标为i,则左指针起始位置为：i-1；右指针起始位置为：i+1 2.长度为偶数：如abba，则我们可以假设当前遍历的字符 下标i 是左指针起始位置，则右指针起始位置为：i+1
- 套路：还是滑动窗口
Java版本
class Solution {
public String longestPalindrome(String s) {
if (s.length() <= 1) return s;
String result = "";
for (int i = 0; i < s.length() - 1; i++) {
//奇数位回文串
int left = i - 1;
int right = i + 1;
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
//right - left -1 = (right -1) - (left + 1) +1
if (result.length() < (right - left - 1)) {
result = s.substring(left + 1, right);
}
//偶数位回文串
left = i;
right = i + 1;
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
//right - left -1 = (right -1) - (left + 1) +1
if (result.length() < (right - left - 1)) {
result = s.substring(left + 1, right);
}
}
return result;
}
}