今天周三，这周的笔记才开始。讲真这周十点之前没回过家。哎，闲话也不说了，直接开始刷题吧。

重构字符串

题目：给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。若可行，输出任意可行的结果。若不可行，返回空字符串。

示例 1:
输入: S = "aab"
输出: "aba"
示例 2:
输入: S = "aaab"
输出: ""
注意:
S 只包含小写字母并且长度在[1, 500]区间内。

思路：这道题似曾相识的感觉。好像做过类似的。首先要判断是不是有一个元素超过全长的一半。如果超了肯定是false。因为怎么插入都有挨着的。如果不超过，那么从最多的字母开始插入。因为都是小写字母，我这里打算用数组下标代替字母。值代替个数。大概思路就这样，我去实现下试试。
直接贴代码：

    public static String reorganizeString(String S) {
        if (S.length() < 2) {
            return S;
        }
        int[] counts = new int[26];
        int maxCount = 0;
        int length = S.length();
        for (char c:S.toCharArray()) counts[c - 'a']++;
        for(int i:counts) maxCount = Math.max(maxCount,i);
        if (maxCount > (length + 1) / 2) {
            return "";
        }
        char[] reorganizeArray = new char[length];
        int evenIndex = 0, oddIndex = 1;
        int halfLength = length / 2;
        for (int i = 0; i < 26; i++) {
            char c = (char) ('a' + i);
            while (counts[i] > 0 && counts[i] <= halfLength && oddIndex < length) {
                reorganizeArray[oddIndex] = c;
                counts[i]--;
                oddIndex += 2;
            }
            while (counts[i] > 0) {
                reorganizeArray[evenIndex] = c;
                counts[i]--;
                evenIndex += 2;
            }
        }
        return new String(reorganizeArray);
    }

这个思路和我上面说的差不太多，就是计数后的处理有点不同，两个指针往上插入字符，所以每次是跳两个单元格的。一个1,3,5插入，一个2,4,6插入。这样防止一样的挨着。而且这里有一个知识点：如果一个元素自己就超过整个数组的一半：比如aaabb这种，那么一定要从第0个开始插入这个元素。当然了如果不足一半则从第一个开始插入就行。这也是上面代码中先从id为1的开始判断的原因。
具体的做法也没啥好说的，而且我这个题的性能已经不错了，所以就不多说了，直接下一题。反正这个题不算难，就这样吧，下一题。

俄罗斯套娃信封问题

题目：给定一些标记了宽度和高度的信封，宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。说明:不允许旋转信封。

示例:
输入: envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出: 3
解释: 最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。

思路：这个题是2021/3/4的每日一题。大体思路是以w排序，然后获取h的最长子序列。这个子序列的长度就是可以套娃的最长长度。感觉思路没啥问题。我去是实现下试试。

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        if(envelopes.length == 0) return 0;
        Arrays.sort(envelopes, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0]>o2[0]) return 1;
                if(o1[0]<o2[0]) return -1;
                //这里是重点，因为装下必须长宽都高。所以这种长一样的防止以后计算出问题，所以一定要宽长的在前面
                return o2[1]-o1[1];
            }
        });
        int[] d = new int[envelopes.length];
        for(int i = 0;i<d.length;i++) d[i] = envelopes[i][1];
        //d是最长递增子序列就是可以套娃的最大数
        int[] dp = new int[envelopes.length];
        for(int i = 1;i<d.length;i++){
            for(int j = 0;j<i;j++){
                //说明当前元素比之前的元素大。可以继续往上续.找一个最长的续上
                if(d[i]>d[j]) dp[i] = Math.max(dp[i],dp[j]+1);
            }
        }
        int ans = 0;
        for(int i : dp){
            ans = Math.max(ans,i);
        }
        return ans+1;
    }
}

又一次凭自己做出困难题目了，贼开心，嘿嘿。简单来说这个题的思路就是我上面说的那个，然后要注意一点的是排序的时候长一样宽度大的要在前面。
因为一个测试案例： [[4,5],[4,6],[6,7],[2,3],[1,1]]
这个测试案例中：4.5 4.6是不可以套娃的，但是如果是长一样宽顺序的话，得出来的解决是5<6，这样结果就会出问题，所以一定是倒叙排序，也就是6,5这样的。
剩下没啥了，就是一个最长递增子序列的问题我也不在这里多说了，下一题。

