[每天两道题]坚持找到工作为止

大龄30＋，生活所迫，上有老下有小，重新找cs的工作，走上做题家的道路，每天晚上就做两道题，希望能坚持到找到工作为止。


补充内容 (2022-04-10 16:09 +8:00):
由于easy太简单，所以从今天开始easy不算数，每天两道中等或者hard题。

随手点进来看了一下，楼主给你点小建议，你的代码格式可以参考https://google.github.io/styleguide/javaguide.html
就我看你的代码时而符合上面链接的格式，时而又不符合，就比如你这个         
if(str.length() == n * 2){
按照“正确”(打引号是因为这种东西没有一定的正确和错误之分，只是那些行业大佬们约定俗成的习惯)的格式应该是
if (str.length() == n * 2) {
我多打这两个空格你看着觉得没什么，但可能在一些面试官看来就是区别有经验和新手的分界线
建议养成习惯

3 Longest Substring Without Repeating Characters
题目大意
给一个string，让找出其中的一段，这一段包含的元素没有重复的，并且要找出最长的这样一段。

分析和解答
string 就是array。所以看到string 要自动联想到array的解题思路。

array的题型中，找出一些符合某种规律的元素，是最常见的题型。这个题也是如此，它本质就是要求找出一段连续的元素，并且这个元素之间都不重复。

连续的子元素，也就是subarray的题，一定是滑动窗口。万能的数据结构就是Deque。
这个题就是如此，最笨的方法，就是用一个Deque，每次放一个新的元素在右边，然后遍历一次Deque里面的元素，看看有没有重复的，若是有重复的，就弹出左边的元素，再遍历一次，检查有没有重复。若是还有，就继续弹出左边，检查 ……直到没有重复的元素。此时我们就得到了一段没有重复元素的substring，记录一下长度。然后继续放一个新的元素在右边。
当右边到达array的尽头，也就是到了string的最后一个字符，就停止。最后记录一次此时的长度。然后我们就得到了所有没有重复元素的字串的长度，就能知道最长的长度是多少。

当然，这是最笨的方法，每次更新Deque，都要重新遍历一次，检查有没有重复的元素。那么有没有办法可以加速呢？当然可以，还记得1 Two sum的思想吗？只要用一个map，key是元素的值，value是元素的index，我们可以在o(1)的时间内找出过去有没有见过某个元素，并且知道它的位置。

所以更改一下，每次我们添加一个新的元素，就去map里检查一下，看看之前有没有这样的元素，有的话，就记录一下这个元素之前的位置，到现在位置的长度，就是一个新的长度了。但是这个方法还是有问题，因为我们还是要弹出deque的左边直到没有重复的元素，并且还要删除map里的值，写起来很麻烦。

更简单的写法，就是我们只记录左边界的位置 - l，和右边界的位置 - r。我们用一个int[256] map数组，来记录有没有出现过某一个字符，map[i] = 1表示冲出现过，=0就是没有出现过。
每一次右边界 - r 扩大，就缩看map[r]是不是为1，若是为1，说明之前出现过，那么我们就不停地增加左边界 - l，并且让map[l] = 0即可表示我们删除了这个字符在map里。
然后我们就得到了新的长度，可以记录了。

1. public int lengthOfLongestSubstring(String s) {
   
2.         char[] sc = s.toCharArray();
   
3.         int[] map= new int[256];
   
4.         int left = 0;
   
5.         int rs = 0;
   
6.         for(int i = 0; i < sc.length; i++){
   
7.             rs = Math.max(rs, i -left);
   
8.             int r_idx = sc[i];
   
9.             
   
10.             while(map[r_idx] > 0 && left < i){
    
11.                 int l_idx= sc[left];
    
12.                 map[l_idx]--;
    
13.                 left++;
    
14.             }
    
15.             
    
16.             map[r_idx]++;
    
17.         }
    
18.         return Math.max(rs, sc.length -left);
    
19.     }

复制代码

48. Rotate Image
顺时间旋转数组90度。这个题非常有实用性，比如旋转一个图片，本质就是这道题了。

这个题解法很多，我认为最好记，也是最容易理解的，就是把它变成两步 －
1. 斜对称翻转数组， 轴的方向是  “\”
2. 左右翻转数组，轴的方向是"|"

这两步代码都有一些坑。
斜对称翻转，行for（i＝ 0； i< len; i++)。列 for(j = i + 1; j < len; j++)
然后互换的两这个数字坐标是 : m[i][j]   m[j][i]。
这个其实挺好理解的，也就是我们只取斜着的一部分，然后把i j对调就是要互换的数字了

左右对称, 行for（i＝ 0； i< len; i++)。列 for(j = 0; j < len / 2; j++)
也就是我们只取列的一半
然后互换的两这个数字坐标是 : m[i][j]   m[i][len - 1 - j]。

