求数组中三个数字相加等于第四个数字的组合的个数.

用map优化一维.

class Solution {
    public int countQuadruplets(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        int res = 0;
        for(int i = 0; i < nums.length; i++){
            for(int j = i + 1; j < nums.length; j++){
                for(int k = j + 1; k < nums.length; k++)
                {
                    res += map.getOrDefault(nums[k] - nums[j] - nums[i], 0);
                }
            }
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        return res;
    }
}

求最小的, 最大pair和..

这题就是先sort, 然后前后加求最大.

class Solution {
    public int minPairSum(int[] nums) {
        Arrays.sort(nums);
        int i = 0;
        int j = nums.length - 1;
        int res = 0;
        while(i < j){
            res = Math.max(res, nums[i] + nums[j]);
            i++;
            j--;
        }
        return res;
    }
}

给两个数组, 求重新排序后, 数字的积的和最小是多少.

这题就是大*小, 所以排序一下, 然后插着乘.

class Solution {
    public int minProductSum(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int res = 0;
        for(int i = 0; i < nums1.length; i++){
            res += nums1[i] * nums2[nums2.length - 1 - i];
        }
        return res;
    }
}

给一个二叉树, 问上面有多少个node的val等于左子树和右子树的和.

这题就travseal 一下就行了

/**
 * 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 equalToDescendants(TreeNode root) {
        count(root);
        return res;
    }
    
    public int count(TreeNode root){
        if(root == null)
            return 0;
        int left = count(root.left);
        int right = count(root.right);
        if(root.val == left+right)
            res++;
        return root.val + left + right;
    }
}

给一个string的数组, 求里面的数字是否能通过移动字符, 变成同一个string.

这题就是统计一下所有的字符, 然后对字符串组长度做整除, 看看是不是能整除.

class Solution {
    public boolean makeEqual(String[] words) {
        int[] count = new int[26];
        for(String w : words)
            for(char c : w.toCharArray()){
                count[c - 'a']++;
            }
        for(int i = 0; i < 26; i++)
            if(count[i] % words.length != 0)
                return false;
        return true;
    }
}

给一个ranges的数组, 求[left, right]之间的数字是否都能被ranges数组覆盖.

class Solution {
    public boolean isCovered(int[][] ranges, int left, int right) {
        int j = 0; 
        for(int i = left; i <= right; i++){
            boolean found = false;
            for(int[] r : ranges){
                if(r[0] <= i && i <= r[1]){
                    found = true;
                    break;
                }
            }
            if(!found)
                return false;
        }
        return true;
    }
}

给一个string和一个char数组, 表示坏的键盘的字符, 问能组成几个string的word.

class Solution {
    public int canBeTypedWords(String text, String brokenLetters) {
        String[] strs = text.split(" ");
        int res = 0;
        Set<Character> set = new HashSet<>();
        for(char c : brokenLetters.toCharArray())
            set.add(c);
        for(String s : strs){
            boolean add = true;
            for(char c : s.toCharArray())
                if(set.contains(c)){
                    add = false;
                    break;
                }
            if(add)
                res++;
        }
        return res;
    }
}

给一个parttern数组和一个string, 问有多少这个string的substring在pattern数组里.

class Solution {
    public int numOfStrings(String[] patterns, String word) {
        Set<String> set = new HashSet<>();
        for(int i = 0; i <= word.length(); i++)
        {
            for(int j = i; j <= word.length(); j++)
            {
                set.add(word.substring(i,j));
            }
        }
        int res = 0;
        for(String p : patterns)
            if(set.contains(p))
                res++;
        return res;
    }
}

给一个无环双向图, 找是否有一个path.

这题就union find的模板题.

class Solution { 
    class DSU{
        int[] p;
        public DSU(int size) {
            this.p = new int[size];
            for(int i = 0; i < size; i++) {
                p[i] = i;
            }
        }
        int get(int v) {
            if(p[v] == v)
                return v;
            return p[v] = get(p[v]);
        }
        boolean union(int a, int b) {
            a = get(a);
            b = get(b);
            if(a == b)
                return false;
            p[a] = b;
            return true;
        }
    }
    public boolean validPath(int n, int[][] edges, int start, int end) {
        if(edges == null || edges.length == 0)
            if(n == 1 && start == 0 && end == 0)
                return true;
            else
                return false;  
        DSU dsu = new DSU(n);
        for(int[] e : edges)
            dsu.union(e[0],e[1]);
        return dsu.get(start) == dsu.get(end);
    }
    
    
    
}

找第k小的subarray sum.

这题吧..如果不卡时间, 应该不难, 但是这题用treeset过不了, 所以只能用binary search做, 已知subarray sum可以用pre sum求, 并且是递增的 (nums[i] >= 1) 所以这题可以用binary search找一个mid最小值下, 第k的值.

class Solution {
    public int kthSmallestSubarraySum(int[] nums, int k) {
        int l = 0;
        int r = Integer.MAX_VALUE;
        while(l < r)
        {
            int m = (l + r) / 2;
            int f = check(nums, m);
            if(f < k)
                l = m + 1;
            else
                r = m;
        }
        return l;
    }
    public int check(int[] nums, int m){
        int sum = 0;
        int i = 0;
        int j = 0;
        int res = 0;
        while(i < nums.length){
            if(sum + nums[i] <= m){
                sum += nums[i];
                i++;
                res += i - j;
            }
            else
            {
                sum -= nums[j];
                j++;
            }
        }
        return res;
    }
}

class Solution {
    public int kthSmallestSubarraySum(int[] nums, int k) {
        int n = nums.length;
        int[] pre = new int[n + 1];
        for(int i = 1 ; i <= n; i++) {
            pre[i] = pre[i - 1] + nums[i - 1];
        }
        LinkedList<Integer> list = new LinkedList<>();
        for(int i = 0; i <= n; i++){
            for(int j = i + 1; j <= n; j++){
                list.add(pre[j] - pre[i]);
            }
        }
        Collections.sort(list);
        System.out.println(list);
        while(--k != 0){
            list.removeFirst();
        }
        return list.getFirst();
    }
}