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

adbase

47. Permutations II
这个题比上一个题多了一个有重复数字的情况，所以写法基本一样，就是我们需要处理重复数字。
在顺序没有影响的情况下，我们处理重复数字的套路都是排序，把重复的数字都放在紧邻的位置，然后每次检验数字的时候，都看一眼前面的数字，看看是不是重复的，若是重复的我们就不用再加入答案了。
这道题也一样，只是skip的条件比较难理解，在全排序的模版中，我们建立了一个seen[]数组，记录我们在之前的递归中，已经检查了哪些数字，若是已经检查过了，那么就不用再检查了。也就是seen[i] = true的时候，我们skip这个nums[i]。
但是这里我们要多检查一下，当seen[i] = false的时候，我们还要看看是否有nums[i] == nums[i - 1]，并且seen[i - 1] = false。也就是当前数字是不是重复的，若是重复的，并且前一个数字不能skip，那么我们就不添加当前的nums[i]了。

这里就很难理解了，若是题目是[1,1,2]。难道我们在第二个1的时候，就不添加了吗？
其实不是的，我们第一次添加0位的1的时候，下一次递归，seen［i - 1] ＝ true。所以即使有nums[i] == nums[i - 1]，但是我们依然要处理1号位的1。
那么什么时候我们有ssen[i - 1= = false呢？当然就是0号位的1我们都递归完了，开始下一个1的处理时候。这时候我们从第二个1 开始递归的第一层，然后第二个1里面的for又回取到一次0号位的1。此时，我们注意到就会出现 seen[0] = false。也就是0号位这个1，我们其实已经处理过了，我们的i＝ 1之前的一个重复数字出现了在本次递归没有见过的情况，那么就意味着我们在更之前的某次遍历中，已经处理过以0为根节点的一个路径了，所以我们就把本次的情况剪枝，不用再产生重复的结果了。

这个情况理解清楚之后，我们就会得到正确的代码

class Solution {
List<List<Integer>> rs;
boolean[] seen;
public List<List<Integer>> permuteUnique(int[] nums) {
rs = new ArrayList<>();
seen = new boolean[nums.length];
Arrays.sort(nums);
helper(nums, new ArrayList<>());
return rs;
}
public void helper( int[] nums, List<Integer> curr) {
if(curr.size() == nums.length) {
rs.add(new ArrayList<>(curr));
return;
}
for(int i = 0; i < nums.length; i++) {
if(seen[i]) continue;
if(i > 0 && nums[i] == nums[i - 1] && !seen[i - 1]) {
continue;
}
seen[i] = true;
curr.add(nums[i]);
helper(nums, curr);
curr.remove(curr.size() - 1);
seen[i] = false;
}
}
}

复制代码

adbase

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]。

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

class Solution {
public void rotate(int[][] matrix) {
transposed(matrix);
reverse(matrix);
}
private void transposed(int[][] matrix) {
for(int i = 0; i < matrix.length; i++) {
for(int j = i + 1; j < matrix[0].length; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
}
private void reverse(int[][] matrix) {
for(int i = 0; i < matrix.length; i++) {
for(int j = 0; j < matrix.length / 2; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[i][matrix.length - 1 - j];
matrix[i][matrix.length - 1 - j] = temp;
}
}
}
}

复制代码

adbase

49. Group Anagrams
这个题其实非常简单，就一个考点－怎么样把数组变字符串。
不过这个题还是挺重要的，因为看起来很多难题都是以它为变化的，或者包含它是其中一个步骤。
思路也非常简单，归类数组，归类那就一定是hashmap。桶排序吗。
不过这里的考点是key怎么定义，很容想到，字母相同，顺序不同，那么就按相同的顺序存字母就可以了。那么存呢？
其实知道了也很简单，就是定义一个字典，26个格子，遇到一个单词，就把对应的格子加1。显而易见，只要字符相同，那么无论顺序如何，最后出来的数组就一定是相同的。

但是接下来就是如何把数字变字符串，粗暴的方法是写stringbuilder。若是熟悉类库的还可以用arrays.toString()等方法。
所以这道题其实不是考算法，而是考你对语言使用的熟练度。

代码当然也非常直白了

class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> rs = new ArrayList<>();
if(strs.length == 0) return rs;
Map<String, List<String>> map = new HashMap<>();
for(String s : strs) {
int[] letter = new int[26];
char[] sc = s.toCharArray();
for(char c : sc) {
letter[c - 'a']++;
}
String key = Arrays.toString(letter);
List<String> temp = map.getOrDefault(key, new ArrayList<>());
temp.add(s);
map.put(key, temp);
}
for(String key : map.keySet()) {
rs.add(map.get(key));
}
return rs;
}
}

