本文最后更新于2021年10月4日,已超过 2 个月没更新!

44. 数字序列中某一位的数字

class Solution {
    public int findNthDigit(int n) {
        int digit = 1;
        long start = 1;
        long count = 9;
        while (n > count) {
            n -= count;
            digit ++;
            start *= 10;
            count = digit * start * 9;
        }
        long num = start + (n - 1) / digit;
        return Long.toString(num).charAt((n - 1) % digit) - '0';
    }
}

45. 把数组排成最小的数

快排

class Solution {
    public String minNumber(int[] nums) {
        int n = nums.length;
        String[] strs = new String[n];
        for (int i = 0; i < n; ++ i) {
            strs[i] = String.valueOf(nums[i]);
        }
        quickSort(strs, 0, n - 1);
        StringBuilder ans = new StringBuilder();
        for (String s : strs) {
            ans.append(s);
        }
        return ans.toString();
    }

    private void quickSort (String[] strs, int start, int end) {
        if (start >= end) return;
        int i = start, j = end;
        String pivot = strs[i];
        while (i < j) {
            while (i < j && (pivot + strs[j]).compareTo(strs[j] + pivot) <= 0) -- j;
            if (i < j) strs[i] = strs[j];
            while (i < j && (pivot + strs[i]).compareTo(strs[i] + pivot) >= 0) ++ i;
            if (i < j) strs[j] = strs[i];
        }
        strs[i] = pivot;
        quickSort(strs, start, i - 1);
        quickSort(strs, i + 1, end);
    }
}

46. 把数字翻译成字符串

递归

class Solution {
    int ans;
    public int translateNum(int num) {
        ans = 0;
        dfs(Integer.toString(num), 0);
        return ans;
    }

    private void dfs (String s, int idx) {
        if (idx >= s.length() - 1) {
            ++ ans;
            return;
        }
        dfs(s, idx + 1);
        if (s.charAt(idx) == '1' || (s.charAt(idx) == '2' && s.charAt(idx + 1) <= '5'))
            dfs(s, idx + 2);
    }
}

动规

class Solution {
    public int translateNum(int num) {
        String s = Integer.toString(num);
        int n = s.length();
        int[] f = new int[n];
        f[0] = 1;
        for (int i = 1; i < n; ++ i) {
            f[i] = f[i - 1];
            if (s.charAt(i - 1) == '1' || (s.charAt(i - 1) == '2' && s.charAt(i) <= '5'))
                f[i] += i - 2 >= 0 ? f[i - 2] : 1;
        }
        return f[n - 1];
    }
}

48. 最长不含重复字符的子字符串

双指针 & HashSet

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int n = s.length();
        int rk = 0, ans = 0;
        for (int i = 0; i < n; ++ i) {
            if (i != 0) set.remove(s.charAt(i - 1));
            while (rk < n && !set.contains(s.charAt(rk))) {
                set.add(s.charAt(rk));
                ++rk;
            }
            ans = Math.max(ans, rk - i);
        }
        return ans;
    }
}

49. 丑数

class Solution {
    public int nthUglyNumber(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        int p2 = 1, p3 = 1, p5 = 1;
        for (int i = 2; i <= n; ++ i) {
            int num2 = dp[p2] * 2;
            int num3 = dp[p3] * 3;
            int num5 = dp[p5] * 5;
            dp[i] = Math.min(num2, Math.min(num3, num5));
            if (dp[i] == num2) ++ p2;
            if (dp[i] == num3) ++ p3;
            if (dp[i] == num5) ++ p5;
        }
        return dp[n];
    }
}

51. 数组中的逆序对

归并排序

class Solution {
    int count;
    public int reversePairs(int[] nums) {
        count = 0;
        mergeSort(nums, 0, nums.length - 1);
        return count;
    }

