LeeCode三百题-4

[TOC]

---

代码工程获取

git clone --depth=1 https://gitee.com/SevDaisy/LeeCode300.git

---

#31 下一个排列

• 基本思路：
• 要找到一个排列，比现在的排列大。
• 假如，现在的排列已经是最大的了，比如，99887654444321
• 这样最大的排列，特点就是，右边的数一定不大于左边的数。
• 如果有遇见不满足num[a] ≥ num[b] (a < b)
  • 那么只要交换这两个数字，就能得到更大的排列
• 关键一：扫描方向
  • 在一个排列中，我们可能找到不止一对(a, b)可以交换
  • 题目要求是，找到一个尽可能小的排列比现在的大
  • 所以，我们应该从右往左扫描数列来寻找(a, b)
• 关键二：扫描次数
  • 我们要扫描两次
  • 第一次是为了找到不合条件的num[a]—— 左边那个数
  • 第二次是为了找到最小的但是比num[a]大的num[b]
  • 然后才可以交换 num[a] 和 num[b]
• 关键三：收尾处理
  • 在完成交换以后，可证，num 中 (a,iMax)的这一段肯定是非严格递减的
  • 我们需要将这一段逆置为非严格递增的
  • 这样才可以保证我们这一排列足够小

class Solution {

    public void nextPermutation(int[] nums) {
      if (nums == null || nums.length < 2) {
        return;
      }
      int iMax = nums.length;
      int leftBound = -1;
      int aLittleBigger;
      int temp;
      int left;
      int right;

      /* 452631 leftBound -> 2 in 526 */
      for (int i = iMax - 2; i >= 0; i--) {
        if (nums[i] < nums[i + 1]) {
          leftBound = i;
          break;
        }
      }

      if (leftBound != -1) {
        /* 452631 leftBound -> 2 in 526; aLittleBigger -> 3 in 631 */
        aLittleBigger = -1;
        for (int i = iMax - 1; i >= 0; i--) {
          /* 只要 leftBound 已经是合法值,那就一定能找到 aLittleBigger */
          if (nums[i] > nums[leftBound]) {
            aLittleBigger = i;
            break;
          }
        }
        /* 452631 => 453621 then 621 must be descend */
        temp = nums[aLittleBigger];
        nums[aLittleBigger] = nums[leftBound];
        nums[leftBound] = temp;

        /* 453621 => 453126 reverse 621 */
        left = leftBound + 1;
        right = iMax - 1;
      } else {
        /* 654321 => 123456 reverse 621 */
        left = 0;
        right = iMax - 1;
      }

      /* reverse [left, right] */
      while (left < right) {
        temp = nums[right];
        nums[right] = nums[left];
        nums[left] = temp;
        left++;
        right--;
      }
    }
  }

#32 最长有效括号

• 自己又做了一遍。成功了。但是写的东西不知道为什么都没保存。累了。不想写第二遍。反正代码也还在。就等下次遇到再说吧。

package Order300;

import java.util.Stack;

public class T32_longest_valid_parentheses {

