常见的算法思路

P1. 回文字符串判断

描述
这个题目说的是，给你一个字符串，你要判断它是否是回文字符串。字符串里只考虑字母和数字，其它的字符可以无视。另外，对于字母，可以忽略大小写。

比如说，给你的字符串是：

" race a E-car "

只考虑字母数字并且忽略大小写，它是一个回文字符串，因此返回 true。再比如说，给你的字符串是

" race a car "

对比到最后，中间的 e 和 a 不相等，因此不是一个回文字符串，返回 false。

算法思路：
设置两个游标分别指向这个字符串的开尾，如果游标指向非字母或者数字时继续调整游标位置直到指向字母或者数字时对比两个游标所指向位置的字符，如果相等继续执行循环，当不相等时结束循环返回false。如果循环顺利执行完毕，说明是一个回文字符串。这种算法只遍历一次，时间复杂度是O(n)，没有使用额外的空间，空间复杂度为O(1)

代码示例：

public class AlgoCasts {

  /**
  * 判断是否只含有字母数字
  */
  private boolean isAlphanumeric(char c) {
    return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')
      || (c >= '0' && c <= '9');
  }

  /**
  * 忽略字母大小写
  */
  private boolean isEqualIgnoreCase(char a, char b) {
    if (a >= 'A' && a <= 'Z') a += 32;
    if (b >= 'A' && b <= 'Z') b += 32;
    return a == b;
  }

  // Time: O(n), Space: O(1)
  public boolean isPalindrome(String s) {
    if (s == null || s.length() == 0) return true;

    int i = 0, j = s.length() - 1;
    for (; i < j; ++i, --j) {
      while (i < j && !isAlphanumeric(s.charAt(i))) ++i;
      while (i < j && !isAlphanumeric(s.charAt(j))) --j;
      if (i < j && !isEqualIgnoreCase(s.charAt(i), s.charAt(j))) return false;
    }
    return true;
  }

}

P2. 求和为给定值的两个数

描述
这个题目说的是，给你一个整数数组和一个目标值，你要找到数组里两个整数， 它们的和等于目标值。然后返回这两个整数的下标。

比如说给你的整数数组是：

1, 2, 3, 6, 8, 11

目标值是 10。那么，满足条件的两个整数是，2 和 8，它们的和是 10。所以你要返回它们的下标是 1 和 4。

算法思路：
思路1：
暴力破解法，使用两层循环for循环依次取出数组里的两个数，加起来如果等于目标值就返回他们两个的下标。 因为使用了两层for循环所以时间复杂度是O（n^2）。
思路2： 使用一个hash表来存储已经访问过的一个整数，key是这个整数，value是这个整数的位置。当遍历组访问一个数时，用目标值减去访问到的这个数得到一个需要的数，如果这个数在hash表中存在则返回这个整数的下标与当前访问这个数的下标。如果循环结束没有返回则说明没有符合的结果，可以返回一个不合法的结果如[-1, -1]。这种算法的时间复杂度是O(n),空间复杂度是O(n)

public class AlgoCasts {

  // Time: O(n^2), Space: O(1)
  public int[] getTwoNumSumToGivenValueBruteForce(int[] nums, int target) {
    for (int i = 0; i < nums.length; ++i) {
      for (int j = i + 1; j < nums.length; ++j) {
        if (nums[i] + nums[j] == target)
          return new int[]{i, j};
      }
    }
    return new int[]{-1, -1};
  }

  // Time: O(n), Space: O(n)
  public int[] getTwoNumSumToGivenValueHashMap(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; ++i) {
      int numNeeded = target - nums[i];
      if (map.containsKey(numNeeded)) {
        return new int[]{map.get(numNeeded), i};
      }
      map.put(nums[i], i);
    }
    return new int[]{-1, -1};
  }

}

P3. 有序数组中求和为给定值的两个数

描述
这个题目说的是，给你一个整数数组，并且这个数组是按递增排序的，你要找到数组中的两个整数，它们的和等于给定的目标值，然后返回它们的下标。题目假设给你的数组总是有且只有一个解，而且同一个元素不能使用两次。另外，返回结果的下标要从 1 开始。

比如说给你的数组是：

1, 2, 3, 6, 8, 11

目标值是 10。那么，满足条件的两个整数是，2 和 8，它们的和是 10。所以你要返回它们的下标是 [2, 5]。

算法思路：
准备两个游标i和j分别从左右向中间移动，如果i和j指向的两个数和大于目标值，如果j指向的数加上最小的话都大于目标值，所以将j--取小一点的值与i指向的数求和k与目标值比较，如果目标值大于k则将i++取大一点的值再进行比较，依次循环。直到找到等于目标值的值，跳出循环时间复杂度是O(n),没有使用额外的，空间复杂度是O(1)。

public class AlgoCasts {

  // Time: O(n), Space: O(1)
  public int[] getTwoNumSumToGivenValue(int[] numbers, int target) {
    int i = 0, j = numbers.length - 1;
    while (i < j) {
      if (numbers[i] + numbers[j] > target) --j;
      else if (numbers[i] + numbers[j] < target) ++i;
      else return new int[]{i + 1, j + 1};
    }
    return new int[]{-1, -1};
  }

}

P4. 判断二叉树是否对称

描述
这个题目说的是，给你一个二叉树，你要判断它是否沿中轴线对称。

比如说，给你的二叉树是：

     1
   /   \
  2     2
 / \   / \
4   8 8   4

这棵二叉树是沿中轴线对称的，因此要返回 true。如果我去掉最后这个 4：

     1
   /   \
  2     2
 / \   /
4   8 8

就不对称了，这时就要返回 false。

算法思路：
因为在对比过程中，对比的个数是不断增加的，所以需要加入辅助结构如：队列或者栈都可以，这个算法使用的是广度优先遍历的方法。

public class AlgoCasts {

  public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
      val = x;
    }
  }
  /**
   * 对比两棵树是否对称
   * */
  boolean isSymmetric(TreeNode s, TreeNode t) {
    if (s != null && t != null)
      return s.val == t.val &&
        isSymmetric(s.left, t.right) && isSymmetric(s.right, t.left); // 两个树根节点的值是否相等，以及左节点的左子树与右节点的右子树，以及左节点的右子树与右节点的左子树是否相等这三个条件共同决定。
    else return s == null && t == null; // 两个节点都为空也表示对称
  }

  // Time: O(n), Space: O(n)
  public boolean isSymmetricTreeRecursive(TreeNode root) {
    if (root == null) return true; // 如果树为空，返回true
    return isSymmetric(root.left, root.right);// 否则返回根节点左右子树的对称性。
  }

  // Time: O(n), Space: O(n)
  public boolean isSymmetricTreeIterative(TreeNode root) {
    if (root == null) return true; // 如果树为空，返回true
    Stack<TreeNode> stack = new Stack<>(); 
    stack.push(root.left); // 如果非空将根节点的左右子树入栈
    stack.push(root.right);

    while (!stack.empty()) { // 当栈不为空时不断执行以下操作
      TreeNode s = stack.pop(), t = stack.pop(); // 栈顶两个元素出栈
      if (s == null && t == null) continue; // 当它们都为空时表示两个子树对称
      if (s == null || t == null) return false; // 如果一棵为空一棵非空，则不对称
      if (s.val != t.val) return false; // 上面没返回则等树都非空，对比两个节点的值，如果不等则不对称

      // 都没返回说明相等，左节点的左子树与右节点的右子树，以及左节点的右子树与右节点的左子树入栈。
      stack.push(s.left);
      stack.push(t.right);
      stack.push(s.right);
      stack.push(t.left);
    }
    // 如果循环结束还没有提前返回则说明这个树是对称的
    return true;
  }

}

P5. 不用+/-求两数之和

描述
这个题目说的是，给你两个整数，在不使用 +/- 这两个运算符的前提下，求它们的和。

代码

public class AlgoCasts {

  public int getSumRecursive(int a, int b) {
    return b == 0 ? a : getSumRecursive(a^b, (a&b)<<1);
  }

  // Time: O(m), Space: O(1)
  public int getSumIterative(int a, int b) {
    while (b != 0) {
      int sum = a ^ b;
      int carry = (a & b) << 1;
      a = sum;
      b = carry;
    }
    return a;
  }

}

