给一个target node和一个范围k, 在一个树上找距离k远的所有node.

这题的node可以跨越root, 也可以是parent.

我是重构整个图..加了个父节点.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    class Node{
        Node(int x) {this.val = x;}
        int val;
        Node p;
        Node l;
        Node r;
    }
    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
        Node nr = new Node(root.val);
        dfs(root, null, nr, null);
        List<Integer> res = new ArrayList<>();
        Node nt = find(target.val, nr);
        Queue<Node> q = new LinkedList<>();
        q.add(nt);
        Set<Node> set = new HashSet<>();
        set.add(nt);
        while(k > 0){
            int size = q.size();
            for(int i = 0; i < size; i++){
                Node c = q.poll();
                if(c.l != null && !set.contains(c.l)){
                    set.add(c.l);
                    q.add(c.l);
                }
                if(c.r != null && !set.contains(c.r)){
                    set.add(c.r);
                    q.add(c.r);
                }
                if(c.p != null && !set.contains(c.p)){
                    set.add(c.p);
                    q.add(c.p);
                }
            }
            k--;
        }
        for(Node cc : q)
            res.add(cc.val);
        return res;
    }
    public Node find(int val, Node nr) {
        if(nr == null)
            return null;
        if(nr.val == val)
            return nr;
        Node l = find(val, nr.l);
        Node r = find(val, nr.r);
        return l == null ? r : l;
    }
    public void dfs(TreeNode cur, TreeNode parent, Node nr, Node nrp){
        if(cur == null)
            return;
        nr.val = cur.val;
        nr.p = nrp;
        if(cur.left != null){
            nr.l = new Node(cur.left.val);
            dfs(cur.left, cur, nr.l, nr);
        }
        if(cur.right != null){
            nr.r = new Node(cur.right.val);
            dfs(cur.right, cur, nr.r, nr);
        }
    }
}

给一个mapping数组, 给一个数组nums, 求按照mapping数组转化后的数字的排列nums.

这题就是存一下转化后的数字, 然后排列即可. 需要注意java里面的lambda不能比较primitive type

class Solution {
    public int[] sortJumbled(int[] mapping, int[] nums) {
        Integer[] nn = new Integer[nums.length];
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            nn[i] = nums[i];
            map.put(nums[i], map.getOrDefault(nums[i], convert(nums[i],mapping)));
        }
        Arrays.sort(nn, (a, b) -> (map.get(a) - map.get(b)));
        for(int i = 0; i < nums.length; i++){
            nums[i] = nn[i];
        }
        return nums;
    }
    
    private int convert(int n, int[] mapping){
        StringBuffer sb = new StringBuffer();
        if(n == 0)
            return mapping[0];
        while(n != 0){
            sb.insert(0,mapping[n % 10]);
            n /= 10;
        }
        return Integer.valueOf(sb.toString());
    }
}

给一个2d数组, 里面是一颗数, 用[parent, child, isleft]的形式表达, 求返回这个树.

这题建树不难, 找到root, 需要记录一下所有的parent, 因为只有一个root是不会成为别人的child的.

/**
 * 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 TreeNode createBinaryTree(int[][] descriptions) {
        Map<Integer, TreeNode> map = new HashMap<>();
        Set<Integer> set = new HashSet<>(); // use to find the root;
        for(int[] d : descriptions){
            TreeNode node = map.getOrDefault(d[0], new TreeNode(d[0]));
            TreeNode child = map.getOrDefault(d[1], new TreeNode(d[1]));
            if(d[2] == 1){
                node.left = child;
            }
            else
            {
                node.right = child;
            }
            map.put(d[0], node);
            map.put(d[1], child);
            set.add(d[0]);
        }
        for(int[] d : descriptions){
            set.remove(d[1]);
        }
        return map.get(set.iterator().next());
    }
}

给两个字符串s和t, 能任意在后边添加字符, 求最少多少步后, 两个字符串能变成anagram.

这题就count下就行了…

class Solution {
    public int minSteps(String s, String t) {
        int res = 0;
        int[] count_s = new int[26];
        int[] count_t = new int[26];
        for(char c : s.toCharArray())
            count_s[c - 'a']++;
        for(char c : t.toCharArray())
            count_t[c - 'a']++;
        for(int i = 0; i < 26; i++){
            res += Math.abs(count_s[i] - count_t[i]);
        }
        return res;
    }
}

给一个string, 求unique的相同字频的子字符串.

这题吧, 我看用rolling hash做能快点, 但是我用的count做的.

class Solution {
    public int equalDigitFrequency(String s) {
        Set<String> set = new HashSet<>();
        int n = s.length();
        for(int i = 0; i < n; i++) {
            int[] count = new int[26];
            for(int j = i; j < n; j++) { 
                count[s.charAt(j) - '0']++;
                if(check(count))
                    set.add(s.substring(i, j + 1));
            }
        }
        return set.size();
    }
    public boolean check(int[] count) { 
        int nn = -1;
        for(int n : count){
            if(n != 0)
            {
                if(nn == -1)
                    nn = n;
                else{
                    if(nn != n)
                        return false;
                }
            }
        }
        return true;
    }
}

class Solution {
    public int prefixCount(String[] words, String pref) {
        int res = 0;
        for(String w : words){
            if(w.startsWith(pref))
                res++;
        }
        return res;
    }
}

给一个数组和一个数字key, 求当数组中一个元素等于key的时候, 下一个元素的出现频数最大的数字.

class Solution {
    public int mostFrequent(int[] nums, int key) {
        int[] count = new int[1001];
        for(int i = 0; i < nums.length - 1; i++){
            if(nums[i] == key)
                count[nums[i + 1]]++;
        }
        int max = -1;
        int max_index = -1;
        for(int i = 0; i < 1001; i++){
            if(count[i] > max){
                max = count[i];
                max_index = i;
            }
        }
        return max_index;
    }
}

class Solution {
    public List<String> cellsInRange(String s) {
        String[] strs = s.split(":");
        String start = strs[0];
        String end = strs[1];
        List<String> res = new ArrayList<>();
        for(char a = start.charAt(0); a <= end.charAt(0); a++){
            for(char b = start.charAt(1); b <= end.charAt(1); b++){
                res.add(""+a+b);
            }
        }
        return res;
    }
}

给一个数组和一个key和一个数字k, 求数组中等于k的index的范围k的所有index, 要求答案排序.

用linkedhashmap去重.

class Solution {
    public List<Integer> findKDistantIndices(int[] nums, int key, int k) {
        List<Integer> res = new ArrayList<>();
        Set<Integer> set = new LinkedHashSet<>();
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] == key) {
                for(int j = Math.max(i - k, 0); j <= Math.min(i + k, nums.length - 1); j++)
                    set.add(j);
            }
        }
        for(int n : set)
            res.add(n);
        return res;
    }
}

给一个数组, 问能不能分成pair, pair的定义是两个相同的数字.

class Solution {
    public boolean divideArray(int[] nums) {
        int[] count = new int[550];
        for(int n : nums)
            count[n]++;
        for(int n : count)
            if(n % 2 != 0)
                return false;
        return true;
    }
}