C++力扣简单算法题整理-2（字符串、数组）

1.数组中第 K 个独一无二的字符串

独一无二的字符串 指的是在一个数组中只出现过 一次 的字符串。

给你一个字符串数组 arr 和一个整数 k ，请你返回 arr 中第 k 个 独一无二的字符串 。如果 少于 k 个独一无二的字符串，那么返回 空字符串 “” 。

注意，按照字符串在原数组中的 顺序 找到第 k 个独一无二字符串。

示例 1:

输入：arr = [“d”,“b”,“c”,“b”,“c”,“a”], k = 2
输出：“a”
解释：
arr 中独一无二字符串包括 “d” 和 “a” 。
“d” 首先出现，所以它是第 1 个独一无二字符串。
“a” 第二个出现，所以它是 2 个独一无二字符串。
由于 k == 2 ，返回 “a” 。
示例 2:

输入：arr = [“aaa”,“aa”,“a”], k = 1
输出：“aaa”
解释：
arr 中所有字符串都是独一无二的，所以返回第 1 个字符串 “aaa” 。
示例 3：

输入：arr = [“a”,“b”,“a”], k = 3
输出：“”
解释：
唯一一个独一无二字符串是 “b” 。由于少于 3 个独一无二字符串，我们返回空字符串 “” 。

提示：

1 <= k <= arr.length <= 1000
1 <= arr[i].length <= 5
arr[i] 只包含小写英文字母。

class Solution {
public:string kthDistinct(vector<string>& arr, int k) {map<string, int> uMap;for(const string& str:arr){if(!uMap.count(str)){uMap[str] = 0;}uMap[str]++;}int n = 0;for(const string& str:arr){if(1 == uMap[str]){n++;if(k == n){return str;}}}return "";}
};

2.截断句子

句子 是一个单词列表，列表中的单词之间用单个空格隔开，且不存在前导或尾随空格。每个单词仅由大小写英文字母组成（不含标点符号）。

例如，“Hello World”、“HELLO” 和 “hello world hello world” 都是句子。
给你一个句子 s​​​​​​ 和一个整数 k​​​​​​ ，请你将 s​​ 截断 ​，​​​使截断后的句子仅含 前 k​​​​​​ 个单词。返回 截断 s​​​​​​ 后得到的句子。

示例 1：

输入：s = “Hello how are you Contestant”, k = 4
输出：“Hello how are you”
解释：
s 中的单词为 [“Hello”, “how” “are”, “you”, “Contestant”]
前 4 个单词为 [“Hello”, “how”, “are”, “you”]
因此，应当返回 “Hello how are you”
示例 2：

输入：s = “What is the solution to this problem”, k = 4
输出：“What is the solution”
解释：
s 中的单词为 [“What”, “is” “the”, “solution”, “to”, “this”, “problem”]
前 4 个单词为 [“What”, “is”, “the”, “solution”]
因此，应当返回 “What is the solution”
示例 3：

输入：s = “chopper is not a tanuki”, k = 5
输出：“chopper is not a tanuki”

提示：

1 <= s.length <= 500
k 的取值范围是 [1, s 中单词的数目]
s 仅由大小写英文字母和空格组成
s 中的单词之间由单个空格隔开
不存在前导或尾随空格

class Solution {
public:string truncateSentence(string s, int k) {string newStr = "";int n = 0;for(const char& c:s){if(' ' == c){n++;}if(n == k){break;}newStr += c;}return newStr;}
};

3.查找共用字符

给你一个字符串数组 words ，请你找出所有在 words 的每个字符串中都出现的共用字符（包括重复字符），并以数组形式返回。你可以按 任意顺序 返回答案。

示例 1：

输入：words = [“bella”,“label”,“roller”]
输出：[“e”,“l”,“l”]
示例 2：

输入：words = [“cool”,“lock”,“cook”]
输出：[“c”,“o”]

提示：

1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] 由小写英文字母组成