P6. 单身数字

描述 这个题目说的是，给你一个非空的整数数组，这个数组中有一个整数只出现了一次，其它的整数都出现两次，你要找出这个只出现一次的整数。

比如说，给你的数组是：

5, 7, 5, 6, 6

这里 7 只出现了一次，因此你要返回的就是 7。

代码

public class AlgoCasts {

  // Time: O(n), Space: O(1)
  public int singleNumberWithXOR(int[] nums) {
    int result = 0;
    for (int num: nums) result ^= num;
    return result;
  }

  // Time: O(n), Space: O(n)
  public int singleNumberWithSet(int[] nums) {
    Set<Integer> set = new HashSet<>();
    int sum = 0, uniqueSum = 0;
    for (int num: nums) {
      if (!set.contains(num)) {
        uniqueSum += num;
        set.add(num);
      }
      sum += num;
    }
    return 2 * uniqueSum - sum;
  }

}

P7. 行列递增的二维数组搜索

描述 这个题目说的是，给你一个二维数组 matrix，和一个目标值 target。你要在数组里找到这个目标值，然后返回它的行/列下标。如果找不到，则返回 [-1,-1]。

这个数组的每一行都是从左向右递增，每一列都是从上到下递增。和「二维数组的二分搜索」不同，这道题目并不保证每一行的第一个数都比上一行的最后一个数要大。

比如说，给你的二维数组是：

1, 3, 5 2, 4, 6

给你的目标值是 4。目标值 4 在这个数组中，找到后返回它的下标 [1, 1] 即可。

如果给你的目标值是 100，显然它不在这个二维数组中，你要返回 [-1，-1]。

代码

public class AlgoCasts {

  // Time: O(m+n), Space: O(1)
  public int[] searchIn2DArray(int[][] matrix, int target) {
    if (matrix == null || matrix.length == 0 ||
      matrix[0] == null || matrix[0].length == 0)
      return new int[]{-1, -1};

    int m = matrix.length, n = matrix[0].length;
    int i = 0, j = n - 1;
    while (i < m && j >= 0) {
      if (target < matrix[i][j]) --j;
      else if (target > matrix[i][j]) ++i;
      else return new int[]{i, j};
    }
    return new int[]{-1, -1};
  }

}

P8. 判断二叉树是否相同

描述 这个题目说的是，给你两个二叉树，你要判断它们是否相同。这里所谓相同，指的是两棵树结构相同，并且相应节点上的数值相等。

比如说，给你的两棵二叉树都是：

   1          1
  / \        / \
 2   4      2   4

它们的结构相同，相应节点上的值也相等，因此返回 true。 如果另一棵树是：

   1
  / \
 2   5

或

    1
   /
  2
 /
4

两棵树则不相同，返回 false。

代码

public class AlgoCasts {

  public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
      val = x;
    }
  }

  // Time: O(n), Space: O(n)
  public boolean isSameTreeRecursive(TreeNode p, TreeNode q) {
    if (p == null && q == null) return true;
    if (p == null || q == null) return false;
    return p.val == q.val &&
      isSameTreeRecursive(p.left, q.left) &&
      isSameTreeRecursive(p.right, q.right);
  }

  // Time: O(n), Space: O(n)
  public boolean isSameTreeIterative(TreeNode p, TreeNode q) {
    Stack<TreeNode> stack = new Stack<>();
    stack.push(p);
    stack.push(q);

    while (!stack.empty()) {
      TreeNode s = stack.pop(), t = stack.pop();
      if (s == null && t == null) continue;
      if (s == null || t == null) return false;
      if (s.val != t.val) return false;

      stack.push(s.left);
      stack.push(t.left);
      stack.push(s.right);
      stack.push(t.right);
    }

    return true;
  }

}

P9. 反转单链表

描述 这个题目说的是，给你一个单链表，你需要反转它，然后返回。

比如说给你的单链表是：

1 -> 2 -> 3 -> 4 -> 5 -> null

你要返回的反转后的链表是：

5 -> 4 -> 3 -> 2 -> 1 -> null

public class AlgoCasts {

  public class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
      val = x;
    }
  }

  // Time: O(n), Space: O(1)
  public ListNode reverseList(ListNode head) {
    ListNode cur = head, pre = null;
    while (cur != null) {
      ListNode next = cur.next;
      cur.next = pre;
      pre = cur;
      cur = next;
    }
    return pre;
  }

}

P10. 数值的 n 次方

描述 这个题目说的是，你要实现一个函数，用它来计算浮点数的 n 次方。

比如说，给你 2 和 11，你要计算出 2 的 11 次方的结果：

f(2, 11) = 211

代码

public class AlgoCasts {

  // Time: O(n), Space: O(1)
  public double pow(double x, int n) {
    double result = 1;
    long N = Math.abs((long)n);

    for (int i = 0; i < N; ++i)
      result *= x;
    return n < 0 ? 1/result : result;
  }

  // Time: O(log(n)), Space: O(1)
  public double powFast(double x, int n) {
    double result = 1;
    long N = Math.abs((long)n);

    while (N != 0) {
      if ((N & 1) == 1) result *= x;
      x *= x;
      N >>= 1;
    }
    return n < 0 ? 1/result : result;
  }

}

P11. 数组的全排列

描述 这个题目说的是，给你一个整数数组，并且数组中没有重复元素，你要返回这个数组所有可能的排列。

比如说给你的数组是：

0, 1, 2

你要返回的所有排列是：

0, 1, 2
0, 2, 1
1, 0, 2
1, 2, 0
2, 0, 1
2, 1, 0

代码

public class AlgoCasts {

  void permuteRec(List<Integer> nums, int start, List<List<Integer>> result) {
    if (start == nums.size()) {
      result.add(new ArrayList<>(nums));
    } else {
      for (int i = start; i < nums.size(); ++i) {
        Collections.swap(nums, i, start);
        permuteRec(nums, start + 1, result);
        Collections.swap(nums, i, start);
      }
    }
  }

  // Time: O(n*n!), Space: O(n)
  public List<List<Integer>> permute(int[] nums) {
    if (nums == null || nums.length == 0) return new ArrayList<>();
    List<List<Integer>> result = new ArrayList<>();

    List<Integer> list = new ArrayList<>();
    for (int num: nums) list.add(num);

    permuteRec(list, 0, result);
    return result;
  }

}

P12. 回文子串个数

描述 这个题目说的是，给你一个字符串，你要计算出它所包含的回文子串个数。只要起始下标或终止下标不同，即使子串相同，我们也认为是不同的回文子串。

比如说，给你的字符串是：

abc

这个字符串中总共有 3 个回文子串，分别是 a， b 和 c。因此你要返回的个数是 3。

再比如说，给你的字符串是：

aba

这个字符串中总共有 4 个回文子串，分别是 a，b，a，和 aba。因此你要返回的个数是 4。

public class AlgoCasts {

  // Time: O(n^2), Space: O(n^2)
  public int countPalindromicSubstringsDP(String s) {
    if (s == null || s.length() == 0) return 0;
    int n = s.length(), count = 0;
    boolean[][] d = new boolean[n][n];

    for (int i = n - 1; i >= 0; --i) {
      for (int j = i; j < n; ++j) {
        if (i == j) d[i][j] = true;
        else if (i+1 == j) d[i][j] = s.charAt(i) == s.charAt(j);
        else d[i][j] = s.charAt(i) == s.charAt(j) && d[i+1][j-1];

        if (d[i][j]) ++count;
      }
    }

    return count;
  }

  int expand(String s, int left, int right) {
    int count = 0;
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
      ++count;
      --left; ++right;
    }
    return count;
  }

  // Time: O(n^2), Space: O(1)
  public int countPalindromicSubstringsExpand(String s) {
    if (s == null || s.length() == 0) return 0;
    int count = 0;
    for (int i = 0; i < s.length(); ++i) {
      count += expand(s, i, i);
      count += expand(s, i, i+1);
    }
    return count;
  }

}

P13. 回文数字判断

描述

