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

adbase

111. Minimum Depth of Binary Tree
有做上一道的画，这道题其实就已经做完了。不过上一道题是用dfs，其实本题用bfs更直接，包括上一道题。我都练习了一下，本题我就用bfs的代码

class Solution {
public int minDepth(TreeNode root) {
if(root == null ) return 0;
int deep = 1;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()) {
int size = queue.size();
for(int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if(node.right == null && node.left == null) return deep;
if(node.left != null) queue.offer(node.left);
if(node.right != null) queue.offer(node.right);
}
deep++;
}
return deep;
}
}

复制代码

adbase

112 Path Sum
本题比113难度小了很多，不需要回溯，只要dfs就可以了，每次传sum ＝ node.val。然后看看子树是否也是符合条件，递归子树的时候sum = sum - node.val即可。

public boolean hasPathSum(TreeNode root, int targetSum) {
if(root == null) return false;
if(root.left == null && root.right == null
&& targetSum == root.val) return true;
return hasPathSum(root.left, targetSum - root.val)
|| hasPathSum(root.right, targetSum -root.val);
}

复制代码

adbase

113. Path Sum II
这题也很简单，DFS回溯就可以了，注意的是终止条件，不能是null节点才返回，否则会重复添加，因为叶节点有左右两个null节点。
所以必须在叶节点直接判断是否已经符合要求，然后添加进最终答案。
class Solution {
List<List<Integer>> rs = new ArrayList<>();
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
      if(root == null) return rs;
      helper(root, targetSum, 0, new ArrayList<>());
      return rs;
}

private void helper(TreeNode node, int t,int sum, List<Integer> curr) {
      if(node == null) return;

      curr.add(node.val);
      if(node.val + sum == t && node.left == null && node.right == null) {
         rs.add(new ArrayList<>(curr));
      }else{
         helper(node.left, t, sum + node.val, curr);
         helper(node.right, t, sum + node.val, curr);
      }
      curr.remove(curr.size() - 1);
}
}

adbase

109. Convert Sorted List to Binary Search Tree
这个题做法也比较直接，和上一道也是一摸一样的思路。同样，我们还是找中间的值，怎么找呢？一个比较粗暴的做法，就是先扫一遍linkedlist，产生一个sorted array。让后题目就变成108题了，接下来复制108的代码即可。或者也有人存到hashmap里，加速查找过程。
我的办法比较笨，其实有点做复杂了，每次递归，用快慢指针，快指针每次走两步，慢指针每次走一步，最后fast.next == null时候停下来。此时slow就是中间点。
但是马上遇到一个问题怎么拆分左右子树。于是我又搞了一个dummy，slow初始化道dummy, fast还是head。这样我们就等于是找到根节点在链表里的上一个节点，也就是root = slow.next;
然后，我们递归下一层的时候，先递归右子树，右子树的head就是，slow.next.next。然后，我们把slow.next = null。也就是左边断开，这么做的意义在于，下一层递归的时候，我们还是判断快指针走到fast.next =null即可。

然后递归的返回有两个特殊情况, head == null || head.next == null return head; 也就是若是空节点，或者最后断到底了，那么就直接生成treenode返回给上一层递归。

这个写法比较装，其实速度并不快空间复杂度还是O(n)。唯一的好处，可能就是代码量小一点……
class Solution {
public TreeNode sortedListToBST(ListNode head) {
      if(head == null) return null;
      if(head.next == null) return new TreeNode(head.val);

      ListNode fast = head;
      ListNode dummy = new ListNode();
      dummy.next = head;
      ListNode slow = dummy;

      while(fast.next != null) {
         fast = fast.next;
         if(fast.next != null) fast = fast.next;
         slow = slow.next;
      }

      TreeNode root = new TreeNode(slow.next.val);

      root.right = sortedListToBST(slow.next.next);
      slow.next = null;
      root.left = sortedListToBST(head);
      return root;
}
}

adbase

115. Distinct Subsequences
思路，先决定用什么算法。一看，是从n个字符中挑m个，然后问有多少种组合方式，不要求返回具体的组合是什么，只要求计算组合方式的个数。那么一定就是dp题了。

接下来就是如何定义dp。有了72. Edit Distance的经验，我们还是模仿着定义一个二维dp，dp[i][j]表示s从[0,i] , t从[0,j]的时候，他们有多少种匹配的组合方式。

