202. 快乐数

该题的难点主要在：如何检测出会发生循环。
如果检测出会发生循环，那么永远不可能变为1，则返回 false。
LC 201 ~ 300 - 图1
方法一：利用「哈希表可以快速判断元素是否在集合中」的特点。
把出现过的值加入到集合中，如果当前值存在集合中，那么就意味着会发生循环，返回 false。
方法二：判断链表是否有环的问题，弗洛伊德循环查找算法
方法三：数学法
所有的非快乐数只存在一个循环，也就是：4 ->16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4
不存在其他循环，只要出现这几个数中的其中一个，就可以判定一定会发生循环，返回 false。

206. 反转链表

反转的步骤：

  • 记录要反转的节点为 curr，记录 curr 的前一个节点为 prev，记录 curr 的后一个节点为 next
  • 改变 curr 的指向，即 curr.next = prev
  • prev 前进一个节点，即 prev = curr
  • curr 前进一个节点，即 curr = next
  • next 前进一个节点，即 next = curr.next（即上面的记录 curr 的后一个节点为 next，循环的起始）

  • 循环往复，直到 curr 为 null，prev 即为反转链表的头节点

    1. class Solution {
    2.   public ListNode reverseList(ListNode head) {
    3.       // curr 的前一个节点
    4.       ListNode prev = null;
    5.       ListNode curr = head;
    6.       // curr 的后一个节点
    7.       ListNode next = null;
    9.       while (curr != null) {
    10.           // next 前进
    11.           next = curr.next;
    12.           // 反转
    13.           curr.next = prev;
    14.           // prev 前进
    15.           prev = curr;
    16.           // curr 前进
    17.           curr = next;
    18.       }
    19.       return prev;
    20.   }
    21. }
    1. class Solution {
    2.   public ListNode reverseList(ListNode head) {
    3.       ListNode node = recursion(null, head);
    4.       return node;
    5.   }
    7.   private ListNode recursion(ListNode prev, ListNode curr) {
    8.       if (curr == null) {
    9.           return prev;
    10.       }
    12.       ListNode node = recursion(curr, curr.next);
    13.       curr.next = prev;
    14.       return node;
    15.   }
    16. }
    1. class Solution {
    2.   public ListNode reverseList(ListNode head) {
    3.       ListNode node = recursion(head);
    4.       return node;
    5.   }
    7.   private ListNode recursion(ListNode node) {
    8.       if ( node == null || node.next == null) {
    9.           return node;
    10.       }
    12.       ListNode node1 = recursion(node.next);
    13.       node.next.next = node;
    14.       node.next = null;
    15.       return node1;
    16.   }
    17. }

    209. 长度最小的子数组

    1. class Solution {
    2.   public int minSubArrayLen(int target, int[] nums) {
    4.       {
    5.           /*
    6.           时间复杂度：O(n)
    7.            */
    8.       }
    10.       // l、r 是窗口的左右边界
    11.       int l = 0;
    12.       int r = 0;
    13.       // sum 是窗口内 nums 的总和
    14.       int sum = 0;
    15.       int result = Integer.MAX_VALUE;
    17.       while (r < nums.length) {
    18.           sum += nums[r];
    19.           while (sum >= target && l <= r) {
    20.               result = Math.min(result, r - l + 1);
    21.               sum -= nums[l];
    22.               l++;
    23.           }
    24.           r++;
    25.       }
    27.       if (result == Integer.MAX_VALUE) {
    28.           return 0;
    29.       } else {
    30.           return result;
    31.       }
    32.   }
    33. }

216. 组合总和 III

  1. class Solution {
  3.     List<List<Integer>> results = new ArrayList<>();
  4.     List<Integer> result = new ArrayList<>();
  5.     int k;
  6.     int n;
  8.     public List<List<Integer>> combinationSum3(int k, int n) {
  9.         this.k = k;
  10.         this.n = n;
  11.         backtracking(1, 0);
  12.         return results;
  13.     }
  15.     // s 代表集合的起始元素 [s...9]
  16.     public void backtracking(int s, int sum) {
  17.         if (result.size() == k) {
  18.             if (sum == n) {
  19.                 results.add(new ArrayList<>(result));
  20.             }
  21.             return;
  22.         }
  24.         for (int i = s; i <= 9; i++) {
  25.             result.add(i);
  26.             backtracking(i + 1, sum + i);
  27.             result.remove(result.size() - 1);
  28.         }
  29.     }
  30. }
  1. class Solution {
  3.     List<List<Integer>> results = new ArrayList<>();
  4.     List<Integer> result = new ArrayList<>();
  5.     int k;
  6.     int n;
  8.     public List<List<Integer>> combinationSum3(int k, int n) {
  9.         this.k = k;
  10.         this.n = n;
  11.         backtracking(1, 0);
  12.         return results;
  13.     }
  15.     // s 代表集合的起始元素 [s...9]
  16.     public void backtracking(int s, int sum) {
  17.         if (result.size() == k) {
  18.             if (sum == n) {
  19.                 results.add(new ArrayList<>(result));
  20.             }
  21.             return;
  22.         }
  24.         // 剪枝:数量不足的情况 和 相加之和必定不能满足条件的情况(和太大、和太小)
  25.         for (int i = s; i <= 9 && (result.size() + 10 - i) >= k && (sum + (k - result.size()) * i) <= n && (sum + (k - result.size()) * 9) >= n; i++) {
  26.             result.add(i);
  27.             backtracking(i + 1, sum + i);
  28.             result.remove(result.size() - 1);
  29.         }
  30.     }
  31. }

有效的字母异位词

有思路，不写了
方法一：先对字符排序，再逐个比较
方法二：哈希表