算法--模拟题目
算法–模拟问题
- 1576. 替换所有的问号
思路:遍历字符串,找到?, 然后遍历字符'a' 到 'z' 找到不等于前后字符,替换即可
class Solution {
public:string modifyString(string s) {for(int i = 0; i < s.size(); i++){if(s[i] == '?'){//替换for(char a = 'a'; a <= 'z'; a++){//当字符不等于第一个字符并且前一个字符等于当前字符是继续.//或当字符不等于最后一个字符且字符后一个字符等于当前字符时继续.if((i > 0 && s[i-1] == a) || i < s.size()-1 && s[i+1] == a){continue;}s[i] = a;break;}}}return s;}
};
- 495. 提莫攻击
思路: 有两种情况:1. 第二次攻击在第一次的中毒持续时间之内, 即 第二次攻击时间 - 第一次攻击时间 >= duration, 则 ans += duration 即可2. 第二次攻击时间在第一中毒持续时间之外, 即 第二次攻击时间 - 第一次攻击时间 < duration 则 ans += duration 即可最后 需要 + duration, 因为最后一次攻击没有考虑在内.
class Solution {
public:int findPoisonedDuration(vector<int>& timeSeries, int duration) {int ans = 0; if(timeSeries.size() == 1){return duration;}for(int right = 1; right < timeSeries.size(); right++){int left = right -1;int x = timeSeries[right] - timeSeries[left];if(x >= duration)ans += duration;else ans += x;}return ans + duration;}
};
-
- N 字形变换](https://gitee.com/link?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Fzigzag-conversion%2F)
思路:用数字模拟字符串找规律即可
0 6 12
1 5 7 11 13
2 4 8 10 14 16
3 9 15
第一行和最后一行的公差d = numRows;
中间行: 每次成对出现,(1,5) (7,11).... 规律: 第二个数 = d - 第一个数, 往后每对数分别增加 d
class Solution {
public:string convert(string s, int numRows) {string ans;int n = s.size();int d = numRows * 2 -2;if(numRows == 1){return s;}//处理第一行for(int i = 0; i < n; i += d){ans += s[i];}//处理中间行for(int row = 1; row < numRows - 1 ; row++){for(int i = row, j = d - i; i < n || j < n; i += d, j += d){if(i < n) ans += s[i];if(j < n) ans += s[j];}}//处理最后一行for(int i = numRows-1; i < n; i += d){ans += s[i];}return ans;}
};
- 38. 外观数列
思路: 使用双指针来确定ans中相同字符的个数和是什么字符.
class Solution {
public:string countAndSay(int n) {string ans{"1"};if(n == 1){return ans;}for(int i = 2; i <= n; i++){ans = describe(ans);}return ans;}string describe(string input){string output;int size = input.size();int left = 0; int right = 0;while(right <= size){if(right == size){output += std::to_string(right - left);output += input[left];return output;}if(input[right] == input[left]){right++;}else {output += std::to_string(right - left);output += input[left];left = right;}}return "0";}
};
- 1419. 数青蛙
思路:使用hash表解决
unordered_map<char,int> map; 存放字符和下标之间的映射关系
vector<int> hash; 模拟哈希表.存放字符出现的次数.
遍历字符串:有两种情况:当前字符是 'c', 需要看一下hash中'k'字符出现的次数是否为0,当为0时,表示此时没有一个青蛙完成叫完,'c'字符++即可,当不为0时,此时表示已经有青蛙叫完,需要'k'--,'c'++ 表示至少有多少只青蛙.当前字符不为'c',需要判断hash中前一个字符次数是否为0,当为零时,表示错误,直接返回-1,即叫出当前字符前必须已经叫出前一个字符,否则错误.当不为零时, 前一个字符次数--, 当前字符次数++;即可.
class Solution {
public:int minNumberOfFrogs(string croakOfFrogs) {unordered_map<char,int> map;//存放字符和下标的映射string s{"croak"};for(int i = 0; i < s.size(); i++){map[s[i]] = i;}vector<int> hash(5);for(char c : croakOfFrogs){if(c == 'c'){int index = map['k'];if(hash[index] != 0){hash[index]--;}hash[0]++;}else {int index = map[c];if(hash[index-1] != 0){hash[index -1]--;hash[index]++;}else{return -1;}}}for(int i = 0; i < hash.size()-1; i++){if(hash[i] != 0)return -1;}return hash[hash.size()-1];}
};
完!!!