  /** 本地调试时用于打印 s 和 dp */
  static void printDP(String s, int[] dp) {
    StringBuilder sdp = new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
      System.out.print(s.charAt(i));
      System.out.print(" ");
      sdp.append(String.valueOf(dp[i]));
      sdp.append(" ");
    }
    System.out.println();
    System.out.println(sdp.toString());
  }

  public static void main(String[] args) {
    // System.out.println(new Solution().longestValidParentheses("()")); // -> 2
    // System.out.println(new Solution().longestValidParentheses("(")); // -> 0
    // System.out.println(new Solution().longestValidParentheses(")")); // -> 0
    // System.out.println(new Solution().longestValidParentheses("(()")); // -> 2
    // System.out.println(new Solution().longestValidParentheses("(())))")); // -> 4
    System.out.println(new Solution().longestValidParentheses(")(())()))")); // -> 6
    System.out.println(
      new Solution_leecode().longestValidParentheses(")(())()))")
    ); // -> 6
    // System.out.println(new Solution().longestValidParentheses("(()())()))")); // -> 8
  }

  static class Solution_me_first {

    public int longestValidParentheses(String s) {
      int iMax = s.length();
      /* 鲁棒性 特殊条件 输入太短 */
      if (s == null || iMax < 2) {
        return 0;
      }
      int[] dp = new int[iMax];
      dp[0] = 0;
      int maxAnswer = 0;
      if ("()".equals(s.substring(0, 2))) {
        maxAnswer = dp[1] = 2;
      } else {
        dp[1] = 0;
      }
      for (int i = 2; i < iMax; i++) {
        if (s.charAt(i) == '(') {
          /* ......( */
          dp[i] = 0;
        } else if (s.charAt(i - 1) == '(') {
          /* ......() */
          dp[i] = dp[i - 2] + 2;
        } else {
          /* ......)) */
          int preLen = dp[i - 1]; // prelen 是不是 0 都OK
          /* 考虑形如 ....((..)) */
          if (i - (preLen + 1) >= 0 && s.charAt(i - (preLen + 1)) == '(') {
            if (i - (preLen + 2) >= 0) {
              /* 如果是 ....((..)) */
              dp[i] = preLen + 2 + dp[i - (dp[i - 1] + 2)];
            } else {
              /* 否则是 ((..)) */
              dp[i] = preLen + 2;
            }
          } else {
            /* 考虑形如 ....)(..)) */
            dp[i] = 0;
          }
        }
        maxAnswer = Math.max(maxAnswer, dp[i]);
      }
      printDP(s, dp);
      return maxAnswer;
    }
  }

  /**
   * 官方的写法比我简洁好多。
   * 可以通过函数 printDP(s,dp) 看出，对于 ")(())()))" 我和官方写法，dp数组值是完全一样的。
   * 再仔细看看代码，感觉官方写法只是省略了 dp[i] = 0 的赋值。
   * 因为Java的数组默认值是0的，所以可以省略，但是没必要。我的代码中还是保留吧。
   **/
  static class Solution_leecode {

    public int longestValidParentheses(String s) {
      int maxans = 0;
      int[] dp = new int[s.length()];
      for (int i = 1; i < s.length(); i++) {
        if (s.charAt(i) == ')') {
          if (s.charAt(i - 1) == '(') {
            dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
          } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
            dp[i] =
              dp[i - 1] +
              ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) +
              2;
          }
          maxans = Math.max(maxans, dp[i]);
        }
      }
      printDP(s, dp);
      return maxans;
    }
  }

  /* 2021年5月1日，删光了之前的代码，也不看题解和自己的博客，只靠自己尝试重写这题，成功了 */
  static class me_dp_20210501 {

    public int longestValidParentheses(String s) {
      if (s == null || s.length() < 2) return 0;

      int iMax = s.length();
      int[] dp = new int[iMax];
      int dpMax = 0;
      /* int[]初值为0，因此此处赋值可省略 */
      // dp[0] = 0;
      dp[1] = "()".equals(s.substring(0, 2)) ? 2 : 0;

      for (int i = 2; i < iMax; i++) {
        if (s.charAt(i) == ')') {
          /* ...) */
          if (s.charAt(i - 1) == '(') {
            /* ...() */
            dp[i] = dp[i - 2] + 2; // 注意，这里是 dp[i-2]+2 而不是 dp[i-1]+2
          } else {
            /* ...)) */
            /* .?(..)) */
            int leftPos = i - dp[i - 1] - 1;
            if (leftPos >= 0 && s.charAt(leftPos) == '(') {
              dp[i] = 2 + dp[i - 1] + ((leftPos > 0) ? dp[leftPos - 1] : 0);
            }
          }

          dpMax = Math.max(dpMax, dp[i]);
        }
      }
      /* 注意 dpMax 还没和 dp[1] 比较过 */
      return Math.max(dpMax, dp[1]);
    }
  }

  /** 
   * 用栈做 
   * TODO 要记得能自己写出来啊 —— T32 栈
   **/
  static class Solution {

    public int longestValidParentheses(String str) {
      int maxans = 0;
      Stack<Integer> stack = new Stack<>();
      stack.push(-1);
      for (int i = 0; i < str.length(); i++) {
        if (str.charAt(i) == '(') {
          /** -> ( */
          stack.push(i);
        } else {
          /** -> ) */
          /** 则 ( -> */
          stack.pop();
          if (stack.empty()) {
            stack.push(i);
          } else {
            maxans = Math.max(maxans, i - stack.peek());
          }
        }
      }
      return maxans;
    }
  }

  /** 
   * 用 伪双指针 做 
   * TODO 要记得得能自己做出来啊 —— T32 伪双指针
   **/
  class Solution_left_right {

    public int longestValidParentheses(String s) {
      int left = 0, right = 0, maxlength = 0;
      for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') {
          left++;
        } else {
          right++;
        }
        if (left == right) {
          maxlength = Math.max(maxlength, 2 * right);
        } else if (right > left) {
          left = right = 0;
        }
      }
      left = right = 0;
      for (int i = s.length() - 1; i >= 0; i--) {
        if (s.charAt(i) == '(') {
          left++;
        } else {
          right++;
        }
        if (left == right) {
          maxlength = Math.max(maxlength, 2 * left);
        } else if (left > right) {
          left = right = 0;
        }
      }
      return maxlength;
    }
  }
}

#33 搜索旋转排序数组

• 二分搜索 —— 基础代码框架

  /* 此代码未验证有效性 */
  while ( left <= right ){
    mid = (letf+right) >> 2;
    if (nums[mid] == target) return mid;
    if (nums[left] <= target && target < nums[mid]) right = mid-1;
    else left = mid + 1;
  }

• 本题关键：数组只被旋转过一次

• 因此，对于任意的 i in [0, iMax-1]

• 可以知道 [0, i] 和 [i, iMax-1] 有且仅有一个是有序的

• 我们只需要

  • 判断出，对于当前的i，有序的区间是 [0, i] 还是 [i, iMax-1]
  • 然后，在有序的这个区间上进行二分搜索，即可

package Order300;

public class T33_search_in_rotated_sorted_array {

  public static void main(String[] args) {
    int[] nums;

    nums = new int[] { 4, 5, 6, 7, 0, 1, 2 };
    System.out.println(new Solution().search(nums, 0));
  }

  static class Solution {

