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 | class Solution { |
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 | class Solution { |
优化
看到一个排名靠前的解法,遍历字符串,以空格为间隔,如果遇到空格,则以倒序连接在res字符串中。
1 | class Solution { |
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 | Example 1: |
题目解析
返回字符串中每一个位置距离给定字符的最小距离,给定字符C必定包含在字符串中,注意不是返回字符串中每个字符距离给定字符的最小距离。
我的方法是先找出C在字符串中的所有位置,然后再计算每一个位置与字符C的距离,取最小值。
1 | class Solution { |
优化
优化:看了计算复杂度较低的解法,设返回值dis:
先遍历字符串,找出字符C的位置,对应位置的dis[i]=0;
再次遍历字符串,若遇到的是目标字符,则以该字符为界,分别向左右两边遍历,更新每个dis的最小值。count记录遍历的位置距离目标字符的距离,每次向左或向右移动时,count++。
1 | class Solution { |
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 | class Solution { |
参考
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 | class Solution { |
优化:直接调用swap函数进行两个字符的交换,关闭iostream的输入缓存。
1 | ios::sync_with_stdio(false); |