最多能完成排序的块

题目：数组arr是[0, 1, ..., arr.length - 1]的一种排列，我们将这个数组分割成几个“块”，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。我们最多能将数组分成多少块？

示例 1:
输入: arr = [4,3,2,1,0]
输出: 1
解释:
将数组分成2块或者更多块，都无法得到所需的结果。
例如，分成 [4, 3], [2, 1, 0] 的结果是 [3, 4, 0, 1, 2]，这不是有序的数组。
示例 2:
输入: arr = [1,0,2,3,4]
输出: 4
解释:
我们可以把它分成两块，例如 [1, 0], [2, 3, 4]。
然而，分成 [1, 0], [2], [3], [4] 可以得到最多的块数。
注意:
arr 的长度在 [1, 10] 之间。
arr[i]是 [0, 1, ..., arr.length - 1]的一种排列。

思路：这个题首先，1是保底答案。其次就是看能分多少块了.我有个模糊的想法，那就是先排序，看这个元素原本应该在的位置和现在的位置一样不一样。有一个模糊的思路，下面我去代码试试。
其实这个题有个重点，是元素的值会分别是0到n-1，而且还不会重复，所以这个题就简单多了，从前往后遍历，如果说遍历到了i，而当前最大值也是i。则说明前面这些元素已经可以单独提出来作为一个块了，也就是块+1.当然这个也不影响保底的1.因为最坏的结果最大的在早早就出来了，所以要遍历到最后一个元素才能进入到这个结果+1的分支。反正情况就是这样，想明白就挺简单了，下面是代码：

class Solution {
    public int maxChunksToSorted(int[] arr) {
        int res = 0, max = 0;
        for (int i = 0; i < arr.length; i++){
            max = Math.max(max, arr[i]);//统计前i个位置的最大元素
            if (max == i) res++;
        }
        return res;
    }
}

因为这个代码比较简单，思路上面也都说了，所以我就不多说什么了。直接接下一题了。

分割回文串

题目：给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。返回符合要求的 最少分割次数 。

示例 1：
输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
示例 2：
输入：s = "a"
输出：0
示例 3：
输入：s = "ab"
输出：1
提示：
1 <= s.length <= 2000
s 仅由小写英文字母组成

思路:这个题我看了标签，是dp。我觉得主要还是每次都获取最大的回文串切分吧。其中如果是dp，那么肯定是有个递推公式，也就是说应该是有个填充规律。所以我目前四路是从前往后。其次是回文串分奇偶。所以每一个元素都要作为中心点来遍历一遍。大概思路是有了，具体的我去代码试试
最终版代码：

class Solution {
    public int minCut(String s) {
        if(s.length()<=1) return 0;
        int len = s.length();
        int[] dp = new int[len];
        Arrays.fill(dp,Integer.MAX_VALUE);
        for(int i = 0;i<len;i++){
            dp(i,i,s,dp);
            dp(i,i+1,s,dp);
        }
        return dp[len-1];
    }
    //因为回文串分单双。所以奇数个中心是temp，偶数个中心是temp和temp1
    public void dp(int temp,int temp1,String s,int[] dp){
        while(temp>=0 && temp1<s.length() &&s.charAt(temp) == s.charAt(temp1)){
            //注意这个三元运算：如果当前元素是第一个，那么是不需要切割的，所以是0.
            //注意咱们因为是从前开始便利的，所以得出的结果这个回文串之后的最小结果
            dp[temp1] = Math.min(dp[temp1],temp == 0?0:dp[temp-1]+1);
            temp--;
            temp1++;
        }
    }
}

这个思路其实也不算很难，但是我自己怎么都绕不过来，所以最终看了题解。发现我离正确答案就差那么一层纱。简而言之其思路也就是递推公式如下：从最左边开始遍历，每一个字符都看作是回文串的中心点来判断。如果是最左边是第一个字符则当前不用切割，如果最左边不是第一个字符，那么切割的方式是左边再往左的那个切割次数+1（因为当前和左边的左边没办法组成一个回文串，一定要割一刀，所以+1）。
以此类推，最后一个字符的割的次数就是需要割的最大次数。
因为dp这种东西本来思路就比写法重要，这个要慢慢理解。我其实当时自己想到了这个递推公式，但是我没有把中间过程的每一步都重新判断赋值，而是一次判断出整个回文串，反正就是爬山100步，我只走了50步，剩下最重要的反而没想明白。
然后这个题就这样吧，懂得自然懂。不懂的建议去debug一步一步跑几次就明白了。下一题。