class Solution {
public:vector<string> commonChars(vector<string>& words) {vector<string> newVector;for(const char& c:words[0]){bool isExit = true;for(int i=1;i<words.size();++i){for(int j=0;j<words[i].size();++j){if(words[i][j] == c){words[i].erase(j,1);break;}if(j==words[i].size()-1){isExit = false;}}}if(isExit){string str;str= c;newVector.push_back(str);}}return newVector;}
};

4.拼写单词

给你一份『词汇表』（字符串数组） words 和一张『字母表』（字符串） chars。

假如你可以用 chars 中的『字母』（字符）拼写出 words 中的某个『单词』（字符串），那么我们就认为你掌握了这个单词。

注意：每次拼写（指拼写词汇表中的一个单词）时，chars 中的每个字母都只能用一次。

返回词汇表 words 中你掌握的所有单词的 长度之和。

示例 1：

输入：words = [“cat”,“bt”,“hat”,“tree”], chars = “atach”
输出：6
解释：
可以形成字符串 “cat” 和 “hat”，所以答案是 3 + 3 = 6。
示例 2：

输入：words = [“hello”,“world”,“leetcode”], chars = “welldonehoneyr”
输出：10
解释：
可以形成字符串 “hello” 和 “world”，所以答案是 5 + 5 = 10。

提示：

1 <= words.length <= 1000
1 <= words[i].length, chars.length <= 100
所有字符串中都仅包含小写英文字母

class Solution {
public:int countCharacters(vector<string>& words, string chars) {int num = 0;for(int i=0;i<words.size();++i){string str = words[i];string str1 = chars;for(int j=0;j<words[i].size();++j){size_t pos = str1.find(words[i][j]);if(pos != std::string::npos){str1.erase(pos,1);str.erase(str.find(words[i][j]),1);}}if("" == str){num += words[i].size();}}return num;}
};

5.文件夹操作日志搜集器

每当用户执行变更文件夹操作时，LeetCode 文件系统都会保存一条日志记录。
下面给出对变更操作的说明：
“…/” ：移动到当前文件夹的父文件夹。如果已经在主文件夹下，则 继续停留在当前文件夹 。
“./” ：继续停留在当前文件夹。
“x/” ：移动到名为 x 的子文件夹中。题目数据 保证总是存在文件夹 x 。
给你一个字符串列表 logs ，其中 logs[i] 是用户在 ith 步执行的操作。
文件系统启动时位于主文件夹，然后执行 logs 中的操作。
执行完所有变更文件夹操作后，请你找出 返回主文件夹所需的最小步数 。

示例 1：
输入：logs = [“d1/”,“d2/”,“…/”,“d21/”,“./”]
输出：2
解释：执行 “…/” 操作变更文件夹 2 次，即可回到主文件夹

示例 2：
输入：logs = [“d1/”,“d2/”,“./”,“d3/”,“…/”,“d31/”]
输出：3
示例 3：

输入：logs = [“d1/”,“…/”,“…/”,“…/”]
输出：0

提示：
1 <= logs.length <= 103
2 <= logs[i].length <= 10
logs[i] 包含小写英文字母，数字，‘.’ 和 ‘/’
logs[i] 符合语句中描述的格式
文件夹名称由小写英文字母和数字组成

class Solution {
public:int minOperations(vector<string>& logs) {int curPos = 0;for(const string& str:logs){if('.' == str[0]){if('.' == str[1] && 0 != curPos){curPos--;}}else{curPos++;}}return curPos;}
};

6.统计前后缀下标对 I

给你一个下标从 0 开始的字符串数组 words 。

定义一个 布尔 函数 isPrefixAndSuffix ，它接受两个字符串参数 str1 和 str2 ：

当 str1 同时是 str2 的前缀（
prefix
）和后缀（
suffix
）时，isPrefixAndSuffix(str1, str2) 返回 true，否则返回 false。
例如，isPrefixAndSuffix(“aba”, “ababa”) 返回 true，因为 “aba” 既是 “ababa” 的前缀，也是 “ababa” 的后缀，但是 isPrefixAndSuffix(“abc”, “abcd”) 返回 false。