这个题目说的是，给你一个整数，你要判断它是否是一个回文数字。所谓回文数字就是，你正着读和反着读都是同一个数字。

比如，给你的数字是：

12321

无论你从左向右读，还是从右向左读，都是 12321，所以它是一个回文数字，你要返回 true。

再比如说：

-232

你从左向右读是 -232，但从右向左读则是 232-，和 -232 不一样，因此它不是一个回文数字，你要返回 false。

代码

public class AlgoCasts {

  // Time: O(m), Space: O(1)
  public boolean isPalindromeString(int x) {
    String str = String.valueOf(x);
    int i = 0, j = str.length() - 1;
    while (i < j) {
      if (str.charAt(i) != str.charAt(j)) return false;
      ++i;
      --j;
    }
    return true;
  }

  // Time: O(m), Space: O(1)
  public boolean isPalindrome(int x) {
    if (x < 0) return false;
    int tmp = x;
    long y = 0;
    while (tmp != 0) {
      int num = tmp % 10;
      y = y * 10 + num;
      tmp = tmp / 10;
    }
    return y == x;
  }

}

P14. 判断单链表是否为回文链表

描述

这个题目说的是，给你一个单链表表示的数，你要判断它是不是一个回文数字。回文数字就是正着读和反着读都相同的数字。

比如说，给你的链表是：

4 -> 2

它表示 42，反过来是 24，不是一个回文数字，因此你要返回 false。

再比如说，给你的链表是：

4 -> 2 -> 2 -> 4

它表示 4224，反过来也是 4224，它是一个回文数字，因此你要返回 true。

public class AlgoCasts {

  public class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
      val = x;
    }
  }

  // Time: O(n), Space: O(n)
  public boolean isPalindromeUsingStack(ListNode head) {
    Stack<Integer> s = new Stack<>();
    for (ListNode p = head; p != null; p = p.next)
      s.push(p.val);

    for (ListNode p = head; p != null; p = p.next)
      if (p.val != s.pop())
        return false;

    return true;
  }

  // Time: O(n), Space: O(1)
  public boolean isPalindromeReverseList(ListNode head) {
    int len = 0;
    for (ListNode p = head; p != null; p = p.next, ++len);

    // reverse half list
    ListNode cur = head, pre = null;
    for (int i = 0; i < len / 2; ++i) {
      ListNode next = cur.next;
      cur.next = pre;
      pre = cur;
      cur = next;
    }

    if (len % 2 == 1) cur = cur.next;
    for (; pre != null && cur != null; pre = pre.next, cur = cur.next) {
      if (pre.val != cur.val) return false;
    }
    return true;
  }

}

P15. 缺失的数字

描述 这个题目说的是，从 0 到 n 这 n+1 个整数中去掉一个，然后把剩下的 n 个整数放进一个长度为 n 的数组，给你这个数组，你要找到那个去掉的整数。

比如说，给你的数组是：

4, 1, 0, 2

这里的数组长度是 4，说明这是从 0 到 4 中去掉一个数字后形成的数组。数组中缺失的数字是 3，因此我们要返回 3。

代码

public class AlgoCasts {

  // Time: O(n), Space: O(1)
  public int missingNumber(int[] nums) {
    int n = nums.length, result = n;
    for (int i = 0; i < n; ++i) result = result ^ i ^ nums[i];
    return result;
  }

}

P16. 二叉树的最小深度

描述 这个题目说的是，给你一棵二叉树，你要找到从根节点到最近的叶子节点的深度。

比如说，给你的二叉树是：

     1
   /   \
  2     4
       / \
      8  16

这棵树有 3 个叶子节点，分别是 2，8，16。最近的叶子节点是 2，根节点到 2 共有两个节点，因此最小深度是 2。

再比如说，给你的二叉树是：

  1
   \
    2
     \
      4

这棵树唯一的叶子节点是 4，根节点到它共有 3 个节点，因此最小深度是 3。

代码

public class AlgoCasts {

  public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
      val = x;
    }
  }

  // Time: O(n), Space: (n)
  public int minDepth(TreeNode root) {
    if (root == null) return 0;
    if (root.left == null && root.right == null) return 1;
    if (root.left == null) return minDepth(root.right) + 1;
    if (root.right == null) return minDepth(root.left) + 1;
    return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
  }

  // Time: O(n), Space: O(n)
  public int minDepthIterative(TreeNode root) {
    if (root == null) return 0;
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);
    int depth = 1;

    while (!q.isEmpty()) {
      int size = q.size();
      for (int i = 0; i < size; ++i) {
        TreeNode s = q.poll();
        if (s.left == null && s.right == null) return depth;
        if (s.left != null) q.add(s.left);
        if (s.right != null) q.add(s.right);
      }
      ++depth;
    }

    return -1;
  }

}

P17. 带有 min 函数的栈

描述 这个题目说的是，你要实现一个栈，除了提供 push，pop，top 等常用函数，还需要提供一个函数在 O(1) 时间内取得这个栈里的最小元素。

代码

public class AlgoCasts {

  class MinStackWithTwoStack {

    private Stack<Integer> stack = new Stack<>();
    private Stack<Integer> min = new Stack<>();

    public void push(int x) {
      stack.push(x);
      if (min.isEmpty() || x <= getMin()) min.push(x);
    }

    public void pop() {
      if (stack.peek() == getMin()) min.pop();
      stack.pop();
    }

    public int top() {
      return stack.peek();
    }

    public int getMin() {
      return min.peek();
    }
  }

  class MinStackWithLinkedList {

    private class Node {
      int val;
      Node next;

      Node(int val, Node next) {
        this.val = val;
        this.next = next;
      }
    }

    private Node head = null;
    private int min = Integer.MAX_VALUE;

    public void push(int x) {
      if (x <= min) {
        head = new Node(min, head);
        min = x;
      }
      head = new Node(x, head);
    }

    public void pop() {
      if (head.val == min) {
        min = head.next.val;
        head = head.next.next;
      } else {
        head = head.next;
      }
    }

    public int top() {
      return head.val;
    }

    public int getMin() {
      return min;
    }
  }

}

P18. 合并两个有序链表

描述 这个题目说的是，给你两个递增排序的链表，你要把它们合成一个链表，并且保持递增排序。另外要求，新链表上的节点使用的就是旧的两个链表上的节点，不能创建新节点。

比如说，给你的两个链表 L1 和 L2，分别是：

L1: 1 -> 3

L2: 2 -> 4 -> 6

合并后的链表就是：

1 -> 2 -> 3 -> 4 -> 6

代码

public class AlgoCasts {

  public class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
      val = x;
    }
  }

  // Time: O(m+n), Space: O(1)
  public ListNode mergeTwoSortedLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0), p = dummy;

    while (l1 != null && l2 != null) {
      if (l1.val < l2.val) {
        p.next = l1;
        l1 = l1.next;
      } else {
        p.next = l2;
        l2 = l2.next;
      }
      p = p.next;
    }

    if (l1 != null) p.next = l1;
    if (l2 != null) p.next = l2;
    return dummy.next;
  }

}

P19. 合并两个有序数组

描述 这个题目说的是，给你两个递增排序的数组，你要把第二个数组合并到第一个，并使其仍然保持递增排序。两个数组中的元素个数会显式地给出，并且第一个数组的大小可以容纳下两个数组中所有的元素。

比如说给你的两个数组是：

2, 4, _, _ 1, 3

它们都有 2 个元素。并且第一个数组后面有足够的空间来填充第二个数组。把第二个数组合并到第一个数组后，得到的是：

1, 2, 3, 4 代码

public class AlgoCasts {

  // Time: O(m+n), Space: O(1)
  public void mergeTwoSortedArray(int[] nums1, int m, int[] nums2, int n) {
    int i = m - 1, j = n - 1, k = m + n - 1;
    while (i >= 0 && j >= 0) {
      if (nums2[j] > nums1[i])
        nums1[k--] = nums2[j--];
      else
        nums1[k--] = nums1[i--];
    }
    while (j >= 0) nums1[k--] = nums2[j--];
  }

}

P20. 求两个有序数组的中位数

描述 这个题目说的是，给你两个排好序的整数数组 nums1 和 nums2，假设数组是以递增排序的，数组的大小分别是 m 和 n。你要找到这两个数组的中位数。要求算法的时间复杂度是 O(log(m+n))。

