1. 回文链表

image-20200801140012736

思路一：使用数组

由于链表只能单向访问，故我们可以将链表中的值先保存到 List 中，再使用双指针分别指向 List 的头尾来依次判断对应元素是否相等

（也可以将所有的节点值入栈中，再比较各节点元素和栈顶元素是否相等）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        // 存入List
        ArrayList<Integer> list = new ArrayList<>();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
		
        // 使用双指针
        int i = 0, j = list.size() - 1;
        while (i < j) {
            // 由于 List 中存的是 Integer 对象，故使用 .equals 判断
            if (!list.get(i).equals(list.get(j))) return false;
            i++;
            j--;
        }
        return true;
    }
}

思路二：快慢指针 + 翻转

先通过快慢指针找到链表中点，再将中点后面的链表倒转，最后进行比较判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {

        ListNode slow = head, fast = head, pre = null;
        // 通过快慢指针找到链表中点
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 翻转后半个链表
        while (slow != null) {
            ListNode temp = slow.next;
            slow.next = pre;
            pre = slow;
            slow = temp;
        }
        // 比较判断
        while (head != null && pre != null) {
            if (head.val != pre.val) return false;
            head = head.next;
            pre = pre.next;
        }
        return true;
    }
}
image-20200801142525492

2. 二叉搜索树的最近公共祖先

image-20200801145403785

思路一：递归

因为题目中给的是 BST，故两个子节点的值一定在他们公共祖先的值左右

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 如果子节点的值均比根节点值小
        if (root.val > p.val && root.val > q.val) 
            return lowestCommonAncestor(root.left, p, q);
        // 如果子节点的值均比根节点值大
        else if (root.val < p.val && root.val < q.val) 
            return lowestCommonAncestor(root.right, p, q);
        // 如果子节点在根节点两侧
        else
            return root;
    }
}

思路二：迭代

与递归思路相同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        // Value of p
        int pVal = p.val;

        // Value of q;
        int qVal = q.val;

        // Start from the root node of the tree
        TreeNode node = root;

        // Traverse the tree
        while (node != null) {

            // Value of ancestor/parent node.
            int parentVal = node.val;

            if (pVal > parentVal && qVal > parentVal) {
                // If both p and q are greater than parent
                node = node.right;
            } else if (pVal < parentVal && qVal < parentVal) {
                // If both p and q are lesser than parent
                node = node.left;
            } else {
                // We have found the split point, i.e. the LCA node.
                return node;
            }
        }
        return null;
    }
}

/*
作者：LeetCode
链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/solution/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian--2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/

3. 删除链表中的节点

image-20200801150351668

思路

函数中只给了一个参数（要删除的节点），要充分利用所给的条件

  • 将要删除节点的值变为下一个节点的值
  • 将要删除节点的下一个节点变为下下个节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

4. 二叉树的所有路径

image-20200803084348259

思路一：递归

一开始想到使用递归，但是递归时无法使用 List 保存已有的路径和全部路径

参考官方解答后发现可以构造一个新的函数，将已有路径和全部路径都作为参数传入，这样就能完美解决这一问题！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    /**
     * @param root 当前节点
     * @param path 一条支路的路径
     * @param paths 全部支路的总和
     */
    public void constructPaths(TreeNode root, String path, LinkedList<String> paths) {
        if (root != null) {
            path += Integer.toString(root.val);
            if (root.left == null && root.right == null) paths.add(path);
            else {
                path += "->";
                constructPaths(root.left, path, paths);
                constructPaths(root.right, path, paths);
            }
        }
    }

    public List<String> binaryTreePaths(TreeNode root) {
        LinkedList<String> paths = new LinkedList<>();
        constructPaths(root, "", paths);
        return paths;
    }
}
image-20200803085808662

思路二：迭代

上面的算法也可以使用迭代（宽度优先搜索）的方法实现。我们维护一个队列，存储节点以及根到该节点的路径。一开始这个队列里只有根节点。在每一步迭代中，我们取出队列中的首节点，如果它是一个叶子节点，则将它对应的路径加入到答案中。如果它不是一个叶子节点，则将它的所有孩子节点加入到队列的末尾。当队列为空时，迭代结束。

作者：LeetCode
链接：https://leetcode-cn.com/problems/binary-tree-paths/solution/er-cha-shu-de-suo-you-lu-jing-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        LinkedList<String> paths = new LinkedList();
        if (root == null)
            return paths;

        LinkedList<TreeNode> node_stack = new LinkedList();
        LinkedList<String> path_stack = new LinkedList();
        node_stack.add(root);
        path_stack.add(Integer.toString(root.val));
        TreeNode node;
        String path;
        while (!node_stack.isEmpty()) {
            node = node_stack.pollLast();
            path = path_stack.pollLast();
            if ((node.left == null) && (node.right == null))
                paths.add(path);
            if (node.left != null) {
                node_stack.add(node.left);
                path_stack.add(path + "->" + Integer.toString(node.left.val));
            }
            if (node.right != null) {
                node_stack.add(node.right);
                path_stack.add(path + "->" + Integer.toString(node.right.val));
            }
        }
        return paths;
    }
}

/*
作者：LeetCode
链接：https://leetcode-cn.com/problems/binary-tree-paths/solution/er-cha-shu-de-suo-you-lu-jing-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/

5. 丑数

image-20200803090835004

思路：递归

  • 先排除 num 为 0 或 num 小于 0 的情况
  • 如果 num 能被 2 、3、5 整除，判断整除后的结果是否为丑数即可
  • num 等于 1 时返回 true，其余结果返回 false
1
2
3
4
5
6
7
8
9
class Solution {
    public boolean isUgly(int num) {
        if (num < 1) return false;
        if (num % 2 == 0) return isUgly(num / 2);
        if (num % 3 == 0) return isUgly(num / 3);
        if (num % 5 == 0) return isUgly(num / 5);
        return num == 1;
    }
}

5. 缺失数字

image-20200803145103333

方法一：排序

将数组排序后进行遍历，如果数组中元素与其下标不同，则为确实元素

1
2
3
4
5
6
7
8
9
class Solution {
    public int missingNumber(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i) return i;
        }
        return nums.length;
    }
}
image-20200803150619515

方法二：哈希表

将数组中的值存入 hash表 中，遍历 1 到 nums.length，返回哈希表中不包含的数

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int missingNumber(int[] nums) {

        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) set.add(nums[i]);
        for (int i = 0; i < nums.length; i++) {
            if (!set.contains(i)) return i;
        }
        return nums.length;
    }
}
image-20200803151135762

方法三：位运算

image-20200803151613269 
1
2
3
4
5
6
7
8
9
10
class Solution {
    public int missingNumber(int[] nums) {     
       int res = nums.length;
        for (int i = 0; i < nums.length; i++) {
            res ^= nums[i];
            res ^= i;
        }
        return res;
	}
}

方法四：数学方法

求 1 到 nums.length 的和，减去数组中所有元素的和，结果就是缺少的数字（有整型溢出风险）

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int missingNumber(int[] nums) {

        int sum = 0;
        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
        }
        // 数列求和公式： Sn = n(a1 + an) / 2
        return nums.length * (nums.length + 1) / 2 - sum;
    }
}