给一个数组, 找最小排序大小的子数组可让数组排序.

这题是双指针, 从左侧找最大值, 然后可以知道最大值右边的数字都是应该被sort的,因为如果是已经排序的数组, 最大值应该在最右侧. 同理, 我们再弄一个指针从右往左走. 然后去两个指针之差

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int left = 0;
        int max = nums[0];
        int n = nums.length;
        for(int i = 1; i < n; i++) {
            if(nums[i] >= max){
                max = nums[i];
            }
            else
            {
                left = i;
            }
        }
        int right = n - 1;
        int min = nums[n - 1];
        for(int i = n - 1; i >= 0; i--) {
            if(nums[i] <= min){
                min = nums[i];
            }
            else
            {
                right = i;
            }
        }
        if(left == 0 && right == n - 1)
            return 0;
        return left - right + 1;
    }
}

定义了一些操作, 求复原perm数组的操作次数.

暴力解…也没有什么简化方法.

class Solution {
    public int reinitializePermutation(int n) {
        int[] perm = new int[n];
        int[] st = new int[n];
        for(int i = 0; i < n; i++){
            perm[i] = i;
            st[i] = i;
        }
        int res = 0;
        while(true){
            int[] ary = new int[n];
            for(int i = 0 ; i < n; i++) {
                if(i % 2 == 0)
                    ary[i] = perm[i / 2];
                else
                    ary[i] = perm[n / 2 + (i - 1) / 2];
            }
            perm = Arrays.copyOf(ary, n);
            res++;
            if(check(perm, st))
                return res;
        }
    }
    
    public boolean check(int[] p, int[] a){
        for(int i = 0 ; i < p.length; i++) {
            if(p[i] != a[i])
                return false;
        }
        return true;
    }
}

定义一个happy string, 求第k个字典序的happy string是什么.

暴力解, 好像没有什么简化方法.

class Solution {
    public String getHappyString(int n, int k) {
        List<String> list = new ArrayList<>();
        dfs(n, list, "", new char[]{'a', 'b', 'c'});
        if(k < 0 || k > list.size())
            return "";
        else
            return list.get(k - 1);
    }
    
    public void dfs(int n, List<String> list, String s, char[] c) {
        if(n == s.length()){
            list.add(s);
            return;
        }
        for(char cc : c) {
            if(s.isEmpty())
                dfs(n, list, s+cc,c);
            else
            {
                if(s.charAt(s.length() - 1) != cc)
                    dfs(n, list, s+cc, c);
            }
        }
    }
}

给一个字符串s和一个字符串part, 删除所有part在s中的字符.

这题就暴力做即可.

class Solution {
    public String removeOccurrences(String s, String part) {
        if(s.indexOf(part) == -1)
            return s;
        return removeOccurrences(s.substring(0, s.indexOf(part)) + s.substring(s.indexOf(part) + part.length(), s.length()), part);
    }
}

给一个string, 里面是0和1, 给一个操作, 可以flip所有在i后的字符, 求最少flip几次.

这题通过观察, 可以发现如果从左往右考虑, 从0到1的flip和从1到0的flip, 其实都不会影响左边已经flip过的字符, 故操作次数只与当前的字符是不是和前一个字符相同有关.

class Solution {
    public int minFlips(String target) {
        int cur = 0;
        int res = 0;
        for(int i = 0; i < target.length(); i++) {
            if(cur != (target.charAt(i) - '0')){
                if(cur == 0)
                    cur = 1;
                else
                    cur = 0;
                res++;
            }
        }
        return res;
    }
}

给一个board, 里面的’X’代表船的位置, 船和船之间隔着至少一个’.’, 问有几艘船

这题就dfs一下即可. 搜过的mark成’Y’

class Solution {
    public int countBattleships(char[][] board) {
        int n = board.length;
        int m = board[0].length;
        int res = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(board[i][j] == 'X'){
                    res++;
                    dfs(board,i, j);
                }
            }
        }
        return res;
    }
    
    public void dfs(char[][] b, int i, int j){
        int[][] dirs = new int[][]{
            {0,1},{1,0},{0,-1},{-1,0}  
        };
        if(0 <= i && i < b.length && 0 <= j && j < b[0].length && b[i][j] == 'X'){
            b[i][j] = 'Y';
            for(int[] d : dirs) {
                dfs(b, i + d[0], j + d[1]);
            }
        }
    }
}

给一个数组, 有多少组triple(i,j,k), 可以让0<= i < j<k <=n中[i,j),[j,k]的xor相等.

这题挺有意思, 直接做就是O(N^3), 是可以过的. 然后考虑优化到O(N^2), 因为xor是半加符号, 所以可以想到是用presum的方法.

首先建立pre xor数组, 但是怎么用这个数组, 可以考虑一下, xor相等的意思是值为0, 所以如果有一个区间[i,k]中的xor为0, 那么这个区间里的所有j都是答案的选项.

class Solution {
    public int countTriplets(int[] arr) {
        int n = arr.length;
        int[] pre = new int[n + 1];
        for(int i = 0; i < n; i++) {
            pre[i + 1] = arr[i] ^ pre[i];
        }
        int res = 0;
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j <= n; j++) { 
                if(pre[j] - pre[i] == 0) //(0,3) (2,5)
                    res += j - i - 1;
            }
        }
        return res;
    }
}

给一个数组， 求做triangle sum后的数字。

这题就模拟一下就可以

class Solution {
    public int triangularSum(int[] nums) {
        int n = nums.length;
        while(n > 1){
            for(int i = 0; i < n - 1; i++) {
                nums[i] += nums[i + 1];
                nums[i] %= 10;
            }
            n--;
        }
        return nums[0];
    }
}

给一个数组, 找里面是不是包含区间[min, min+nums.length-1]的所有数字.

class Solution {
    public boolean isConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int min = Integer.MAX_VALUE;
        for(int n : nums){
            set.add(n);
            min = Math.min(min, n);
        }
        for(int i = min ; i <= min + nums.length - 1; i++){
            if(!set.contains(i))
                return false;
        }
        return true;
    }
}

给一个数组, 求距离0最近的数字, 如果2个数字相同, 返回最大的.

class Solution {
    public int findClosestNumber(int[] nums) {
        int min = Integer.MAX_VALUE;
        int res = Integer.MAX_VALUE;
        for(int i = 0; i < nums.length; i++){
            if(min >= Math.abs(nums[i])){
                 if(min == Math.abs(nums[i]))
                    res = Math.max(res, nums[i]);
                else
                    res = nums[i];
                min = Math.abs(nums[i]);
            }
        }
        return res;
    }
}