依次运行两个方法，就能得到答案了，所以代码就是

1. class Solution {
   
2.     public void rotate(int[][] matrix) {
   
3.         transposed(matrix);
   
4.         reverse(matrix);
   
5.     }
   
6.    
   
7.     private void transposed(int[][] matrix) {
   
8.         for(int i = 0; i < matrix.length; i++) {
   
9.             for(int j = i + 1; j < matrix[0].length; j++) {
   
10.                 int temp = matrix[i][j];
    
11.                 matrix[i][j] = matrix[j][i];
    
12.                 matrix[j][i] = temp;
    
13.             }
    
14.         }
    
15.     }
    
16.    
    
17.     private void reverse(int[][] matrix) {
    
18.         for(int i = 0; i < matrix.length; i++) {
    
19.             for(int j = 0; j < matrix.length / 2; j++) {
    
20.                 int temp = matrix[i][j];
    
21.                 matrix[i][j] = matrix[i][matrix.length - 1 - j];
    
22.                 matrix[i][matrix.length - 1 - j] = temp;
    
23.             }
    
24.         }
    
25.     }
    
26. }

复制代码

哈哈哈 才两道 打回去重做。刷题要上瘾的。

握爪楼主，我29了，一起努力

1. Two Sum
心得 －
n数之和是一个系列的问题，可以连着做，随着n的增加难度也提升。

解法 －
首先培养解题步骤习惯，所有算法题目，要求你进行计算对象，只有四种 － 数字、数列、图、链表。其中数列是最多的，也是最复杂的。
这个第一题就给了一个数列，要求找出符合条件的某两个数字。

这道题很简单，但是思想很重要 － 我们可以把数列，保存成一个hashmap。用hashmap来加快查找速度。

解法，首先定义一个hashmap，key是数列中的数字，value是它的index。
从index = 0开始，挨个看数列里的每一个数字是什么。每看到一个数字 x ，根据题意，我们要找数列中另外一个数字 y ，使得x， y满足x + y = target。简单地小学代数一下，可知y = targey - x。 所以，题目就变成是我们看到一个x ，就在数列里找一下，看看数列里有没有target - x。

因为我们有map，所以只要用map.containsKey(target -x)即可知道有没有这样数。若是有，那我们就找到了一对数字x 和  target - x满足题目要求，然后我们按照要求把x的index， 和 target - x的index，组成一个int[2]数组返回。
若是没有，我们就把x和它的index保存在map里面。然后继续看下一个数字。

这里，巧妙的地方在于，若是当前的map里没有target - x，我们就保存当前的x到map里，这样我们就是一边建立map，一边找数字，两个事情可以同时完成。
实际上你也可以一步一步来，我第一次写就写了两个循环，先用一个for循环把所有的数字和它们对应index，都保存在map里面，然后再用一个for循环再找taget -x 。这样理论上时间复杂度是一样的。但是可以更清楚地看清题目解法的本质。

2 Add two numbers
题目大意
这个题给了两个listnode，每一个listnode的节点，都是一个0~9的数字，然后它说 － 每一个链表代表了一个数字，比如2->4 -> 3 就是243。然后它让你计算一下，这两个listnode所代表的数字相加之后等于多少，并且把结果也用listnode的方式返回。

解法：
先看给了我们什么东西，给了listnode，那么我们就知道这个题就是要考listnode的知识。listnode的知识点主要就是考两个，你如何去查找listnode里面的内容，或者如何生成一个新的listnode。

这到题两个内容都考了，它让你找出两个listnode的内容，并且再生成一个新的。所以它是一个中等难度的题。但是它并不难。
首先看如何取出listnode内容，其实也就是两个方法用while，或者用递归。这道题用哪个都可以，我只写了用while的方法。

