6月24日

直线上最多的点数

哈希表 + 枚举 + 最大公约数算法

class Solution {
    public int maxPoints(int[][] points) {
        int n = points.length;
        if (n <= 2) return n;
        int ans = 0;
        for (int i = 0; i < n; ++ i) {
            if (ans >= n - i || ans > n / 2)
                break;
            Map<Integer, Integer> map = new HashMap<>();
            int max = 0;
            for (int j = i + 1; j < n; ++ j) {
                int a = points[i][0] - points[j][0];
                int b = points[i][1] - points[j][1];
                int k = gcb(a, b);
                int num = a / k, den = b / k;
                // 负号全部转移到分子上
                if (den < 0) {
                    num = -num;
                    den = -den;
                }
                Integer key = num + den * 20001;
                map.put(key, map.getOrDefault(key, 0) + 1);
                max = Math.max(max, map.get(key));
            }
            ans = Math.max(ans, max + 1);
        }
        return ans;
    }

    // 求最大公约数算法
    private int gcb (int a, int b) {
        return b == 0 ? a : gcb(b, a % b);
    }
}

6月23日

单词搜索

回溯

class Solution {
    char[][] board;
    int n, m;
    String word;
    boolean flag;
    public boolean exist(char[][] board, String word) {
        this.word = word;
        this.board = board;
        this.n = board.length;
        this.m = board[0].length;
        for (int i = 0; i < n; ++ i) {
            for (int j = 0; j < m; ++ j) {
                dfs(i, j, 0, new boolean[n][m]);
                if (flag) return true;
            }
        }
        return false;
    }

    public void dfs (int i, int j, int idx, boolean[][] visited) {
        if (flag || word.length() == idx) {
            flag = true;
            return;
        }
        if (i < 0 || i >= n || j < 0 || j >= m || visited[i][j]) {
            return;
        }
        if (word.charAt(idx) == board[i][j]) {
            visited[i][j] = true;
            dfs(i + 1, j, idx + 1, visited);
            dfs(i - 1, j, idx + 1, visited);
            dfs(i, j + 1, idx + 1, visited);
            dfs(i, j - 1, idx + 1, visited);
            visited[i][j] = false;
        }
        return;
    }
}

6月22日

字符串的排列⭐⭐

回溯 - 使用排序剪枝

class Solution {

    boolean[] visited;
    List<String> ans; 
    public String[] permutation(String s) {
        int n = s.length();
        visited = new boolean[n];
        ans = new ArrayList<>();
        char[] cs = s.toCharArray();
        Arrays.sort(cs);
        dfs(cs, 0, "");
        return ans.toArray(new String[0]);
    }

    private void dfs(char[] cs, int pos, String s) {
        if (pos == cs.length) {
            ans.add(s);
            return;
        }
        for (int i = 0; i < cs.length; ++ i) {
            // 确保相同字符传入同一目标位置的动作只发生一次
            if (i > 0 && !visited[i - 1] && cs[i] == cs[i - 1]) continue; // 剪枝
            if (!visited[i]) {
                visited[i] = true;
                dfs(cs, pos + 1, s + cs[i]);
                visited[i] = false;
            }
        }
    }
}

回溯 - 使用set剪枝

class Solution {
    List<String> ans = new ArrayList<>();
    char[] c;
    public String[] permutation(String s) {
        c = s.toCharArray();
        dfs(0);
        return ans.toArray(new String[0]);
    }

    private void dfs (int x) {
        if (x == c.length - 1) {
            ans.add(String.valueOf(c));
            return;
        }
        // 确保相同字符传入同一目标位置的动作只发生一次
        Set<Character> set = new HashSet<>();
        for (int i = x; i < c.length; ++ i) {
            if (set.contains(c[i])) continue;  // 剪枝
            set.add(c[i]);
            swap(i, x);
            dfs(x + 1);
            swap(i, x);
        }
    }

    private void swap (int a, int b) {
        char tmp = c[a];
        c[a] = c[b];
        c[b] = tmp;
    }
}

6月21日

二进制手表

二进制枚举

class Solution {
    public List<String> readBinaryWatch(int turnedOn) {
        List<String> ans = new ArrayList<>();
        // 二进制枚举
        for (int i = 0; i < 1 << 10; ++ i) {
            int h = i >> 6, m = i - (h << 6);
            if (h < 12 && m < 60 && Integer.bitCount(i) == turnedOn)
                ans.add(h + ":" + (m < 10 ? "0" : "") + m);
        }
        return ans;
    }
}

设计哈希集合⭐⭐

class MyHashSet {
    private static final int BASE = 769;
    private LinkedList[] data;