复制代码

adbase

50. Pow(x, n)
这道题是数学题，我这种人最怕数学题了，只能死记硬背套路。
x的n次方，最直接的方法就是把x乘以n次，当然这个是不行的。我们是要求一个更快的方法。
那么更快的方法有两种，我只理解了一种，面试也够用了……

方法也很弱智
n是偶数 x ^n = x ^ (n/2)  * x ^ (n/2）
n是奇数 x ^n = x ^ (n/2)  * x ^ (n/2）＊ x
什么意思呢？其实说白了，比如 16 = 2 的四次方。那么我们不用计算它的2^4，我只要计算一次2 ^2 ＝ 4 。然后答案就是4 ＊ 4。
也就是我不用把2乘四次，我把2和2乘一次，再把结果跟结果乘一次（4 ＊ 4），我就知道最后的答案了（16）。也就是一共我就乘了二次就得到了答案16，比直接乘四次2少两次，所以更快～

那么这种思路，我们发现其实可以递归地无限拆分n，直到n = 0 ，我们直接返回1。剩下的，我们就看n是计奇数还是偶数，奇数的话就多乘一个底。
这样逻辑就完成了
最后处理一下n是负数的情况，其实也很简单 2 ^ -2 = 1 /4 = 1 / 2 ^ 2。也就是我们把n取正，让后把结果被1除一下，也就是取倒数，就可以了。

这道题其实没有任何编程难度，理解了之后，就是个脑经急转弯……本质就是让你知道，怎么更快的计算n次方，可以少乘几次。当然，计算机中，可以节约时间的话，当然是大大有帮助地。
最后的代码非常简单
class Solution {
public double myPow(double x, int n) {
      if(n == 0) return 1.0;
      if(n == 1) return x;

      if(n > 0) return pow(x, n);
      else return 1.0 / pow(x, n);
}
private double pow(double x, int n) {
      if(n == 0) return 1;

      double y = pow(x, n / 2 );
      if(n % 2 == 0) {
         return y * y;
      }else {
         return y * y * x;
      }
}
}

adbase

50道题感想。
今天为止，刷了大半个月，我刷完了第一页的50道题。

我认为效果的确非常好，这次我逼迫自己用自己话写下解题思路，后来发现很多过看了答案，都不太不理解的题，写到一半就豁然开朗了。
包括难题也是，并且写下思路是非常有利于记忆和复习的。

不过，虽然理解了，但是我今天随机考核一下，发现还是不会做，比如第四题，哈哈哈～
但是，的确有模糊的印象，大概知道是怎么个思路。

所以明天开始，准备花几天时间，复习一下，前面的题。复习就不会写心得了，但是会写一个总结。

adbase

51. N-Queens
51和52的解法是一摸一样的，所以放在一起来写了。
经典的n皇后问题，记得这是大学时第一次学计算机的时候课堂作业。当时完全无法理解递归的说……人也是能继续进步的吧。

这个的题的解法当然就是暴力回溯了，先选一个位置，让后把不能放棋子的格子ban掉，再选下一个格子。直到我们找到一个答案。
这个题的难点在于如何处理ban掉的格子。
很显然，皇后必须不能在同一行，所以，我们其实可以一行一行地看。也就是我们选定了某一个位置摆放皇后，我们只要计算下一行的格子，哪些能摆皇后就可以了。

这么计算的话，我们就不用管往上的格子，因为上面的行我们已经处理过了。只要看左右斜线，和垂直方向三个方向即可。
我的方法就是建三个数组，长度为能。分别记录下一行中，
有哪些格子是处于上面所有行中，皇后们的左斜方向上的，
哪些格子是处于上面所有行中，皇后们的右斜方向上的，
哪些格子是处于上面所有行中，皇后们的垂直方向上的。

显然，每次我们看下一行的时候，对于左斜方向的数列，我们只要把当下这一行所有的禁区，左移一格，然后加上这次摆放皇后位置 i的左侧。即是下一行的左禁区。
同理，右斜数组，就是全部右移一次。垂直就更简单了，不移动。

然后每次，开始校验的一行的时候，我们会跳过三个数列中存储的禁区，若是所有的格子都被ban掉了，那么说明之前皇后的位置选择不对，要回溯到之前的递归行数重新选择一个新的位置。

最后若是我们能走完所有的行数，就可以得到一个解。把它保存在答案里。由于我们是不会重复选择皇后的位置的，所以我们可以保证最后的答案都是不同的，不会出现重复的情况。所以52题要求我们返回答案数量，只要返回解的数量即可。

我的解答就到此为止。但是这道题还有优化的空间，比如我们可以利用二进制的位操作，来代替数组。比如 n = 5。
我们用二进制中的数字0表示可以放皇后，1表示不能放皇后。那么一行的禁区就可以表示位一个1～5位数，
比如 0 ＝ 00000表示都能摆
1 = 00001 表示最右侧的格子不能摆
2 = 00010 表示最右侧的第二个格子不能摆
……
31 ＝ 11111 表示所有格子都不能摆。
所以这相当于，我们用一个数字就能代替一个复杂的数组，知道哪个位置不能摆皇后。并且我们更新这个数字也非常方便，只要分别左移或者右移就可以了。

最后我放出我自己的52题代码，里面已经包含了51的解法，位运算的代码可以参考网上的写法

class Solution {
public int totalNQueens(int n) {
List<List<String>> rs = solveNQueens(n);
return rs.size();
}
List<List<String>> rs = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
if(n == 1){
String[] temp = {"Q"};
rs.add(Arrays.asList(temp));
}
if(n < 3) return rs;
boolean[] left = new boolean[n];
boolean[] right = new boolean[n];
boolean[] ve = new boolean[n];
int[][] m = new int[n][n];
helper(left, right ,ve, 0, n, m);
return rs;
}
private void helper(boolean[] l,
boolean[] r,
boolean[] v,
int deep, int n,
int[][] m) {
if(n == deep) {
List<String> curr = new ArrayList<>();
for(int i = 0 ; i < n; i++) {
StringBuilder sb = new StringBuilder();
for(int j = 0; j < n; j++) {
if(m[i][j] == 1) {
sb.append("Q");
}else sb.append(".");
}
curr.add(sb.toString());
}
rs.add(curr);
}
for(int i = 0; i < n; i++) {
if(l[i] || r[i] || v[i]) continue;
m[deep][i] = 1;
v[i] = true;
boolean[] nl = new boolean[n];
if(i > 0) nl[i - 1] = true;
for(int j = 1; j < n; j++) {
if(l[j]) nl[j - 1] = true;
}
boolean[] nr = new boolean[n];
if(i < n - 1) nr[i + 1] = true;
for(int j = 0; j < n - 1; j++) {
if(r[j]) nr[j + 1] = true;
}
helper(nl, nr, v, deep + 1, n, m);
v[i] = false;
m[deep][i] = 0;
}
}
}

复制代码

adbase

53. Maximum Subarray
这是一道非常好的题，非常适合面试。它从不同角度都能解答，最终可以看出面试者对于算法的理解程度。
题目非常简单，找出总和最大的连续子串。原数组可能有负数。
这个题乍一看是滑动窗口，但是滑动窗口的左右边界讨论有点困难。
然后我们注意到子串的之和，是可以考虑presum来快速计算的。那么题目就变成，找出presum数组中，两个位置之差最大的两个下标，就对应着原数组的左右边界。

此时可以用暴力搜索，也就是对于每一个i，都去看前面的每一个数字，计算一下差值，也就是以它右边界的每一个子串之和，这样就能计算出最大值。
然后再优化，就是我自己写的笨方法，用一个最小堆，这样我们可以立刻得知前面最小的一个数，自然也马上能得到坐标和值，然后再放入新的presum。这样时间复杂度为nlogn因为每次要重新排序。

但是由这道题其实可以更快，那就是用dp。这种思路要求我们开阔一些。之前的堆的方法，我们是检讨每一个数字，把它当作右边界。
这个方向是对，但是可以更优化一步。
因为我们把当前数字 nums[i]作为右边界，找之前左边界那个数算出来的和最大。所以对于下一个数字nums[i + 1]其实可以这么想，若是以nums[i ]为右边界，我们计算出来一个最大值为sum。若是这个sum是负数，那么一定有 sum ＋ nums[i ＋ 1] < nums[i ＋ 1]。
所以，此时，我们知道nums[i + 1］]一定是一个左边界，因为它之前的nums[i]到nums[0]的这个子串，算不出一个正数最大值，还不如从nums[i + 1]重新开始计算。

所以，我们发现每一个数字nums[i]我们考虑要不要把它加入到最后的答案中，只取决于它前面的[0 , i -1]这个子串的最大子串和，所以问题就缩小了规模，这意味着这个题可以使用dp去解答。
事实也的确如此，我们定义一个dp[]数组，每一个dp[i]表示[0 ~ i]的子串，它的最大子串之和是多少。此时就只有两种情况
if dp[i - 1] > 0 : dp[i] = nums[i] + dp[i - 1];
else dp[i] = nums[i]
最后，我们找出dp中，最大的一个数字，就是答案了。

这个问题，还可以继续优化，由于我们根本不要求返回左右边界是什么的。其实dp还是再找右边界。我们连右边界都不需要知道，只要一直算presum。若是发现presum小于0，我们就重新计算，因为此时i 一定是一个右边界，我们不需要记录这个i，只要记录这个sum就可以了。这就是贪心法。

可见，这道题虽然简单，但是其实解法的思想非常深，是一个可以一直追问下去的好题。最后我放出我自己写的dp的代码，贪心法的代码更简单各位可以去网上看。

class Solution {
public int maxSubArray(int[] nums) {
int[] dp = new int[nums.length];
for(int i = 0; i < nums.length; i++) {
if(i > 0 && dp[i - 1] > 0) {
dp[i] = nums[i] + dp[i - 1];
}else dp[i] = nums[i];
}
int rs = Integer.MIN_VALUE;
for(int n : dp) {
rs = Math.max(rs, n);
}
return rs;
}
}

复制代码

adbase

54. Spiral Matrix
这个题出得不好，几乎没有什么算法内容，就是用一个复杂的逻辑，考硬编程水平。
题目要求按照某种规律遍历矩阵，其实就是变种的dfs。所以写法也就是dfs的改进。

每次进入递归，我们就检查是否越界，越界就返回。并且也检查是否已经遇到过此格子，遇到过也返回。
若是通过了越界检查，说明这是一个新的格子，我们直接添加进答案，然后把格子的值设置为101，因为题目说格子值最大是100，我们用101来标记已经看过这个格子了。
之后就是确定方向，先按原来的方向找下一个格子的坐标，然后检查以给，若是下一个格子越界或者已经遇到过了，就转变方向。方向就按左下右上的循环。我们可以用一个int = 0, 1,2,3来标记。
转变方向之后，再找出新的方向的下一个格子，然后进入下一层递归。

这样题目就做完了。
当然本题，不用递归做dfs可以更快，但是写起来太烧脑，非常不直观。我认为此题只要能写出来，就可以达到考核的目的了。况且用递归写，起码证明你懂递归，而递归比会while循环更能证明对语言的理解水平。所以我认为这道题不好，它的最优解，反而并不能证明面试者的实际水平。只能说明这个面试者聪明，或者背答案了。

最后我的代码就是

class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> rs = new ArrayList<>();
helper(rs, 0, 0, 0, matrix);
return rs;
}
private void helper(List<Integer> rs, int currI, int x, int y, int[][] m) {
if(x > m.length - 1 ||
x < 0 ||
y > m[0].length - 1 ||
y < 0 ||
m[x][y] == 101) return;
int n = m[x][y];
rs.add(n);
m[x][y] = 101;
int[] next = update( x, y, currI);
if(next[0] > m.length - 1 ||
next[0] < 0 ||
next[1] > m[0].length - 1 ||
next[1] < 0 ||
m[next[0]][next[1]] == 101) {
currI = currI == 3 ? 0 : currI + 1;
next = update( x, y, currI);
}
helper(rs, currI, next[0], next[1], m);
}
private int[] update(int x, int y, int currI) {
int nextx = x, nexty = y;
if(currI == 0) {
nexty = y + 1;
}else if(currI == 1) {
nextx = x + 1;
}else if(currI == 2) {
nexty = y - 1;
}else if(currI == 3) {
nextx = x - 1;
}
int[] rs = new int[2];
rs[0] = nextx;
rs[1] = nexty;
return rs;
}
}