全局倒置与局部倒置

题目：数组 A 是 [0, 1, ..., N - 1] 的一种排列，N 是数组 A 的长度。全局倒置指的是 i,j 满足 0 <= i < j < N 并且 A[i] > A[j] ，局部倒置指的是 i 满足 0 <= i < N 并且 A[i] > A[i+1] 。当数组 A 中全局倒置的数量等于局部倒置的数量时，返回 true 。

示例 1:
输入: A = [1,0,2]
输出: true
解释: 有 1 个全局倒置，和 1 个局部倒置。
示例 2:
输入: A = [1,2,0]
输出: false
解释: 有 2 个全局倒置，和 1 个局部倒置。
注意:
A 是 [0, 1, ..., A.length - 1] 的一种排列
A 的长度在 [1, 5000]之间
这个问题的时间限制已经减少了。

思路：我审题三四遍才看明白，不知道是我语文没救了，还是leetcode越来越不说人话了。总而言之，所谓的全局倒置就是前面的比后面的大（非连续）。比如 1，2，0。这里1和0，2和0是两对全局倒置，而局部倒置是一定要连续的递减。比如1，2，0.只有2，0是局部倒置。其实这样我们可以直接想象得到：局部倒置本身就是全局倒置之一，所以哪怕不等一定是全局倒置大于局部倒置，我们只要判断是不是有不是连续的全局倒置就行了，这样只要看有没有不连续的递减就行，我去试试代码。
直接上最终版代码：

class Solution {
    public boolean isIdealPermutation(int[] A) {
        //只要判断是不是有非连续全局倒置就可以了。
        int max = A[0];
        for(int i = 2;i<A.length;i++){
            if(max>A[i]){
                return false;
            }
            max = Math.max(max,A[i-1]);
        }
        return true;
    }
}

一次ac，而且性能超过百分百，所以说这个题就不多说啥了，最近做题最顺的一道，开心。思路啥的都没问题。代码也很简单，直接下一题了。

在KR字符串中交换相邻字符

题目：在一个由 'L' , 'R' 和 'X' 三个字符组成的字符串（例如"RXXLRXRXL"）中进行移动操作。一次移动操作指用一个"LX"替换一个"XL"，或者用一个"XR"替换一个"RX"。现给定起始字符串start和结束字符串end，请编写代码，当且仅当存在一系列移动操作使得start可以转换成end时， 返回True。

示例 :
输入: start = "RXXLRXRXL", end = "XRLXXRRLX"
输出: True
解释:
我们可以通过以下几步将start转换成end:
RXXLRXRXL ->
XRXLRXRXL ->
XRLXRXRXL ->
XRLXXRRXL ->
XRLXXRRLX
提示：
1 <= len(start) = len(end) <= 10000。
start和end中的字符串仅限于'L', 'R'和'X'。

思路：看题目所说：XL可以换成LX，RX可以换成XR。大概题目要求就是这样。重点是这个题目的标签是脑筋急转弯。仔细审题：首先因为只是字母交换，所以如果起始字符串的字母个数不一样肯定不行。其次连起来：因为只能这三种元素组成，而且这里XL替换成LX，RX替换成XR注意一下，这里只有X与L,R的位置变化了，而且都是X往后换了，L和R之间是不能换位的，所以我们可以理解为起始串除了X以后应该相等。不然怎么也换不了的。其次因为是只能从start开始转换，也就是本质上是单向的。
而相对于L，X只能往后移，也就是说L只能往X前面移动。而R则相反，可以往X的后面移动。也就是说LLLRXLRRR.我们可以把X往R前面移动，或者把X往L后面移动，但是X前面的LLL最少三个，不能变少，同样X后面的R最少三个，也不能变少。
- 所以如果start的X前面的L比end中X前面的L多，是怎么也少不了的，也转化不成功。
- 同理，如果start的X前面的R小于end的X前面的R，因为R只能往后，是多不了了，所以也转化不成功。
以上三个条件就是决定转化能否成功的全部因素，下面我去写代码：

