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

6月30日

二叉树的序列化与反序列化

剑指offer - 37

6月29日

Excel表列名称

1开始的26进制转换问题

class Solution {
    public String convertToTitle(int columnNumber) {
        StringBuilder sb = new StringBuilder();
        while (columnNumber != 0) {
            columnNumber --; // 关键
            int t = columnNumber % 26;
            sb.append((char)(t + 'A'));
            columnNumber /= 26;
        }
        return sb.reverse().toString();
    }
}

柱状图中最大的矩形

单调栈

class Solution {
    public int largestRectangleArea(int[] nums) {
        int n = nums.length;
        Deque<Integer> stack = new ArrayDeque<>();
        int[] left = new int[n + 1];
        int[] right = new int[n + 1];
        for (int i = 0; i < n; ++ i) {
            while (!stack.isEmpty() && nums[i] < nums[stack.peek()]) {
                right[stack.pop()] = i;
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) right[stack.pop()] = n;

        for (int i = n - 1; i >= 0; -- i) {
            while (!stack.isEmpty() && nums[i] < nums[stack.peek()]) {
                left[stack.pop()] = i;
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) left[stack.pop()] = -1;

        int ans = 0;
        for (int i = 0; i < n; ++ i) {
            ans = Math.max(ans, (right[i] - left[i] - 1) * nums[i]);
        }
        return ans;
    }
}

验证二叉搜索树

前序遍历 递归

class Solution {
    public boolean isValidBST(TreeNode root) {
        return preOrder(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean preOrder (TreeNode node, long lower, long upper) {
        if (node == null) return true;
        if (node.val <= lower || node.val >= upper)
            return false;
        return preOrder(node.left, lower, node.val) && preOrder(node.right, node.val, upper);
    }
}

中序遍历 迭代

class Solution {
    public boolean isValidBST(TreeNode root) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        long last = Long.MIN_VALUE;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (root.val <= last) return false;
            last = root.val;
            root = root.right;
        }
        return true;
    }
}

6月28日

公交路线

优化建图 + BFS

class Solution {
    public int numBusesToDestination(int[][] routes, int source, int target) {

        if (source == target) return 0;
        int n = routes.length;

        // 建图
        boolean[][] edge = new boolean[n][n];
        Map<Integer, List<Integer>> rec = new HashMap<>();
        for (int i = 0; i < n; ++ i) {
            for (int site : routes[i]) {
                List<Integer> list = rec.getOrDefault(site, new ArrayList<>());
                for (int j : list) {
                    edge[i][j] = edge[j][i] = true;
                }
                list.add(i);
                rec.put(site, list);
            }
        }

        int[] dis = new int[n];
        Arrays.fill(dis, -1);
        Queue<Integer> q = new LinkedList<>();
        for (int site : rec.getOrDefault(source, new ArrayList<>())) {
            dis[site] = 1;
            q.offer(site);
        }

        // 广度优先遍历
        while (!q.isEmpty()) {
            int x = q.poll();
            for (int y = 0; y < n; ++ y) {
                if (edge[x][y] && dis[y] == -1) {
                    dis[y] = dis[x] + 1;
                    q.offer(y);
                }
            }
        }

        // 筛选结果
        int ret = Integer.MAX_VALUE;
        for (int site : rec.getOrDefault(target, new ArrayList<>())) {
            if (site != -1) {
                ret = Math.min(ret, dis[site]);
            }
        }
        return ret == Integer.MAX_VALUE ? -1 : ret;
    }
}

6月27日

蛇梯棋

BFS

class Solution {
    public int snakesAndLadders(int[][] board) {
        int n = board.length;
        boolean[] visited = new boolean[n * n + 1];
        Queue<int[]> q = new LinkedList<int[]>();
        q.offer(new int[]{1, 0});
        while (!q.isEmpty()) {
            int[] p = q.poll();
            for (int i = 1; i <= 6; ++ i) {
                int next = p[0] + i;
                if (next > n * n)
                    break;
                int[] rc = id2rc(next, n); // 编号转坐标
                if (board[rc[0]][rc[1]] > 0) {
                    next = board[rc[0]][rc[1]];
                }
                if (next == n * n) { // 抵达终点
                    return p[1] + 1;
                }
                if (!visited[next]) {
                    visited[next] = true;
                    q.offer(new int[]{next, p[1] + 1});
                }
            }
        }
        return -1;
    }

    // 编号转为坐标
    private int[] id2rc(int id, int n) {
        int r = (id - 1) / n, c = (id - 1) % n;
        if (r % 2 == 1) {
            c = n - 1 - c;
        }
        return new int[]{n - 1 - r, c};
    }
}

6月26日

滑动谜题

BFS

class Solution {
    public int slidingPuzzle(int[][] board) {
        int n = board.length, m = board[0].length;
        String end = "123450";
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; ++ i)
            for (int j = 0; j < m; ++ j)
                sb.append(board[i][j]);

        String start = sb.toString();
        int step = 0;
        if (end.equals(start)) return step;

        // 定义向量
        int[] dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};

        Queue<String> q = new LinkedList<>();
        Set<String> seen = new HashSet<>();
        q.offer(start);
        seen.add(start);

        while (!q.isEmpty()) {
            ++step;
            int size = q.size();
            for (int i = 0; i < size; ++ i) {
                String str = q.poll();
                sb = new StringBuilder(str);
                int k = sb.indexOf("0");
                int x = k / 3, y = k % 3;
                for (int j = 0; j < 4; ++ j) {
                    int a = x + dx[j], b = y + dy[j];
                    if (a >= 0 && a < n && b >= 0 && b < m) {
                        int idx = a * 3 + b;
                        swap(sb, idx, k);
                        str = sb.toString();
                        if (str.equals(end)) return step;
                        if (!seen.contains(str)) {
                            seen.add(str);
                            q.offer(str);
                        }
                        swap(sb, idx, k); // 交换回来
                    }
                }
            }
        }
        return -1;
    }