复制代码

adbase

55. Jump Game
这个题和jump game ii是一样的，但是更简单，那道题要求你返回最少步数。此题干脆就是让你判断能不能走到终点。
此题最佳解法比较容易想到，也就是贪心法。我依次检查每一个格子，看看这个格子最远能走多远，并且我用一个数字记录每一个格子最远值的最大值， max_r = Math.max(i + nums[i]).
若是max_r超过了数组的长度，那么就说明可以走到终点，我们就愉快滴返回true；
反之，若是走着走着，发现max_r < i了。那就说明前面的格子走不到现在的i，那么就返回false；
最后若是for循环能顺利走完，说明是一个特殊情况，也就是前面所有的格子恰好只能走到最后一个格子，那么此时max_r就是最后一个格子的最远距离，我们就判断一下此时mar_r和数组长度的大小，若是能到最后，那么就返回true。反之就返回false。

所以代码就是

class Solution {
public boolean canJump(int[] nums) {
int maxI = 0;
for(int i = 0; i < nums.length; i++) {
if(maxI >= nums.length) return true;
if(maxI < i) return false;
maxI = Math.max(maxI, i + nums[i]);
}
return maxI >= nums.length - 1;
}
}

复制代码

我据的本题没有中等难度，应该属于一个简单题。当然可能因为最优解比较简单，但是若是用dp或者双指针等，反而会难一些，所以才判定为中等了吧。