    public int search(int[] nums, int target) {
      if (nums == null || nums.length == 0) {
        return -1;
      }
      int iMax = nums.length;
      int left, right, mid;

      if (iMax == 1) return nums[0] == target ? 0 : -1;

      left = 0;
      right = iMax - 1;
      /* 二分合法条件 left≤right */
      while (left <= right) {
        /* 取得当前 mid 的值 */
        mid = (left + right) >> 1;
        /* 如果找到了 则 退出 */
        if (nums[mid] == target) return mid;
        if (nums[0] <= nums[mid]) {
          /* 如果 0～mid 上，数组是有序的，那就在 0~mid 上正常二分搜索 */
          if (nums[0] <= target && target < nums[mid]) {
            right = mid - 1;
          } else left = mid + 1;
        } else {
          /* 如果 0～mid 上，数组不是升序的，那么，mid～iMax-1 上，数组一定是有序的，在此范围正常二分搜索即可 */
          if (nums[mid] < target && target <= nums[iMax - 1]) {
            left = mid + 1;
          } else right = mid - 1;
        }
      }

      return -1;
    }
  }
}

#34 在排序数组中查找元素的第一个和最后一个位置

• 我的思路：
• 先用二分搜索随便找到一个 mayAt ，满足 nums[mayAt] == target
• 然后延展左边界 for i from mayAt-1 to 0 —— if (nums[i]==target) leftBound = i —— else break
• 然后延展右边界 for i from mayAt+1 to iMax-1 —— if (nums[i]==target) rightBound = i —— else break
• 这样就已经可以 0ms => 100% 了
• 优化 —— 完美掌握二分搜索
• 考虑 target 开始和结束位置
  • 其实我们要找的就是数组中 —— 从左数向右边
  • 「第一个等于 target 的位置」（记为 leftIdx ）
  • 「第一个大于 target 的位置减一」（记为 rightIdx ）
• 如果 nums[mid] > target，则 右边界左移
• 如果 nums[mid] ≤ target， 考虑，需要的是 第一个等于 target 的位置 还是 第一个大于 target 的位置
  • 如果是 第一个等于 target 的位置 则 右边界左移
  • 如果是 第一个大于 target 的位置 则当 nums[mid] >= target 才有 右边界左移
• 如果 nums[mid] ≤ target 且 nums[mid] < target 才有 左边界右移
• 提出问题：
  • 我求出的 mayBe 和 leftBound 或者 rightBound 有没有什么必然关系？

package Order300;

public class T34_find_first_and_last_position_of_element_in_sorted_array {

  public static void main(String[] args) {
    int[] nums;
    int[] ans;

    nums = new int[] { 0, 0, 0, 1, 2, 3 };
    ans = new Solution().searchRange(nums, 0);
    for (int x : ans) {
      System.out.print(x + " ");
    }
    System.out.println();

    nums = new int[] { 2, 2 };
    ans = new Solution().searchRange(nums, 2);
    for (int x : ans) {
      System.out.print(x + " ");
    }
    System.out.println();

    nums = new int[] { 5, 7, 7, 8, 8, 10 };
    ans = new Solution().searchRange(nums, 8);
    for (int x : ans) {
      System.out.print(x + " ");
    }
    System.out.println();

    nums = new int[] { 5, 7, 7, 8, 8, 10 };
    ans = new Solution().searchRange(nums, 6);
    for (int x : ans) {
      System.out.print(x + " ");
    }
    System.out.println();
  }

  /** 我自己的算法 二分搜索找到 mayBe，然后向左向右做 step 为 1 的 for 循环，得到左边界和右边界的值。
   * 对比官方题解，可以提出一个问题。
   * ? 我求出的 mayBe 和 leftBound 或者 rightBound 有没有什么必然关系？
   */
  static class Solution_me {

    public int[] searchRange(int[] nums, int target) {
      if (nums == null || nums.length == 0) {
        return new int[] { -1, -1 };
      }
      int iMax = nums.length;
      int left, right, mid;
      int mayAt, leftBound, rightBound;

      mayAt = -1;
      left = 0;
      right = iMax - 1;
      while (left <= right) {
        mid = (left + right) >> 1;
        if (nums[mid] == target) {
          mayAt = mid;
          break;
        }
        if (nums[left] <= target && target < nums[mid]) {
          right = mid - 1;
        } else left = mid + 1;
      }

      if (mayAt == -1) return new int[] { -1, -1 };

      leftBound = mayAt;
      for (int i = mayAt - 1; i >= 0; i--) {
        if (nums[i] == target) leftBound = i; else break;
      }
      rightBound = mayAt;
      for (int i = mayAt + 1; i < iMax; i++) {
        if (nums[i] == target) rightBound = i; else break;
      }

      return new int[] { leftBound, rightBound };
    }
  }

  /** LeeCode官方题解的方法 精准地理解和掌握了二分 */
  static class Solution {

    public int[] searchRange(int[] nums, int target) {
      int leftIdx = binarySearch(nums, target, true);
      int rightIdx = binarySearch(nums, target, false) - 1;
      if (
        leftIdx <= rightIdx &&
        rightIdx < nums.length &&
        nums[leftIdx] == target &&
        nums[rightIdx] == target
      ) {
        return new int[] { leftIdx, rightIdx };
      }
      return new int[] { -1, -1 };
    }