    private void swap (StringBuilder sb, int i, int j) {
        char tmp = sb.charAt(i);
        sb.setCharAt(i, sb.charAt(j));;
        sb.setCharAt(j, tmp);
    }
}

6月25日

打开转盘锁

BFS

class Solution {
    public int openLock(String[] deadends, String target) {
        if (target.equals("0000")) return 0;

        Set<String> deadSet = new HashSet<>();
        for (String deadend : deadends)
            deadSet.add(deadend);

        if (deadSet.contains("0000")) return -1;

        Queue<String> q = new LinkedList<>();
        Set<String> seenSet = new HashSet<>();
        q.offer("0000");
        seenSet.add("0000");
        int step = 0;
        while (!q.isEmpty()) {
            ++ step;
            int n = q.size();
            for (int i = 0; i < n; ++ i) {
                String status = q.poll();
                for (String nextStatus : getNextNumList(status)) {
                    if (!seenSet.contains(nextStatus) && !deadSet.contains(nextStatus)) {
                        if (nextStatus.equals(target)) return step;
                        q.offer(nextStatus);
                        seenSet.add(nextStatus);
                    }
                }
            }
        }
        return -1;
    }

    private char numPrev (char ch) {
        return ch == '0' ? '9' : (char)(ch - 1);
    }

    private char numSucc (char ch) {
        return ch == '9' ? '0' : (char)(ch + 1);
    }

    public List<String> getNextNumList(String num) {
        List<String> numList = new ArrayList<>();
        char[] chars = num.toCharArray();
        for (int i = 0; i < 4; ++ i) {
            char ch = chars[i];
            chars[i] = numPrev(ch);
            numList.add(new String(chars));
            chars[i] = numSucc(ch);
            numList.add(new String(chars));
            chars[i] = ch;
        }
        return numList;
    }
}

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);
    }
}

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