这里两个数组中位数的意思是，两个数组合到一起排序后，位于中间的那个数，如果一共有偶数个，则是位于中间的两个数的平均数。

比如说，给你的两个数组是：

1, 3 2

它们放在一起排序后是：

1, 2, 3

所以中位数就是 2。

再比如说，给你的两个数组是：

1, 3 2, 4

它们放在一起排序后是：

1, 2, 3, 4

所以中位数就是 (2 + 3) / 2 = 2.5。 代码

public class AlgoCasts {

  public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int total = nums1.length + nums2.length;
    if ((total & 1) == 1) {
      return findKthSmallestInSortedArrays(nums1, nums2, total / 2 + 1);
    } else {
      double a = findKthSmallestInSortedArrays(nums1, nums2, total / 2);
      double b = findKthSmallestInSortedArrays(nums1, nums2, total / 2 + 1);
      return (a + b) / 2;
    }
  }

  // Time: O(log(k)) <= O(log(m+n)), Space: O(1)
  public double findKthSmallestInSortedArrays(int[] nums1, int[] nums2, int k) {
    int len1 = nums1.length, len2 = nums2.length, base1 = 0, base2 = 0;
    while (true) {
      if (len1 == 0) return nums2[base2 + k - 1];
      if (len2 == 0) return nums1[base1 + k - 1];
      if (k == 1) return Math.min(nums1[base1], nums2[base2]);

      int i = Math.min(k / 2, len1);
      int j = Math.min(k - i, len2);
      int a = nums1[base1 + i - 1], b = nums2[base2 + j - 1];

      if (i + j == k && a == b) return a;

      if (a <= b) {
        base1 += i;
        len1 -= i;
        k -= i;
      }
      if (a >= b) {
        base2 += j;
        len2 -= j;
        k -= j;
      }
    }
  }

}

P21. 连续子序列的最大和

描述
这个题目说的是，给你一个非空整数数组，你要找到和最大的连续子序列，然后返回它的和。

比如说，给你的数组 a 是：

2, -8, 3, -2, 4, -10

和最大的连续子序列是 3, -2, 4, 他们的和是 5。

算法思路： 定义一个变量用于存放最大和，再用一个变量存放当前的序列和，从头到尾依次遍历。遍历前先将第一个元素做为最大和，依次往下相加，如果前面累加的和小于等于0，重新开始一个子序列，当前和更新为当前的元素值，否则子序列继续相加，每次子序列更新后，都要更新最大值，以此记录最大值

代码

public class AlgoCasts {

  // Time: O(n), Space: O(1)
  public int maxSumOfSubArray(int[] nums) {
    int max = Integer.MIN_VALUE, cur = 0;

    for (int i = 0; i < nums.length; ++i) {
      cur = cur <= 0 ? nums[i] : (cur + nums[i]);
      max = Math.max(max, cur);
    }

    return max;
  }

}

P22. 二叉树的最大深度

描述 这个题目说的是，给你一棵二叉树，你要找到从根节点到最远叶子节点的深度。

比如说，给你的二叉树是

    1
  /   \
 2     4
      / \
     8  16

这棵树有 3 个叶子节点，分别是 2，8，16。最远的叶子节点是 8 和 16，根节点到 8 或 16 都有 3 个节点，因此最大深度是 3。

代码

public class AlgoCasts {

  public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
      val = x;
    }
  }

  // Time: O(n), Space: (n)
  public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
  }

  // Time: O(n), Space: O(n)
  public int maxDepthIterative(TreeNode root) {
    if (root == null) return 0;
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);
    int depth = 0;

    while (!q.isEmpty()) {
      int size = q.size();
      for (int i = 0; i < size; ++i) {
        TreeNode s = q.poll();
        if (s.left != null) q.add(s.left);
        if (s.right != null) q.add(s.right);
      }
      ++depth;
    }

    return depth;
  }

}

P23. 数组中超过一半的数字

描述 这个题目说的是，给你一个数组，里面有一个数字出现的次数超过了一半，你要找到这个数字并返回。

比如说，给你的数组是

1, 3, 3, 1, 3, 1, 1

这个数组的长度是 7，这里我们只考虑整数除法，长度 7 除以 2 是 3。数组里面 1 出现了 4 次，超过了一半的数量 3，因此你要返回的就是 1。

代码

public class AlgoCasts {

  // Time: O(n), Space: O(n)
  public int getMajorityWithHashMap(int[] nums) {
    Map<Integer, Integer> map = new HashMap<>();
    int maxNum = 0, maxCount = 0;
    for (int num: nums) {
      int newCnt = map.getOrDefault(num, 0) + 1;
      map.put(num, newCnt);
      if (newCnt > maxCount) {
        maxCount = newCnt;
        maxNum = num;
      }
    }
    return maxNum;
  }

  // Time: O(n), Space: O(1)
  public int getMajority(int[] nums) {
    int num = nums[0], count = 1;
    for (int i = 1; i < nums.length; ++i) {
      if (count == 0) {
        num = nums[i];
        count = 1;
      } else if (nums[i] == num) {
        ++count;
      } else --count;
    }
    return num;
  }

}

P24. 实现 LRU 缓存

描述 这个题目说的是，你要实现一个 LRU 缓存，提供 get 和 put 两个操作，并且要求两个操作的时间复杂度都是 O(1)。另外为了简单起见，在这个题目中，key 和 value 都是整数值，并且 value 只为正整数。因此在 get 操作中，当 key 不存在时，返回 -1 即可。

代码

public class AlgoCasts {

  public class LRUCache {

    private class Node {
      int key, val;
      Node prev, next;

      Node(int key, int val, Node prev, Node next) {
        this.key = key;
        this.val = val;
        this.prev = prev;
        this.next = next;
      }
    }

    private Node head = new Node(-1, -1, null, null);
    private Map<Integer, Node> map = new HashMap<>();

    private void move2Head(Node cur) {
      if (cur == head) {
        head = head.prev;
        return;
      }
      // detach
      cur.prev.next = cur.next;
      cur.next.prev = cur.prev;
      // attach
      cur.next = head.next;
      cur.next.prev = cur;
      head.next = cur;
      cur.prev = head;
    }

    public LRUCache(int capacity) {
      Node cur = head;
      for (int i = 0; i < capacity-1; ++i) {
        cur.next = new Node(-1, -1, cur, null);
        cur = cur.next;
      }
      cur.next = head;
      head.prev = cur;
    }

    public int get(int key) {
      if (!map.containsKey(key)) return -1;
      Node cur = map.get(key);
      move2Head(cur);
      return cur.val;
    }


    public void put(int key, int value) {
      if (map.containsKey(key)) {
        Node cur = map.get(key);
        cur.val = value;
        move2Head(cur);
      } else {
        if (head.val != -1) map.remove(head.key);
        head.key = key;
        head.val = value;
        map.put(key, head);
        head = head.prev;
      }
    }
  }

}

P25. 没有重复字符的最长子串长度

描述 这个题目说的是，给你一个字符串，你要找到没有重复字符的最长子串，然后返回它的长度。

比如说给你的字符串 s 是：

abcabcbb

没有重复字符的最长子串是 abc，这里再往下的字符是 a，和前面这个 a 重复了。

后面满足条件的子串还有 bca，cab，abc 等，不过它们的长度都是 3 ，因此返回的长度为 3。

再比如说 ddd，没有重复字符的最长子串就是一个 d，因此你要返回的长度是 1。

代码

public class AlgoCasts {

  // Time: O(n), Space: O(m), m 是字符集大小
  public int lengthOfLongestSubstring2N(String s) {
    int[] counts = new int[256];
    int i = 0, j = 0, maxLen = 0;
    for (; i < s.length(); ++i) {
      for (; j < s.length(); ++j) {
        if (counts[s.charAt(j)] != 0) break;
        counts[s.charAt(j)] += 1;
      }
      maxLen = Math.max(maxLen, j - i); // j - i is current length
      counts[s.charAt(i)] -= 1;
    }
    return maxLen;
  }