    /**
     * 二分搜索
     * @param nums 待搜索的数组
     * @param target 待搜索的目标值
     * @param lower 是否要求 {@code nums[mid]==target }
     * @return 若{@code lower==false } 则定有 {@code nums[ans]>target } 并可能有 {@code nums[ans-1]==target }
     */
    public int binarySearch(int[] nums, int target, boolean lower) {
      int left = 0, right = nums.length - 1, ans = nums.length, mid;
      while (left <= right) {
        mid = (left + right) >> 1;
        if (nums[mid] > target || (lower && nums[mid] >= target)) {
          /**
           * 如果 nums[mid] > target, 则 右边界左移
           * 如果 nums[mid] ≤ target, 考虑，需要的是 第一个等于 target 的位置 还是 第一个大于 target 的位置
           * - 如果是 第一个等于 target 的位置 则 右边界左移
           * - 如果是 第一个大于 target 的位置 则当 nums[mid] >= target 才有 右边界左移
           */
          right = mid - 1;
          ans = mid;
        } else {
          /**
           * 如果 nums[mid] ≤ target 且 nums[mid] < target 才有 左边界右移
           */
          left = mid + 1;
        }
      }
      return ans;
    }
  }
}

• 基于此题，可以看到新的二分搜索 —— 基础代码框架——显然这个框架可以更优化

/**
 * 二分搜索
 * @param nums 待搜索的数组
 * @param target 待搜索的目标值
 * @param lower 是否要求 {@code nums[mid]==target }
 * @return 若{@code lower==false } 则定有 {@code nums[ans]>target } 并可能有 {@code nums[ans-1]==target }
 */
public int binarySearch(int[] nums, int target, boolean lower) {
  int left = 0, right = nums.length - 1, ans = nums.length, mid;
  while (left <= right) {
    mid = (left + right) >> 1;
    if (nums[mid] > target || (lower && nums[mid] >= target)) {
      /**
       * 如果 nums[mid] > target, 则 右边界左移
       * 如果 nums[mid] ≤ target, 考虑，需要的是 第一个等于 target 的位置 还是 第一个大于 target 的位置
       * - 如果是 第一个等于 target 的位置 则 右边界左移
       * - 如果是 第一个大于 target 的位置 则当 nums[mid] >= target 才有 右边界左移
       */
      right = mid - 1;
      ans = mid;
    } else {
      /**
       * 如果 nums[mid] ≤ target 且 nums[mid] < target 才有 左边界右移
       */
      left = mid + 1;
    }
  }
  return ans;
}

• 这时，我才想到，为什么不看看JDK里的二分搜索的源码实现呢？

// Like public version, but without range checks.
private static int binarySearch0(Object[] a, int fromIndex, int toIndex, Object key) {
  int low = fromIndex;
  int high = toIndex - 1;

  while (low <= high) {
    int mid = (low + high) >>> 1;
    @SuppressWarnings("rawtypes")
    Comparable midVal = (Comparable)a[mid];
    @SuppressWarnings("unchecked")
    int cmp = midVal.compareTo(key);

    if (cmp < 0)
      low = mid + 1;
    else if (cmp > 0)
      high = mid - 1;
    else
      return mid; // key found
  }
  return -(low + 1);  // key not found.
}

/**
 * Searches a range of
 * the specified array for the specified object using the binary
 * search algorithm.
 * The range must be sorted into ascending order
 * according to the
 * {@linkplain Comparable natural ordering}
 * of its elements (as by the
 * {@link #sort(Object[], int, int)} method) prior to making this
 * call.  If it is not sorted, the results are undefined.
 * (If the range contains elements that are not mutually comparable (for
 * example, strings and integers), it <i>cannot</i> be sorted according
 * to the natural ordering of its elements, hence results are undefined.)
 * If the range contains multiple
 * elements equal to the specified object, there is no guarantee which
 * one will be found.
 *
 * @param a the array to be searched
 * @param fromIndex the index of the first element (inclusive) to be
 *          searched
 * @param toIndex the index of the last element (exclusive) to be searched
 * @param key the value to be searched for
 * @return index of the search key, if it is contained in the array
 *         within the specified range;
 *         otherwise, <code>(-(<i>insertion point</i>) - 1)</code>.  The
 *         <i>insertion point</i> is defined as the point at which the
 *         key would be inserted into the array: the index of the first
 *         element in the range greater than the key,
 *         or {@code toIndex} if all
 *         elements in the range are less than the specified key.  Note
 *         that this guarantees that the return value will be &gt;= 0 if
 *         and only if the key is found.
 * @throws ClassCastException if the search key is not comparable to the
 *         elements of the array within the specified range.
 * @throws IllegalArgumentException
 *         if {@code fromIndex > toIndex}
 * @throws ArrayIndexOutOfBoundsException
 *         if {@code fromIndex < 0 or toIndex > a.length}
 * @since 1.6
 */
public static int binarySearch(Object[] a, int fromIndex, int toIndex, Object key) {
    rangeCheck(a.length, fromIndex, toIndex);
    return binarySearch0(a, fromIndex, toIndex, key);
}

• 补充知识点 >> 与 >>>
  • >> 是 有符号移位 —— 前补0
  • >>> 是 无符号移位 —— 防溢出有用

---

对照源码 编写自己的二分搜索模板

/* 此代码未验证 —— 不过毕竟是对照着源码的重写，应该不至于出错叭 */
int binarySearch(int[] nums, int target) {
  int left = 0;
  int right = (nums == null) ? 0 : nums.length - 1;

  while (left <= right) {
    int mid = (left + right) >>> 1;
    if (nums[mid] < target) {
      left = mid + 1;
    } else if (nums[mid] > target) {
      right = mid - 1;
    } else return mid; // key found
  }
  return -(left + 1); // key not found.
}

#35 搜索插入位置

• 时隔多天以后才来写这题，一遍过，开心。

package Order300;

public class T35_search_insert_position {

