2.28
题目：最多可达成的换楼请求
1.这里使用了dfs遍历算法，但是，没能引用每次的数组，导致每次都要拷贝数组，增加了时间复杂度。
2.__builtin_popcount(n) 计算一个 整数 n 有多少个位为1
3.fill(delta.begin(), delta.end(), 0); ,将数组dalta全部填充为 0
4.all_of(delta.begin(), delta.end(), [](int x) { return x == 0; })
区间[开始, 结束)中是否所有的元素都满足_Pred，所有的元素都满足返回 true，否则返回 false
3.1
题目：Z字形变换
1.仔细思考可能的规律，最后再考虑暴力解法
2.这里边界值的上下变换值得学习与借鉴
3.2
题目：寻找最近的回文数
1.查找最近的回文数的方法，直接将数字前半段按照回文的方法复制到后半段：
int len = n.size();
for(int i = 0; i < len / 2; i++)
n[len - 1 - i] = n[i];
2.寻找比该回文数小的最接近的回文数
string get_last(string s){
int len = s.size(), pos = len / 2;
string original = s;
if(len % 2 == 1){
if(s[pos] != '0'){
s[pos] -= 1;
return s;
}
}
else{
if(s[pos] != '0'){
s[pos] -= 1;
s[pos - 1] -= 1;
if(s[0] == '0') return to_string(stoll(original) - 2);
return s;
}
}
while(pos >= 0 && s[pos] == '0')
s[pos--] = '9';
if(pos >= 0) s[pos] -= 1;
int index = 0;
while(index < s.size() && s[index] == '0') index++;
if(index == s.size()) return "0";
else s = s.substr(index, s.size() - index);
for(int i = 0; i < s.size() / 2; i++)
s[s.size() - i - 1] = s[i];
return s;
}
3.寻找比该回文数大的最接近的回文数
string get_next(string s){
int len = s.size(), pos = len / 2;
if(len % 2 == 1){
if(s[pos] != '9'){
s[pos] += 1;
return s;
}
}
else{
if(s[pos] != '9'){
s[pos] += 1;
s[pos - 1] += 1;
return s;
}
pos--;
}
string original = s;
while(pos >= 0 && s[pos] == '9')
s[pos--] = '0';
if(pos >= 0) s[pos] += 1;
else return to_string(stoll(original) + 2);
for(int i = 0; i < len / 2; i++)
s[len - i - 1] = s[i];
return s;
}
3.3
题目：各位相加
数学的方法详解题目中的解析，不赘述。
这里暴露了对数论知识还是不了解的问题。
3.4
题目：子数组范围和
直接暴力解决了
3.5
题目：最长特殊序列1
题目太绕了，没有读懂。
3.6
题目：适合打劫银行的日子
前缀和和后缀和的动态规划问题
3.7
题目：七进制数
10以内进制转化的模板：
string convertToBase(int index, int num) {
bool flag = true;
string result = "";
if(num == 0) return "0";
if(num < 0){
flag = false;
num *= -1;
}
while(num){
result += to_string(num % index);
num /= index;
}
if(flag == false)
result += '-';
reverse(result.begin(), result.end());
return result;
}
16进制转化的模板：
string toHex(int num) {
if (num == 0) {
return "0";
}
string sb = "";
// 从高位到低位进行与运算
for (int i = 7; i >= 0; i --) {
// 四位一组进行运算
int val = (num >> (4 * i)) & 0xf;
if (sb.length() > 0 || val > 0) {
char digit = val < 10 ? (char) ('0' + val) : (char) ('a' + val - 10);
sb.push_back(digit);
}
}
return sb;
}
3.8
题目：蜡烛之间的盘子
针对抽象情况下，关键的问题缺乏认知和解决的能力
3.9
题目：得分最高的最小轮调
差分的思想，没有充分理解题目的意思，赶时间做其他事了
3.10
题目：N叉树的前序遍历
深度优先遍历n叉树所有的节点
3.11
题目：统计最高分的节点数目
统计二叉树的左右子树的节点数目，再乘以去除1 + 左右节点的数目，就是该节点的积分，之后统计每个节点的节点数目，找出最高分，然后进行计数。
3.12
题目：N叉树的层序遍历
可复用的层序遍历代码：
vector<vector<int>> levelOrder(Node* root) {
if(root == NULL) return {};
queue<Node*> q;
vector<vector<int>> result;
vector<int> level;
q.push(root);
while(! q.empty()){
int size = q.size();
level.clear();
while(size){
Node* tmp = q.front();
level.emplace_back((tmp->val));
q.pop();
for(auto& item : tmp -> children){
if(item != NULL)
q.push(item);
}
size--;
}
result.emplace_back(level);
}
return result;
}
3.13
题目：UTF-8编码
读懂题目，正常做就完事
3.14
题目：两个列表的最小索引总和
hash表的运用。
3.15
题目：统计按位或能得到最大值的子集数目
简单的dfs题目
3.19
题目：根据二叉树创建字符串
dfs题目
4.5
题目：二进制表示中质数个计算置位
判断质数的函数:
bool isPrime(int x) {
if (x < 2) {
return false;
}
for (int i = 2; i * i <= x; ++i) {
if (x % i == 0) {
return false;
}
}
return true;
}
统计一个数字的二进制数有多少个1构成
int cnt = __builtin_popcount(x);
4.18
对[1,n]区间所有数字按字典序进行排序
对数字乘10到下一层 如果数字超出范围则退回到上一层
时间复杂度：O(n)
空间复杂度：O(1)
题目：字典序排数
循环代码：
vector<int> lexicalOrder(int n) {
vector<int> ret(n);
int number = 1;
for (int i = 0; i < n; i++) {
ret[i] = number;
if (number * 10 <= n) {
number *= 10;
} else {
while (number % 10 == 9 || number + 1 > n) {
number /= 10;
}
number++;
}
}
return ret;
}
递归代码：
vector<int> nums;
void dfs(int n, int index) {
if(index > n) return;
nums.emplace_back(index);
for(int i = 0; i < 10; i++){
dfs(n, index * 10 + i);
}
}
vector<int> lexicalOrder(int n) {
for(int i = 1; i <= 9; i++)
dfs(n, i);
return nums;
}