163.缺失的区间
题目链接：163.missing-ranges
解法：
基本逻辑是，依次遍历nums中的所有的元素，判断这个元素（right）和上一个元素（left）的差值是否>=2，如果是，那么缺失区间为[left+1, right-1]。比如上一个为1，当前为3，那么缺失的区间为[2,2]，如果上一个为1，当前为4，那么缺失的区间为[2,3]。都满足[left+1, right-1]这个逻辑。
但是lower和upper这两个端点需要单独考虑，因为lower本身可能就是缺失区间的左区间，upper本身可能就是缺失区间的右区间（闭区间）。
另外整数操作可能会溢出，因为32 位的 int 类型可以安全地表示的十进制数的范围大约是 −10^(9)到10^(9)， 所以lower如果是10^(-9)，那么lower-1就会溢出了。
下面给出了两种写法，第一种可以自动处理边界条件，可能会溢出，但是提交后通过了。第二种写法代码量大一些，但是清晰，而且没有溢出风险。
边界条件：nums为空
时间复杂度：O(n)，n为nums的长度
空间复杂度：
class Solution {
public:
vector<vector<int>> findMissingRanges(vector<int>& nums, int lower, int upper) {
vector<vector<int>> res;
// lower本身要包含进去，所以left的起始值取lower-1
// 这里可能溢出
int left = lower - 1;
for (int right: nums) {
// 这里可能溢出
int val = right - left;
if (val > 1) {
res.push_back({left+1, right-1});
}
left = right;
}
// upper如果不在nums中，那么upper本身也要包含进去
if (upper > left) {
res.push_back({left+1, upper});
}
return res;
}
};class Solution {
public:
vector<vector<int>> findMissingRanges(vector<int>& nums, int lower, int upper) {
vector<vector<int>> res;
// 如果nums为空，那么就是[lower, upper]
if (nums.empty()) {
res.push_back({lower, upper});
return res;
}
// 处理lower为左区间的情况
if (lower < nums[0]) {
res.push_back({lower, nums[0]-1});
}
for (int i=1; i<nums.size(); i++) {
int left = nums[i-1];
int right = nums[i];
if (right > (left + 1)) {
res.push_back({left+1, right-1});
}
}
// 处理upper为右区间的情况
if (upper > nums.back()) {
res.push_back({nums.back()+1, upper});
}
return res;
}
};1861.旋转箱子
题目链接：1861.rotating-the-box
解法：
先将数组旋转90°，如果m和n分别是原箱子box的行数和列数，那么旋转后的箱子满足 rBox[j][m-1-i] = box[i][j]。
定义一个变量，是石头能落下的最低位置 cur。然后再从最底部开始，往上遍历，把石头放到落下的最低位置，再更新这个最低位置。
如果当前是空的，那么最低位置不变，因为没有石头落下去占据最低位置，也没有障碍挡住石头下落。如果当前是障碍，那么石头只能落在障碍上面了，于是最低位置是障碍上面。如果当前是石头，那么石头会落下，最低位置往上挪一位，也就是 cur--。
有种情况下石头能落下的最低位置，本身就已经是石头了，也不用单独考虑，就算是落在了原地。
参考题解：旋转箱子
边界条件：无
时间复杂度：O(mn)
空间复杂度：O(mn)，mn为返回结果的空间，如果不计，那就是O(1)
class Solution {
public:
vector<vector<char>> rotateTheBox(vector<vector<char>>& box) {
// m、n分别是原box的行数和列数
int m = box.size();
int n = box[0].size();
// 对箱子进行旋转
vector<vector<char>> rBox(n, vector<char>(m));
for (int i=0; i<m; i++) {
for (int j=0; j<n; j++) {
rBox[j][m-1-i] = box[i][j];
}
}
// n、m分别是旋转box的行数和列数，先从第一列开始
for (int j=0; j<m; j++) {
// 当前石头能放置的最低位置
int cur = n - 1;
// 从最后一行往上遍历
for (int i=n-1; i>=0; i--) {
// 如果是障碍物，那么上面一行才是最低位置
if (rBox[i][j] == '*') {
cur = i - 1;
// 如果是石头，那么往下落到最低位置
} else if (rBox[i][j] == '#') {
rBox[i][j] = '.';
rBox[cur][j] = '#';
cur--;
}
}
}
return rBox;
}
};2217.找到指定长度的回文数
题目链接：2217.find-palindrome-with-fixed-length
解法：
这道题已经不知道该怎么评价了，因为一些公式也不知道咋来的。有俩公式得记住，一个是根据 intLength 求回文数的左半部分，一个是更具 intLength 求回文数的个数。
（1）如果回文数的长度为 intLength，那么第q位回文数的左半部分（回文数是奇数，那么包含中间的那个数）的计算公式如下。表示 (intLength - 1) / 2 再向下取整。怎么来的咱也不知道。
（2）求出左半部分后，可以对左半部分翻转，得到右半部分，再拼接，就得到了回文数。如果回文数是奇数，那么翻转后得去掉第一位（也就是左半部分的最后一位）。
（3）题目中说了如果第q位不存在回文数，那么返回为-1。为啥可能不存在呢？因为给定 intLength，回文数的个数是有限的。如果q超出了回文数的个数，那么就不存在了。比如长度为3，那么回文数的左半部分为10,11,12,..., 99，那么一共有99-10+1=90个回文数。于是q必须小于等于90。
那么怎么根据 intLength知道有多少个回文数呢？有些题解给出的是 9 * base，这个base是如下的数。咱也不知道它咋来的。
（4）由于length的最大长度为15，意味着回文数得用64位的整型表示，在 c++中是long long类型。
参考题解：回文数
边界条件：无
时间复杂度：O(N∗intLength)， N为 queries.length，翻转字符串的时间复杂度为O(intLength)
空间复杂度：O(intLength)，返回的结果不计入空间。
class Solution {
public:
vector<long long> kthPalindrome(vector<int>& queries, int intLength) {
vector<long long> res;
int base = pow(10, (intLength-1)/2);
// 回文数的个数
int cnt = 9 * base;
for (int q: queries) {
if (q > cnt) {
res.push_back(-1);
continue;
}
int left = base + q - 1;
string str_left = to_string(left);
string str_right = str_left;
reverse(str_right.begin(), str_right.end());
if (intLength % 2 == 1) {
str_right.erase(str_right.begin());
}
str_left += str_right;
// 把字符串转为long
res.push_back(stol(str_left));
}
return res;
}
};