    public void mergeSort(int[] nums, int l, int r) {
        if (l >= r) return;

        int mid = (l + r) >> 1;
        mergeSort(nums, l, mid);
        mergeSort(nums, mid + 1, r);

        int[] tmp = new int[r - l + 1];
        int idx = 0;
        int i = l, j = mid + 1;
        while (i <= mid && j <= r) {
            if (nums[i] <= nums[j]) {
                tmp[idx] = nums[i];
                count += j - (mid + 1); // 关键
                ++ i;
            } else {
                tmp[idx] = nums[j];
                ++ j;
            }
            ++ idx;
        }
        for (int k = i; k <= mid; ++ k) {
            tmp[idx] = nums[k];
            count += j - (mid + 1);// 相当于r - mid
            ++ idx;
        }
        for (int k = j; k <= r; ++ k) {
            tmp[idx] = nums[k];
            ++ idx;
        }
        // 修改原数组
        for (int k = l; k <= r; ++ k) {
            nums[k] = tmp[k - l];
        }
    }
}

52. 两个链表的第一个公共节点

双指针

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode cur1 = headA, cur2 = headB;
        while (cur1 != cur2) {
            if (cur1 == null) cur1 = headB;
            else cur1 = cur1.next;

            if (cur2 == null) cur2 = headA;
            else cur2 = cur2.next;
        }
        return cur1;
    }
}

53-I. 在排序数组中查找数字I

二分

class Solution {
    public int search(int[] nums, int target) {
        return helper(nums, target) - helper(nums, target - 1);
    }

    private int helper (int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (nums[mid] <= target) l = mid + 1;
            else r = mid - 1;
        }
        return l;
    }
}

53-II. 0~n-1中缺失的数字

二分

class Solution {
    public int missingNumber(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (nums[mid] == mid) l = mid + 1;
            else r = mid - 1;
        }
        return l;
    }
}

56-I. 数组中数字出现的次数

位异或分组

class Solution {
    public int[] singleNumbers(int[] nums) {
        int xorNum = 0;
        for (int num : nums) {
            xorNum ^= num;
        }
        int div = 1;
        while ((div & xorNum) == 0) {
            div <<= 1;
        }
        int[] ans = new int[2];
        for (int num : nums) {
            if ((num & div) == div) {
                ans[0] ^= num; 
            } else {
                ans[1] ^= num;
            }
        }
        return ans;
    }
}

56-II. 数组中数字出现的次数II

有限状态自动机

class Solution {
    public int singleNumber(int[] nums) {
        int ones = 0, twos = 0;
        for(int num : nums){
            ones = ones ^ num & ~twos;
            twos = twos ^ num & ~ones;
        }
        return ones;
    }
}

57. 和为s的两个数字

双指针

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            if (nums[l] + nums[r] < target) {
                ++ l;
            } else if (nums[l] + nums[r] > target) {
                -- r;
            } else {
                return new int[]{nums[l], nums[r]};
            }
        }
        return new int[]{};
    }
}

57-II. 和为s的连续正数序列

滑动窗口

class Solution {
    public int[][] findContinuousSequence(int target) {
        List<int[]> list = new ArrayList<>();
        for (int l = 1, r = 2; l < r;) {
            int tmpSum = (l + r) * (r - l + 1) / 2;
            if (tmpSum < target) ++ r;
            else if (tmpSum > target) ++ l;
            else {
                int[] tmp = new int[r - l + 1];
                for (int i = l; i <= r; ++ i) {
                    tmp[i - l] = i;
                }
                list.add(tmp);
                ++ l;
                ++ r;
            }
        }
        return list.toArray(new int[0][]);
    }
}

59-I. 滑动窗口的最大值⭐⭐

单调队列

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        if (n == 0 || k > n) return new int[0];

        int[] ans = new int[n - k + 1];
        Deque<Integer> q = new LinkedList<>();
        // 未形成窗口前
        for (int i = 0; i < k; ++ i) {
            while (!q.isEmpty() && q.peekLast() < nums[i])
                q.pollLast();
            q.addLast(nums[i]);
        }
        ans[0] = q.peekFirst();
        // 形成窗口后
        for (int i = k; i < n; ++ i) {
            if (!q.isEmpty() && nums[i - k] == q.peekFirst())
                q.pollFirst();
            while (!q.isEmpty() && q.peekLast() < nums[i])
                q.pollLast();
            q.addLast(nums[i]);
            ans[i - k + 1] = q.peekFirst();
        }
        return ans;
    }
}

59-II. 队列的最大值

单调双端队列

class MaxQueue {
    Queue<Integer> q;
    Deque<Integer> dq;

    public MaxQueue() {
        q = new LinkedList<>();
        dq = new LinkedList<>();
    }

