算法题一(贪心算法类型)

题目来自leetcode

第一题 平衡字符串

在一个「平衡字符串」中，’L’ 和 ‘R’ 字符的数量是相同的。

给出一个平衡字符串 s，请你将它分割成尽可能多的平衡字符串。

返回可以通过分割得到的平衡字符串的最大数量。

示例 1：

1
2
3
输入：s = "RLRRLLRLRL"
输出：4
解释：s 可以分割为 "RL", "RRLL", "RL", "RL", 每个子字符串中都包含相同数量的 'L' 和 'R'。

示例 2：

1
2
3
输入：s = "RLLLLRRRLR"
输出：3
解释：s 可以分割为 "RL", "LLLRRR", "LR", 每个子字符串中都包含相同数量的 'L' 和 'R'。

示例 3：

1
2
3
输入：s = "LLLLRRRR"
输出：1
解释：s 只能保持原样 "LLLLRRRR".

提示：

1
2
1 <= s.length <= 1000
s[i] = 'L' 或 'R'

解题答案已通过

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
class Solution {
    public int balancedStringSplit(String s) {
        int result=0;
        int numR=0;
        int numL=0;
        char[] schar=s.toCharArray();

         for (int i=0;i<=schar.length-1;i++){

             if(schar[i]=='R')
             {
                 numR++;
             }
             if(schar[i]=='L'){
                 numL++;
             }
             if(numR==numL&&numR!=0)
             {
                 result++;
                 numR=0;
                 numL=0;
             }

         }
       return result;
    }
}

思路

开始走了一些弯路,试图使用这种判断方式

1
2
3
4
5
6
7
if(schar[i]=='R')
       {
           numR++;
       }
       if(schar[i+1]=='L'){
           numL++;
       }

示例一和3都能过

但这种不回去判断最后一个

在解示例2时

分成了这几组

i=0时 获得 RL 一组

i-7时 获得 LLLRRR

i =8时 numL+1 不去遍历最后一个9

这题基本没啥难度..

官方题解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int balancedStringSplit(String s) {
        int R=0,L=0,ans=0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='R') R++;
            else if(s.charAt(i)=='L') L++;
            if(R==L) ans++;
            if(Math.abs(R-L)>(s.length()-1-i)) return ans;
        }
        return  ans;
    }
}

作者：xi_xi_xi
链接：https://leetcode-cn.com/problems/split-a-string-in-balanced-strings/solution/guan-fang-ti-jie-by-xi_xi_xi/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

第二题 删列造序

给定由 N 个小写字母字符串组成的数组 A，其中每个字符串长度相等。

删除 操作的定义是：选出一组要删掉的列，删去 A 中对应列中的所有字符，形式上，第 n 列为 [A[0][n], A[1][n], …, A[A.length-1][n]]）。

比如，有 A = [“abcdef”, “uvwxyz”]，

要删掉的列为 {0, 2, 3}，删除后 A 为[“bef”, “vyz”]， A 的列分别为[“b”,”v”], [“e”,”y”], [“f”,”z”]。

你需要选出一组要删掉的列 D，对 A 执行删除操作，使 A 中剩余的每一列都是 非降序 排列的，然后请你返回 D.length 的最小可能值。

示例 1：

1
2
3
4
5
输入：["cba", "daf", "ghi"]
输出：1
解释：
当选择 D = {1}，删除后 A 的列为：["c","d","g"] 和 ["a","f","i"]，均为非降序排列。
若选择 D = {}，那么 A 的列 ["b","a","h"] 就不是非降序排列了。

示例 2：

1
2
3
输入：["a", "b"]
输出：0
解释：D = {}

示例 3：

1
2
3
输入：["zyx", "wvu", "tsr"]
输出：3
解释：D = {0, 1, 2}

提示：

1
2
1 <= A.length <= 100
1 <= A[i].length <= 1000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/delete-columns-to-make-sorted
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这里我想的太绕了 直接看了答案

代码解释如下

方法一：贪心
对于每一列，我们检查它是否是有序的。如果它有序，则将答案增加 1，否则它必须被删除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
    public int minDeletionSize(String[] A) {
        int ans = 0;
        for (int c = 0; c < A[0].length(); ++c)
            for (int r = 0; r < A.length - 1; ++r)
                if (A[r].charAt(c) > A[r+1].charAt(c)) {
                    ans++;
                    break;
                }

        return ans;
    }

}

复杂度分析

时间复杂度：O(N)O(N)，其中 NN 是数组 A 中的元素个数。

空间复杂度：O(1)O(1)。

作者：LeetCode
链接：https://leetcode-cn.com/problems/delete-columns-to-make-sorted/solution/shan-lie-zao-xu-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。