  public static void main(String[] args) {
    int[] nums;

    nums = new int[] { 1, 3, 5, 6 };
    System.out.println(new Solution().searchInsert(nums, 5)); // -> 2
    System.out.println(new Solution().searchInsert(nums, 2)); // -> 1
    System.out.println(new Solution().searchInsert(nums, 7)); // -> 4
    System.out.println(new Solution().searchInsert(nums, 0)); // -> 0
  }

  static class Solution {

    public int searchInsert(int[] nums, int target) {
      if (nums == null || nums.length == 0) {
        return 0;
      }
      int iMax = nums.length;
      int low = 0;
      int high = iMax - 1;
      int mid = 0;
      while (low <= high) {
        mid = (low + high) >>> 1;
        if (nums[mid] == target) return mid;

        if (nums[mid] < target) {
          low = mid + 1;
        } else {
          high = mid - 1;
        }
      }
      return nums[mid] > target ? mid : (mid + 1);
    }
  }
}

#36 有效的数独

• 读入的同时，判断出口。很棒。1ms => 100%

public class T36_valid_sudoku {

  /* 1ms => 100% */
  static class Solution {

    public boolean isValidSudoku(char[][] board) {
      boolean[][] lineX = new boolean[9][9];
      boolean[][] lineY = new boolean[9][9];
      boolean[][] lineS = new boolean[9][9];

      for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
          if (board[i][j] != '.') {
            int val = board[i][j] - '1';/* [0,8] */
            int sIndex = i / 3 * 3 + j / 3;
            if (lineX[i][val] || lineY[j][val] || lineS[sIndex][val]) {
              return false;
            } else {
              lineX[i][val] = true;
              lineY[j][val] = true;
              lineS[sIndex][val] = true;
            }
          }
        }
      }
      return true;
    }
  }
}

#37 解数独

• 都在注释里。今天早点溜号，就不转录到这边的文本了。偷懒嘻嘻。

package Order300;

import java.util.ArrayList;
import java.util.List;

public class T37_sudoku_solver {

  public static void main(String[] args) {
    new Solution()
    .solveSudoku(
        new char[][] {
          { '5', '3', '4', '6', '7', '8', '9', '1', '2' },
          { '6', '7', '2', '1', '9', '5', '3', '4', '8' },
          { '1', '9', '8', '3', '4', '2', '5', '6', '7' },
          { '8', '5', '9', '7', '6', '1', '4', '2', '3' },
          { '4', '2', '6', '8', '5', '3', '7', '9', '1' },
          { '7', '1', '3', '9', '2', '4', '8', '5', '6' },
          { '9', '6', '.', '.', '.', '.', '2', '8', '.' },
          { '.', '.', '.', '4', '1', '9', '.', '.', '5' },
          { '.', '.', '.', '.', '8', '.', '.', '7', '9' },
        }
      );
  }
/* 第二次尝试，借鉴他人，优化了代码结构 时间 1ms => 99.96% 空间 35.7MB => 80.16% */
  static class Solution {

    /* 学习变量处理 用类变量代替方法传参 */
    /* 学习命名 row 代表 行 */
    boolean[][] row = new boolean[9][9];
    /* 学习命名 col 代表 列 */
    boolean[][] col = new boolean[9][9];
    /* 学习命名 cell 代表 小单元 */
    /* 学习数据格式 大胆使用高维数组 */
    boolean[][][] cell = new boolean[3][3][9];

    public void solveSudoku(char[][] board) {
      /* 初始化读入 */
      for (int xi = 0; xi < 9; xi++) {
        for (int yi = 0; yi < 9; yi++) {
          if (board[xi][yi] != '.') {
            int step = board[xi][yi] - '1';
            /* 这三行可以用连等来写成一行，但是我觉得丑、就算了 */
            row[xi][step] = true;
            col[yi][step] = true;
            cell[xi / 3][yi / 3][step] = true;
          }
        }
      }
      dfs(board, 0, 0);
      // System.out.println(dfs(board, 0, 0));
      /* 打印结果 */
      // for (int ii = 0; ii < 9; ii++) {
      // for (int jj = 0; jj < 9; jj++) {
      // System.out.printf(" %c", board[ii][jj]);
      // }
      // System.out.println();
      // }
    }

    /**
     * 这个问题实际上是 深度优先搜索 而不是 回溯
     * 因为题目的目标是找到答案，而不是找出全路径
     * 所以，
     * - 命名上：应该是 DFS 而不是 回溯
     * - 函数处理上：
     *  - 不需要保存历史路径
     *  - 及时退出，返回结果
     * 特别的，其实，参数 x:int 也可以抽离到成员变量中去
     */
    private boolean dfs(char[][] board, int x, int y) {
      /**
       * 观察当前状态
       * 确定下一步怎么走
       * 看看是，走一步，还是退出，还是回头
       */
      if (y == 9) {
        /* 一个方向走到头了，换行，回头 */
        x++;
        y = 0;
      }
      if (x == 9) {
        /* 走到第九行了，说明前0～8行都走完了，成功，退出 */
        /* 打印结果 */
        // for (int ii = 0; ii < 9; ii++) {
        // for (int jj = 0; jj < 9; jj++) {
        // System.out.printf(" %c", board[ii][jj]);
        // }
        // System.out.println();
        // }
        return true;
      }
      if (board[x][y] != '.') {
        /**
         * 现在这步不用走，那就跳过，去走下一步
         * 无需考虑新的 x y 是否合法
         * 在下一次函数执行体的头部再来做（x,y) 的矫正
         */
        return dfs(board, x, y + 1);
      }
      /**
       * 状态观察/位置矫正 Over
       * 接下来是，认真走一步，要做的业务处理
       */
      for (int step = 0; step < 9; step++) {
        /* 如果这一步可以这样走 */
        if (!(row[x][step] || col[y][step] || cell[x / 3][y / 3][step])) {
          /* 那就走这样的一步 */
          board[x][y] = (char) (step + '1');
          row[x][step] = col[y][step] = cell[x / 3][y / 3][step] = true;
          if (dfs(board, x, y + 1)) {
            /* DFS 中的及时退出处理 —— 上游函数栈传递返回 true */
            return true;
          }
          /* 然后把这一步撤回来 */
          board[x][y] = '.';
          row[x][step] = col[y][step] = cell[x / 3][y / 3][step] = false;
        }
      }
      /* 没能在前面的逻辑中return，走到这儿了，那就是失败了，返回 false */
      return false;
    }
  }