    public int max_value() {
        return dq.isEmpty() ? -1 : dq.peekFirst();
    }

    public void push_back(int value) {
        q.offer(value);
        while (!dq.isEmpty() && dq.peekLast() < value) {
            dq.pollLast();
        }
        dq.addLast(value);
    }

    public int pop_front() {
        if (q.isEmpty()) return -1;
        int val = q.poll();
        if (!dq.isEmpty() && dq.peekFirst() == val)
            dq.pollFirst();
        return val;
    }
}

60. n个骰子的点数

动态规划 & 正向递推

class Solution {
    public double[] dicesProbability(int n) {
        //正向递推
        double[] dp = new double[6];
        Arrays.fill (dp, 1.0 / 6.0);

        for (int i = 2; i <= n; ++i) {
            double[] tmp = new double[i * 5 + 1];
            for (int j = 0; j < dp.length; ++j) {
                for (int k = 0; k < 6; ++k){
                    tmp[j + k] += dp[j] / 6.0;
                }
            }
            dp = tmp;
        }
        return dp;
    }
}

62. 圆圈中最后剩下的数字

class Solution {
    public int lastRemaining(int n, int m) {
        // 约瑟夫环问题
        // f(n) = (f(n - 1) + m) % i;
        // 最后一轮剩下2个人,所以从2开始反推
        int ans = 0;
        for (int i = 2; i <= n; ++i) {
            ans = (ans + m) % i;
        }
        return ans;
    }
}

63. 股票的最大利润

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length == 0) return 0;
        int minPrice = prices[0];
        int ans = 0;

        for (int i = 1; i < prices.length; ++i) {
            minPrice = Math.min(minPrice, prices[i]);
            ans = Math.max(ans, prices[i] - minPrice);
        }
        return ans;
    }
}

65. 不用加减乘除做加法

位运算

class Solution {
    public int add(int a, int b) {
        while (b != 0) {
            int c = (a & b) << 1; // 所有的进位
            a ^= b;// 不进位之和
            b = c;
        }
        return a;
    }
}

66. 构建乘积数组

双向前缀乘积

class Solution {
    public int[] constructArr(int[] a) {
        int n = a.length;
        if (n == 0) return new int[0];
        int[] b = new int[n];
        b[0] = 1;
        for (int i = 1; i < n; ++ i) {
            b[i] = b[i - 1] * a[i - 1];
        }
        int tmp = 1;
        for (int i = n - 2; i >= 0; -- i) {
            tmp *= a[i + 1];
            b[i] *= tmp;
        }
        return b;
    }
}

67. 把字符串转换成整数

一次遍历

class Solution {
    public int strToInt(String str) {
        char[] c = str.trim().toCharArray();
        int n = c.length;
        if (n == 0) return 0;
        int idx = 1, sign = 1;
        if (c[0] == '-') sign = -1;
        else if (c[0] != '+') idx = 0;
        long ans = 0;
        for (int i = idx; i < c.length && Character.isDigit(c[i]); ++ i) {
            ans = ans * 10 + c[i] - '0';
            ans = sign == 1 ? Math.min(ans, (long)Integer.MAX_VALUE) : Math.min(ans, -(long)Integer.MIN_VALUE); 
        }
        return (int) (ans * sign);
    }
}

同:LeetCode题库 – May - 5月21日

68-I. 二叉搜索树的最近公共祖先

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode ans = root;
        while (true) {
            if (ans.val < p.val && ans.val < q.val) ans = ans.right;
            else if (ans.val > p.val && ans.val > q.val) ans = ans.left;
            else break;
        }
        return ans;
    }
}

68-II. 二叉树的最近公共祖先

DFS & 剪枝

class Solution {
    TreeNode ans;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        ans= null;
        dfs (root, p, q);
        return ans;
    }

    private boolean dfs (TreeNode node, TreeNode p, TreeNode q) {
        if (node == null || ans != null) return false;
        boolean a = dfs(node.left, p, q);
        boolean b = dfs(node.right, p , q);
        if ((a && b) || (node.val == p.val || node.val == q.val) && (a || b)) {
            ans = node;
        }
        return a || b || node.val == p.val || node.val == q.val;
    }
}

Try and fail, but don't fail to try.