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

6月18日

最小的好进制

class Solution {
    public String smallestGoodBase(String n) {
        long nVal = Long.parseLong(n);
        int mMax = (int) Math.floor(Math.log(nVal) / Math.log(2));

        for (int m = mMax; m > 1; -- m) {
            int k = (int) Math.pow(nVal, 1.0 / m);
            long mul = 1, sum = 1;
            for (int i = 0; i < m; ++ i) {
                mul *= k;
                sum += mul;
            }
            if (sum == nVal) return Integer.toString(k);
        }

        return Long.toString(nVal - 1);
    }
}

注:
- Math.floor 下取整 返回值为double类型
- Math.ceil 上取整 返回值为double类型

6月17日

有效数字

剑指offer - 20

6月16日

石子游戏

区间dp

class Solution {
    public boolean stoneGame(int[] piles) {
        int n = piles.length;
        // f[i][j]表示在下标范围[i,j]中,当前玩家与另一个玩家的石子数量之差的最大值
        int[][] f = new int[n + 1][n + 1];
        for (int i = 0; i < n; ++ i) {
            f[i][i] = piles[i];
            for (int j = n - 1; j > i; -- j) {
                f[i][j] = Math.max(piles[j] - f[i][j - 1], piles[j] - f[i][j + 1]);
            }
        }
        return f[0][n - 1] > 0;
    }
}

博弈论

class Solution {
    public boolean stoneGame(int[] piles) {
        return true;
    }
}

6月15日

山脉数组的峰顶索引

二分

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

6月14日

猜数字大小

二分

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int l = 1, r = n;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (guess(mid) == 1) l = mid + 1;
            else r = mid;
        }
        return l;
    }
}

6月13日

第一个错误的版本

二分

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int l = 0, r = n;
        while (l < r) {
            int mid = l + (r - l) / 2;  // 防溢出
            if (isBadVersion(mid)) r = mid;
            else l = mid + 1;
        }
        return l;
    }
}

背包问题专题

6月12日

数位成本和为目标值的最大数字

完全背包

class Solution {
    public String largestNumber(int[] cost, int target) {
        int n = cost.length;

        String[] f = new String[target + 1];
        f[0] = "";

        for (int i = 1; i <= n; ++ i) {
            for (int j = cost[i - 1]; j <= target; ++ j) {
                if (f[j - cost[i - 1]] == null) continue;
                f[j] = max(String.valueOf(i) + f[j - cost[i - 1]], f[j]);
            }
        }
        return f[target] == null ? "0" : f[target];
    }

    public String max (String s1, String s2) {
        if (s2 == null) return s1;
        int n = s1.length(), m = s2.length();
        if (n != m) return n > m ? s1 : s2;

        for (int i = 0; i < n; ++ i) {
            if (s1.charAt(i) == s2.charAt(i))
                continue;
            return s1.charAt(i) > s2.charAt(i) ? s1 : s2;
        }
        return s1;
    }
}

6月11日

全平方数

完全背包

class Solution {
    public int numSquares(int n) {
        int m = (int)Math.sqrt(n) + 1;
        int[][] f = new int[m + 1][n + 1];
        for (int i = 2; i <= m; ++ i) Arrays.fill(f[i], Integer.MAX_VALUE);
        for (int i = 0; i <= n; ++ i) f[1][i] = i;

        for (int i = 2; i <= m; ++ i) {
            for (int j = 0; j <= n; ++ j) {
                f[i][j] = f[i - 1][j];
                if (i * i <= j) {
                    f[i][j] = Math.min(f[i][j], f[i][j - i * i] + 1);
                }
            }
        }
        return f[m][n];
    }
}

优化

class Solution {
    public int numSquares(int n) {
        int m = (int)Math.sqrt(n) + 1;
        int[] f = new int[n + 1];
        for (int i = 0; i <= n; ++ i) f[i] = i;

        for (int i = 2; i <= m; ++ i) {
            for (int j = i * i; j <= n; ++ j) {
                f[j] = Math.min(f[j], f[j - i * i] + 1);
            }
        }
        return f[n];
    }
}

6月10日

零钱兑换 II

完全背包问题

