面试刷题咯～每天10道～

Leetcode 415 Add String

看到面经有好几次提到这题，就又做了做。
这题还是挺简单的，就是用一个sum 和一个carrier来记录两个数加起来的最低位和进位。
最后如果进位不是0的话，说明我们需要增加长度。
代码如下

1. class Solution {
   
2.     public String addStrings(String num1, String num2) {
   
3.         StringBuilder sb = new StringBuilder();
   
4.         
   
5.         int i = num1.length()-1;
   
6.         int j = num2.length()-1;
   
7.         
   
8.         int sum = 0;
   
9.         int carrier = 0;
   
10.         
    
11.         while(i >= 0  || j >=0 )
    
12.         {
    
13.             int n1 = 0;
    
14.             int n2 = 0;
    
15.             
    
16.             if(i>=0)
    
17.                 n1 = num1.charAt(i) - '0';
    
18.             
    
19.             if(j>=0)
    
20.                 n2 = num2.charAt(j) - '0';
    
21.             
    
22.             sum = carrier + n1 + n2;
    
23.             carrier = sum / 10;
    
24.             sum %= 10;
    
25.             
    
26.             sb.insert(0, sum);
    
27.             i--;
    
28.             j--;
    
29.         }
    
30.         
    
31.         if(carrier != 0)
    
32.             sb.insert(0, carrier);
    
33.         
    
34.         return sb.toString();
    
35.     }
    
36. }

复制代码

感谢大佬carry！

Leetcode 399 Evaluate Division
这道题呢在很多咕咕的面试中出现过变种，比如汇率转换，但本质就是这道题。
我比较喜欢Union Find，并且这道题union find的时间复杂度相比较起DFS来说要小。
首先思路是这样的，我们需要把信息包装成一个node的形式，这样比较方便。node里面包含它的parent和它到parent的距离。
然后我们需要一个hashmap，用来通过string获取我们封装好的node。比如我们在这道题中就是变量“a”,"b"之类的string 来获取相应的node。
接着就是实现unionfind的基本函数find 和 union。
find：output是parent node，input是变量名。首先查看这个变量在不在map里，如果不在，则不存在，就更不用说find parent了。直接return null。如果在map里，检查一下这个node的parent是不是自己，如果是，则直接返回自己。说明这个node是root。
如果不是的话，就再call这个find（node.parent）。这个会返回parent node，再把一开始的node的parent设定为这个找到的parent，然后distance再乘上到parent的distance。
union就更多case了。如果两个变量都没有在map里，就直接创建两个node，然后把第一个变量的node的parent设置为第二个变量node，距离为给定的value。第二个变量的parent设为自己，距离为1.0
然后如果第一个变量在map中，第二个不在，则把第二个变量node的parent设为第一个，然后距离是1/value
如果是第二个变量在map中，第一个不在，则把第一个node的parent设为第二个，距离是value。
最后一种情况是两个变量都在map中，这意味着两个变量是disconnected graph，现在我们要链接起来。首先找到他们分别的root，然后如果这两个root不是一样的话，将第一个parent设为第二个，然后距离设为给定value * 第二个变量node的距离。这里的意思是，首先我们从第一个变量连接到第二个变量，再从第二个变量走到他的parent。这样就相当于完成第一个变量到parent。
最后iterate一遍query，如果都能找到parent，返回第一个变量距离/第二个变量距离。
否则返回-1、