    /** Initialize your data structure here. */
    public MyHashSet() {
        data = new LinkedList[BASE];
        for (int i = 0; i < BASE; ++ i) {
            data[i] = new LinkedList<Integer>();
        }
    }

    public void add(int key) {
        int idx = hash(key);
        if (!data[idx].contains(key)) {
            data[idx].add(key);
        }
    }

    public void remove(int key) {
        int idx = hash(key);
        data[idx].remove((Integer)key); // 这里要转为 Integer 否则传入的参数为下标而非元素
    }

    /** Returns true if this set contains the specified element */
    public boolean contains(int key) {
        int idx = hash(key);
        return data[idx].contains(key);
    }

    private int hash(int key) {
        return key % BASE;
    }
}

设计哈希映射⭐⭐

class MyHashMap {

    private static final int BASE = 769;
    private LinkedList[] data;

    /** Initialize your data structure here. */
    public MyHashMap() {
        data = new LinkedList[BASE];
        for (int i = 0; i < BASE; ++ i) {
            data[i] = new LinkedList<Pair>();
        }
    }

    /** value will always be non-negative. */
    public void put(int key, int value) {
        int idx = hash(key);
        Iterator<Pair> iterator = data[idx].iterator();
        while (iterator.hasNext()) {
            Pair e = iterator.next();
            if (e.getKey() == key) {
                e.setVal(value);
                return;
            }
        }
        data[idx].offerLast(new Pair(key, value));
    }

    /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
    public int get(int key) {
        int idx = hash(key);
        Iterator<Pair> iterator = data[idx].iterator();
        while (iterator.hasNext()) {
            Pair e = iterator.next();
            if (e.getKey() == key) {
                return e.getVal();
            }
        }
        return -1;
    }

    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    public void remove(int key) {
        int idx = hash(key);
        Iterator<Pair> iterator = data[idx].iterator();
        while (iterator.hasNext()) {
            Pair e = iterator.next();
            if (e.getKey() == key) {
                data[idx].remove(e);
                return;
            }
        }
    }

    private int hash(int key) {
        return key % BASE;
    }

    private class Pair{
        private int key;
        private int val;

        public Pair(int key, int val) {
            this.key = key;
            this.val = val;
        }

        public int getKey() {
            return key;
        }

        public int getVal() {
            return val;
        }

        public void setKey(int key) {
            this.val = val;
        }

        public void setVal(int val) {
            this.val = val;
        }
    }
}

6月20日

皇位继承顺序

多叉树前序遍历

class ThroneInheritance {
    HashMap<String, List<String>> edges;
    HashSet<String> deads;
    String king;

    public ThroneInheritance(String kingName) {
        edges = new HashMap<String, List<String>>();
        deads = new HashSet<String>();
        king = kingName;
    }

    public void birth(String parentName, String childName) {
        List<String> children = edges.getOrDefault(parentName, new ArrayList<String>());
        children.add(childName);
        edges.put(parentName, children);
    }

    public void death(String name) {
        deads.add(name);
    }

    public List<String> getInheritanceOrder() {
        List<String> ans = new ArrayList<>();
        preOrder(ans, king);
        return ans;
    }

    private void preOrder(List<String> ans ,String name) {
        if (!deads.contains(name)) ans.add(name);

        List<String> children = edges.getOrDefault(name, new ArrayList<String>());
        for (String child : children)
            preOrder(ans, child);
    }
}

6月19日

串联字符串的最大长度

回溯

class Solution {
    public int maxLength(List<String> arr) {
        List<Integer> masks = new ArrayList<>();
        // 预处理 获取有没有重复字符的字符串对应的mask
        for (String s : arr) {
            int n = s.length();
            int mask = 0;
            for (int i = 0; i < n; ++ i) {
                int ch = s.charAt(i) - 'a';
                if (((mask >> ch) & 1) == 1) {
                    mask = 0;
                    break;
                }
                mask |= 1 << ch;
            }
            if (mask > 0) masks.add(mask);
        }
        // 开始回溯
        List<Integer> res = new ArrayList<>();
        backTrack(masks, 0, 0, res);
        return res.stream().max((x ,y) -> x - y).get(); // stream流取集合最大值
    }

    // 回溯
    private void backTrack(List<Integer> masks, int pos, int ans, List<Integer> res) {
        if (pos == masks.size()) {
            res.add(Integer.bitCount(ans));
            return;
        }
        int mask = masks.get(pos);
        if ((mask & ans) == 0) backTrack(masks, pos + 1, ans | mask, res);
        backTrack(masks, pos + 1, ans, res);
    }
}

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.