  // Time: O(n), Space: O(m)，m 是字符集大小
  public int lengthOfLongestSubstring1N(String s) {
    int[] index = new int[256];
    Arrays.fill(index, -1);
    int maxLen = 0;
    for (int i=0, j=0; j < s.length(); ++j) {
      i = Math.max(index[s.charAt(j)] + 1, i);
      maxLen = Math.max(maxLen, j - i + 1);
      index[s.charAt(j)] = j;
    }
    return maxLen;
  }

}

P26. 最长回文子串

描述 这个题目说的是，给你一个字符串，你要在它所有的回文子串中，找到长度最长的子串，并返回它。

比如说，给你的字符串是：

abcbab

你要返回的最长回文子串是：

abcba

代码

public class AlgoCasts {

  // Time: O(n^2), Space: O(n^2)
  public String longestPalindromeDP(String s) {
    if (s == null || s.length() == 0) return "";
    int n = s.length(), start = 0, maxLen = 0;
    boolean[][] d = new boolean[n][n];

    for (int i = n - 1; i >= 0; --i) {
      for (int j = i; j < n; ++j) {
        if (i == j) d[i][j] = true;
        else if (i+1 == j) d[i][j] = s.charAt(i) == s.charAt(j);
        else d[i][j] = s.charAt(i) == s.charAt(j) && d[i+1][j-1];

        if (d[i][j] && (j-i+1) > maxLen) {
          start = i;
          maxLen = j - i + 1;
        }
      }
    }

    return s.substring(start, start+maxLen);
  }

  int expand(String s, int left, int right) {
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
      --left; ++right;
    }
    // (right-1) - (left+1) + 1
    return right - left - 1;
  }

  // Time: O(n^2), Space: O(1)
  public String longestPalindromeExpand(String s) {
    if (s == null || s.length() == 0) return "";
    int start = 0, maxLen = 0;
    for (int i = 0; i < s.length(); ++i) {
      int len1 = expand(s, i, i);
      int len2 = expand(s, i, i+1);
      int len = Math.max(len1, len2);
      if (len > maxLen) {
        start = i - (len-1)/2;
        maxLen = len;
      }
    }
    return s.substring(start, start+maxLen);
  }

}

P27. 判断单链表是否有环

描述 这个题目说的是，给你一个单链表，你要判断它是否会形成环，也就是链表的最后一个节点指向了前面一个已经存在的节点。

代码

public class AlgoCasts {

  public class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
      val = x;
    }
  }

  // Time: O(n), Space: O(n)
  public boolean hasCycleWithHashSet(ListNode head) {
    Set<ListNode> set = new HashSet<>();
    for (ListNode p = head; p != null; p = p.next) {
      if (set.contains(p)) return true;
      set.add(p);
    }
    return false;
  }

  // Time: O(n), Space: O(1)
  public boolean hasCycleWithTwoPointer(ListNode head) {
    ListNode fast = head, slow = head;
    while (fast != null && fast.next != null) {
      fast = fast.next.next;
      slow = slow.next;
      if (fast == slow) return true;
    }
    return false;
  }

}

P28. 链表的相交节点

描述 这个题目说的是，给你两个单链表，你要找到它们相交的第一个节点。如果两个链表没有相交，则返回空指针。假设链表无环，并且你不能改变它的原始结构。另外要求算法是线性时间复杂度，空间复杂度要求是 O(1)。

比如说，两条链表分别是：

A:     1 -> 2
              \
               6 -> 7 -> null
              /
B: 3 -> 4 -> 5

你要返回的是 6 这个节点。

代码

public class AlgoCasts {

  public class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
      val = x;
    }
  }

  // Time: O(m+n), Space: O(1)
  public ListNode getIntersectionNodeWithoutLen(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;
    ListNode p = headA, q = headB;
    while (p != q) {
      p = p == null ? headB : p.next;
      q = q == null ? headA : q.next;
    }
    return p;
  }

  // Time: O(m+n), Space: O(1)
  public ListNode getIntersectionNodeWithLen(ListNode headA, ListNode headB) {
    int lenA = 0, lenB = 0;
    for (ListNode p = headA; p != null; p = p.next, ++lenA);
    for (ListNode p = headB; p != null; p = p.next, ++lenB);
    ListNode p = headA, q = headB;
    if (lenA > lenB)
      for (int i = 0; i < lenA - lenB; ++i) p = p.next;
    else
      for (int i = 0; i < lenB - lenA; ++i) q = q.next;
    while (p != q) {
      p = p.next;
      q = q.next;
    }
    return p;
  }

}

P29. 括号的合法排列

描述 这个题目说的是，给你 n 对括号，你要返回这 n 对括号的所有合法排列方式。

比如说，n 等于 3 时，合法的排列有 5 个：

 ((()))
 (()())
 (())()
 ()(())
 ()()()

代码

public class AlgoCasts {

  private void generate(List<String> result, String str, int left, int right) {
    if (left == 0 && right == 0) {
      result.add(str);
    } else {
      if (left > 0) generate(result, str + '(', left - 1, right);
      if (right > left) generate(result, str + ')', left, right - 1);
    }
  }

  // Time: O(4^n / sqrt(n)), Space: O(n)
  public List<String> generateParentheses(int n) {
    if (n <= 0) return new ArrayList<>();
    List<String> result = new ArrayList<>();
    generate(result, "", n, n);
    return result;
  }

  // Time: O(4^n / n*sqrt(n)), Space: O(4^n / n*sqrt(n))
  public List<String> generateParenthesesDP(int n) {
    if (n <= 0) return new ArrayList<>();
    List<List<String>> d = new ArrayList<>(n+1);
    for (int i = 0; i < n+1; ++i) d.add(new ArrayList<>());
    d.get(0).add("");
    for (int i = 1; i < n+1; ++i)
      for (int j = 0; j < i; ++j)
        for (String left: d.get(j))
          for (String right: d.get(i-j-1))
            d.get(i).add('(' + left + ')' + right);

    return d.get(n);
  }

}

P30. 编辑距离

描述 这个题目说的是，给你两个字符串，你要求出由其中一个字符串转成另一个所需要的最少编辑操作次数。允许的操作有 3 种，分别是：替换一个字符，插入一个字符和删除一个字符。

比如说，给你的两个字符串是 car 和 ba。

s1: car
s2: ba

你要把 car 转成 ba，需要先把 c 替换成 b，然后再删除 r。总共操作 2 次，因此它们的编辑距离是 2。

代码

public class AlgoCasts {

  private int min(int a, int b, int c) {
    return Math.min(a, Math.min(b, c));
  }

  // Time: O(m*n), Space: O(m*n)
  public int editDistance(String s, String t) {
    if (s == null || t == null) return 0;

    int m = s.length() + 1, n = t.length() + 1;
    int[][] d = new int[m][n];

    for (int i = 0; i < m; ++i)
      d[i][0] = i;
    for (int j = 0; j < n; ++j)
      d[0][j] = j;

    for (int i = 1; i < m; ++i) {
      for (int j = 1; j < n; ++j) {
        if (s.charAt(i-1) == t.charAt(j-1)) {
          d[i][j] = d[i-1][j-1];
        } else {
          d[i][j] = min(d[i-1][j-1], d[i-1][j], d[i][j-1]) + 1;
        }
      }
    }

    return d[m-1][n-1];
  }

  // Time: O(m*n), Space: O(n)
  public int editDistance1dArray(String s, String t) {
    if (s == null || t == null) return 0;

    int m = s.length() + 1, n = t.length() + 1;
    int[] d = new int[n];

    for (int j = 0; j < n; ++j)
      d[j] = j;

    for (int i = 1; i < m; ++i) {
      int pre = d[0];
      d[0] = i;
      for (int j = 1; j < n; ++j) {
        int tmp = d[j];
        if (s.charAt(i-1) == t.charAt(j-1)) {
          d[j] = pre;
        } else {
          d[j] = min(pre, d[j], d[j-1]) + 1;
        }
        pre = tmp;
      }
    }
    return d[n-1];
  }

}

P31. 容纳最多水的凹槽容量

