1002 Find Common Characters
题目描述
Given an array A of strings made only from lowercase letters, return a list of all characters that show up in all strings within the list (including duplicates). For example, if a character occurs 3 times in all strings but not 4 times, you need to include that character three times in the final answer.
You may return the answer in any order.
题目解析
寻找字符串中出现的相同字符，重复的字符按照重复的次数算。
每个字符串是等长的，以第一个字符串为标准对其他字符串进行字符查找，如果找到该字符，就删除该字符，因为被查找的字符中可能有重复的字符，计数器加1，若其他字符串都有这个字符，计数器的值为A.size()-1，最后判断计数器，直接将字符push_back进入res会报类型错误，可以用一个string类型的变量中转一下。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25class Solution {
public:
vector<string> commonChars(vector<string>& A) {
vector<string> res;
string s;
size_t npos = -1;
int i,j,num=0;
for(i=0;i<A[0].length();i++){
for(j=1;j<A.size();j++){
int pos = A[j].find_first_of(A[0][i]);
if(pos != npos){
num += 1;
A[j].erase(pos,1);
}
}
if(num==A.size()-1){
s = A[0][i];
res.push_back(s);
}
num = 0;
}
return res;
}
};
557 Reverse Words in a String III
题目描述
Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.
Example 1:
Input: “Let’s take LeetCode contest”
Output: “s’teL ekat edoCteeL tsetnoc”
Note: In the string, each word is separated by single space and there will not be any extra space in the string.
题目解析
以空格为间隔，对字符串内的每个子串进行反转。
思路：以空格为间隔，取每个子串，然后对每个子串反转，然后连接。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
33class Solution {
public:
string reverseWords(string s){
string res = "";
int pre_space = -1;
int space = 0;
string str;
while(space != -1){
space = s.find(' ',space+1);
str = s.substr(pre_space+1,space-pre_space-1);
reverseWord(str);
res += str;
res += " ";
pre_space = space;
}
res.erase(res.length()-1,1);
return res;
}
void reverseWord(string &s){
if(s.length()==0)
return;
char temp;
int length = s.length();
for(int i=0;i<length/2;i++){
temp = s[i];
s[i] = s[length-1-i];
s[length-1-i] = temp;
}
return;
}
};
优化
看到一个排名靠前的解法，遍历字符串，以空格为间隔，如果遇到空格，则以倒序连接在res字符串中。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
26class Solution {
public:
string reverseWords(string s) {
ios::sync_with_stdio(false);
string ans="";
string temp="";
s+=' ';
for(int i=0;i<s.length();i++){
if(s[i]!=' ')
temp+=s[i];
else{
for(int j=0;j<temp.length();j++){
ans+=temp[temp.length()-j-1];
}
if(i<s.length()-1)
ans+=' ';
temp="";
}
}
return ans;
}
};
821 Shortest Distance to a Character
题目描述
Given a string S and a character C, return an array of integers representing the shortest distance from the character C in the string.1
2
3Example 1:
Input: S = "loveleetcode", C = 'e'
Output: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]
题目解析
返回字符串中每一个位置距离给定字符的最小距离，给定字符C必定包含在字符串中，注意不是返回字符串中每个字符距离给定字符的最小距离。
我的方法是先找出C在字符串中的所有位置，然后再计算每一个位置与字符C的距离，取最小值。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24class Solution {
public:
vector<int> shortestToChar(string S, char C) {
vector<int> dis(S.length(),S.length()+1);
vector<int> pos;
int first_idx = S.find(C,0);
for(int i=0;i<S.length();i++){
dis[i] = abs(i-first_idx);
if(S[i] == C){
pos.push_back(i);
dis[i] = 0;
}
}
for(int i=0;i<dis.size();i++){
for(int j=1;j<pos.size();j++){
if(dis[i] > abs(pos[j] - i))
dis[i] = abs(pos[j] - i);
}
}
return dis;
}
};
优化
优化：看了计算复杂度较低的解法，设返回值dis：
先遍历字符串，找出字符C的位置，对应位置的dis[i]=0；
再次遍历字符串，若遇到的是目标字符，则以该字符为界，分别向左右两边遍历，更新每个dis的最小值。count记录遍历的位置距离目标字符的距离，每次向左或向右移动时，count++。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
34class Solution {
public:
vector<int> shortestToChar(string S, char C) {
int len = S.length();
int count;
vector<int> vec(len,20000);
for(int i=0;i<len;i++)
{
if(S[i] == C)
vec[i] = 0;
}
for(int i=0;i<len;i++)
{
if(vec[i] == 0)
{
count =1;
for(int j = i-1;j>= 0 ;j--)
{
if(vec[j] > count)
vec[j] = count;
count++;
}
count = 1;
for(int j = i+1;j<len ;j++)
{
if(vec[j] > count)
vec[j] = count;
count++;
}
}
}
return vec;
}
};
1047 Remove All Adjacent Duplicates In String
题目描述
Given a string S of lowercase letters, a duplicate removal consists of choosing two adjacent and equal letters, and removing them.
We repeatedly make duplicate removals on S until we no longer can.
Return the final string after all such duplicate removals have been made. It is guaranteed the answer is unique.
题目解析
反复的删除给定字符串中两个相邻且相等的字符。
做的时候有一个问题就是不要调用S.erase()在原来字符串S上进行删除，因为在遍历中S.length()作为循环的遍历条件，运行过程会出现Runtime Error。
看到题目属于的类别是栈，相邻其实就是将栈顶的字符与字符串中未入栈的字符比较，如果相等，则弹出栈顶字符，否则压入字符串中被比较的字符。如果栈为空，就直接压入字符串中的字符。
还是对一些数据结构的特点不熟悉，无法快速的转化。1
2
3
4
5
6
7
8
9
10
11
12
13
14class Solution {
public:
string removeDuplicates(string S){
string res;
for(int i=0;i<S.length();i++){
if(!res.empty() && res[res.size()-1] == S[i]){
res.pop_back();
}
else
res.push_back(S[i]);
}
return res;
}
};
参考
344 Reverse String
题目简述
Write a function that reverses a string. The input string is given as an array of characters char[].
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
You may assume all the characters consist of printable ascii characters.
题目解析
反转字符串，要求空间复杂度为O(1)。1
2
3
4
5
6
7
8
9
10
11class Solution {
public:
void reverseString(vector<char>& s){
for(int i=0;i<s.size()/2;i++){
char temp = s[i];
s[i] = s[s.size()-1-i];
s[s.size()-1-i] = temp;
}
return;
}
};
优化：直接调用swap函数进行两个字符的交换，关闭iostream的输入缓存。1
2ios::sync_with_stdio(false);
cin.tie(0);