  /* 第一次尝试 时间 3ms => 86.88% 空间 38.2 => 7.76% */
  static class Solution_me_1 {

    /** 对参数中对res进行修改，则，res的值真的会发生变化
     * Java的方法传递是 值传递
     * 对于基本数据类型，值传递，所以，对形式参数的赋值不会改变实际参数的值
     * 而对于引用数据类型，就需要考虑 Enverment 和 Store 的不同了
     */
    // boolean[][] tempDo(boolean[][] res, int i, int j, boolean value) {
    //   res[i][j] = value;
    //   return res;
    // }

    List<String> debugPrintBoard(char[][] board) {
      List<String> out = new ArrayList<>();
      StringBuilder sb;
      for (int i = 0; i < 9; i++) {
        sb = new StringBuilder();
        for (int j = 0; j < 9; j++) {
          sb.append(" ");
          sb.append(board[i][j]);
        }
        out.add(sb.toString());
      }
      return out;
    }

    List<Character> mixUp(boolean[] lineX, boolean[] lineY, boolean[] lineS) {
      int iMax = lineX.length;
      List<Character> out = new ArrayList<Character>();
      for (int i = 0; i < iMax; i++) {
        if (!(lineX[i] || lineY[i] || lineS[i])) {
          out.add((char) (i + '1'));
        }
      }
      return out;
    }

    boolean backtrack(
      char[][] board,
      boolean[][] lineX,
      boolean[][] lineY,
      boolean[][] lineS,
      int pi,
      int pj
    ) {
      searchNext:for (int i = pi; i < 9; i++) {
        for (int j = (i == pi ? pj : 0); j < 9; j++) {
          if (board[i][j] == '.') {
            pi = i;
            pj = j;
            break searchNext;
          } else if (i == 8 && j == 8) {
            /* 打印结果 */
            // for (int jj = 0; jj < 9; jj++) {
            // for (int ii = 0; ii < 9; ii++) {
            // System.out.printf(" %c", board[ii][jj]);
            // }
            // System.out.println();
            // }
            return true;
          }
        }
      }
      List<Character> choices = mixUp(
        lineX[pi],
        lineY[pj],
        lineS[pi / 3 * 3 + pj / 3]
      );
      for (char x : choices) {
        // char old = board[pi][pj];
        board[pi][pj] = x;
        lineX[pi][x - '1'] = true;
        lineY[pj][x - '1'] = true;
        lineS[pi / 3 * 3 + pj / 3][x - '1'] = true;
        if (backtrack(board, lineX, lineY, lineS, pi, pj)) {
          /* 及时退出 */
          return true;
        }
        /* 复原到上一步 但是由于前文的逻辑限制，所以，此处的 old 必定为 '.' */
        // board[pi][pj] = old;
        // System.out.println("old\t" + old);
        board[pi][pj] = '.';
        lineX[pi][x - '1'] = false;
        lineY[pj][x - '1'] = false;
        lineS[pi / 3 * 3 + pj / 3][x - '1'] = false;
      }
      return false;
    }

    public void solveSudoku(char[][] board) {
      boolean[][] lineX = new boolean[9][9];
      boolean[][] lineY = new boolean[9][9];
      boolean[][] lineS = new boolean[9][9];

      /* 初始化读入 */
      for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
          if (board[i][j] != '.') {
            int val = board[i][j] - '1';/* [0,8] */
            int sIndex = i / 3 * 3 + j / 3;
            lineX[i][val] = true;
            lineY[j][val] = true;
            lineS[sIndex][val] = true;
          }
        }
      }

      /* 调用回溯函数 */
      backtrack(board, lineX, lineY, lineS, 0, 0);
      /* 打印结果 */
      // for (int i = 0; i < 9; i++) {
      // for (int j = 0; j < 9; j++) {
      // System.out.printf(" %c", board[i][j]);
      // }
      // System.out.println();
      // }
    }
  }
}

#38 外观数列

• 妙就妙在，递归比迭代快嗷

package Order300;

public class T38_count_and_say {

  public static void main(String[] args) {
    // System.out.println(new Solution().countAndSay(0));
    System.out.println(new Solution().countAndSay(1));
    System.out.println(new Solution().countAndSay(2));
    System.out.println(new Solution().countAndSay(3));
    System.out.println(new Solution().countAndSay(4));
    System.out.println(new Solution().countAndSay(5));
  }

