知识星球 英雄算法联盟 五月集训 打卡第二天（2）_键盘出现了一些故障,有些字母无法正常工作 算法

 

---

目录

 三、题目三

1、题目描述

2、基础框架

3、原题链接

二、解题报告

1、思路分析

2、代码详解

  四、题目四

1、题目描述

2、基础框架

3、原题链接

二、解题报告

1、思路分析

2、代码详解

---

---

 一、题目三  1047

1、题目描述

  

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例 1：

输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

2、基础框架

   Java 版本给出的基础框架代码如下：   

 class Solution {
    public String removeDuplicates(String S) {
}

提示：

1. 1 <= S.length <= 20000
2. S 仅由小写英文字母组成。

                            ​

3、原题链接

    LeetCode 1047. 删除字符串中的所有相邻重复项

二、解题报告

1、思路分析

利用栈的思想，

只需要遍历该字符串，如果当前字符和栈顶字符相同，我们就贪心地将其消去，否则就将其入栈即可。

2、代码详解

class Solution {
    public String removeDuplicates(String S) {
        int index = -1;
        char[] chars = S.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if (index >= 0 && chars[index] == chars[i]) {
                index--;
            } else {
                index++;
                chars[index] = chars[i];
            }
        }
        return String.copyValueOf(chars, 0, index + 1);
    }
}

 二、题目四 1935

1、题目描述

键盘出现了一些故障，有些字母键无法正常工作。而键盘上所有其他键都能够正常工作。

给你一个由若干单词组成的字符串 text ，单词间由单个空格组成（不含前导和尾随空格）；另有一个字符串 brokenLetters ，由所有已损坏的不同字母键组成，返回你可以使用此键盘完全输入的 text 中单词的数目。

示例 1：

输入：text = "hello world", brokenLetters = "ad"
输出：1
解释：无法输入 "world" ，因为字母键 'd' 已损坏。

示例 2：

输入：text = "leet code", brokenLetters = "lt"
输出：1
解释：无法输入 "leet" ，因为字母键 'l' 和 't' 已损坏。

示例 3:

输入：text = "leet code", brokenLetters = "e"
输出：0
解释：无法输入任何单词，因为字母键 'e' 已损坏。

2、基础框架

   Java 版本给出的基础框架代码如下：   

class Solution {
    public int canBeTypedWords(String text, String brokenLetters) {
}

提示：

•     1 <= text.length <= 10000
•     0 <= brokenLetters.length <= 26
•     text 由若干用单个空格分隔的单词组成，且不含任何前导和尾随空格
•     每个单词仅由小写英文字母组成
•     brokenLetters 由 互不相同 的小写英文字母组成

3、原题链接

    LeetCode 1935. 可以输入的最大单词数

二、解题报告

1、思路分析

见代码详解注释

2、代码详解

class Solution {
    public int canBeTypedWords(String text, String brokenLetters) {
       int n=text.length();
       //将字符串按" "分为若干字符数组
        String[] str=text.split(" ");
        //把坏掉的字母转换成char[]
        char[] chars = brokenLetters.toCharArray();
        int rst=0;
        //两层遍历外层放存放单词的数组
        for(int i=0;i<str.length;i++){
            //内层放存放坏掉的字母的char数组
            for(int j=0;j<chars.length;j++){
                //如果str[i]中含有坏掉的字母则计数++，且结束本次循环防止重复查找
                if(str[i].contains(chars[j]+"")){
                    rst++;
                    break;
                }
            }
        }
        //返回总的单词数减去含有坏的字母的单词数即为可以完全输入的单词数目
       return str.length-rst;
    }
}