用while实际上就是while(node != null) node = node.next;
这样相当于，每次我都把node这个变量，都更新成它的下一个。本质上就是把node这个东西对应的内存，更新一下。这里看似简单，但是一定要理解node指针到底对应什么东西，对于我这种非计算机专业的，计算机硬件原理什么的真心学不懂。我就理解为，这个node就是个cd播放器，每次node = node.next，就是换了一张碟进去。然后碟片是有编号的，你只能按顺序放碟片……虽然根本不准确，但是意思差不多……

这样我们就可以取出listnode的值，进而得到里面对应的数字了。

然后再看，新生成一个listnode。但凡看到新生成一个listnode，就要考虑要不要建立一个dummy head node。为什么呢？还是考虑播放器的例子，因为我要看碟片里的内容，所以每次我换一个碟，记录一下内容，直到最后，但是换到最后，我的播放器里装的是最后一张碟。但是题目要求返回的结果，要从头开始听，由于碟片有编号，只能从1号碟片开始听。所以我们要把里面的碟片换成1号碟片。
可是问题来了，这个播放器不能倒着放，此时我的内存里没有1号碟片了，怎么办？

所以，我们要建立一个dummy head，把它的next变成1号碟片。也就是另外建立一个内存，保存一下1号碟片。最后，我们就把这个dummy head的next也就是1号碟片返回。

这样，我们用while，每次分别取出给定的两listnode中的值，然后把这两个值相加，再把相加的结果放到一个新的listnode里面即可。

注意这里还有一个小考点就是如何处理进位，我们要定义一个整数，初始化为0, 用于保存进位。‘这样，相加的值就是sun = （x + y + carray) % 10。carray = (x + y + carray) / 10。
最后，当while结束之后，别忘了若是carray不为0，我们还要继续把它也添加进结果里，比如 999 + 1 = 1000   这样的。

这种进位，在很多其他题目里都是基础技能，一定要熟练到本能地就能写出来。
这么这道题就做完了，我自己的代码是

1. public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
   
2.         ListNode dummy = new ListNode();
   
3.         ListNode node = dummy;
   
4.         int carry = 0;
   
5.         dummy.next = node;
   
6.         while(l1 != null || l2 != null){
   
7.             int v1 = l1 == null ? 0 : l1.val;
   
8.             int v2 = l2 == null ? 0 : l2.val;
   
9.             
   
10.             node.next = new ListNode((v1 + v2 + carry) % 10);
    
11.             carry = (v1 + v2 + carry) / 10;
    
12.             
    
13.             node = node.next;
    
14.             l1 = l1 == null ? null : l1.next;
    
15.             l2 = l2 == null ? null : l2.next;
    
16.         }
    
17.         if(carry > 0)
    
18.             node.next = new ListNode(carry);
    
19.         return dummy.next;
    
20.     }

复制代码

加油加油！
楼主很懂，解题思想最重要。

4. Median of Two Sorted Arrays
这个题是hard难度的，我自己是hard题就直接看答案，反正光理解答案就够我研究半天的了。
题目大意：
这个题依然是给array，找出元素的题型。
题目给了两个array，并且已经排好序。然后让你找出它们两个合并后，位置在正中间的一个值，或者位置在正中间的两个值的平均数。

题目分析和解答
题目若是允许合并之后再找，那就是一点难度都没有了。题目要求是O(log(n))的时间复杂度。看到log肯定就是二分法了。但是这个题怎么用二分法就非常难理解了，我看了半天答案才看明白。

先看看，我们要找出中间位置的数字 k，假设两个array，一个长度是m，一个长度是n。那么这个中间数字，一定是或者包含第(m + n + 1 ) / 2个数。例如 1 2 3 4 5。五个数字，中间数字是3，3是第 6 / 2 = 3个数字。

所以，题目就是要求我们， 在第一个array里淘汰m1个数字，在第二个array 里淘汰m2个数字，m1 + m2 = (m+n+1) / 2，这样第m1个数或者第m2个数字就有可能是中间的数字。

那么问题就是m1和m2怎么分配？