以整数形式，返回满足 i < j 且 isPrefixAndSuffix(words[i], words[j]) 为 true 的下标对 (i, j) 的 数量 。

示例 1：

输入：words = [“a”,“aba”,“ababa”,“aa”]
输出：4
解释：在本示例中，计数的下标对包括：
i = 0 且 j = 1 ，因为 isPrefixAndSuffix(“a”, “aba”) 为 true 。
i = 0 且 j = 2 ，因为 isPrefixAndSuffix(“a”, “ababa”) 为 true 。
i = 0 且 j = 3 ，因为 isPrefixAndSuffix(“a”, “aa”) 为 true 。
i = 1 且 j = 2 ，因为 isPrefixAndSuffix(“aba”, “ababa”) 为 true 。
因此，答案是 4 。
示例 2：

输入：words = [“pa”,“papa”,“ma”,“mama”]
输出：2
解释：在本示例中，计数的下标对包括：
i = 0 且 j = 1 ，因为 isPrefixAndSuffix(“pa”, “papa”) 为 true 。
i = 2 且 j = 3 ，因为 isPrefixAndSuffix(“ma”, “mama”) 为 true 。
因此，答案是 2 。
示例 3：

输入：words = [“abab”,“ab”]
输出：0
解释：在本示例中，唯一有效的下标对是 i = 0 且 j = 1 ，但是 isPrefixAndSuffix(“abab”, “ab”) 为 false 。
因此，答案是 0 。

提示：

1 <= words.length <= 50
1 <= words[i].length <= 10
words[i] 仅由小写英文字母组成

class Solution {
public:int countPrefixSuffixPairs(vector<string>& words) {int n = 0;for(int i=0;i<words.size();++i){for(int j=i+1;j<words.size();++j){if(isPrefixAndSuffix(words[i], words[j])){n++;}}}return n;}bool isPrefixAndSuffix(string str1, string str2){if(str1.size() > str2.size()){return false;}string newStr = "";for(int i=0;i<str1.size();++i){newStr += str2[i];}if(str1 != newStr){return false;}newStr = "";for(int j=str2.size() - str1.size();j<str2.size();++j){newStr += str2[j];}if(str1 != newStr){return false;}return true;}
};

7.删列造序

给你由 n 个小写字母字符串组成的数组 strs，其中每个字符串长度相等。

这些字符串可以每个一行，排成一个网格。例如，strs = [“abc”, “bce”, “cae”] 可以排列为：

abc
bce
cae
你需要找出并删除 不是按字典序非严格递增排列的 列。在上面的例子（下标从 0 开始）中，列 0（‘a’, ‘b’, ‘c’）和列 2（‘c’, ‘e’, ‘e’）都是按字典序非严格递增排列的，而列 1（‘b’, ‘c’, ‘a’）不是，所以要删除列 1 。

返回你需要删除的列数。

示例 1：

输入：strs = [“cba”,“daf”,“ghi”]
输出：1
解释：网格示意如下：
cba
daf
ghi
列 0 和列 2 按升序排列，但列 1 不是，所以只需要删除列 1 。
示例 2：

输入：strs = [“a”,“b”]
输出：0
解释：网格示意如下：
a
b
只有列 0 这一列，且已经按升序排列，所以不用删除任何列。
示例 3：

输入：strs = [“zyx”,“wvu”,“tsr”]
输出：3
解释：网格示意如下：
zyx
wvu
tsr
所有 3 列都是非升序排列的，所以都要删除。

提示：

n == strs.length
1 <= n <= 100
1 <= strs[i].length <= 1000
strs[i] 由小写英文字母组成

class Solution {
public:int minDeletionSize(vector<string>& strs) {int n = 0;for(int i=0;i<strs[0].size();++i){for(int j=0;j<strs.size()-1;++j){int i1 = strs[j][i]-'a';int i2 = strs[j+1][i]-'a';if(i1 > i2){n++;break;}}}return n;}
};