给一个rooms的列表, 里面只有第一个room是开锁的, 其他room的锁的钥匙在各个房间, 求是否能访问所有的room

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        int n = rooms.size();
        boolean[] visited = new boolean[n];
        Queue<Integer> q = new LinkedList<>();
        visited[0] = true;
        for(int nn : rooms.get(0)){
            q.add(nn);
        }
        while(!q.isEmpty()){
            int t = q.poll();
            if(!visited[t]){
                visited[t] = true;
                for(int nn : rooms.get(t))
                    q.add(nn);
            }
        }
        for(boolean b : visited)
            if(!b)
                return false;
        return true;
    }
}

给一个字符串是序列的order, 求排序一个字符串.

class Solution {
    public String customSortString(String order, String s) {
        Map<Character, Integer> m = new HashMap<>();
        int k = 100;
        for(char c : order.toCharArray())
            m.put(c, k--);
        List<Character> list = new ArrayList<>();
        for(char c : s.toCharArray())
            list.add(c);
        Collections.sort(list, (a,b) ->{
            int aa = m.getOrDefault(a, Integer.MAX_VALUE / 2);
            int bb = m.getOrDefault(b, Integer.MAX_VALUE / 2);
            return bb - aa;
        });
        StringBuilder sb = new StringBuilder();
        for(char c : list)
            sb.append(c);
        return sb.toString();
    }
}

给一个grids, 里面是3d的unit tube, 求三面投影.

这题读懂这个grids的设计即可. 还有个测试是value = 0…

class Solution {
    public int projectionArea(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int xy = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++){
                if(grid[i][j] != 0)
                   xy++; 
            }
        }      
        int xz = 0; 
        for(int i = 0; i < n; i++) {
            int max = 0;
            for(int j = 0; j < m; j++){
                if(grid[i][j] != 0)
                    max = Math.max(max,grid[i][j]);
            }
            xz += max;
        }
        int zy = 0;
        for(int j = 0; j < m; j++) {
            int max = 0;
            for(int i = 0; i < n; i++){
                if(grid[i][j] != 0)
                    max = Math.max(max,grid[i][j]);
            }
            zy += max;
        }
        return xy + xz + zy;
    }
}

给一个数组和一个数字k, 可以有一种操作, 把k个数组变成最大的数字. 求最大的数组.

这题动态规划直接做, 然后注意一下边界.

class Solution {
    public int maxSumAfterPartitioning(int[] arr, int k) {
        int n = arr.length;
        int[] dp = new int[n + 1];
        int res = 0;
        for(int i = 0; i <= n; i++) {
            int max = 0;
            int t = Math.max(0, i - k);
            for(int j = i - 1; t <= j; j--) {
                max = Math.max(max, arr[j]); 
                dp[i] = Math.max(dp[i], dp[j] + max * (i - j)); // dp[i - 1] dp[i - 2]
            }
        }
        return dp[n];
    }
}

这题就是看L和R的特性, 有三个特性, L不能往右走,R不能往左走, 去掉X两个string一样.

class Solution {
    public boolean canTransform(String start, String end) {
        int i = 0;
        int j = 0;
        int n = start.length();
        int m = end.length();
        while(i < n && j < m){
            if(start.charAt(i) == 'X'){
                i++;
            }else if(end.charAt(j) == 'X'){
                j++;
            }else{ // no X
                if(start.charAt(i) != end.charAt(j))
                    return false;
                if(start.charAt(i) == 'R' && i > j)
                    //  s[i] == e[j]   start = xxR (i == 2) end = xRx (i == 1)
                    return false;
                if(start.charAt(i) == 'L' && i < j)
                    //  s[i] == e[j]  start = xLx (i == 1) end = xxL (i == 2)
                    return false;
                i++;
                j++;
            }       
        }
        while(i < n){
            if(start.charAt(i) != 'X') // xxxxLRLRLxxxxxL false
                return false;
            i++;
        }
        while(j < m){
            if(end.charAt(j) != 'X')
                return false;
            j++;
        }
        return true;
    }
}

class Solution {
    public String encode(int num) {
        return Integer.toBinaryString(num + 1).substring(1);
    }
}