class Solution {
    public int change(int amount, int[] coins) {
        int n = coins.length;
        int[] f = new int[amount + 1];
        f[0] = 1;
        for (int i = 1; i <= n; ++ i) {
            for (int j = coins[i - 1]; j <= amount; ++ j) {
                f[j] += f[j - coins[i - 1]];
            }
        }
        return f[amount];
    }
}

6月9日

盈利计划

背包问题扩展

class Solution {
    static int mod = (int)(1e9 + 7);
    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        int m = profit.length;
        // dp[i][j][k] 表示在前 i 个工作中选择了 j 个员工,并且满足工作利润至少为 k 的情况下的盈利计划的总数目
        int[][][] f = new int[m + 1][n + 1][minProfit + 1];
        f[0][0][0] = 1;
        for (int i = 1; i <= m; ++ i) {
            for (int j = 0; j <= n; ++ j) {
                for (int k = 0; k <= minProfit; ++ k) {
                    if (j < group[i - 1]) f[i][j][k] = f[i - 1][j][k];
                    else f[i][j][k] =  (f[i - 1][j][k] + f[i - 1][j - group[i - 1]][\Math.max(0, k - profit[i - 1])]);
                }
            }
        }
        int ans = 0;
        for (int j = 0; j <= n; ++ j) {
            ans = (ans + f[m][j][minProfit]) % mod;
        }
        return ans;
    }
}

6月8日

最后一块石头的重量 II

转化为背包问题

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = Arrays.stream(stones).sum();
        int n = stones.length, m = sum / 2;
        boolean[][] f = new boolean[n + 1][m + 1];
        f[0][0] = true;
        for (int i = 1; i <= n; ++ i) {
            for (int j = 0; j <= m; ++ j) {
                f[i][j] = f[i - 1][j];
                if (j >= stones[i - 1] && !f[i][j])
                    f[i][j] = f[i - 1][j - stones[i - 1]];
            }
        }
        int idx = m;
        for (; idx >= 0; -- idx) {
            if (f[n][idx]) break;
        }
        return sum - 2 * idx;
    }
}

优化

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = Arrays.stream(stones).sum();
        int n = stones.length, m = sum / 2;
        boolean[] f = new boolean[m + 1];
        f[0] = true;
        for (int i = 1; i <= n; ++ i) {
            for (int j = m; j >= stones[i - 1]; -- j) {
                if (!f[j])
                    f[j] = f[j - stones[i - 1]];
            }
        }
        int idx = m;
        for (; idx >= 0; -- idx) {
            if (f[idx]) break;
        }
        return sum - 2 * idx;
    }
}

6月7日

目标和

计数型dp & 完全背包做法

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int n = nums.length;
        int sum = Arrays.stream(nums).sum();
        int diff = (sum - target) ;
        if (diff < 0 || diff % 2 != 0) return 0;
        int neg = diff / 2;
        int[][] f = new int[n + 1][neg + 1];
        f[0][0] = 1;
        for (int i = 1; i <= n; ++ i) {
            int num = nums[i - 1];
            for (int j = 0; j <= neg; ++ j) {
                f[i][j] = f[i - 1][j];
                if (j >= num)
                    f[i][j] += f[i - 1][j - num];
            }
        }
        return f[n][neg];

    }
}

优化

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int n = nums.length;
        int sum = Arrays.stream(nums).sum();
        int diff = (sum - target) ;
        if (diff < 0 || diff % 2 != 0) return 0;
        int neg = diff / 2;
        int[] f = new int[neg + 1];
        f[0] = 1;
        for (int i = 1; i <= n; ++ i) {
            int num = nums[i - 1];
            for (int j = neg; j >= num; -- j) {
                    f[j] += f[j - num];
            }
        }
        return f[neg];
    }
}

6月6日

一和零

01背包问题

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        int[][] f = new int[m + 1][n + 1];
        for (int i = 1; i <= len; ++ i) {
            int[] nums = getZerosOnes(strs[i - 1]);
            int zeros = nums[0], ones = nums[1];
            for (int j = m; j >= zeros; -- j) {
                for (int k = n; k >= ones; -- k) {
                    f[j][k] = Math.max(f[j][k], f[j - zeros][k - ones] + 1);
                }
            }
        }
        return f[m][n];
    }

    public int[] getZerosOnes (String s) {
        int[] ans = new int[2];
        int len = s.length();
        for (int i = 0; i < len; ++ i) {
            ans[s.charAt(i) - '0'] ++ ;
        }
        return ans;
    }
}