adbase

56. Merge Intervals 57. Insert Interval
这两个题也放到一起说，因为解法也是一摸一样的。虽然二者都有更快的解法，但是我认为heap的解法足以应付面试了。
合并区间是经典题，我人生中第一次做lc的中等难度就是这道题，哈哈哈。当时研究了好久，完全没有解题思路，后来画图画了半天，也没有写对。想起来物是人非。

这个题经典解法就是用heap，也就是用堆来给每一个区间进行排序，排序的规则是每一个区间的左边从小到大排序。也就是一个最小堆。
然后我们依次从堆中取出区间，每取出一个区间，就把它和前一个区间比较。
比较什么呢？
比较取出来的区间，它和前一个有没有重叠。也就是它的左边，是不是比前一个右边还小 curr[0] <= pre[1];
若是有重叠，那么我们就合并二者，合并的方法，是更新一下前面区间的右边，因为前面区间的左边一定小于现在的区间，我们只要更新右边就可以了。由于重叠方式不同，右边有可能是前一个区间的右边更大，比如 pre = [1, 1000] curr = [2,5] 这样的。
所以我们挑两个区间更大的右边 pre[1] = max(pre[1], curr[1])。
然后我们在答案list中更新pre即可。
若是没有重叠，那么我们直接把当前的区间添加进答案list。