1. class Solution {
   
2.   class Node {
   
3.     public String parent;
   
4.     public double ratio;
   
5.     public Node(String parent, double ratio) {
   
6.       this.parent = parent;
   
7.       this.ratio = ratio;
   
8.     }
   
9.   }
   
10.   
    
11.   class UnionFindSet {
    
12.     private Map<String, Node> parents = new HashMap<>();
    
13.    
    
14.     public Node find(String s) {
    
15.       if (!parents.containsKey(s)) return null;
    
16.       Node n = parents.get(s);
    
17.       if (!n.parent.equals(s)) {
    
18.         Node p = find(n.parent);
    
19.         n.parent = p.parent;
    
20.         n.ratio *= p.ratio;
    
21.       }
    
22.       return n;
    
23.     }
    
24.    
    
25.     public void union(String s, String p, double ratio) {
    
26.       boolean hasS = parents.containsKey(s);
    
27.       boolean hasP = parents.containsKey(p);
    
28.       if (!hasS && !hasP) {
    
29.         parents.put(s, new Node(p, ratio));
    
30.         parents.put(p, new Node(p, 1.0));
    
31.       } else if (!hasP) {
    
32.         parents.put(p, new Node(s, 1.0 / ratio));
    
33.       } else if (!hasS) {
    
34.         parents.put(s, new Node(p, ratio));
    
35.       } else {
    
36.         
    
37.         Node rS = find(s);
    
38.         Node rP = find(p);
    
39.         if(rS != rP)
    
40.         {
    
41.             rS.parent = rP.parent;
    
42.             rS.ratio = ratio * rP.ratio;  
    
43.         }
    
44. 
    
45.       }
    
46.     }
    
47.   }
    
48.   
    
49.   public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
    
50.     UnionFindSet u = new UnionFindSet();
    
51.    
    
52.     for (int i = 0; i < equations.length; ++i)
    
53.       u.union(equations[i][0], equations[i][1], values[i]);
    
54.    
    
55.     double[] ans = new double[queries.length];
    
56.    
    
57.     for (int i = 0; i < queries.length; ++i) {      
    
58.       Node rx = u.find(queries[i][0]);
    
59.       Node ry = u.find(queries[i][1]);
    
60.       if (rx == null || ry == null || !rx.parent.equals(ry.parent))
    
61.         ans[i] = -1.0;        
    
62.       else
    
63.         ans[i] = rx.ratio / ry.ratio;
    
64.     }
    
65.    
    
66.     return ans;
    
67.   }
    
68. }

复制代码

543. Diameter of Binary Tree
这道题最近经常在google面试中出现，且有一定的follow up。
ex：二叉树最长路径（任意节点之间）
Follow up. (1) 如何找到具体最长路径, (2) 如何判断两个图的结构相同.

我在discuss里面发现了一个比较聪明的idea，特此加入我自己的理解。
首先，我们需要相同的一点是，最长的path一定中间有一个节点用到了两个children，如果只有一个children不算。也就是说，更新max的时候我们是Math.max(max, left+right); 最长的path一定是left subtree中path最长 + right subtree最长。
然后了解了这一点之后我们就要去找到最长的subtree。我们从用inorder 来遍历。如果一个node是null 则返回0.这样的话，一个node加入左孩子和右孩子都是0的话，我们还需要加上他自己。其他的我们就要选择左右两边中大的一个。

1. /**
   
2. * Definition for a binary tree node.
   
3. * public class TreeNode {
   
4. *     int val;
   
5. *     TreeNode left;
   
6. *     TreeNode right;
   
7. *     TreeNode(int x) { val = x; }
   
8. * }
   
9. */
   
10. class Solution {
    
11.     int max = 0;
    
12.     public int diameterOfBinaryTree(TreeNode root) {
    
13.         maxDepth(root);
    
14.         return max;   
    
15.     }
    
16.    
    
17.     public int maxDepth(TreeNode root)
    
18.     {
    
19.         if(root == null)
    
20.             return 0;
    
21.         int left = maxDepth(root.left);
    
22.         int right = maxDepth(root.right);
    
23.         max = Math.max(max, left+right);
    
24.         
    
25.         return Math.max(left, right)+1;
    
26.     }
    
27. }

复制代码

Leetcode 637. Average of Levels in Binary Tree
这道题是经典的bfs题。
然后我们用一个queue来存下下一层的node然后计算average。