  /* 第二次尝试 - 递归 时间 1ms => 98.11% 空间 36.4MB => 33.98% */
  static class Solution {

    // 递归写法
    public String countAndSay(int n) {
      if (n == 1) {
        return "1";
      }
      StringBuilder builder = new StringBuilder();
      String history = countAndSay(n - 1);
      int cnt = 0;
      char k = history.charAt(0);
      for (char ch : history.toCharArray()) {
        if (k == ch) {
          cnt++;
        } else {
          builder.append(cnt);
          builder.append(k);
          cnt = 1;
          k = ch;
        }
      }
      builder.append(cnt);
      builder.append(k);

      return builder.toString();
    }
  }

  /* 第一次尝试 时间 5ms => 48.80% 空间 37.9MB => 25.42% */
  static class Solution_fi {

    public String countAndSay(int n) {
      int loops = 1;
      String str = "1";
      while (loops < n) {
        StringBuilder builder = new StringBuilder();
        int cnt = 0;
        char k = '-';

        for (char ch : str.toCharArray()) {
          if (ch == k) {
            cnt++;
          } else {
            if (k != '-') {
              builder.append(String.valueOf(cnt));
              builder.append(k);
            }
            k = ch;
            cnt = 1;
          }
        }
        builder.append(String.valueOf(cnt));
        builder.append(k);

        loops++;
        str = builder.toString();
      }
      return str;
    }
  }
}

#39 组合总和

• 回溯算法，熟练度练习题

package Order300;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

@SuppressWarnings("unchecked")
public class T39_combination_sum {

  public static void main(String[] args) {
    List<List<Integer>> out = new Solution_second()
    .combinationSum(new int[] { 2, 3, 6, 7 }, 7);
    for (List<Integer> list : out) {
      for (int x : list) {
        System.out.printf(" %d", x);
      }
      System.out.println();
    }
  }

  /* 第三次尝试，改写自己的回溯，时间 2ms => 99.96% 空间 38.8MB => 32.49% */
  static class Solution {

    /* 命名更改为 nums 方便多了 */
    int[] nums;
    List<List<Integer>> answers = new ArrayList<List<Integer>>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
      this.nums = candidates;
      /* 排序完全可以省略 Arrays.sort(this.table); */
      /* 健壮性考虑 */
      if (candidates == null || candidates.length == 0) return answers;
      backtrace(target, 0, new ArrayList<Integer>());
      return answers;
    }

    private void backtrace(int target, int pos, ArrayList<Integer> path) {
      if (target == 0) {
        // BaseNode.util.errPrintList(path, "Add Path");
        answers.add(new ArrayList<Integer>(path));
        /* 此处 return ，做到了 及时终止、主动退出。防止回溯二次遍历到这个解路径 */
        return;
      }
      if (pos == nums.length) return;
      backtrace(target, pos + 1, path);
      /* 写到这里才明白，这个 target-nums[pos]>=0 中的 ≥0 实在是精妙绝伦 */
      if (target - nums[pos] >= 0) {
        path.add(nums[pos]);
        backtrace(target - nums[pos], pos, path);
        path.remove(path.size() - 1);
      }
    }
  }

  /* 第二次尝试 借鉴别人的回溯 时间 2ms => 99.96% 空间 38.7MB => 40.03%  */
  static class Solution_second {

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
      List<List<Integer>> answers = new ArrayList<>();

      /* 考虑学习 健壮性考虑 */
      if (candidates == null || candidates.length == 0) return answers;

      findSum(candidates, target, answers, new ArrayList<Integer>(), 0);
      return answers;
    }

    /* 考虑学习 dfs 返回值为 void */
    private void findSum(
      int[] nums,
      int target,
      List<List<Integer>> answers,
      ArrayList<Integer> path,
      int i
    ) {
      if (target == 0) {
        /* 考虑学习，不是用 clone 再强制类型转换，而是利用 ArrayList 的特性支持 */
        answers.add(new ArrayList<Integer>(path));
        return;
      }
      /* 考虑学习 在这个位置处理 i 的合法越界问题 */
      if (i == nums.length) return;
      findSum(nums, target, answers, path, i + 1);
      if (target - nums[i] >= 0) {
        path.add(nums[i]);
        /* 考虑学习 更新 target 来代替对 lastSum 的依赖!!! */
        findSum(nums, target - nums[i], answers, path, i);
        path.remove(path.size() - 1);
      }
    }
  }

  /* 第一次尝试 回溯 时间 6ms => 20.13% 空间 38.6MB => 68.03% */
  static class Solution_first {

    int targetSum;
    int[] table;
    List<List<Integer>> answers = new ArrayList<List<Integer>>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
      this.table = candidates;
      this.targetSum = target;
      Arrays.sort(this.table);
      backtrace(new ArrayList<Integer>(), 0, 0);
      return answers;
    }

    private boolean backtrace(ArrayList<Integer> path, int lastSum, int pos) {
      if (lastSum == targetSum) {
        answers.add((ArrayList<Integer>) path.clone());
        return true;
      }
      if (lastSum < targetSum) {
        if (pos + 1 < table.length) {
          backtrace(path, lastSum, pos + 1);
        }
        path.add(table[pos]);
        backtrace(path, lastSum + table[pos], pos);
        path.remove(path.size() - 1);
      }
      return false;
    }
  }
}

#40 组合总和 II