描述 这个题目说的是，给你一个非负整数数组，数组中的数字表示高度值，在平面坐标画出来后，连同 X 轴一起，会形成许多的凹槽。你要找到两个高度值，使其形成的凹槽所能容纳的水最多。最后返回容纳的水量。

代码

public class AlgoCasts {

  // Time: O(n), Space: O(1)
  public int maxWater(int[] height) {
    int max = 0;
    int i = 0, j = height.length - 1;

    while (i < j) {
      int cur = Math.min(height[i], height[j]) * (j - i);
      max = Math.max(max, cur);
      if (height[i] < height[j]) ++i;
      else --j;
    }

    return max;
  }

}

P32. 爬楼梯方法数

描述 这个题目说的是，给你一个 n 阶的楼梯，每次你可以爬 1 阶或 2 阶，你要求出爬完这个楼梯有多少种不同的方法。

比如说，楼梯只有 1 阶，显然你只有一种爬法，就是爬 1 阶，然后到顶。

再比如说，楼梯有 2 阶，那么你可以用两次 1 阶爬到顶，也可以用一次 2 阶爬到顶。共 2 种爬法。

代码

public class AlgoCasts {

  public int climbstairsRecursive(int n) {
    if (n < 2) return 1;
    return climbstairsRecursive(n-1) + climbstairsRecursive(n-2);
  }

  // Time: O(n), Space: O(1)
  public int climbstairsIterative(int n) {
    int first = 1, second = 1;

    for (int i = 1; i < n; ++i) {
      int third = first + second;
      first = second;
      second = third;
    }

    return second;
  }

}

P33. 二叉树的层序遍历

描述 这个题目说的是，给你一棵二叉树，要求你从根节点到叶子节点一层一层地对其进行访问，对于每一层的节点，则是从左向右进行访问。将访问的结果以二维数组返回。

比如说，给你的二叉树是：

     1
   /   \
  2     4
       / \
      8  16

它的层序遍历结果是：

[
 [1],
 [2, 4],
 [8, 16]
]

代码

public class AlgoCasts {

  public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
      val = x;
    }
  }

  // Time: O(n), Space: O(n)
  public List<List<Integer>> levelOrderTraversal(TreeNode root) {
    if (root == null) return new ArrayList<>();
    List<List<Integer>> result = new ArrayList<>();
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);

    while (!q.isEmpty()) {
      List<Integer> elem = new ArrayList<>();
      int size = q.size();
      for (int i = 0; i < size; ++i) {
        TreeNode s = q.poll();
        elem.add(s.val);
        if (s.left != null) q.add(s.left);
        if (s.right != null) q.add(s.right);
      }
      result.add(elem);
    }

    return result;
  }

}

P34. 二叉树的逆层序遍历

描述 这个题目说的是，给你一棵二叉树，要求你从叶子节点到根节点一层一层地对其进行访问，对于每一层的节点，则是从左向右进行访问。将访问的结果以二维数组返回。

这道题目和二叉树层序遍历的唯一区别是，它是从下向上一层一层去访问的。

比如说，给你的二叉树是：

     1
   /   \
  2     4
       / \
      8  16

它的逆层序遍历结果是：

[
 [8, 16]，
 [2, 4],
 [1],
]

代码

public class AlgoCasts {

  public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
      val = x;
    }
  }

  // Time: O(n), Space: O(n)
  public List<List<Integer>> levelOrderTraversalFromBottom(TreeNode root) {
    if (root == null) return new ArrayList<>();
    List<List<Integer>> result = new ArrayList<>();
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);

    while (!q.isEmpty()) {
      List<Integer> elem = new ArrayList<>();
      int size = q.size();
      for (int i = 0; i < size; ++i) {
        TreeNode s = q.poll();
        elem.add(s.val);
        if (s.left != null) q.add(s.left);
        if (s.right != null) q.add(s.right);
      }
      result.add(elem);
    }

    for (int i = 0; i < result.size()/2; ++i) {
      int j = result.size() - 1 - i;
      List<Integer> tmp = result.get(j);
      result.set(j, result.get(i));
      result.set(i, tmp);
    }
    return result;
  }

}

P35. 二叉树中序遍历

描述 这个题目说的是，给你一个二叉树，你要返回一个数组，表示二叉树中序遍历的结果。

比如说，给你的二叉树是：

     1
   /   \
  2     3
   \
    4
   /
  5

你要返回的中序遍历结果是：2, 5, 4, 1, 3

代码

public class AlgoCasts {

  public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
      val = x;
    }
  }

  // Time: O(n). Space: O(n)
  public List<Integer> inorderTraversalRecursive(TreeNode root) {
    if (root == null) return new ArrayList<>();

    List<Integer> left = inorderTraversalRecursive(root.left);
    List<Integer> right = inorderTraversalRecursive(root.right);
    left.add(root.val);
    left.addAll(right);
    return left;
  }

  // Time: O(n). Space: O(n)
  public List<Integer> inorderTraversalIterative(TreeNode root) {
    Stack<TreeNode> s = new Stack<>();
    List<Integer> result = new ArrayList<>();

    while (root != null || !s.empty()) {
      while (root != null) {
        s.push(root);
        root = root.left;
      }
      root = s.pop();
      result.add(root.val);
      root = root.right;
    }

    return result;
  }

}

P36. 二分搜索

描述
这个题目说的是，给你一个递增排序的整数数组 nums，和一个目标值 target。你要在数组里找到 target，然后返回它的下标。如果找不到则返回 -1。

比如说，给你的数组是：

-2, 0, 2, 4, 5, 8, 9

给你的目标值是 5。5 在这个数组中，找到后返回它的下标 4 即可。

代码

public class AlgoCasts {

  // Time: O(log(n)), Space: O(1)
  public int binarySearch(int[] nums, int target) {
    if (nums == null) return -1;

    int low = 0, high = nums.length - 1;
    while (low <= high) {
      int mid = low + (high - low) / 2;
      if (target < nums[mid]) high = mid - 1;
      else if (target > nums[mid]) low = mid + 1;
      else return mid;
    }
    return -1;
  }

}

P37. 二分搜索插入位置

描述
这个题目说的是，给你一个递增排序的整数数组 nums，和一个目标值 target。你要在数组里找到 target，然后返回它的下标。如果找不到，则返回目标值应该插入的位置的下标，要求插入目标值后，数组仍然保持有序。

代码

public class AlgoCasts {

  // Time: O(log(n)), Space: O(1)
  public int binarySearchInsertPosition(int[] nums, int target) {
    if (nums == null) return -1;

    int low = 0, high = nums.length - 1;
    while (low <= high) {
      int mid = low + (high - low) / 2;
      if (target < nums[mid]) high = mid - 1;
      else if (target > nums[mid]) low = mid + 1;
      else return mid;
    }
    return low;
  }

}

P38. 二维数组的二分搜索

描述
这个题目说的是，给你一个二维数组 matrix，和一个目标值 target。你要在数组里找到这个目标值，然后返回它的行/列下标。如果找不到，则返回 [-1,-1]。

这个数组的每一行都是递增的，并且每一行的第一个数都比上一行的最后一个数要大。也就是，这个数组可以看成，从左到右、从上到下，呈 Z 字形递增。

比如说，给你的二维数组是：

1, 3, 5
7, 9, 11

给你的目标值是 9。9 在这个数组中，找到后返回它的下标 [1, 1] 即可。

如果给你的目标值是 100。显然它不在这个二维数组中，你要返回 [-1，-1]。

代码

public class AlgoCasts {

  // Time: O(log(m*n)), Space: O(1)
  public int[] binarySearchIn2DArray(int[][] matrix, int target) {
    if (matrix == null || matrix.length == 0 ||
      matrix[0] == null || matrix[0].length == 0)
      return new int[]{-1, -1};

    int m = matrix.length, n = matrix[0].length;
    int low = 0, high = m * n - 1;
    while (low <= high) {
      int mid = low + (high - low) / 2;
      int r = mid / n, c = mid % n;
      if (target < matrix[r][c]) high = mid - 1;
      else if (target > matrix[r][c]) low = mid + 1;
      else return new int[]{r, c};
    }
    return new int[]{-1, -1};
  }

}

P39. 判断二叉树是否平衡

