13-其余问题
1.模拟
31. 下一个排列
class Solution {
public:
void nextPermutation(vector<int>& nums) {
for(int i = nums.size() - 1; i >= 0; i--)
{
for(int j = nums.size() - 1; j > i;j--)
{
if(nums[j] > nums[i])
{
swap(nums[j],nums[i]);
reverse(nums.begin() + i + 1, nums.end());
return;
}
}
}
reverse(nums.begin(), nums.end());
}
};
556. 下一个更大元素 III
class Solution {
public:
int nextGreaterElement(int n) {
string s = to_string(n);
for(int i = s.size() - 1;i >= 0; i--)
{
for(int j = s.size() - 1; j > i ;j--)
{
if(s[i] < s[j])
{
swap(s[i],s[j]);
reverse(s.begin() + i + 1,s.end());
long r = stol(s);
return (r <= INT_MAX && r != (long)n) ? r : -1;
}
}
}
return -1;
}
};
463. 岛屿的周长
class Solution {
int calc(vector<vector<int>>& grid,int i ,int j)
{
int c = 0;
if (i == 0 || grid[i-1][j] == 0) c++;
if (i == grid.size() - 1 || grid[i+1][j] == 0) c++;
if (j == 0 || grid[i][j-1] == 0) c++;
if (j == grid[0].size() -1 || grid[i][j+1] == 0) c++;
return c;
}
public:
int islandPerimeter(vector<vector<int>>& grid) {
int row = grid.size() , col = grid[0].size();
int count = 0;
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
if (grid[i][j] == 1)
{
count += calc(grid,i,j);
}
}
}
return count;
}
};
166. 分数到小数***
class Solution {
using ll = long long;
public:
string fractionToDecimal(int numerator, int denominator) {
ll n = numerator, d = denominator;
string ret;
// 计算整数部分
// 判断负数
if(n * d < 0) ret += "-";
ll a = n / d;
if(a < 0) a *= -1;
ret += to_string(a);
if(n < 0) n*= -1;
if(d < 0) d*= -1;
// 计算小数部分
n %= d;
if(n == 0) {
// 无小数
return ret;
}
ret += ".";
// 连除
// 哈希表记录是否有数组第二次出现
unordered_map<int, int> st;
string t;
int index = 0;
while(n && !st.count(n)) {
st[n] = index++;
n *= 10;
t.push_back((char)(n / d + '0'));
n %= d;
}
if(n != 0) {
// 说明出现了循环，此时对循环部分 [st[n], index] 加括号
ret += t.substr(0, st[n]) + "(" + t.substr(st[n]) + ")";
} else {
ret += t;
}
return ret;
}
};
2.排序
剑指 Offer 45. 把数组排成最小的数
class Solution {
public:
string minNumber(vector<int>& nums) {
sort(nums.begin(),nums.end(),[&](const int &a , const int &b){
string sa = to_string(a);
string sb = to_string(b);
return sa + sb < sb + sa;
});
string res;
for(int x :nums) res += to_string(x);
return res;
}
};
LCR 034. 验证外星语词典
class Solution {
public:
bool isAlienSorted(vector<string>& words, string order) {
vector<string> words_sort = words;
unordered_map<char,int> umap;
for(int i = 0; i < order.size() ;i++) umap[order[i]] = i;
sort(words_sort.begin(),words_sort.end(),[&](const string &s1,const string &s2){
int left = 0 , right = 0;
while(left < s1.size() && right < s2.size())
{
if(umap[s1[left]] > umap[s2[right]]) return false;
else if(umap[s1[left]] < umap[s2[right]]) return true;
left++;
right++;
}
if(right < s2.size()) return true;
else return false;
});
return words == words_sort;
}
};
LCR 035. 最小时间差
class Solution {
public:
int findMinDifference(vector<string>& timePoints) {
vector<int> res(timePoints.size());
for(int i = 0; i < timePoints.size();i++)
{
res[i] = 60 * stoi(timePoints[i].substr(0,2)) + stoi(timePoints[i].substr(3,2));
}
sort(res.begin(),res.end());
int mins = min(abs(res[0] - res.back()),abs(res[0] - res.back() + 24 * 60));
for(int i = 1 ; i < res.size();i++)
{
mins = min(mins,res[i] - res[i - 1]);
}
return mins;
}
};LCR 035. 最小时间差
215. 数组中的第K个最大元素（快排版本）
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
//快排思想 - 最左边 第k个值
function<int (int ,int)> quitSort = [&](int start , int end)->int{
//if(start >= end) return ;
int left = start , right = end , tmp = nums[start];
while(left < right)
{
while(left < right && nums[right] >= tmp) right--;
nums[left] = nums[right];
while(left < right && nums[left] <= tmp) left++;
nums[right] = nums[left];
}
nums[left] = tmp;
//left值是 nums数组中 第 nums.size() - left大的数
if(nums.size() - k == left) return nums[left];
else if(nums.size() - k > left) return quitSort(left + 1 ,end);
else return quitSort(start,left - 1);
};
return quitSort(0,nums.size() - 1);
}
};
786. 第 K 个最小的素数分数
class Solution {
public:
vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) {
vector<pair<int,int>> nums;
int n = arr.size();
for(int i = 0; i < n - 1; i++) {
for(int j = i + 1; j < n; j++) {
nums.push_back({arr[i],arr[j]});
}
}
sort(nums.begin(),nums.end(),[](const auto& a,const auto& b) {
return a.first * b.second < b.first * a.second;
});
return {nums[k - 1].first,nums[k - 1].second};
}
};
658. 找到 K 个最接近的元素
class Solution {
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
sort(arr.begin(),arr.end(),[&](const int &a , const int &b){
if (abs(a - x) == abs(b - x)) return a < b;
return abs(a - x) < abs(b - x);
});
vector<int>res(arr.begin(),arr.begin() + k);
sort(res.begin(),res.end());
return res;
}
};
1424. 对角线遍历 II
class Solution {
public:
vector<int> findDiagonalOrder(vector<vector<int>>& nums) {
vector<int> res;
vector<array<int,2>> temp; // a[0],a[1]横纵坐标
for(int i = 0; i < nums.size();i++)
for(int j = 0; j < nums[i].size();j++)
temp.push_back({i,j});
sort(temp.begin(),temp.end(),[&](const array<int,2> &a,const array<int,2> &b){
if(a[0] + a[1] == b[0] + b[1]) return a[0] > b[0];
return a[0] + a[1] < b[0] + b[1];
});
for(array<int,2> &x: temp) res.push_back(nums[x[0]][x[1]]);
return res;
}
};
3.字符串哈希
**214. 最短回文串
找到在s前面添加最少的字符使得s变成一个回文串。例如，如果s是"aacecaaa"，那么答案是"aaacecaaa"。只需要找最长回文的前缀。
代码的思路是使用滚动哈希的方法，即对字符串s的每个前缀计算一个哈希值，然后与其反转后的后缀的哈希值进行比较，如果相等，说明这个前缀是一个回文串。为了避免哈希值的冲突和溢出，代码中使用了一个素数base和一个模数mod作为哈希函数的参数。代码中还使用了一个变量mul来记录base的幂次，方便计算后缀的哈希值。
代码中定义了两个变量left和right，分别表示从左到右和从右到左计算的哈希值。初始时，left和right都为0，mul为1。然后遍历字符串s中的每个字符，更新left和right的值。具体地，left乘以base再加上当前字符的ASCII码，然后对mod取模；right加上当前字符的ASCII码乘以mul，然后对mod取模；mul乘以base再对mod取模。这样，当遍历到第i个字符时，left就是s[0…i]的哈希值，right就是s[i…n-1]反转后的哈希值。
接下来，判断left和right是否相等，如果相等，说明s[0…i]是一个回文串，那么就更新一个变量best为i。best表示最长的回文前缀的末尾位置。最后，如果best不等于n-1，说明s不是一个回文串，那么就需要在s前面添加一些字符。这些字符就是s[best+1…n-1]反转后的字符串。将这个字符串与s拼接起来，就得到了最短的回文串。
代码的时间复杂度是O(n)，空间复杂度是O(1)。
class Solution {
public:
string shortestPalindrome(string s) {
int n = s.size();
const int mod = 1e10 + 7;
const int base = 131;
int left = 0, right = 0, res = -1,cur = 1;
for(int i = 0; i < s.size();i++)
{
left = ((long long)left * base + s[i]) % mod;
right = (right + (long long)cur * s[i])% mod;
if(left == right) res = i;
cur = ((long long)cur * base) % mod;
}
string add = res == -1 ? "":s.substr(res + 1);
reverse(add.begin(),add.end());
return add + s;
}
};
4.数位dp
求多少位数字满足一个条件。
2376. 统计特殊整数
class Solution {
public:
int countSpecialNumbers(int n) {
auto s = to_string(n);
int m = s.length(), memo[m][1 << 10];
memset(memo, -1, sizeof(memo)); // -1 表示没有计算过
//func i -> 第i位 ，mask已经被选择的集合，is_limit是不是有限制，is_num前一位有没有数字
function<int(int, int, bool, bool)> func = [&](int i, int mask, bool is_limit, bool is_num)-> int{
if(i == m) return is_num;
if (!is_limit && is_num && memo[i][mask] != -1)
return memo[i][mask];
int res = 0;
if(!is_num) res = func(i + 1,mask,false,false);
int up = is_limit ? s[i] - '0' : 9;
for(int d = 1 - is_num; d <= up;d++)
{
if((mask >> d & 1) == 0)
res += func(i + 1,mask | (1 << d),is_limit && d == up,true);
}
if(!is_limit && is_num) memo[i][mask] = res;
return res;
};
return func(0,0,true,false);
}
};
902. 最大为 N 的数字组合
class Solution {
public:
int atMostNGivenDigitSet(vector<string>& digits, int n) {
auto s = to_string(n);
int m = s.length(), memo[m];
memset(memo, -1, sizeof(memo)); // -1 表示没有计算过
function<int(int, bool, bool)> func = [&](int i, bool is_limit, bool is_num)-> int{
if(i == m) return is_num;
if (!is_limit && is_num && memo[i] != -1)
return memo[i];
int res = 0;
if(!is_num) res = func(i + 1,false,false);
for(string ss : digits)
{
int d = stoi(ss);
if(is_limit && d > s[i] - '0') break;
res += func(i + 1,is_limit && d == s[i] - '0',true);
}
if(!is_limit && is_num) memo[i] = res;
return res;
};
return func(0,true,false);
}
};