给两个字符串s和t, 求有多少个s和t的子字符串差一个字符.

这题和数相同子串不同的就是数差一个字符的子串个数. 首先先数一下相同的子串个数, 然后再数不同的.

class Solution {
    public int countSubstrings(String s, String t) {
        int n = s.length();
        int m = t.length();
        int[][] allMatch = new int[n][m]; // # of substring all match for s and t untill i,j
        for(int i = 0; i < s.length(); i++) {
            for(int j = 0; j < t.length(); j++) {
                boolean ma = s.charAt(i) == t.charAt(j);
                if(i == 0 || j == 0){
                    if(ma){
                        allMatch[i][j] = 1;
                    }
                }
                else
                {
                    if(ma){
                        allMatch[i][j] = allMatch[i - 1][j - 1] + 1;
                    }
                    else{
                        allMatch[i][j] = 0;
                    }
                }
            }
        }
        int[][] missOne = new int[n][m];
        int res = 0;
        for(int i = 0; i < s.length(); i++) {
            for(int j = 0; j < t.length(); j++) {
                boolean ma = s.charAt(i) == t.charAt(j);
                if(i == 0 || j == 0){
                    if(!ma){
                        missOne[i][j] = 1;
                    }
                }
                else
                {
                    if(ma){
                        missOne[i][j] = missOne[i - 1][j - 1];
                    }
                    else{
                        missOne[i][j] = allMatch[i - 1][j - 1] + 1;
                    }
                }
                res += missOne[i][j];
            }
        }
        return res;
    }
}

求设计一个数据结构，里面有add,添加一个点, 和count,算有多少个可以用这个点和其他的点围成的正方形.

因为是正方形, 所以边长都一样, 而且题目要求是以轴为基准的正方形, 所以只需要判断有多少个正方形是同y和同x, 即可.

class DetectSquares {
    int[][] g = new int[1001][1001];
    public DetectSquares() {
        
    }
    
    public void add(int[] point) {
        g[point[0]][point[1]]++;
    }
    
    public int count(int[] point) {
        int res = 0;
        for(int i = 0; i < 1001; i++){
            if(Math.abs(point[0] - i) > 0){
                int j1 = point[1] + Math.abs(point[0] - i);
                if(0 <= j1 && j1 <= 1000){
                    res += g[i][j1] * g[i][point[1]] * g[point[0]][j1];
                }
                int j2 = point[1] - Math.abs(point[0] - i);
                if(0 <= j2 && j2 <= 1000){
                    res += g[i][j2] * g[i][point[1]] * g[point[0]][j2];
                }
            }
        }
        return res;
    }
}

 

/**
 * Your DetectSquares object will be instantiated and called as such:
 * DetectSquares obj = new DetectSquares();
 * obj.add(point);
 * int param_2 = obj.count(point);
 */

给一个数组, 求如何取到最大值, 取得方法是从每行取一个，但是距离上一行取的时候要减去格子的距离。

这题就dp。。。

class Solution {
    public long maxPoints(int[][] points) {
        int n = points.length;
        int m = points[0].length;
        long[][] dp = new long[n][m];
        long res = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                long tmp = 0;
                for(int k = 0; k < m; k++) {  
                    if(i == 0)
                    {
                        tmp = points[i][j];
                        break;
                    }
                    else
                    {
                        tmp = Math.max(tmp, points[i][j] + dp[i - 1][k]- Math.abs(k - j));
                    }
                }
                dp[i][j] = tmp;
                res = Math.max(res, dp[i][j]);
            }
        }  
        return res;
    }
}

给一个数组， 求里面最大or运算结果的子集的多少。

暴力

class Solution {
    int res = 0;
    public int countMaxOrSubsets(int[] nums) {
        int max = 0;
        for(int n : nums)
            max |= n; 
        dfs(nums, max, 0, 0);
        return res;
    }
    public void dfs(int[] nums,int max,int tmp, int pos){
        if(tmp == max)
            res++;
        if(pos >= nums.length)
            return;
        for(int i = pos; i < nums.length; i++){
            int tt = tmp;
            dfs(nums, max, tmp | nums[i], i+1);
            tmp = tt;
         }
    }
}