这个题还比较考验对于语言的运用能力，比如如何定义一个最小堆。对于java 来说， lambda 表达式一定要纯熟。
还有就是如何产生int[][]形式的答案，由于最终答案可能会比输入更短，所以一定要用arraylist做过渡，此时你会不会用toArray()，也代表了你对语言的熟悉程度。

然后就是57题，57题其实只要把需要添加进去的新区间和原有的区间，都放入堆当中，就变成了56题。

这两道题都有更优解，也就是用桶排序。可以省去堆的排序时间。有兴趣的可以自己了解一下。
所以我57题最终代码就是

class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
PriorityQueue<int[]> pq= new PriorityQueue<>((a, b) ->{
return a[0] - b[0];
});
pq.offer(newInterval);
for(int[] interval : intervals) {
pq.offer(interval);
}
List<int[]> rs = new ArrayList<>();
rs.add(pq.poll());
while(!pq.isEmpty()) {
int[] curr= pq.poll();
int[] pre = rs.get(rs.size() - 1);
if(pre[1] >= curr[0]) {
pre[1] = Math.max(pre[1], curr[1]);
rs.set(rs.size() - 1, pre);
}else {
rs.add(curr);
}
}
int[][] rsm = new int[rs.size()][2];
return rs.toArray(rsm);
}
}

复制代码

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

浏览过的版块