给一个数组, 是个圈, 里面有n个人编号为[1..n], 每次游戏踢出第k个, 问剩下的标号是多少

这个就模拟一下吧. 我用set标示被踢出的. 然后当set的大小等于n-1 剩下没标到的就是答案.

class Solution {
    public int findTheWinner(int n, int k) {
        if(n == 1)
            return 1; 
        LinkedList<Integer> list = new LinkedList<>();
        Set<Integer> set = new HashSet<>();
        for(int i = 1; i <= n; i++){
            list.addLast(i);
        }
        for(int i = 1; i < n; i++){
            for(int j = 0; j < k;){
                if(!set.contains(list.peek())){
                    j++;
                }
                list.addLast(list.removeFirst());
            }
            set.add(list.getLast());
            if(set.size() == n - 1){
                for(int f = 1; f <= n; f++){
                    if(!set.contains(f))
                        return f;
                }
            }
        }
        return -1;
    }
}

给一个2d数组是points, 然后给一个数组里面是queries, query里面有一个圆的圆点坐标x,y和半径r, 求这个圆里面有多少个点.

这个题就是利用每个query的圆点位置和points的位置求解

class Solution {
    public int[] countPoints(int[][] points, int[][] queries) {
        int[] res = new int[queries.length];
        for(int i = 0; i < queries.length; i++){
            int count = 0;
            for(int j = 0; j < points.length; j++) {
                if(dis(queries[i][0], queries[i][1], points[j][0], points[j][1]) <= (queries[i][2] * queries[i][2])){
                    count++;
                }
            }
            res[i] = count;
        }
        return res;
    }
    
    private double dis(int x1, int y1, int x2, int y2) {
        return Math.pow(x2 - x1, 2) + Math.pow(y2 -y1, 2);
    }
}

这个题是看了hint, 发现如果一个十进制数字的三进制表示有2, 那么这个十进制数不是答案.

class Solution {
    public boolean checkPowersOfThree(int n) {
        while(n > 0){
            if(n % 3 == 2)
                break;
            n = n / 3;
        }
        if(n > 0)
            return false;
        return true;
    }
}

给一个数组, 求里面的数字乘积是正负还是0.

class Solution {
    public int arraySign(int[] nums) {
        int count = 0;
        for(int n : nums){
            if(n < 0)
                count++;
            if(n == 0)
                return 0;
        }
        return count % 2 == 0 ? 1 : -1;
    }
}

给一个数组, 里面的数字是一个冰激凌的cost, 给一个数字coin, 问最多能买几个冰激凌.

贪婪算法, 直接排序后算.

class Solution {
    public int maxIceCream(int[] costs, int coins) {
        Arrays.sort(costs);
        int res = 0;
        for(int c : costs){
            if(coins >= c){
                res++;
                coins -= c;
            }else{
                break;
            }
        }
        return res;
    }
}

给一个数组, 定义一个操作是让数组任意的数字加一, 那么求多少个操作后, 数组可以变成严格递增的数组.

class Solution {
    public int minOperations(int[] nums) {
        int res = 0;
        for(int i = 1; i < nums.length; i++) {
            if(nums[i - 1] < nums[i])
                continue;
            res += (nums[i - 1] - nums[i] + 1);
            nums[i] = nums[i - 1] + 1;
        }
        return res;
    }
}

check一个string是不是包含所有的26个字母

class Solution {
    public boolean checkIfPangram(String sentence) {
        int[] count = new int[26];
        for(char c : sentence.toCharArray()){
            count[c - 'a']++;
        }
        for(int n : count){
            if(n == 0)
                return false;
        }
        return true;
    }
}

给一个2d数组，里面是一个信封的长宽，问多少个信封能套起来。

这个题和前几天的盒子那个题很想，就是最长连续递增子序列， 先要按照长度排序， 然后就知道从前到后的长度的信封都能放到前一个信封里，然后要考虑同样长度的信封， 这时候要按照从大到小排序， 即同样长的信封，如果宽度不一样， 那么可以构造成不同的递增子序列。另外答案的这个LIS是我跟leetcode学的写法。

class Solution {
    private int lenOfLIS(int[] nums) {
        int len = 0;
        int[] dp = new int[nums.length];
        for(int n : nums) {
            int i = Arrays.binarySearch(dp, 0, len, n);
            if(i < 0) {
                i = -(i + 1);
            }
            dp[i] = n;
            if(i == len)
                len++;
        }
        return len;
    }
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, (a,b) -> (a[0] == b[0] ? b[1] - a[1]: a[0] - b[0]));
        int[] s = new int[envelopes.length];
        for(int i = 0; i < envelopes.length; i++){
            s[i] = envelopes[i][1];
        }
        return lenOfLIS(s);
    }
    
}

给一个国际象棋的板子, 问某个个子的颜色.

class Solution {
    public boolean squareIsWhite(String c) {
        boolean res = (c.charAt(0) - 'a') % 2 == 0 ? false : true ;
        res = (c.charAt(1) - '1') % 2 == 0 ? res : !res;
        return res;
    }
}

给一个log是<user, min>, 定义UAM是一个user对应唯一的min的个数, 给一个k, 求[1,k]min中独立user的个数.

这题就是读懂题….

class Solution {
    public int[] findingUsersActiveMinutes(int[][] logs, int k) {
        int[] res = new int[k];
        Map<Integer, Set<Integer>> map = new HashMap<>();// <user id, unique min>
        for(int[] l : logs) {
            if(map.containsKey(l[0])){
                Set<Integer> set = map.get(l[0]);
                set.add(l[1]);     
                map.put(l[0], set);
            }else{
                Set<Integer> set = new HashSet<>();
                set.add(l[1]);        
                map.put(l[0], set);
            }
        } 
        for(Map.Entry<Integer, Set<Integer>> e : map.entrySet()){
            res[e.getValue().size() - 1]++;
        }
        return res;
    }
}