描述
这个题目说的是，给你一棵二叉树，你要判断它是否平衡。这里平衡指的是，对于树上任意一个节点，它的两棵子树的高度差不能大于 1。

比如说，给你的二叉树是：

     1
   /   \
  2     4
       / \
      8  16

它的任意节点的左右子树高度差都不大于 1，因此它是一棵平衡二叉树。

再比如说，给你的二叉树是：

     1
   /   \
  2     4
         \
          8
           \
           16

在这棵树中，根节点的左右子树高度差为 2，因此它不是一棵平衡二叉树。

代码

public class AlgoCasts {

  public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
      val = x;
    }
  }

  int getHeight(TreeNode root) {
    if (root == null) return 0;
    int left = getHeight(root.left);
    int right = getHeight(root.right);
    return Math.max(left, right) + 1;
  }

  // Time: O(nlog(n)), Space: O(n)
  public boolean isBalancedTreeTopDown(TreeNode root) {
    if (root == null) return true;
    return Math.abs(getHeight(root.left) - getHeight(root.right)) <= 1 &&
      isBalancedTreeTopDown(root.left) && isBalancedTreeTopDown(root.right);
  }

  // Time: O(n), Space: O(n)
  public boolean isBalancedTreeBottomUp(TreeNode root) {
    return getHeightAndCheck(root) != -1;
  }

  int getHeightAndCheck(TreeNode root) {
    if (root == null) return 0;

    int left = getHeightAndCheck(root.left);
    if (left == -1) return -1;

    int right = getHeightAndCheck(root.right);
    if (right == -1) return -1;

    if (Math.abs(left - right) > 1) return -1;
    return Math.max(left, right) + 1;
  }

}

P40. 求两个单链表之和

描述 这个题目说的是，给你两个非空的单链表，它们代表两个非负整数，并且逆序表示。你要将这两个数求和，并将结果以链表形式返回。你不需要考虑前导 0 这种情况，也就说 3 不会表示成 003 这样子。

比如说给你的两个链接表是：

1 -> 2 -> 3
6 -> 7 -> 8 -> 9

1 -> 2 -> 3 表示的整数是 321，6 -> 7 -> 8 -> 9 表示的整数是 9876。我们需要输出的是它们求和后的链表：

7 -> 9 -> 1 -> 0 -> 1

代码

public class AlgoCasts {

  public class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
      val = x;
    }
  }

  // Time: O(max(m, n)), Space: O(max(m, n))
  public ListNode addTwoLinkedListNumbers(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0), p = dummy;
    int carry = 0;
    while (l1 != null || l2 != null || carry != 0) {
      int sum = carry;
      if (l1 != null) {
        sum += l1.val;
        l1 = l1.next;
      }
      if (l2 != null) {
        sum += l2.val;
        l2 = l2.next;
      }
      p.next = new ListNode(sum % 10);
      p = p.next;
      carry = sum / 10;
    }
    return dummy.next;
  }

}

P41. 丑数

描述 这个题目说的是，给你一个数字，你要判断它是不是一个丑数。丑数的定义是质因数只包含 2，3，5 的正整数。另外，1 作为特例，也定义为丑数。

比如说给你的数字是 45，45 做质因数分解，可以写成：

45 = 3 x 3 x 5

不包含 2，3，5 以外的质因数，因此它是一个丑数。

再比如说 42，它做质因数分解得到：

42 = 2 x 3 x 7

7 不在 2，3，5 中，因此 42 不是丑数。

代码

public class AlgoCasts {

  // Time: O(m+n+l), Space: O(1)
  public boolean isUglyNumber(int num) {
    if (num <= 0) return false;
    while(num % 2 == 0) num /= 2;
    while(num % 3 == 0) num /= 3;
    while(num % 5 == 0) num /= 5;
    return num == 1;
  }

}

P42. 字符串转整数

描述 这个题目说的是，给你一个字符串，你要把它转成一个 int 类型的数字。这个字符串里可能会包含空格，字母或是其它字符。

一个可以有效地转成数字的字符串包含以下特点：

1. 可以有前导空格或前导 0，但不能有其它前导字符
2. 可能会有一个加号或减号表示正负，也可能没有，连续的多个加号或减号则视为不合法
3. 紧接着是一段连续的数字，如果没有数字则示为不合法
4. 数字后的其它字符都可以忽略
5. 如果数字大于 int 的最大值或小于 int 的最小值，返回相应的极值即可
6. 字符串如果不能合法地转为整数，则返回 0

代码

public class AlgoCasts {

  public int string2Integer(String str) {
    int start = 0, p = 0, n = str.length();
    boolean negative = false;
    while (p < n && str.charAt(p) == ' ') ++p;
    if (p == n) return 0;

    if (str.charAt(p) == '+') {
      ++p;
    } else if (str.charAt(p) == '-') {
      ++p;
      negative = true;
    }

    while (p < n && str.charAt(p) == '0') ++p;
    start = p;

    while (p < n && str.charAt(p) >= '0' && str.charAt(p) <= '9') ++p;
    if (p == start) return 0;

    if (p - start > 10) {
      if (negative) return Integer.MIN_VALUE;
      else return Integer.MAX_VALUE;
    }

    long num = 0;
    for (int i = start; i < p; ++i)
      num = num * 10 + (str.charAt(i) - '0');
    num = negative ? -num : num;

    if (num < Integer.MIN_VALUE) return Integer.MIN_VALUE;
    else if (num > Integer.MAX_VALUE) return Integer.MAX_VALUE;
    else return (int)num;
  }

}

P43. 实现 strstr

描述 这个题目说的是，你要实现 C 语言里面的 strstr 函数，这个函数接收两个字符串，你要找到第二个字符串在第一个字符串中的开始下标，如果找不到则返回 -1。

比如说，给你的两个字符串分别是：

marvel studio 和 studio

第二个字符串存在于第一个字符串中，于是你要返回它在第一个字符串中的开始下标 7。

再比如说给你的字符串是：

doctor strange 和 master

第二个字符串没有在第一个字符串中出现，因此返回 -1。

代码

public class AlgoCasts {

  // Time: O((n-m+1)*m), Space: O(1)
  public int strstr(String haystack, String needle) {
    if (haystack == null || needle == null) return -1;
    if (needle.length() == 0) return 0;
    int n = haystack.length(), m = needle.length();

    for (int i = 0; i <= n-m; ++i) {
      int j = 0, k = i;
      for (; j < m && k < n && needle.charAt(j) == haystack.charAt(k); ++j, ++k);
      if (j == needle.length()) return i;
    }
    return -1;
  }

}

P44. 检验二叉搜索树

描述 这个题目说的是，给你一棵二叉树，你要判断它是不是一棵二叉搜索树。

二叉搜索树的定义是：

1. 左子树所有节点上的值都小于根节点上的值
2. 右子树所有节点上的值都大于根节点上的值
3. 左右子树同时也为二叉搜索树

比如说，给你的二叉树是：

    4
   / \
  2   6

左子树只有一个节点 2，小于 4；右子树也只有一个节点 6，大于 4。因此这是一棵二叉搜索树。

再比如说，给你的二叉树是：

    4
   / \
  2   6
     / \
    3   8

右子树存在一个节点 3，它不大于根节点 4。因此这不是一棵二叉搜索树。

代码

public class AlgoCasts {

  public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
      val = x;
    }
  }

  TreeNode min(TreeNode root) {
    while (root.left != null) root = root.left;
    return root;
  }

  TreeNode max(TreeNode root) {
    while (root.right != null) root = root.right;
    return root;
  }

  // Time: O(n*log(n)), Space: O(n)
  public boolean isValidBST(TreeNode root) {
    if (root == null) return true;
    boolean leftValid = root.left == null || root.val > max(root.left).val;
    boolean rightValid = root.right == null || root.val < min(root.right).val;
    return leftValid && rightValid && isValidBST(root.left) && isValidBST(root.right);
  }

  // Time: O(n), Space: O(n)
  public boolean isValidBSTBound(TreeNode root) {
    return isValidBSTBound(root, null, null);
  }

  boolean isValidBSTBound(TreeNode root, TreeNode lower, TreeNode upper) {
    if (root == null) return true;
    if (lower != null && lower.val >= root.val) return false;
    if (upper != null && upper.val <= root.val) return false;
    return isValidBSTBound(root.left, lower, root) && isValidBSTBound(root.right, root, upper);
  }

}