1. /**
   
2. * Definition for a binary tree node.
   
3. * public class TreeNode {
   
4. *     int val;
   
5. *     TreeNode left;
   
6. *     TreeNode right;
   
7. *     TreeNode(int x) { val = x; }
   
8. * }
   
9. */
   
10. class Solution {
    
11.     public List<Double> averageOfLevels(TreeNode root) {
    
12.         Queue<TreeNode> level = new LinkedList<>();
    
13.         List<Double> res = new ArrayList<>();
    
14. 
    
15.         if(root == null)
    
16.             return res;
    
17.         
    
18.         level.add(root);
    
19.         
    
20.         while(!level.isEmpty())
    
21.         {
    
22.             int len = level.size();
    
23.             double sum = 0;
    
24.             for(int i=0;i<len;i++)
    
25.             {
    
26.                 TreeNode temp = level.poll();
    
27.                 sum+=temp.val;
    
28.                 if(temp.left != null)
    
29.                     level.offer(temp.left);
    
30.                 if(temp.right != null)
    
31.                     level.offer(temp.right);
    
32.             }
    
33.             
    
34.             res.add(sum/len);
    
35.             
    
36.             
    
37.             
    
38.             
    
39.             
    
40.         }
    
41.    
    
42.         return res;
    
43.     }
    
44. }

复制代码

Leetcode 105 Construct Binary Tree From Preorder And Inorder Traversal
这道题有几个重点需要掌握。首先我们知道在preorder中第一个元素是root。然后我们可以在inorder中找到这个相应的值，他左边的就是left children，右边是right children。然后我们可以递归调用一个function来build tree。
我们需要几个节点。1.我们需要知道pre_start 也就是某个tree/subtree 的 root。然后in_start和in_end代表左右孩子的起始点。

1. /**
   
2. * Definition for a binary tree node.
   
3. * public class TreeNode {
   
4. *     int val;
   
5. *     TreeNode left;
   
6. *     TreeNode right;
   
7. *     TreeNode(int x) { val = x; }
   
8. * }
   
9. */
   
10. class Solution {
    
11.     public TreeNode buildTree(int[] preorder, int[] inorder) {
    
12.         if(preorder == null || inorder == null || preorder.length == 0 || inorder.length == 0)
    
13.             return null;
    
14.         return helper(preorder, inorder, 0, 0, inorder.length-1);
    
15.     }
    
16.    
    
17.     public TreeNode helper(int[] preorder, int[] inorder, int pre_start, int in_start,int in_end)
    
18.     {
    
19.         if(pre_start > preorder.length || in_start > in_end)
    
20.             return null;
    
21.         
    
22.         TreeNode cur = new TreeNode(preorder[pre_start]);
    
23.         
    
24.         int index = in_start;
    
25.         
    
26.         while(index <= in_end)
    
27.         {
    
28.             if(inorder[index] == preorder[pre_start])
    
29.                 break;
    
30.             index++;
    
31.         }
    
32.         
    
33.         cur.left = helper(preorder, inorder, pre_start+1, in_start, index-1);
    
34.         cur.right = helper(preorder, inorder, pre_start+(index-in_start+1), index+1, in_end);
    
35.         
    
36.         return cur;
    
37.     }
    
38. }

复制代码

Leetcode 358. Rearrange String k Distance Apart
这道题借用了操作系统里面对于task的一种方式。我们首先运行priority最高的task一段时间，接着再减少这个task的priority，提升其他task priority。如果其他的task priority比目前的高，则允许其他的task。然后循环往复。我们这道题也是这样，我们先把每个letter的频率记录下来，然后因为output和input string的长度一样，我们循环一个input string的长度，在每个位置，考虑两点1：找到频率最大的letter，并且这个我们目前所处的位置比letter的valid位置要大。这里valid是怎么定义的呢，就是能够被允许的位置。比如a出现过了，我们下次出现a的valid位置就是a加上要求separate的距离。找到之后，减低这个letter 的频率 然后更新valid，把这个letter加到output string里面。

