给一个可以任意摆放的keypad和一个字符串, 求如果得到这个字符串最少按几次keypad.

因为keypad只有0-9, 所以这题和频率大小有关, 贪婪算法.

class Solution {
    class Pair{
        int cnt;
        char c;
        public Pair(int cnt, char c){
            this.cnt = cnt;
            this.c = c;
        }
    }
    public int minimumKeypresses(String s) {
        int res = 0;
        Map<Character, Integer> map = new HashMap<>();
        for(char c : s.toCharArray())
            map.put(c, map.getOrDefault(c, 0) + 1);
        List<Pair> pairs = new ArrayList<>();
        for(Map.Entry<Character, Integer> entry : map.entrySet())
            pairs.add(new Pair(entry.getValue(), entry.getKey()));
        Collections.sort(pairs, (a, b) -> (b.cnt - a.cnt));
        int i = 0;
        Map<Character, Integer> keypad = new HashMap<>();
        for(Pair p : pairs) {
            map.put(p.c,(i / 9) + 1);
            i++;
        }
        for(char c : s.toCharArray())
            res += map.get(c);
        return res;
    }
}

给一个二叉树， 求树中有几个node的左子树和右子树的平均值等于root的值。、

这题就算dfs算一下即可。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int res = 0;
    public int averageOfSubtree(TreeNode root) {
        if(root == null)
            return 0;
        dfs(root);
        return res;
    }
    
    public int[] dfs(TreeNode root) {
        if(root == null)
            return new int[]{0,0};
        int[] left = dfs(root.left);
        int[] right = dfs(root.right);
        int sum = left[0] + right[0] + root.val;
        int count = left[1] + right[1] + 1;
        if(Math.floor(sum / count) == root.val)
            res++;
        return new int[]{sum, count};
    }
}

给一个字符串组, 和一个string, 求这个string有几个prefix在这个数组里.

class Solution {
    public int countPrefixes(String[] words, String s) {
        Set<String> set = new HashSet<>();
        for(int i = 1; i <= s.length(); i++){
            set.add(s.substring(0,i));
        }
        int res =0;
        for(String w : words)
            if(set.contains(w))
                res++;
        return res;
    }
}

给一个数, 给一个数组, 删除树上的数组的节点. 然后返回删除后的森林(不连接的节点)

这题注意的是删完后要看下是否有root….

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
        List<TreeNode> res = new ArrayList<>();
        Set<Integer> d = new HashSet<>();
        for(int n: to_delete)
            d.add(n);
        if(!d.contains(root.val))
            res.add(root);
        inorder(res, root, d);
        return res;
    }
    
    public TreeNode inorder(List<TreeNode> res, TreeNode root, Set<Integer> d){
        if(root == null)
            return null;
        root.left = inorder(res, root.left, d);
        root.right = inorder(res, root.right, d);
        if(d.contains(root.val)){
            d.remove(root.val);
            if(root.left != null)
                res.add(root.left);
            if(root.right != null)
                res.add(root.right);
            return null;
        }
        return root;
    }
}

给一个数组,里面是灯能覆盖的范围, 给一个数组, 里面是requirement, 求有多少个位置的灯meet requirement.

这题就是range addition升级版, 因为要考虑inclusive的覆盖问题,所以建数组的时候, 我们多加一个数. 这样相当于把数组扩展了1位.

class Solution {
    public int meetRequirement(int n, int[][] lights, int[] requirement) {
        int[] ary = new int[n + 1];
        for(int[] l : lights) {
            int start = Math.max(0, l[0] - l[1]);
            int end = Math.min(n, l[0] + l[1] + 1);
            ary[start]++;
            ary[end]--;
        }
        int cur = 0;
        int res = 0;
        for(int i = 0; i < n; i++) {
            cur += ary[i];
            if(cur >= requirement[i])
                res++;
        }
        return res; 
    }
}

给两个字符串, 长度一样, 是字符对应的mapping, 给一个字符串, 求mapping后字典序最小的结果.

典型的并查集模板题.

class Solution {
    public String smallestEquivalentString(String s1, String s2, String baseStr) { 
        unionfind uf = new unionfind(26);
        int n = s1.length();
        for(int i = 0; i < n; i++){
            char x = s1.charAt(i);
            char y = s2.charAt(i);
            uf.union((int)(x - 'a'),(int)(y - 'a'));
        }
        StringBuilder sb = new StringBuilder();
        for(char c : baseStr.toCharArray()){
            sb.append((char)('a' + uf.find(c - 'a')));
        }
        return sb.toString();
    }
    