P45. 有效的括号序列

描述 这个题目说的是，给你一个括号序列，里面包含小括号，中括号和大括号。你要判断这个括号序列是否有效。有效的括号序列要求，每个左括号都必须有一个同类的右括号与它正确配对。另外，空字符串认为是有效的括号序列。

比如说，给你的序列是：

()[]{}

小括号/中括号/大括号的左右括号都能正确配对，因此这是一个有效的括号序列。

再比如说给你的序列是：

([)]

这里面虽然正好有一对小括号和一对中括号，但它们的顺序不对，括号间无法正确配对，因此这不是一个有效的括号序列。

代码

public class AlgoCasts {

  // Time: O(n), Space: O(n)
  public boolean isValidBrackets(String s) {
    Stack<Character> stack = new Stack<>();

    for (int i = 0; i < s.length(); ++i) {
      if (s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{') {
        stack.push(s.charAt(i));
      } else if (stack.isEmpty()) {
        return false;
      } else {
        if (s.charAt(i) == ')' && stack.peek() != '(') return false;
        if (s.charAt(i) == ']' && stack.peek() != '[') return false;
        if (s.charAt(i) == '}' && stack.peek() != '{') return false;
        stack.pop();
      }
    }
    return stack.isEmpty();
  }

  // Time: O(n), Space: O(n)
  public boolean isValidBracketsShort(String s) {
    Stack<Character> stack = new Stack<>();

    for (int i = 0; i < s.length(); ++i) {
      if (s.charAt(i) == '(') stack.push(')');
      else if (s.charAt(i) == '[') stack.push(']');
      else if (s.charAt(i) == '{') stack.push('}');
      else if (stack.isEmpty() || s.charAt(i) != stack.pop()) return false;
    }
    return stack.isEmpty();
  }

}

P46. 买卖股票的最大利润

描述 这个题目说的是，给你一个整数数组，其中第 i 个元素表示的是第 i 天的股票价格，你要计算出先买一股，然后再卖出它能获得的最大利润。

比如说，给你的数组是：

9, 3, 7, 5, 1, 8

如果你在价格为 1 时买入并在价格为 8 时卖出，这时能获得最大的利润 7。

再比如说给你的数组是：

9, 8, 7, 6

这时股票每天都在跌，不存在买入再卖出来获利的可能，因此没有交易，最大利润为 0。

代码

public class AlgoCasts {

  // Time: O(n^2), Space: O(1)
  public int maxProfitBruteForce(int[] prices) {
    if (prices.length < 2) return 0;
    int maxProfit = 0;

    for (int i = 0; i < prices.length; ++i)
      for (int j = i+1; j < prices.length; ++j)
        maxProfit = Math.max(maxProfit, prices[j] - prices[i]);

    return maxProfit;
  }

  // Time: O(n), Space: O(1)
  public int maxProfitOnePass(int[] prices) {
    if (prices.length < 2) return 0;

    int maxProfit = 0, buy = prices[0];
    for (int i = 1; i < prices.length; ++i) {
      if (prices[i] < buy) buy = prices[i];
      else maxProfit = Math.max(maxProfit, prices[i] - buy);
    }
    return maxProfit;
  }

}

P47. 翻转二叉树

描述 这个题目说的是，给你一棵二叉树，你要把它左右镜像翻转，然后返回翻转后的二叉树。

比如说，给你的二叉树是：

     1
   /   \
  2     4
       / \
      8  16

左右翻转后的二叉树是：

      1
    /   \
   4     2
  / \
 16  8

我们可以看到，二叉树上所有节点都沿中轴线左右互换了位置。

代码

public class AlgoCasts {

  public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
      val = x;
    }
  }

  // Time: O(n), Space: O(n)
  public TreeNode invertBinaryTreeRecursive(TreeNode root) {
    if (root == null) return root;
    TreeNode tmp = root.left;
    root.left = root.right;
    root.right = tmp;
    invertBinaryTreeRecursive(root.left);
    invertBinaryTreeRecursive(root.right);
    return root;
  }

  // Time: O(n), Space: O(n)
  public  TreeNode invertBinaryTreeIterative(TreeNode root) {
    if (root == null) return root;
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);

    while (!q.isEmpty()) {
      TreeNode node = q.poll();
      TreeNode tmp = node.left;
      node.left = node.right;
      node.right = tmp;
      if (node.left != null) q.add(node.left);
      if (node.right != null) q.add(node.right);
    }
    return root;
  }

}

P48. 单链表删除数字

描述 这个题目说的是，给你一个单链表和一个数字，你要删除节点上数字等于给定数字的那些节点，然后返回删除节点后的单链表。

比如说，给你的单链表是：

1 -> 2 -> 4 -> 1 -> 8 -> 1

要删除的数字是 1。那么删除 1 后，你要返回的单链表是：

2 -> 4 -> 8

代码

public class AlgoCasts {

  public class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
      val = x;
    }
  }

  // Time: O(n), Space: O(1)
  public ListNode remove(ListNode head, int val) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode notEqual = dummy;

    while (notEqual.next != null) {
      if (notEqual.next.val == val) notEqual.next = notEqual.next.next;
      else notEqual = notEqual.next;
    }
    return dummy.next;
  }

}

P49. 二进制中 1 的个数

描述
这个题目说的是，给你一个整数，你要计算它的二进制表示中 1 的个数，然后返回。

比如说，给你的整数是 12，它的二进制表示是：

1100

包含两个 1，因此你要返回 2。

算法思路：
思路一：将数字和1进行与运算，如果结果是1时可以加1，如果非1时与运算后为0不需要加1，循环每一位，直到32位时变为0 ，结束循环 思路二：n&(n-1) 可以把这个数的最低位的1消除。当n为0时结束循环

代码

public class AlgoCasts {

  // Time: O(m), Space: O(1)
  public int numberOfOneWithMask(int n) {
    int mask = 1, count = 0;
    while (mask != 0) {
      if ((n & mask) != 0) ++count;
      mask <<= 1;
    }
    return count;
  }

  // Time: O(k), Space: O(1)
  public int numberOfOne(int n) {
    int count = 0;
    while (n != 0) {
      ++count;
      n &= (n - 1);
    }
    return count;
  }

}

P50. 矩阵置零

描述
这个题目说的是，给你一个 m x n 的矩阵，你要把这个矩阵中等于 0 的元素所在的行和列都置 0。

比如说，给你的矩阵 a 是：

 1, 2, 3
 4, 0, 6
 0, 8, 9

这个矩阵中有两个 0，把它们所在的行和列都置 0 后，得到的矩阵是：

 0, 0, 3
 0, 0, 0
 0, 0, 0

代码

public class AlgoCasts {

  // Time: O(m*n), Space: O(m+n)
  public void setZeroInMatrix(int[][] a) {
    int m = a.length, n = a[0].length;
    boolean[] rows = new boolean[m];
    boolean[] cols = new boolean[n];

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        if (a[i][j] == 0)
          rows[i] = cols[j] = true;

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        if (rows[i] || cols[j])
          a[i][j] = 0;
  }

  // Time: O(m*n), Space: O(1)
  public void setZeroInMatrixO1(int[][] a) {
    int m = a.length, n = a[0].length;
    boolean row0 = false, col0 = false;

    for (int i = 0; i < m; ++i)
      if (a[i][0] == 0) col0 = true;
    for (int j = 0; j < n; ++j)
      if (a[0][j] == 0) row0 = true;

    for (int i = 1; i < m; ++i)
      for (int j = 1; j < n; ++j)
        if (a[i][j] == 0)
          a[i][0] = a[0][j] = 0;

    for (int i = 1; i < m; ++i)
      for (int j = 1; j < n; ++j)
        if (a[i][0] == 0 || a[0][j] == 0)
          a[i][j] = 0;

    if (row0)
      for (int j = 0; j < n; ++j)
        a[0][j] = 0;
    if (col0)
      for (int i = 0; i < m; ++i)
        a[i][0] = 0;
  }

}