Day11 0~n-1中缺失的数字+打印从1到最大的n位数+序列
2021-06-23 本文已影响0人
吃掉夏天的怪物
TODO:
- 全排列问题还是不大会
- 重做序列化二叉树
剑指 Offer 53 - II. 0~n-1中缺失的数字(简单)
虽然做出来了,但是开始想复杂了
class Solution {
public:
int missingNumber(vector<int>& nums) {
int left = 0, right = nums.size()-1;
int mid;
while(left <= right){
mid = left + (right-left);
if(mid == nums[mid]){//用等于来判断会比用不等于好
left = left+1;
}else{
right = right - 1;
}
}
return left;
}
};
剑指 Offer 17. 打印从1到最大的n位数(简单)
不考虑越界问题特别简单,竟然也提交成功了。可是面试应该不允许这样
class Solution {
public:
vector<int> printNumbers(int n) {
if(n ==0) return {};
int big = pow(10,n);
vector<int> res;
for(int i =1; i < big; i++){
res.push_back(i);
}
return res;
}
};
于是看了题解...
说,解决大数问题一般会用上字符串,那这个就变成了个全排列问题。(所以返回int
class Solution {
public:
vector<int> ans;
int pos = 0;
vector<int> printNumbers(int n) {
string s = "0123456789";
string str = "";
dfs(s, str, n);
return ans;
}
void dfs(string &s, string &str, int k){
if(str.length()== k){
if(pos==0){pos=1;return;} //前导零的去除
ans.push_back(atoi(str.c_str())); //但是atoi里转换的字符串表示的值若是超过int可能会出现问题
return ;
}
for(int i=0; i<s.length();++i){
str+=s[i];
dfs(s, str, k);
str.pop_back();
}
}
};
class Solution {
public:
vector<int> ans;
int firstZero = 1;
vector<int> printNumbers(int n) {
if(n ==0) return {};
else if(n == 1) return {1,2,3,4,5,6,7,8,9};
string dai = "0123456789";
string str = "";
dfs(dai,str,n);
return ans;
}
void dfs(string&dai ,string& str, int n){
if(str.size() == n){
if(firstZero) {firstZero = 0; return ;}
ans.push_back(atoi(str.c_str()));
return ;
}
for(int i = 0; i < dai.size();i++){
str += dai[i];
dfs(dai,str,n);
str.pop_back();
}
}
};
剑指 Offer 37. 序列化二叉树
感觉就像是一道简单递归题,但是它写的是困难,所以事情没有那么简单?
不会不会,值得再做
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
string res ="";
dfs1(root,res);
return res;
}
void dfs1(TreeNode* root, string&res){
if(root == nullptr){
res+="#,";
return ;
}
res += (to_string(root->val)+",");
dfs1(root->left,res);
dfs1(root->right,res);
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
int u = 0;
return dfs2(data,u);
// return nullptr;
}
TreeNode* dfs2(string&res,int& u){
if(res[u] == '#'){
u += 2;
return nullptr;
}
int t = 0;
int flag = 1;
while(res[u] != ','){
if(res[u]=='-')flag=0;
else t = t*10 + res[u]-'0';
u++;
}
u++;
if(!flag) t = -t;
TreeNode* root = new TreeNode(t);
root->left = dfs2(res,u);
root->right = dfs2(res,u);
return root;
}
};
// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));