您的位置: 首页  >  IT文章  >  [leetcode]Weekly Contest 68 （767. Reorganize String&&769. Max Chunks To Make Sorted&&768. Max Chunks To Make Sorted II）

[leetcode]Weekly Contest 68 （767. Reorganize String&&769. Max Chunks To Make Sorted&&768. Max Chunks To Make Sorted II）

分类: IT文章 • 2022-03-07 17:45:47

766. Toeplitz Matrix

第一题不说，贼麻瓜，好久没以比赛的状态写题，这个题浪费了快40分钟，我真是。。。。。。

767. Reorganize String

就是给你一个字符串，能不能转换成：任意一个字符S[i]，使得S[i-1]和S[i+1]都不等于S[i]。如果能输出，不能就输出一个空字符串。

大一的时候好像有印象，队友做出来的，贪心吧，如果遇到相邻两个一样的，就从后面找一个插到中间，具体原理我也不知道为什么，反正是对的，从头到尾扫一遍，再倒着来一遍，为什么要两边我也不知道，反正是对的。。。我也很凌乱啊！！！

 1 class Solution {
 2 public:
 3     string reorganizeString(string S) {
 4         int len = S.size();
 5         string ts = S;
 6         bool ans1 = true;
 7         for(int i=0;i<len;i++)
 8         {
 9             if(ts[i]==ts[i+1]) {
10                 if(i == len-2) ans1 = false;
11                 for(int j=i+2;j<len;j++)
12                 {
13                     if(ts[j]!=ts[i] && ts[j]!=ts[i+1])
14                     {
15                         swap(ts[j], ts[i+1]);
16                         break;
17                     }
18                     if(j == len-1) {
19                         ans1 = false;
20                     }
21                 }
22             }
23         }
24         string ts2 = ts;
25         reverse(ts2.begin(), ts2.end());
26         bool ans2 = true;
27         for(int i=0;i<len;i++)
28         {
29             if(ts2[i]==ts2[i+1]) {
30                 if(i == len-2) ans2 = false;
31                 for(int j=i+2;j<len;j++)
32                 {
33                     if(ts2[j]!=ts2[i] && ts2[j]!=ts2[i+1])
34                     {
35                         swap(ts2[j], ts2[i+1]);
36                         break;
37                     }
38                     if(j == len-1) {
39                         ans2 = false;
40                     }
41                 }
42             }
43         }
44         if(ans1){
45             return ts;
46         }
47         else if(ans2) {
48             return ts2;
49         }
50         else {
51             return "";
52         }
53     }
54 };
View Code

769. Max Chunks To Make Sorted

给你一个序列，问你把这个序列分成n块，每个块单独排序，且排完序后和整体排序得到的结果要一模一样，求n的最大值

因为这个题说了，序列的内容是0——length-1，所以序列的内容唯一且连续

遍历序列从i到length-1，对前i的内容进行求最大值max，和最小值min，若在前i的序列中，min == 下标的最小值，max == 下标的最大值，即最小块，只是比赛时想到的，虽然也对，但太麻烦

 1 class Solution {
 2 public:
 3     int maxChunksToSorted(vector<int>& arr) {
 4         int ans = 0;
 5         int start = 0;
 6         while(start != arr.size()){
 7             int min = arr[start], max = arr[start];
 8             for(int end=start;end<arr.size();end++)
 9             {
10                 max = max>arr[end]?max:arr[end];
11                 min = min<arr[end]?min:arr[end];
12                 if(min == start&&max == end) {
13                     ans ++;
14                     start = end + 1;
15                     break;
16                 }
17             }
18         }
19         return ans;
20     }
21 };
View Code

题解，只用求最大值就可以了，因为所以序列的内容唯一且连续，所以若arr[i]为最大值且 i == arr[i]，则说明，小于 i的部分已经可以且一定顺序连续地排序

1 class Solution(object):
2     def maxChunksToSorted(self, arr):
3         ans = ma = 0
4         for i, x in enumerate(arr):
5             ma = max(ma, x)
6             if ma == i: ans += 1
7         return ans

768. Max Chunks To Make Sorted II

这是第二题的升级版

序列里的内容不一定（唯一且连续）了，其他都是一样的

我们来看一个特殊的序列1，1，0，0，1

对于正确的序列来说，是0，0，1，1，1

如果用上一种方法，那么到第三个数的时候，ans就要加一了

所以判断是否是最小且正确的块的时候，还要判断，前面出现的内容，和全部排好序的序列，是否一致

我在这里引入一个已遍历的序列和作为判断，这个算法的正确性，我还不得而知，我自己甚至认为可能不对，因为我数学学得是真的烂。。。。。。

希望若有人证明是正确的可以告诉我

 1 class Solution:
 2     def maxChunksToSorted(self, arr):
 3         ans = 0
 4         sum1 = 0
 5         sum2 = 0
 6         arr_pre_max = arr[0]
 7         tarr = sorted(arr)
 8         for x, y in zip(arr, tarr):
 9             sum1 += x
10             sum2 += y
11             arr_pre_max = max(arr_pre_max, x)
12             if arr_pre_max == y and sum1 == sum2:
13                 ans += 1
14         return ans

最后一题没做看起来很难的样子

相关推荐