接下来就是搞动态转移方程
还是问自己怎么缩小问题规模。
显然，若是最后一个字符相等，那么一定有dp[i][j] = dp[i -1][j - 1];
因为若是最后一个字符相同，我们就可以去掉这个最后一个字符，只看他们各自前面的字符串有多少种匹配。
但是，同样，我们虽然最后一个字符串是匹配的，但是也许这个字符串是多余的，我不要s中这个字符，还是可以匹配。
比如：s = bcb t = b.
那么dp[3][2]的时候，虽然s最后一个b还是匹配的，但是它前面的字串bc 也可以匹配t = b。也就是dp[i][j] = dp[i - 1][j]。
所以，我们就得出了最后的转移方程
dp[i][j] = s[i] == t[j] : dp[i -1][j - 1] + dp[i - 1][j]。实际上，它的意思就是当最后一个字符匹配的，有两种情况，一种是选取这个字符在组合方式里，一种不选取这个字符在组合方式里。这两种情况相加，就是当下一共有多少种可能性。
然后看不匹配的情况，显然不匹配的时候我们就有 dp[i][j] = dp[i - 1][j]。
也就是说，我们肯定可以不需要这个字符。

接下来看初始化，虽然问题一定是保证有一个字符，但是由于我们要比较少一个，所以我们就引入空字符串的概念，若是两个字符串都是空，那么dp[0][0] = 1.
接下来是最难理解的地方，当t 为空的时候，dp[i][0] = 1。
为什么呢，因为若是我们可以不选取任何s里的字符，那么二者就是匹配的，也就是s也可以选空。所以dp[i][0] = 1;

但是反过来是不行的，也就是dp[0][j] = 0。j > 0 其实，想想也简单，任何时候 i< j都不可能有匹配方法。
然后我们从i = 1, j = 1开始填写矩阵，最后返回dp[lens][lent]即可。

代码并不难：

class Solution {
public int numDistinct(String s, String t) {
int lens = s.length();
int lent = t.length();
int[][] dp = new int[lens + 1][lent + 1];
dp[0][0] = 1;
for(int i = 1; i < lens; i++) {
dp[i][0] = 1;
}
for(int i = 1; i <= lens; i++) {
for(int j = 1; j <= lent; j++) {
if(i < j) {
dp[i][j] = 0;
}else {
if(s.charAt(i - 1) == t.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
}else {
dp[i][j] = dp[i - 1][j];
}
}
}
}
return dp[lens ][lent];
}
}

复制代码

adbase

114. Flatten Binary Tree to Linked List

这道题也有点难度，还是morris遍历。主要还是morris遍历需要理解和熟悉，否则很难做。

morris遍历中，
若是一个节点node没有左子树，那么我们直接遍历它的右子树 node = node.right
若是node有左子树，我们会找每一个节点node的左子树node.left里，最右的一个叶节点rightMost，把这个最右节点的right，链接回node。也就是rightMost.right = node.

然后我们继续遍历node.left。继续重复上面的步骤，我们一定最后转回到node，再次走一次左子树，此时，我再找到node的righMost的时候，我们就可以重新链接树了。

因为此时，node就是我们需要处理的根节点，它的左孩子，就应该是重构后右孩子，也就是右子树的起点，而rightMost，就是重构后，要链过去的终点，我们把node原来的右孩子，接到rightMost.right就可以了。

这个东西最好画画图，若是熟悉morris遍历，应该立刻可以理解

lass Solution {
public void flatten(TreeNode root) {
while(root!= null) {
if(root.left != null) {
TreeNode rightMost = root.left;
while(rightMost.right != null && rightMost.right != root) {
rightMost = rightMost.right;
}
if(rightMost.right != null) {
TreeNode rootRight = root.right;
root.right = root.left;
rightMost.right = rootRight;
root.left = null;
root = root.right;
}else{
rightMost.right = root;
root = root.left;
}
}else {
root = root.right;
}
}
}
}

复制代码

adbase

116 117. Populating Next Right Pointers in Each Node I and II

这两道题做法是一样的，都是用bfs，若是我们每次先把左孩子入队列，再把右孩子入队列。那么下一次输出的时候，就是按照从左到右的顺序。所以我们直接记录一下本层之前一个节点pre，下一次再出一个node，那么就有pre.next = node。

class Solution {
public Node connect(Node root) {
      if(root == null) return root;
      Queue<Node> queue = new LinkedList<>();
      queue.offer(root);

      while(!queue.isEmpty()) {
         int size = queue.size();
         Node pre = queue.peek();
         for(int i = 0; i < size; i++) {
            Node node = queue.poll();
            if(i > 0){
                  pre.next = node;
            }

            if(node.left != null) queue.offer(node.left);
            if(node.right != null) queue.offer(node.right);
            pre = node;
         }
      }
      return root;
}
}

