目录
- 模拟
- 1. 替换所有的问号
- 2. 提莫攻击
- 3. Z字形变换
- 4. 外观数列
- 5. 数青蛙
- 分治快排
- 1. 颜色分类
- 2. 排序数组
- 3. 数组中的第K个最大元素
- 4. 库存管理Ⅲ
模拟
1. 替换所有的问号
算法思路: 本题就是简单的模拟, 只需按照题目的思路遍历所有的字符, 如果为?则将其替换, 替换时寻找26个小写字母中符合要求的, 即前一个字符和后一个字符都不等于当前字符, 如果为第一个字符和最后一个字符就不需要判断.
class Solution {
public:
string modifyString(string s) {
int n = s.size();
for(int i = 0; i < n; i++)
{
if(s[i] == '?')
{
for(char ch = 'a'; ch < 'z'; ch++)
{
if((i == 0 || s[i - 1] != ch) && (i == n - 1 || s[i + 1] != ch))
{
s[i] = ch;
break;
}
}
}
}
return s;
}
};
2. 提莫攻击
算法思路: 根据题意, 如果后一个与前一个间隔小于d秒, 则只能释放它们之间的时间差值, 如果时间大于等于d秒,则可以释放d秒, 最后加上最后一个释放的时间.
class Solution {
public:
int findPoisonedDuration(vector<int>& nums, int d) {
int n = nums.size(), ret = 0;
for(int i = 1; i < n; i++)
{
int k = nums[i] - nums[i-1];
if(k < d)
ret += k;
else ret += d;
}
return ret + d;
}
};
3. Z字形变换
算法思路: 本题也可以使用模拟, 可以创建一个二维矩阵, 将所有的字符全部放到矩阵中, 然后再遍历矩阵, 但是时间复杂度和空间复杂度都为O(len * N).
第二种, 找规律, 百分之九十九的模拟题的优化都是找规律, 我们把下标列出来, 就可以直观的发现规律, 求出公差d, 然后根据公差d计算出每一行.
class Solution {
public:
string convert(string s, int numRows) {
if(numRows == 1) return s;
string ret;
int n = s.size();
int d = 2 * numRows - 2;
for(int k = 0; k < n; k += d)
ret += s[k];
for(int i = 1; i < numRows - 1; i++)
{
for(int k = i, j = d - i; k < n || j < n; k += d, j += d)
{
if(k < n) ret += s[k];
if(j < n) ret += s[j];
}
}
for(int k = numRows - 1; k < n; k += d)
ret += s[k];
return ret;
}
};
4. 外观数列
算法思路:
对于任意一个字符串, 我们仅需转换成几个什么的形式即可, 使用双指针算法, 滑动窗口, 然后转换成字符串, 进行n次变换.
class Solution {
public:
string countAndSay(int n) {
string ret = "1";
for(int i = 0; i < n - 1; i++)
{
int len = ret.size();
string tmp;
for(int left = 0 ,right = 0; right < len;)
{
while(ret[right] == ret[left]) right++;
tmp += to_string(right - left) + ret[left];
left = right;
}
ret = tmp;
}
return ret;
}
};
5. 数青蛙
算法思路: 采用哈希的思想, 如果当前字符为c,则hash[c]++, 再判断k字符是否存在, 如果存在则k–, 当遍历到其余字符时取查看前一个字符是否存在, 进行讨论, 然后遍历字符串, 除k之外如果还有多余的字符则返回-1.
class Solution {
public:
int minNumberOfFrogs(string croakOfFrogs) {
string s = "croak";
int n = s.size();
vector<int> hash(n);
unordered_map<char,int> index;
for(int i = 0 ; i < n; i++)
index[s[i]] = i;
for(auto x : croakOfFrogs)
{
if(x == 'c')
{
if(hash[n-1]) hash[n-1]--;
hash[0]++;
}
else
{
int i = index[x];
if(hash[i-1] == 0) return -1;
hash[i-1]--;hash[i]++;
}
}
for(int i = 0; i < n - 1 ; i++)
{
if(hash[i] != 0)
return -1;
}
return hash[n-1];
}
};
分治快排
1. 颜色分类
算法思路: 将数组分为三个区域, 采用三指针法, 如果=0, 则交换nums[++left]和nums[i++]. 如果nums[i] == 1, 则i直接++, 进行下一个字符的扫描, 如果等于1, 则交换nums[–right]和nums[i], 此时i不能++,因为当前字符仍然是待扫描字符, 我们的扫描是从左到右扫描, 当i和right位置相同时就不需要扫描, 此后就划分为三个区域.
class Solution {
public:
void sortColors(vector<int>& nums) {
int n = nums.size();
int left = -1, right = n, i = 0;
while(i < right)
{
if(nums[i] == 0)
swap(nums[++left],nums[i++]);
else if(nums[i] == 1) i++;
else swap(nums[--right],nums[i]);
}
}
};
2. 排序数组
算法思路: 我们采用上一道题三路划分的思想, 将数组划分为三块, 然后取最左边和最右边在进行排序, 采用随机数取基准值的方法.
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
srand(time(NULL));
qsort(nums,0,nums.size() - 1);
return nums;
}
void qsort(vector<int>& nums,int l,int r)
{
if(l >= r) return;
int tmp = getrandom(nums,l,r);
int i = l, left = l - 1, right = r + 1;
while(i < right)
{
if(nums[i] < tmp) swap(nums[++left], nums[i++]);
else if(nums[i] == tmp) i++;
else swap(nums[--right],nums[i]);
}
//[l,left] [left+1,right-1],[right,r]
qsort(nums,l,left);
qsort(nums,right,r);
}
int getrandom(vector<int>& nums,int l,int r)
{
int tmp = rand();
return nums[tmp % (r - l + 1) + l];
}
};
3. 数组中的第K个最大元素
算法思路: 本道题我们可以有多种解法, 比如排序, 堆, 但是这里我们采用快速选择算法, 根据算法导论一书的证明, 该方法的时间复杂度渐近与O(N).
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
srand(time(NULL));
return qsort(nums,0,nums.size() - 1,k);
}
int qsort(vector<int>& nums,int l,int r, int k)
{
//随机数选择
int key = getrandom(nums,l,r);
int left = l - 1, right = r + 1, i = l;
//划分区间
while(i < right)
{
if(nums[i] < key) swap(nums[++left],nums[i++]);
else if(nums[i] == key) i++;
else swap(nums[--right],nums[i]);
}
//分类讨论
//[l,left] [left+1,right-1] [right,r]
int c = r - right + 1;
int b = right - left - 1;
if(k <= c) return qsort(nums,right,r,k);
else if(b + c >= k) return key;
else return qsort(nums,l,left,k-b-c);
}
int getrandom(vector<int>& nums,int l,int r)
{
return nums[rand() % (r - l + 1) +l];
}
};
4. 库存管理Ⅲ
class Solution {
public:
vector<int> inventoryManagement(vector<int>& nums, int cnt)
{
srand(time(NULL));
qsort(nums,0,nums.size()-1,cnt);
return {nums.begin(),nums.begin()+cnt};
}
void qsort(vector<int>& nums,int l,int r, int cnt)
{
if(l >= r) return;
int key = getrandom(nums,l,r);
//划分区间
int i = l, left = l - 1, right = r + 1;
while(i < right)
{
if(nums[i] < key) swap(nums[++left],nums[i++]);
else if(nums[i] == key) i++;
else swap(nums[--right],nums[i]);
}
//分类讨论
int a = left - l + 1, b = right - left - 1;
if(cnt < a) return qsort(nums,l,left,cnt);
else if(cnt <= a + b) return;
else return qsort(nums,right,r,cnt-a-b);
}
//随机数取基准值
int getrandom(vector<int>& nums,int l,int r)
{
return nums[rand() % (r - l + 1) + l];
}
};
完