简化路径

class Solution {
    public String simplifyPath(String path) {
        String[] strs = path.split("/");
        Deque<String> dq = new LinkedList<>();
        for (String s : strs) {
            if (s.equals("") || s.equals("."))
                continue;
            if (s.equals("..")) {
                if (!dq.isEmpty()) dq.poll();
            } else {
                dq.push(s);
            }
        }
        StringBuilder sb = new StringBuilder();
        while (!dq.isEmpty()) {
            sb.append("/").append(dq.pollLast());
        }
        if (sb.length() == 0) sb.append('/');
        return sb.toString();
    }
}

6月5日

接雨水

双指针

class Solution {
    public int trap(int[] height) {
        int l = 0, r = height.length - 1;
        int lmax = l, rmax = r;
        int ans = 0;
        while (l < r) {
            if (height[l] < height[r]) {
                ++ l;
                if (height[l] >= height[lmax]) lmax = l;
                ans += height[lmax] - height[l];
            } else {
                -- r;
                if (height[r] >= height[rmax]) rmax = r;
                ans += height[rmax] - height[r];
            }
        }
        return ans;
    }
}

N皇后

DFS

class Solution {
    static int N = 20;
    static char[][] g;
    static boolean[] col = new boolean[N];
    static boolean[] dg = new boolean[N];
    static boolean[] udg = new boolean[N];
    public void dfs (int u, int n, List<List<String>> ans) {
        if (u == n) {
            List<String> list = new LinkedList<>();
            for (int i = 0; i < n; ++ i) list.add(String.valueOf(g[i]));
            ans.add(list);
            return;
        }
        for (int i = 0; i < n; ++ i) {
            if (!col[i] && !dg[u + i] && !udg[n + u - i]) {
                g[u][i] = 'Q';
                col[i] = dg[u + i] = udg[n + u - i] = true;
                dfs(u + 1, n, ans);
                col[i] = dg[u + i] = udg[n + u - i] = false;
                g[u][i] = '.';
            }
        }
    }

    public List<List<String>> solveNQueens(int n) {
        g = new char[n][n];
        for (int i = 0; i < n; ++ i) {
            for (int j = 0; j < n; ++ j) {
                g[i][j] = '.';
            }
        }
        List<List<String>> ans = new LinkedList<>();
        dfs(0, n, ans);
        return ans;
    }
}

6月4日

相交链表

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA, curB = headB;
        while (curA != curB) {
            if (curA!= null) curA = curA.next;
            else curA = headB;
            if (curB != null) curB = curB.next;
            else curB = headA;
        }
        return curA;
    }
}

旋转图像

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        // 先沿对角线翻转
        for (int i = 0; i < n; ++ i) {
            for (int j = 0; j < n - i - 1; ++ j) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[n - j - 1][n - i - 1];
                matrix[n - j - 1][n - i - 1] = tmp;
            }
        }

        // 上下翻转
        for (int i = 0; i < n / 2; ++ i) {
            for (int j = 0; j < n; ++ j) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[n - i - 1][j];
                matrix[n - i - 1][j] = tmp;
            }
        }
    }
}

6月3日

连续数组

class Solution {
    public int findMaxLength(int[] nums) {
        int n = nums.length;
        HashMap<Integer, Integer> map = new HashMap<>() {{
            put(0, -1);
        }};
        int ans = 0, cnt = 0;
        for (int i = 0; i < n; ++ i) {
            cnt += nums[i] % 2 == 0 ? -1 : 1;
            if (map.containsKey(cnt))
                ans = Math.max(ans, i - map.get(cnt));
            else
                map.put(cnt, i);
        }
        return ans;
    }
}

字典序的第K小数字⭐⭐

字典树

class Solution {
    public int findKthNumber(int n, int k) {
        long cur = 1;
        while (k > 1) {
            int sumNodes = getNodes(n, cur);
            if (k >= sumNodes) {
                cur += 1; // 向左走
                k -= sumNodes;
            } else {
                cur *= 10; // 向下走
                k --;
            }
        }
        return (int)cur;
    }

    // 获取节点cur下的所有节点数量(包括cur本身)
    public int getNodes(int n, long cur) {
        long next = cur + 1;
        long sumNodes = 0;
        while (cur <= n) {
            sumNodes += Math.min(n - cur + 1, next - cur);
            next *= 10;
            cur *= 10;
        }
        return (int)sumNodes;
    }
}