    class unionfind{
        int[] a;
        public unionfind(int n){
            a = new int[n];
            for(int i = 0; i < n; i++)
                a[i] = i;
        }
        public int find(int i) {
            if(a[i] == i)
                return i;
            a[i] = find(a[i]);
            return a[i];
        }
        public void union(int i, int j){
            int x = find(i);
            int y = find(j);
            if(x != y){
                if(x < y)
                    a[y] = x;
                else
                    a[x] = y;
            }
        }
    }
}

给两个数组,a和b, 两个人从[1,a]的正整数轮流取数, 不能取相同的数字, 不能取了就算输了, 两个人都是选择自己最佳方案, 求胜负.

看似博弈论, 起始就是便利所有可能, 没有优化的地方.

这题傻逼在于, 它非要让状态压缩, 就tm一个最大32个数字的boolean数组, 非让用bitmask压一下表示状态, 不然就TLE, 我真是服了

class Solution {
    public boolean canIWin(int m, int d) {
        Map<Integer, Boolean> memo = new HashMap<>();
        boolean[] visited = new boolean[m + 1];
        Arrays.fill(visited, false);
        if(m >= d)
            return true;
        if(m*(m+1) / 2 < d)
            return false;
        return dfs(memo, m, d, visited);
    }
    
    public int mask(boolean[] visited){
        int res = 0;
        for(int i = 0; i < visited.length; i++){
            if(visited[i]){
                res |= (1 << i);
            }
        }
        return res;//10100111
    }
    
    public boolean dfs(Map<Integer, Boolean> memo, int m, int d, boolean[] visited){
        if(d <= 0)
            return false;
        int encode = mask(visited);
        if(memo.containsKey(encode))
            return memo.get(encode);
        for(int i = 1; i <=m; i++){
            if(!visited[i]){
                visited[i] = true;
                boolean res = dfs(memo, m, d - i, visited);
                visited[i] = false;
                if(!res){
                     memo.put(encode, true);
                     return true;
                }
            }
        }
        memo.put(encode, false);
        return false;
    }
}

给一个长度为length的数组和一个update[from, to, val]query. 求跑完query的结果.

这题用一个diff数组记录变化的起始和结果的地方, 这里可以看成累计频率的记录. 所以在结果的时候要把累积多余的val减去.

class Solution {
    public int[] getModifiedArray(int length, int[][] updates) {
        int[] diff = new int[length];
        for(int[] u : updates){
            diff[u[0]] += u[2];
            if(u[1] < length - 1)
                diff[u[1] + 1] -= u[2]; // remove the increament 
        }
        int cur = 0;
        int[] res = new int[length];
        for(int i = 0; i < length; i++){
            cur += diff[i];
            res[i] = cur;
        }
        return res;
    }
}

给一个数字n, 按照以下处理后, 求结果第k个大的数字是什么.

• if x is even then x = x / 2
• if x is odd then x = 3 * x + 1

肯定要算下的, 用memo算下, 然后建个map存下, 然后排序, 然后找第k个.

class Solution {
    Map<Integer, Integer> map = new HashMap<>();
    class Pair{
        int a;
        int b;
        Pair(int a, int b){
            this.a = a;
            this.b = b;
        }
    }
    public int getKth(int lo, int hi, int k) {
        List<Pair> list = new ArrayList<>(); 
        for(int i = lo; i <= hi; i++)
            list.add(new Pair(power(i), i));
        Collections.sort(list, (a, b) -> {
            if(a.a == b.a)
                return a.b - b.b;
            else
                return a.a - b.a;
        });
        k--;
        return list.get(k).b;
    }
    public int power(int n){
        if(n == 1)
            return 0;
        if(map.containsKey(n))
            return map.get(n);
        if(n % 2 == 0){
            map.put(n, 1 + power(n / 2));
        }
        else{
            map.put(n, 1 + power(3 * n + 1));
        }
        return map.get(n);
    }
}

给n个人, 坐n个座位, 第一个人随机选, 问第n个人坐到自己座位的概率.

这题就多写几个例子就行了

class Solution {
    public double nthPersonGetsNthSeat(int n) {
        if(n == 1)
            return 1d;
        if(n == 2)
            return 0.5;
        return 0.5;
    }
}

// f(n) = 1/n+ 1/n*f(n-1)