一、数的反转:
int reverse(int x) {
long long res = 0;
while(x) {
res = res * 10 + x % 10;
x /= 10;
}
if(res > INT_MAX || res < INT_MIN) return 0;
return res;
}
1.如何判断超过int的表示范围
2.c++对负数的取模运算
-1234 % 10 = -4;
-123 % 10 = -3;....
int res = 0;
while(x) {
if(x > 0 && res > (INT_MAX - x % 10) / 10) return 0;
if(x < 0 && res < (INT_MIN - x % 10) / 10) return 0;
res = res * 10 + x % 10;
x /= 10;
}
使用int表示答案,在计算过程中判断int是否溢出
(1)正数 res * 10 + x % 10 > MAX 因为左边会超过int的表示范围,所以对等式进行等价转化
(2)负数同理
二、去除前导空格
int k = 0;
while(k < s.size() && s[k] == ' ') k ++;
三、转化成string类型
string s = to_string(x);
将s逆序,reverse()方法直接对s进行操作了,没有返回值
reverse(s.begin(),s.end());.
四、sort函数的使用
int a[] = {3,2,1};
sort(a,a + 3);
vector<int> nums;
sort(nums.begin(),nums.end());
求三数之和
先排序,这样数组就有序,可以使用双指针,优化时间复杂度
如何对答案排重?
vector<vector<int>> res;
for(int i = 0;i < n;i ++) {
if(i >= 1 && nums[i] == nums[i - 1]) continue;
for(int l = i + 1,r = n - 1;l < r;l ++) {
if(l > i + 1 && nums[l] == nums[l - 1]) continue;
while(l < r && nums[i] + nums[l] + nums[r] > 0) r --;
if(l != r && nums[i] + nums[l] + nums[r] == 0)
res.push_back({nums[i],nums[l],nums[r]});
}
}
四数之和
for(int i = 0;i < nums.size();i ++) {
if(i > 0 && nums[i] == nums[i - 1]) continue;
for(int j = i + 1;j < nums.size();j ++) {
if(j > i + 1 && nums[j] == nums[j - 1]) continue;
for(int k = j + 1,u = nums.size() - 1;k < u;k ++) {
if(k > j + 1 && nums[k] == nums[k - 1]) continue;
while(k < u && (long long)nums[i] + nums[j] + nums[k] + nums[u] > target) u --;
if(k < u && (long long)nums[i] + nums[j] + nums[k] + nums[u] == target)
res.push_back({nums[i],nums[j],nums[k],nums[u]});
}
}
}
读入一行的字符串
string s;
getline(cin, s);
map<string,int> h;有按键排序的功能,因为它使用红黑树实现的
unordered_map<string,int> h;没有这个功能,因为他是使用哈希表实现的
括号问题
1.任意前缀中左括号的数量大于等于有括号的数量
2.左括号的数量等于有括号的数量
22题写出所有的合法序列
不要把左右括号看成一个整体出现,分别列举n个。
判断何时左括号,何时右括号。
void dfs(int n,int lc,int rc,string path) {
if(lc == n && rc == n) res.push_back(path);
else {
if(lc < n) dfs(n,lc + 1,rc,path + '(');
if(rc < n && lc > rc) dfs(n,lc,rc + 1,path + ')');
}
}