6月2日

连续的子数组和

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        int n = nums.length;
        HashMap<Integer,Integer> map = new HashMap<>(){{
            put(0, -1);
        }};
        int sum = 0;
        for (int i = 0; i < n; ++ i) {
            sum += nums[i];
            int mod = (sum % k + k) % k;
            if (map.containsKey(mod)) {
                if (i - map.get(mod) > 1)
                    return true;
            }
            else map.put(mod, i);
        }
        return false;
    }
}

重排链表

class Solution {
    public void reorderList(ListNode head) {
        if (head == null) return;
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode mid = slow.next;
        slow.next = null;
        ListNode list2 = reverseList(mid);
        mergeTwoList(head, list2);
    }

    // 翻转链表
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode tmp = cur.next;
            cur.next = prev;
            prev = cur;
            cur = tmp;
        }
        return prev;
    }

    // 合并链表
    public void mergeTwoList (ListNode list1, ListNode list2) {
        ListNode dummyNode = new ListNode();
        ListNode cur = dummyNode;
        int idx = 0;
        while (list1 != null && list2 != null) {
            if (idx % 2 == 0) {
                cur.next = list1;
                list1 = list1.next;
            } else {
                cur.next = list2;
                list2 = list2.next;
            }
            ++ idx;
            cur = cur.next;
        }
        cur.next = list1 == null ? list2 : list1;
    }
}

复原 IP 地址

回溯

class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> ans = new LinkedList<>();
        trackback(s, 0, 0, new StringBuilder(), ans);
        return ans;
    }

    private void trackback(String s, int idx, int segment, StringBuilder str, List<String> ans) {
        if (idx == s.length()) {
            if (segment == 4)
                ans.add(str.toString());
            return;
        }
        if (segment >= 4) return;
        if (str.length() != 0) str.append('.');
        if (s.charAt(idx) == '0') {
            str.append(s.charAt(idx));
            trackback(s, idx + 1, segment + 1, new StringBuilder(str), ans);
            return;
        }
        for (int i = idx; i < s.length() && i < idx + 3; ++ i) {
            if (Integer.parseInt(s.substring(idx, i + 1)) <= 255) {
                str.append(s.charAt(i));
                trackback(s, i + 1, segment + 1, new StringBuilder(str), ans);
            } else return;
        }
    }
}

编辑距离

线性dp

class Solution {
    public int minDistance(String word1, String word2) {
        int len1 = word1.length(), len2 = word2.length();
        if (len1 == 0 || len2 == 0) return len1 == 0 ? len2 : len1;
        int[][] f = new int[len1 + 1][len2 + 1];

        for (int i = 0; i <= len1; ++ i) f[i][0] = i;
        for (int i = 0; i <= len2; ++ i) f[0][i] = i;

        for (int i = 1; i <= len1; ++ i) {
            for (int j = 1; j <= len2; ++ j) {
                f[i][j] = Math.min(f[i - 1][j], f[i][j - 1]) + 1;
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    f[i][j] = Math.min(f[i][j], f[i - 1][j - 1]);
                } else {
                    f[i][j] = Math.min(f[i][j], f[i - 1][j - 1] + 1);
                }
            }
        }
        return f[len1][len2];
    }
}

6月1日

你能在你最喜欢的那天吃到你最喜欢的糖果吗?

前缀和 & 爆int

class Solution {
    public boolean[] canEat(int[] candiesCount, int[][] queries) {
        int n1 = queries.length;
        int n2 = candiesCount.length;
        long[] pre = new long[n2 + 1];
        for (int i = 1; i <= n2; ++ i) {
            pre[i] = pre[i - 1] + candiesCount[i - 1];
        }

        boolean[] ans = new boolean[n1];
        int i = 0;
        for (int[] q : queries) {
            long maxCnt = pre[q[0] + 1] - pre[0];
            long minCnt = pre[q[0]] - pre[0];
            long eatMaxCnt = (long)(q[1] + 1) * q[2];
            long eatMinCnt = q[1] + 1;
            if (eatMaxCnt <= minCnt || eatMinCnt > maxCnt)
                ans[i ++] = false;
            else ans[i ++] = true;
        }
        return ans;
    }
}

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