• 如果说我原先的回溯算法是单起点多分支
• 那么，2ms范程的回溯算法就是多起点多分支
• 对于，某一个位置的元素可以不被选取，
  • 单起点多分支：途径节点，但是不accept这个节点
  • 多起点多分支：以这个节点作为子树的起点，那么对于兄弟子树而言，就没有对这个元素的访问了。

package Order300;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class T40_combination_sum_ii {

  public static void main(String[] args) {
    for (List<Integer> list : new Solution()
    .combinationSum2(new int[] { 10, 1, 2, 7, 6, 1, 5 }, 8)) {
      for (int x : list) {
        System.out.printf(" %d", x);
      }
      System.out.println();
    }
    System.out.println();
    for (List<Integer> list : new Solution()
    .combinationSum2(new int[] { 10, 1, 2, 7, 6, 1, 5 }, 8)) {
      for (int x : list) {
        System.out.printf(" %d", x);
      }
      System.out.println();
    }
  }

  static class Solution_2ms {

    List<List<Integer>> list = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
      Arrays.sort(candidates);
      dfs(candidates, target, 0);
      return list;
    }

    private void dfs(int[] candidates, int target, int index) {
      if (target == 0) {
        list.add(new ArrayList<>(path));
        return;
      }
      for (int i = index; i < candidates.length; i++) {
        if (candidates[i] <= target) {
          if (i > index && candidates[i] == candidates[i - 1]) {
            continue;
          }
          path.add(candidates[i]);
          dfs(candidates, target - candidates[i], i + 1);
          path.remove(path.size() - 1);
        }
      }
    }
  }

  /* 第二次尝试 改编自 2ms 范程 时间 2ms => 99.94% 空间 38.6% => 64.29% */
  static class Solution {

    int[] nums;
    List<List<Integer>> answers = new ArrayList<List<Integer>>();
    /* path只有尾部操作，所以，其实完全可以用 Deque 来做 */
    ArrayList<Integer> path = new ArrayList<Integer>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
      /* 健壮性考虑 */
      if (candidates == null || candidates.length == 0) return answers;
      this.nums = candidates;
      Arrays.sort(this.nums);
      // BaseNode.util.errPrintList(new ArrayList<Integer>() {{for (int i = 0; i < nums.length; i++) {add(nums[i]);}}},"nums");
      backtrace(target, 0);
      return answers;
    }

    private void backtrace(int target, int pos) {
      if (target == 0) {
        answers.add(new ArrayList<Integer>(path));
        return;
      }

      for (int i = pos; i < nums.length; i++) {
        if (nums[i] <= target) {
          /* 对于多次访问到的重复元素进行跳过 */
          if (i > pos && nums[i] == nums[i - 1]) continue;
          path.add(nums[i]);
          backtrace(target - nums[i], i + 1);/* 注意！此处应为 i+1 而非 pos+1 */
          path.remove(path.size() - 1);
        }
      }
    }
  }

  /* 第一次尝试 频率表 + 回溯 时间 4ms => 54.52% 空间 38.7MB => 39.91% */
  static class Solution_first {

    /* 用一个 int[2] 代替 元组（x,y） */
    List<int[]> numList = new ArrayList<int[]>();
    List<List<Integer>> answers = new ArrayList<List<Integer>>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
      /* 健壮性考虑 */
      if (candidates == null || candidates.length == 0) return answers;
      /**
       * 既要【去除重复解】又要【可以多次使用相同的数字】
       * 处理：
       * 第一步，排序
       * 第二步，过滤原数组为[(x,cnt)]
       * 例如 2，5，2，1，2 => [(1,1) (2,3) (5,1)]
       * 第三步，基于过滤后的数组来排序（而非基于原数组）
       */
      Arrays.sort(candidates);
      for (int x : candidates) {
        int index = numList.size() - 1;
        if (index < 0 || numList.get(index)[0] != x) {
          numList.add(new int[] { x, 1 });
        } else {
          numList.get(index)[1]++;
        }
      }
      backtrace(target, 0, new ArrayList<Integer>());
      return answers;
    }

    private void backtrace(int target, int pos, ArrayList<Integer> path) {
      if (target == 0) {
        answers.add(new ArrayList<Integer>(path));
        return;
      }
      if (pos == numList.size()) return;

      /* 根据 x,cnt 进行 accept x with {$timeCnt} times 多条递归路径 timeCnt in [0,cnt] */
      int x = numList.get(pos)[0];
      int cnt = numList.get(pos)[1];
      for (int i = 0; i <= cnt; i++) {
        if (target - x * i >= 0) {
          if (i > 0) path.add(x);
          backtrace(target - x * i, pos + 1, path);
        }
      }
      /**
       * 弹出之前往 path 中添加的 x
       * 这段代码确实有趣, 请试着理解为什么注释中的这段代码不行
       * int size = path.size();
       * for (int i = 1; i <= cnt && (size - i) >= 0; i++) {
       *   path.remove(size - i);
       * }
       * 答案是，缺少了条件 path.get(size-i) == x
       * 正确的写法 如下
       * int size = path.size();
       * for (
       *   int i = 1;
       *   i <= cnt && (size - i) >= 0 && path.get(size - i) == x;
       *   i++
       * ) {
       *   path.remove(size - i);
       * }
       */
      for (
        int lastIndex = path.size() - 1;
        lastIndex >= 0 && path.get(lastIndex) == x;
        lastIndex = path.size() - 1
      ) {
        path.remove(lastIndex);
      }
    }
  }
}