【Day30】LeetCode算法 [769. 最多能完成排序的块 ] [2131. 连接两字母单词得到的最长回文串]

---

题目一、769. 最多能完成排序的块

原题链接：769. 最多能完成排序的块

题目描述：

给定一个长度为 n 的整数数组 arr ，它表示在 [0, n - 1] 范围内的整数的排列。
我们将 arr 分割成若干 块 (即分区)，并对每个块单独排序。将它们连接起来后，使得连接的结果和按升序排序后的原数组相同。
返回数组能分成的最多块数量。
/
示例 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] 可以得到最多的块数。
/
提示:

• n == arr.length
• 1 <= n <= 10
• 0 <= arr[i] < n
• arr 中每个元素都 不同

解题思路：
题目要求我们将数组元素分块，分块的子数组分别升序排序后连接起来，需要与原数组升序排序后相同，要求我们输出能分得最多得块数。

乍一看没有任何思路，但是我们需要注意题目给到得条件，巧妙地解决问题。题目中有一个核心得条件呢，那就是：

• 数组arr表示在 [0, n - 1] 范围内的整数的排列

也就是说，原始数组按照升序排序后，元素得值与其下标是一一对应且相同的，那么我们在选区分块时就借助这个结论。

我们需要关注的是，但前遍历过的区块中，最大的元素，如果最大元素与遍历到的下标相等，就说明该分块升序排序后，与原数组升序排序后是等价的，这时候我们就可以记录分块数量 + 1了。

按照上述这个方式将原始数组遍历完，自然就将最大分块数记录下来，直接返回即可。

提交代码：

class Solution {
    public int maxChunksToSorted(int[] arr) {
        int total = 0;       //记录最多块数量
        int max = 0;         //记录遍历到当前位置，最大的元素值
        for(int i = 0;i < arr.length;++i){  //遍历数组
            max = Math.max(max,arr[i]);     //获取当前最大值

            //当前最大值=当前位置下标，说明排序后是与原数组升序后是相等的，块数+1
            if(max == i) total++;           
        }
        return total;         //返回记录下来的块数
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

提交结果：

---

题目二、2131. 连接两字母单词得到的最长回文串

原题链接：2131. 连接两字母单词得到的最长回文串

题目描述：

给你一个字符串数组 words 。words 中每个元素都是一个包含 两个 小写英文字母的单词。
请你从 words 中选择一些元素并按 任意顺序 连接它们，并得到一个 尽可能长的回文串 。每个元素 至多 只能使用一次。
请你返回你能得到的最长回文串的 长度 。如果没办法得到任何一个回文串，请你返回 0 。
回文串 指的是从前往后和从后往前读一样的字符串。
/
示例 1：
输入：words = [“lc”,“cl”,“gg”]
输出：6
解释：一个最长的回文串为 “lc” + “gg” + “cl” = “lcggcl” ，长度为 6 。
“clgglc” 是另一个可以得到的最长回文串。
/
示例 2：
输入：words = [“ab”,“ty”,“yt”,“lc”,“cl”,“ab”]
输出：8
解释：最长回文串是 “ty” + “lc” + “cl” + “yt” = “tylcclyt” ，长度为 8 。
“lcyttycl” 是另一个可以得到的最长回文串。
/
示例 3：
输入：words = [“cc”,“ll”,“xx”]
输出：2
解释：最长回文串是 “cc” ，长度为 2 。
“ll” 是另一个可以得到的最长回文串。“xx” 也是。

解题思路：
字符串数组中保存的都是两个一组的小写字符串，题目要求我们从中选取元素，按照任意顺序拼接，返回最长回文串的长度。

那么我们就可以将能够组成回文串的因素提取出来分析：

① 字符串中的两个字符相等（例如"aa"），且总数为奇数，那么我们可以选取其中一个作为回文串的中心，这是唯一一个中心，中心仅为回文串增长两个长度。

② 当字符串中的两个字符相等（例如"aa"），且字符串出现的次数大于一，我们可以选取其中的最大对数加入回文串中，平均放置在回文串的两侧，而每对字符串为回文串增加四个长度。比如字符串中出现9次，最大对数就是4对，为回文串增长4×4的长度。

③ 当我们遇到的字符串两个字符不相等（例如"xl"），我们需要判断字符串数组中是否存在其逆转字符串（"xl"的逆转字符串为"lx"）我们就获取原串与逆串对应成对的对数，有个比较好的办法就是，我们找出两者中出现较少的次数，这个次数就是两者对应的对数，每对依旧为回文串提供四个长度。

三个为回文串怎加长度的因素找到了，就可以动手实现功能，为了获取每个字符串在数组中出现的次数，我们需要遍历数组，同时使用双列集合Map来记录出现的字符串以及出现的次数（Key-Value）。Key代表出现的字符串，Value代表字符串出现的次数。

接下来我们为了判断逆串以及字符相等的串，需要借助到StringBuffer，这是可变的字符串序列，我们将字符串存入，调用reverse()方法，就能轻松获取字符串逆串，判断逆串原串是否相等，就能得知是不是字符相等的串。

之后按照上述提到的条件，来记录回文串的长度即可，需要注意的是，为了判断字符串中心是否能被获取到，我们设置一个标志，默认值为false（没有获取回文串中心）。当遇到情况①，我们将标志设置为true,这代表我们需要在返回长度前为长度+2.

提交代码：

class Solution {
    public int longestPalindrome(String[] words) {
        //创建双列集合map，存档Key-Value键值对
        //主键值Key我们存放String数组中出现的字符串。
        //Value值我们存放对应字符串出现的次数
        Map<String,Integer> map = new HashMap<>(); 
        int total = 0;

        for(String s : words){      //遍历字符串数组
            if(!map.containsKey(s)){//若集合中未记录，创建记录，出现次数为1
                 map.put(s,1);
            }else{                  //集合中以及存在记录，出现次数+1
                map.replace(s,map.get(s).intValue() + 1);
            }
        }

        boolean flag = false;  //设置标记，，默认false
        
        //利用构造器，遍历map集合，同时获取集合中每个键值对的主键Key以及Value值
        Iterator<Map.Entry<String,Integer>> iterator = map.entrySet().iterator();
        while(iterator.hasNext()){
            Map.Entry<String,Integer> entry = iterator.next();

            String key  = entry.getKey(); //主键：出现的字符串
            int value = entry.getValue(); //Value：字符串出现的次数

            StringBuffer sb = new StringBuffer();  //创建StringBuffer对象
            sb.append(key);                        //字符串存入可变字符串序列对象中
            String rev = sb.reverse().toString();  //调用reverse()获取逆串

            if(key.equals(rev)){                   //原串逆串相等，是字符相等的串
                total += value/2 * 4;              //每对串为回文串增加4个长度
                if(value%2 == 1) flag = true;      //如果字符相等串出现奇数次，设置标记为true
            }
            
            else if(map.containsKey(rev)){         //字符不相等的串
                int value_2 = map.get(rev);        //获取逆串出现的次数
                int min = Math.min(value,value_2); //出现较小次数即使对应的对数
                //每对为回文串提供4个长度，遍历过程会获取两次长度(原串一次，逆串一次)，所以需要/2
                total += min*4/2;                  
            }
        }
        if(flag) total += 2;             //如果标记为true，需要加上中心的两个长度
        return total;                    //返回最长的回文串长度
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

提交结果：

---

---

⚽求关注⚽ 作者🥇 .29. 🥇 的✔博客主页✔
⚽来刷题⚽ 记录每日LeetCode✔刷题专栏✔
您的点赞，收藏以及关注是对作者最大的鼓励喔 ~~