1. class Solution {
   
2.     public String rearrangeString(String s, int k) {
   
3.         int[] freq = new int[26];
   
4.         int[] valid = new int[26];
   
5.         
   
6.         for(char c: s.toCharArray())
   
7.         {
   
8.             freq[c-'a']++;
   
9.         }
   
10.         
    
11.         StringBuilder sb = new StringBuilder();
    
12.         
    
13.         for(int i=0;i<s.length();i++)
    
14.         {
    
15.             int candidate = helper(freq, valid, i);
    
16.             if(candidate == -1)
    
17.                 return "";
    
18.             freq[candidate]--;
    
19.             valid[candidate] = i + k;
    
20.             sb.append((char)(candidate+'a'));
    
21.         }
    
22.         return sb.toString();
    
23.     }
    
24.    
    
25.     public int helper(int[] freq, int[] valid, int index)
    
26.     {
    
27.         int max = 0;
    
28.         int candidate = -1;
    
29.         for(int i=0;i<freq.length;i++)
    
30.         {
    
31.             if(freq[i]>max && index>= valid[i])
    
32.             {
    
33.                 max = freq[i];
    
34.                 candidate = i;
    
35.             }
    
36.         }
    
37.         return candidate;
    
38.     }
    
39. }

复制代码

295. Find Median from Data Stream
这道题虽然是标注为hard难度，但是只要想到了一个trick就相当于是easy 难度的了。
首先，如果把一个数insert进一个data structure里，怎么做都是不行的，因为这样涉及到搜索和排序。而其实找到中位数只需要中间的两个数就行。而如果用两个priority queue的话就不一样了，把整个数组分成两半，左半边我们需要最大的数，右半边我们需要最小的数。
这样我们左半边用descending 的priorityqueue，右半边用default的pq。
这样insert是logn，最终结果也可以是O（1）。

1. class MedianFinder {
   
2.     Queue<Integer> left;
   
3.     Queue<Integer> right;
   
4.     /** initialize your data structure here. */
   
5.     public MedianFinder() {
   
6.         left = new PriorityQueue<>(Collections.reverseOrder());
   
7.         right = new PriorityQueue<>();
   
8.         
   
9.     }
   
10.    
    
11.     public void addNum(int num) {
    
12.         left.offer(num);
    
13.         right.offer(left.poll());
    
14.         if(left.size() < right.size())
    
15.             left.offer(right.poll());
    
16.     }
    
17.    
    
18.     public double findMedian() {
    
19.         if(left.size() != right.size())
    
20.             return 1.0*left.peek();
    
21.         else
    
22.             return (left.peek()+right.peek())/2.0;
    
23.     }
    
24. }
    
25. 
    
26. /**
    
27. * Your MedianFinder object will be instantiated and called as such:
    
28. * MedianFinder obj = new MedianFinder();
    
29. * obj.addNum(num);
    
30. * double param_2 = obj.findMedian();
    
31. */

复制代码

Leetcode 198 House Robber
可以用dp的思想去想这道题。
我们在某一个房子前面有两个选择，偷或者不偷。如果偷，那么我的结果就是上一个房子不偷的结果加上这个房子的钱数。如果不偷，则找到之前偷和不偷的最大值。这个过程int array里面所有的都走一遍。

1. class Solution {
   
2.     public int rob(int[] nums) {
   
3.         int rob = 0;
   
4.         int no_rob = 0;
   
5.         for(int num: nums)
   
6.         {
   
7.             int pre = Math.max(rob, no_rob);
   
8.             rob = no_rob + num;
   
9.             no_rob = pre;   
   
10.         }
    
11.         
    
12.         return Math.max(rob,no_rob);
    
13.     }
    
14. }

复制代码

请问这是按照什么顺序做的？