[toc]

2022-10-20#

字符串截取一段的函数是substring(起始位置闭区间，终止位置开区间)

注意0不能用来取余

2022-10-13#

取前后石子的博弈论#

先是用dp动态规划+博弈论求解

class Solution {
    public boolean stoneGame(int[] piles) {
        int n = piles.length;
        int[][][] dp = new int[n][n][2];
        for (int len=1;len<=n;len++) {
            for (int i = 0;i < n;i++) {
                int j = i + len-1;
                if (j >= n) {
                    continue;
                }
                int p1 = piles[i];
                int p2 = piles[j];
                if (len == 1) {
                    dp[i][j][0] = p1;
                    dp[i][j][1] = -p1;
                    continue;
                }

                dp[i][j][0] =  Math.max(p1 + dp[i+1][j][1], p2
                 + dp[i][j-1][1]);
                
                dp[i][j][1] = Math.min(-p1 + dp[i+1][j][0], -p2 + dp[i][j-1][0]);
            }
        }

        return dp[0][n-1][0] > 0;
    }
}

然而实际上先手方可以做到一直只取奇数位，或者只取偶数位，那么只要求出奇数位总和和偶数位总和拿个大即可，所以先手必胜。

分块排序最终有序问题#

769. 最多能完成排序的块 - 力扣（LeetCode）

我先是用了一个O(n^2logn)的麻烦方法, 欺负他量级小。

class Solution {
    public int maxChunksToSorted(int[] arr) {
        int left = 0;
        int needMin = 0;
        int count = 0;
        for (int r = left;r<arr.length;r++) {
            if (isValid(arr, left, r, needMin)) {
                count++;
                left = r+1;
                needMin = r + 1;
            }
        }
        return count;
    }

    public boolean isValid(int[] arr, int left ,int right , int needMin) {
        int[] newa = new int[right -left + 1];
        boolean found = false;
        for (int i = 0; i < newa.length;i++) {
            newa[i] = arr[left + i];
            if (needMin == newa[i]) {
                found = true;
            }
        }
        Arrays.sort(newa);
        for (int i = 1; i < newa.length;i++) {
            if (newa[i] != newa[i-1] +1) {
                return false;
            }
        }
        return found;
    }
}

实际上应该是如果当前最大值且正在在对应位置，则左边的都可以排序了，因为自己一定是稳定排的（左边没有比自己小的，而自己又正好在自己这个值的索引处，那么左边肯定能排）

class Solution {
    public int maxChunksToSorted(int[] arr) {
        int count = 0;
        int max = -1;
        for (int i = 0; i < arr.length;i++) {
            max = Math.max(arr[i], max);
            if (max == i) {
                count++;
            }
        }
        return count;
    }

 
}

2022-10-12#

负二进制问题#

1073. 负二进制数相加 - 力扣（LeetCode）

模拟了半天才知道规律好头疼。下面这个感觉很难记住，其实就是

-1的时候，此位变1，下一位+1

1的时候，此位变1，下一位-1

0的时候不变

提交二里看到一个，没看懂怎么利用

class Solution {
    public int[] addNegabinary(int[] arr1, int[] arr2) {
        int add  =0;
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < Math.max(arr1.length, arr2.length);i++) {
            int index1 = arr1.length - 1 - i;
            int index2 = arr2.length - 1 - i;
            int num1 = index1 < 0 ? 0 : arr1[index1];
            int num2 = index2 < 0 ? 0 : arr2[index2];
            int num3 = add + num1 + num2;
            if (num3 == -1) {
                num3 = 1;
                add = 1;
            } else {
                add = -(num3  / 2);
                num3 %= 2;
            }
            res.add(num3);
        }

        if (add==-1) {
            res.add(1);
            res.add(1);
        } else if (add==1){
            res.add(add);
        }

        // 去除前导0
        while(res.size() > 1 && res.get(res.size()-1) == 0) {
            res.remove(res.size()-1);
        }
        
        int[] resArr = new int[res.size()];
        for (int i = 0; i < res.size();i++) {
            resArr[i] = res.get(res.size()-1-i);
        }
        return resArr;
    }
}

破晓的知识屋

2022年10月