这里就可以用二分法了，比如我们就看m1，只要m1定了，那么m2  = (m + n + 1) / 2 = m1;
那么m1 有多少种分配方法呢？
当然就是 从第0个开始到第m个或者第 (m + n + 1) / 2 个（看 (m + n + 1) / 2 和m哪个更小），也就是 [0, 1, 2, 3, 4, 5, 6, 7….m] 或者[0,1,2,3,.... (m + n + 1) / 2 ］

所以这个分配方法也是个排好顺序的数列，这个地方就是最难想的，我感觉正常人基本上没有提示不太可能想得出来……

那么我们就可以用二分法来选择m1了，l  = 0, r = m ；
那么mid = l + (r - l) / 2的意思，就是我们m1选了mid个，也就是在第一个数列里，淘汰mid个。那么第二个数列里就是淘汰(m + n + 1) / 2  - mid个。
此时，我们怎么知道这样的选择是否是正确的呢，这也是这个题第二个难点。

判断的方法是这样的，因为两个数组是排序的，所以选定一个数字，那么它左边的都比它小，右边的都比它大（废话）。
所以，我们各自选定两个数字c1, c2之后，我们就看这两个数字的大小。
若是c1 < c2，说明答案一定 在区间[c1, c2]里面。并且说明我们c1可能选得小了。
不过此时，比c1小的数字，就确定一定可以淘汰了。所以我们可以把[0, 1, 2, 3, 4, 5, 6, 7….m] 中左边比c1小的数字个数都淘汰掉。

反过来，若是c1 > c2。那就是说明比c2小的数字，也可以淘汰掉了。而且我们要意识到，可能c1选大了，淘汰了太多数字，所以我就缩小r。不让下次mid变得太大。

最后当 l = r的时候，我们就找到了答案 。

最后两个点
1是奇偶判断，奇数长的数列只有c1，我们直接返回答案即可。
2是当答案都在同一个数列里面，此时就会出现l <= 0或者r>m等情况，所以我们要用这中情况淘汰掉无用的坐标，只保留有意义的坐标即可。

1. public double findMedianSortedArrays(int[] nums1, int[] nums2) {
   
2.         int m = nums1.length;
   
3.         int n = nums2.length;
   
4.         
   
5.         if(m > n)
   
6.             return findMedianSortedArrays(nums2, nums1);
   
7.         
   
8.         int k = (m + n + 1) / 2;
   
9.         
   
10.         int l = 0, r = m;
    
11.         
    
12.         while(l < r){
    
13.             int d_m = l + (r - l) / 2;
    
14.             int d_n = k - d_m;
    
15.             
    
16.             if(nums1[d_m] < nums2[d_n - 1]){
    
17.                 l = d_m + 1;
    
18.             }else{
    
19.                 r = d_m;
    
20.             }
    
21.         }
    
22.         
    
23.         int m1 = l;
    
24.         int m2 = k - l;
    
25.         
    
26.         int c1 = Math.max(m1 <= 0 ? Integer.MIN_VALUE : nums1[m1 - 1],
    
27.                           m2 <= 0 ? Integer.MIN_VALUE : nums2[m2 - 1]);
    
28.         
    
29.         if((m + n) % 2 == 1){
    
30.             return (double)c1;
    
31.         }
    
32.         
    
33.         int c2 = Math.min(m1 >= m ? Integer.MAX_VALUE : nums1[m1],
    
34.                           m2 >= n ? Integer.MAX_VALUE : nums2[m2]);
    
35.         
    
36.         return (c1 + c2) * 0.5;
    
37.     }

复制代码

5. Longest Palindromic Substring
题目大意
给一个字符串，找出最长的回文字符串。
回文字符串就是对称的字符串。

题目分析和解答
String就是array，这道题很好滴体现了这个思想。这道经典题最佳解法就是著名的马拉车算法了。
不过这个算法对于我这种智力较低者实在无法记住，若是面试的时候遇到对方一定要我写马拉车算法，那么我最好还是用话术来回避这个问题才是上策。
但是马拉车算法中，中心扩展法也是基础。所以这道题，我就用中心扩展法写了一遍。这就已经足够我们通过面试了。

这道题就算用中心扩展法，依然比较难写对。首先，中心扩展法的思路很简单，核心方法就是以某一个字符 C 为中心，逐个比较它两边的字符是不是一样的，直到不一样为止。假设我们比较了R次之后，两边的字符不一样了。这样我们就得到了以C为中心，半径长度为R的一个回文字符串。
我们把给我们的字符串S中，每一个字符为中心，它的回文传的长度都算出来之后，自然就可以找到最长的那个了。

思想明白之后，就是技巧了。这个题因为奇偶的情况不一样，所以有一个预处理的过程，就是把babac处理成#b#a#b#a#c#，也就是每一个字符前后都夹一个#。这样我们就不用担心bb这样的回文串了，因为bb处理完之后是b#b。所以我们可以用＃为中心，去计算长度。最后我们把#b#b#中的#去掉，就是答案了。这样处理，可以避免讨论奇偶的不同。

那么我的代码就是这样的：

1. public String longestPalindrome(String s) {
   
2.         char[] sc = preprocess(s);
   
3.         int max = 0; int cindx = 0;
   
4.         for(int i = 0; i < sc.length; i++){
   
5.             char center = sc[i];
   
6.             int r = 1;
   
7.             while(i - r >= 0 && i + r < sc.length && sc[i - r] == sc[i + r] ){
   
8.                 r++;
   
9.             }
   
10.             if(r > max){
    
11.                 max = r;
    
12.                 cindx = i;
    
13.             }
    
14.         }
    
15.        //System.out.print(new String(sc) + " " + cindx + " " + max);
    
16.         StringBuilder sb= new StringBuilder();
    
17.         for(int i = cindx - max + 1 ; i < cindx + max - 1 ;i++){
    
18.             
    
19.             if(sc[i] != '#'){
    
20.                 sb.append(sc[i]);
    
21.             }
    
22.         }
    
23.         return sb.toString();
    
24.         
    
25.     }
    
26. 
    

复制代码

题目大意
这道题给你一个string，和一个整数numRow。然后让你按照一种规律来重新拼接字符串。
规律就是。假设numRow 是3，也就是3行。字符串是 123456789
那么它要求你这么拐着拼
1    5   9
2 4 6 8
3    7
最后答案就是 - 159246837。

题目分析和解答。

这道题非常不好，点踩的人很多，很容陷入计算下标的无意义的数字游戏中。当然若是你数学足够强，应该可以很快地推导出公式。不过对于我们这种凡人来说，可能还是需要一个更方便的方法比较好。

这个更方便，更容易的记的方法，就是桶排序。
实际上，我感觉好像所有代zigzag的题，应该马上反应过来用童排序去解答。

那么桶排序是什么意思呢。其实还是第一道题two sum的思想扩展。因为我们可以把array保存在一个map里面，方便以后进行查询。

但是two sum里，我们key是元素值，也就是我们是按照元素本身的值，进行分类和保存的。

那么扩展一下思路的话，我们当然可以用其他的特征值，来把元素分类和保存啊。
所以此时，key就是一个一个木桶，或者你想象成垃圾分类也可以。

我们拿到一个元素，就判断一下它的特征，或者你想象成这个元素是属于某种垃圾的。然后我们把它保存在对应的桶里，或者说就是把规定的类别的垃圾，扔在对应的垃圾桶里。

那么这个题一下子就解决了，这个题里面，垃圾的类别，就是numRows，也就是行数。从0 到numRows-1。
然后怎么分类垃圾呢，一开始就按顺序：
第一个就是0类，第二个是1类……到了第numRows- 1就是numRows-1类。

到了numRow-1 之后，就是第numRow个了，此时我们再往回数就可以了 －
第numRow个是numRow-2
第numRow+1个是 numRow-3

然后到了第numRow + numRow个，是0类垃圾。此时我们再重新往上分类。如此反复直到我们把字符串中所有的字母都分类完成。

此时，我们再从第0个桶开始按顺序取出字母，然后拼起来，就是答案了～
多么的简单。

所以这道题我觉得还是个挺基础的，也是个挺好的题，应该要记住zigzag都是桶排序～

最后就是我写的代码：

1. public String convert(String s, int numRows) {
   
2.         if(numRows == 1) return s;
   
3.         Map<Integer, String> map = new HashMap<>();
   
4.         char[] sc = s.toCharArray();
   
5.         int currR = 0;
   
6.         boolean up = false;
   
7.         for(int i = 0 ; i < sc.length; i++){
   
8.             String str = map.getOrDefault(currR, "")  + (sc[i] + "");
   
9.             map.put(currR, str);
   
10.             if(up){
    
11.                 currR--;
    
12.                 up = currR == 0 ? false : true;
    
13.             }else{
    
14.                 currR++;
    
15.                 up = currR == numRows - 1 ? true : false;
    
16.             }
    
17.         }
    
18.         
    
19.         StringBuilder sb = new StringBuilder();
    
20.         for(int i = 0; i < numRows; i++){
    
21.             sb.append(map.getOrDefault(i, ""));
    
22.         }
    
23. 
    
24.         return sb.toString();
    
25.     }
    

复制代码

7. Reverse Integer
题目大意
给同一个整数，然后让你给出它每一个位数反转过来的数字，比如12 就是 21。 120 就是 12。注意，若是溢出int的最大或者最小值了，那么就返回0.

题目分析和解答
这个题是一个非常另外的题，因为它不包含任何数据结构的部分。比如什么map, array, 或者树啊，图啊什么的。
这种题我总结为单独的一类 － 纯数学逻辑题。

这种题目的特征就是只给一些数字，然后让你计算。计算过程通常都是纯数学公式的，不需要定义复杂的数据结构。

这种数学题通常不适合作为面试的题，因为它们几乎没有什么计算机语言的运用，就是单纯的数学计算。这道题也是如此，但是我认为这道题无比地重要，因为它包含了一个我认为必须要记住的方法，这个方法在实际工作中非常具有实用性。那就是：
如何在不改变数据类型的情况下，判断某个数字会不会溢出。

这道题的的计算并不难，反转一个数字，步骤就是两个：
先用% 10取出原数字的末尾一位  a ，把新的数字 y , 乘以十再加上这个a,然后再把原数字/10。不停地重复，就得到了原数字的反转数。
比如 原数字是123 。新的数字 是y = 0;
1 先 123 ％ 10 ＝3
2 然后 y * 10 + 3 = 0 * 10 + 3 = 3;
3 再把123 / 10 = 12.

重复1 : 原数字现在是 12 .  12 % 10 = 2
重复2 ：y * 10 + 2 = 3 * 10 + 2 = 32
重复3 ： 12 / 10 = 1

继续重复1到3步骤，最后我们的y就是321。

然后接下来是本题重点，如何判断反转之后的数字溢出了？
若是不直到这个技巧的话，很容就会想到把int变成long去判断。

其实，这个题不同转换为long。甚至题目中强行限制你不允许使用long。必须使用int。
那应该怎么判断呢？

方法也很简单，我们判断它的倒数第二步。
比如，我们直到java 中 int的最大值是2147483647
由于我们是从2开始生成答案的，也就是先生成2，然后生成21，再生成214这样的。

所以到了倒数第二步，答案y若是有溢出的风险，那么它倒数第二部一定比2147483647 / 10 = 214748364更大，或者一样大，但是接下来最后一位大于7。
或者因为2147483647不 整齐，不好理解。

假设我们最大数字是1006。
那么我们判断一个四位数字y是不是大于1006，方法就是
y的前三位大于100，也就是比如假如我们知道y ＝ 200X。那么我们就知道，无论这个X是什么数字，y一定比1000大。
或者我们知道y的前三位是100，也就是y= 100X。此时我们只要判断X是不是 大于6，就可以知道y是不是大于1006了。

这样，我们就解决了溢出问题，所以答案就是：

1. public int reverse(int x) {
   
2.         int y = 0;
   
3.         int sign = x > 0 ? 1 : -1;
   
4.         
   
5.         int t = x > 0 ? x : -x;
   
6.         while(t > 0){
   
7.             int chr = t % 10;
   
8.             t /= 10;
   
9.             
   
10.             if(y > Integer.MAX_VALUE / 10 ||
    
11.               (y == Integer.MAX_VALUE && chr > 7)){
    
12.                 return 0;
    
13.             }
    
14.             y = y * 10 + chr;
    
15.         }
    
16.         
    
17.         return y * sign;
    
18.         
    
19.     }

复制代码