对于116，还有一种dfs的做法，因为是满二叉树，所以我们一定有，node.right = node.next.left。除非node.next == null 。
但是117不能这么做，因为你node.next=null的时候，node.right.next可能还是有值的，因为右侧可能还有更上面一层下来的一个节点。
class Solution {
public Node connect(Node root) {
      if(root == null) return root;

      if(root.left != null && root.right != null)
         root.left.next = root.right;
      if(root.next != null && root.right != null)
         root.right.next = root.next.left;

      connect(root.left);
      connect(root.right);
      return root;
}
}

adbase

120. Triangle
这道题很容易想到的解法就是如同树一样递归。难度在于如何计算左右孩子。
比如当前层数是level，我们在第i个数字，那么递归下两个孩子就是t[level+1][i] 和t[level+1][i + 1]。
每次我们返回给上一层这两个孩子的传上来的值中更小的那个，加上当前数字。
return t[level][i] + min( dfs(t[level+1][i]),  t[level+1][i + 1);

不过这道题还有更好的解法就是dp，只是dp是从下往上计算的。
也就是从三角形的底开始计算的，我们初始化一个二维dp，高是三角形的层数，宽是最后一列也就是三角形的底的宽。

然后我们把dp最后一列，初始化成三角形的底的值。然后从下往上计算，转移方程也非常简单，那就是
dp[i][j] = t[i][j] + min(dp[i - 1][j], dp[i- 1][j + 1]);

其实和dfs算孩子是一样的。
比如例子中
2
  3 4
6 5 7
4 1 8 3
dp的数组就是
  0  1 2 3
0 11
1 9 10
2 7 6 10
3 4 1 8 3
最后我们返回dp[0][0]即可~

class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int height = triangle.size();
int lastRowLen = triangle.get(height - 1).size();
int[][] dp = new int[height][lastRowLen];
for(int i = 0; i < lastRowLen; i++) {
dp[height - 1][i] = triangle.get(height - 1).get(i);
}
for(int i = height - 2; i >= 0; i--) {
for(int j = 0; j <= i; j++) {
dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle.get(i).get(j);
}
}
return dp[0][0];
}
}

复制代码

adbase

Best Time to Buy and Sell Stock I II III IV
这两天研究了一下买卖股票的最佳时机系列。

这个题可能是最难的几个dp之一。用的是三维dp。
dp[i][j][k]表是第i天，交易了第j次之后，当状态是k = 1(持有股票), k = 0（持有现金）时最大的收益是多少。

那么转移方程就是
dp[i][j][0] = max( dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
dp[i][j][1] = max( dp[i - 1][j][0], dp[i - 1][j - 1][1] - prices[i]);

这也很好理解，意思其实就是，
第一行 k = 0 - 要么是今天有现金，要么是一直没买，和上一天持有的现金一样。要么是把股票卖了变成现金，持有现金 + prices[i]。二者取最大值
第二行 k = 1 - 要么是买了股票，交易次数要减-1, 持有现金-prices[i]，要么是昨天买的股票没有卖，今天还握着。二者取最大值。

最后返回dp[len - 1][k][0]，也就是交易k次，最后一天，卖掉股票时，手里的现金还有多少。

代码

class Solution {
public int maxProfit(int[] prices) {
// 3, 3, 5, 0, 0, 3, 1, 4
// 0 1 2 3 4 5 6 7
// dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1]] + prices[i]);
// dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i- 1][j - 1][0] - prices[i]);
int len = prices.length;
int[][][] dp = new int[len][3][2];
for(int i = 0; i < len; i++) {
for(int j = 2; j > 0; j--) {
if(i == 0) {
dp[i][j][0] = 0;
dp[i][j][1] = -prices[i];
}else{
dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i- 1][j - 1][0] - prices[i]);
dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
}
}
}
return dp[len - 1][2][0];
}
}

复制代码

adbase

当然若是无限制买卖还可以用贪心法

class Solution {
public int maxProfit(int[] prices) {
int rs = 0;
int min = Integer.MAX_VALUE;
int max = 0;
for(int num : prices) {
if(num < max) {
rs += max - min;
min = num;
max = num;
}
min = Math.min(min, num);
max = Math.max(max, num);
}
rs += max - min;
return rs;
}
}

复制代码

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

浏览过的版块