LeetCode 1545. Find Kth Bit in Nth Binary String
- 题目描述
- 思路
- 代码
- 复杂度分析
题目描述
Given a string s of lower and upper case English letters.
A good string is a string which doesn’t have two adjacent characters s[i] and s[i + 1] where:
0 <= i <= s.length - 2
s[i] is a lower-case letter and s[i + 1] is the same letter but in upper-case or vice-versa.
To make the string good, you can choose two adjacent characters that make the string bad and remove them. You can keep doing this until the string becomes good.
Return the string after making it good. The answer is guaranteed to be unique under the given constraints.
Notice that an empty string is also good.
Example 1:
Input: s = “leEeetcode”
Output: “leetcode”
Explanation: In the first step, either you choose i = 1 or i = 2, both will result “leEeetcode” to be reduced to “leetcode”.
Example 2:
Input: s = “abBAcC”
Output: “”
Explanation: We have many possible scenarios, and all lead to the same answer. For example:
“abBAcC” --> “aAcC” --> “cC” --> “”
“abBAcC” --> “abBA” --> “aA” --> “”
Example 3:
Input: s = “s”
Output: “s”
Constraints:
1 <= s.length <= 100
s contains only lower and upper case English letters.
思路
2020年8月8日周赛第一题，当时周赛的时候看完这个题一下还没反应过来，懵了几分钟才想到是栈。这个题数据量只有100，暴力扫描也是可以的。题目的意思是中间的消掉以后两头的还能碰到一起继续消。这个题目是个简单的“消消乐”问题，而且只要最后消完的结果，消消乐规则也很无脑。主要是保证中间的消完了两头的还能见到面就行。
代码
const int d = abs('A' - 'a');//定义了一个常量，同一个字母大小写之间的差值
class Solution {
public:string makeGood(string s) {int n = s.length();string res;for ( auto c : s ) {if ( !res.empty() && abs(res.back() - c) == d ) res.pop_back(); //消掉了else res.push_back(c); }return res;}
};
};
复杂度分析
时间o(n)
空间o(1)，这里利用了res的空间来当栈，额外空间是o(1)