class Solution {
    public boolean canTransform(String start, String end) {
        String s1 = start.replace("X","");
        if(!s1.equals(end.replace("X",""))) return  false;
        int[][] d = new int[start.length()-s1.length()][2];
        int l = 0;
        int r = 0;
        int temp = 0;
        for(int i = 0;i<start.length();i++){
            if(start.charAt(i) == 'X'){
                d[temp] = new int[]{l,r};
                temp++;
            }else if(start.charAt(i) == 'L'){
                l++;
            }else {
                r++;
            }
        }
        l = 0;
        r = 0;
        temp = 0;
        for(int i = 0;i<start.length();i++){
            if(end.charAt(i) == 'X'){
                if(d[temp][0]>l || d[temp][1]<r) return false;
                temp++;
            }else if(end.charAt(i) == 'L'){
                l++;
            }else {
                r++;
            }
        }
        return true;
    }
}

思路没啥问题，但是代码的性能不是很好。我直接去看看性能第一的代码吧，get不到优化点了：

class Solution {
    public boolean canTransform(String start, String end) {
        int n=start.length();
        char[] src=start.toCharArray();
        char[] des=end.toCharArray();
        int i=0;
        int j=0;
        while(i<n||j<n) {
            while(i<n&&src[i]=='X') i++;
            while(j<n&&des[j]=='X') j++;
            if((i==n&&j<n)||(j==n&&i<n)) return false;
            if(i<n&&j<n) {
                if(src[i]!=des[j]||(src[i]=='L'&&i<j)||(src[i]=='R'&&i>j)) {
                    return false;
                }
                i++;
                j++;
                
            }
        }
        return true;

    }
}

我竟然看了半天才看懂，大概的思路和我之前的是一样的：
第一个判断（因为遇到X会继续往下，所以可以看作跳过X），跳过X后如果两个字符串不全等肯定是不行的。这里是一个一个元素比较的。
第二个判断：当前是L的话，如果i小于j。也就是说start的L多余end的L。又因为L只能往前不能往后，所以一定不行。
第三个判断：当前是R的话，如果i大于j。也就是说start的R小余end的R。因为R只能往后不能往前，所以前面的补不了，所以也无法变换。
这三种情况都是直接false，否则就是true。
其实这个思路是差不多的，但是具体的实现我没有那么透彻，还是理解不深，哎，下一题。

第K个语法符号

题目：在第一行我们写上一个 0。接下来的每一行，将前一行中的0替换为01，1替换为10。给定行数 N 和序数 K，返回第 N 行中第 K个字符。（K从1开始）

例子:
输入: N = 1, K = 1
输出: 0
输入: N = 2, K = 1
输出: 0
输入: N = 2, K = 2
输出: 1
输入: N = 4, K = 5
输出: 1
解释:
第一行: 0
第二行: 01
第三行: 0110
第四行: 01101001
注意：
N 的范围 [1, 30].
K 的范围 [1, 2^(N-1)].

思路：这个题的话，审完题我的第一个想法居然是暴力获取每一行的每一个字符。。。但是看看这个N和K的范围，还是算了吧。。简单来说这个题我觉额其实应该是有规律的。比如每一行都是上一行翻倍的元素数目。其次 0-> 0 1 1->1 0 也就是说偶数位是上一层的元素。奇数位是偶数位%1的结果。这个题应该是个找规律的题目，我去仔细看看怎么写代码。
ps:找出个规律，下一行就是上一行+上一行翻转（0变1，1变0）.感觉可以用到。
这个题就是一个标准的数学题，所以我屈服了，思路是有，但是写出来怎么写怎么不对：

class Solution {
    public int kthGrammar(int N, int K) {
        return Integer.bitCount(K - 1) % 2;
    }
}

于是看了题解，一行代码搞定。这块其实是关于位的运算。每一行的后半部分都是前半部分的翻转。把下标 K 写成二进制的形式，如果 K 在第二部分，那么二进制形式的第一个比特位一定是 1。据此可以将方法三继续简化，实际上翻转的次数等于 K-1 二进制表示形式中 1 出现的个数。（这个是题解的说法）

这篇笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注，也祝大家工作顺顺利利！生活愉快！