锐客网

  1. 首页 > it技术 > >

剑指week4

1.二叉搜索树的后序遍历序列

class Solution { public: vectorseq; bool verifySequenceOfBST(vector sequence) { seq=sequence; return dfs(0,seq.size()-1); } bool dfs(int l,int r) { if(l>=r)return true; int root=seq[r]; int k=l; while(k

2.二叉树中和为某一值的路径
class Solution { public: vector>ans; vectorvt; vector> findPath(TreeNode* root, int sum) { dfs(root,sum); return ans; } void dfs(TreeNode* root,int sum) { if(!root)return ; vt.push_back(root->val); sum-=root->val; if(!sum&&!root->left&&!root->right) ans.push_back(vt); dfs(root->left,sum); dfs(root->right,sum); vt.pop_back(); } };

3.复杂链表的复刻
class Solution { public: ListNode *copyRandomList(ListNode *head) { if(!head)return head; unordered_mappos; pos[NULL]=NULL; for(auto p=head; p; p=p->next) { pos[p]=new ListNode(p->val); } for(auto p=head; p; p=p->next) { pos[p]->next=pos[p->next]; pos[p]->random=pos[p->random]; } return pos[head]; } }; class Solution { public: ListNode *copyRandomList(ListNode *head){ //每个结点后面添加一个他的复制 for(auto p=head; p; ) { auto np=new ListNode(p->val); auto next=p->next; p->next=np; np->next=next; p=next; } //复制random for(auto p=head; p; p=p->next->next) { if(p->random) p->next->random=p->random->next; } //分离两个链表 auto dummy=new ListNode(-1); auto cur=dummy; for(auto p=head; p; p=p->next) { cur->next=p->next; cur=cur->next; p->next=p->next->next; } return dummy->next; } };

4.二叉搜索树与双向链表
class Solution { public: TreeNode* pre=NULL; TreeNode* convert(TreeNode* root) { dfs(root); while(root&&root->left)root=root->left; return root; } void dfs(TreeNode* root) { if(!root)return ; dfs(root->left); root->left=pre; if(pre)pre->right=root; pre=root; dfs(root->right); } };

5.序列化二叉树
class Solution { public:// Encodes a tree to a single string. string serialize(TreeNode* root) { string res; dfs_s(root, res); return res; }void dfs_s(TreeNode* root, string &res){ if(!root) { res += "null "; //如果当前节点为空，保存null和一个空格 return ; } res += to_string(root->val) + ' '; //如果当前节点不为空，保存数字和一个空格 dfs_s(root->left, res); dfs_s(root->right, res); } // Decodes your encoded data to tree. TreeNode* deserialize(string data) { int u = 0; //用来保存当前的字符串遍历的位置 return dfs_d(data, u); }TreeNode* dfs_d(string data, int &u){//这里的u是传的引用，不是值传递 if (u == data.size()) return NULL; //如果已经达到了字符串的尾端，则退出。 int k = u; while(data[k] != ' ') k++; //k记录当前数字的位数如134是个三位数的数字，56是个两位数的数字，退出的时候，k指向了字符的中间的空格，所以回到下个字符的首部需要加1.if(data[u] == 'n') {//如果当前字符串是“null” u = k+1; //回到下一个数字的首部，注意是u = k+1, 不是u = u+1; return NULL; //表示这次构造的是一个null节点，并没有孩子节点，所以跳过后面的递归 } int val = 0; //如果数字是负的 if(data[u] == '-'){ for (int i = u+1; i < k; i++) val = val * 10 + data[i] - '0'; val= -val; } else{ //如果是数字是正的 for (int i = u; i < k; i++) val = val * 10 + data[i] - '0'; } u = k + 1; //回到下个数字的首部 //递归算法总是先写退出条件，然后才递归调用。 auto root = new TreeNode(val); root->left = dfs_d(data, u); root->right = dfs_d(data, u); return root; } };

6.数字排列
class Solution { public: vector>ans; vectorpath; vector> permutation(vector& nums) { path.resize(nums.size()); sort(nums.begin(),nums.end()); dfs(nums,0,0,0); //当前枚举的位子，从哪一个位置开始枚举，状态 return ans; } void dfs(vector&nums,int u,int start,int state) { if(u==nums.size())//找到了一个方案 { ans.push_back(path); return ; } //规定当前数和上一个数相同，只能把当前数放在这个数后面 if(!u||nums[u]!=nums[u-1])//如果是第一个数，或者当前数和上一个数不同 start=0; for(int i=start; i>i&1)) { path[i]=nums[u]; dfs(nums,u+1,i,state+(1<

7. 数组中出现次数超过一半的数字
class Solution { public: int moreThanHalfNum_Solution(vector& nums) { //考虑用栈，如果和当前栈内元素不同，就将栈顶元素弹出一个 //如果相同，就往里面加入元素 stackst; for(int i=0; i

8.数据流中的中位数
class Solution { public: priority_queuemax_heap; //前一半元素放在大根堆 priority_queue,greater>min_heap; //后一半元素放在小根堆void insert(int num){ //先是无条件插入 max_heap.push(num); //如果小根堆里有值，但是比大根堆堆顶要小，交换‘ if(min_heap.size()&&min_heap.top()min_heap.size()+1) { min_heap.push(max_heap.top()); max_heap.pop(); } }double getMedian(){ if(max_heap.size()+min_heap.size()&1)//是奇数 return max_heap.top(); else return (max_heap.top()+min_heap.top())/2.0; } };

9.连续子数组的最大和
class Solution { public: int maxSubArray(vector& nums) { int n=nums.size(); int dp[n+5]; //表示以i结尾的连续子数组的最大和 dp[0]=nums[0]; int ans=dp[0]; for(int i=1; i

10.从1到n整数中1出现的次数
class Solution { public: int numberOf1Between1AndN_Solution(int n) { if(!n)return 0; vectornumber; while(n) { number.push_back(n%10); n/=10; } int res=0; //从最高位开始枚举 for(int i=number.size()-1; i>=0; i--) { //eg:abcdef //left用于求ab，right用于求def auto left=0,right=0,t=1; for(int j=number.size()-1; j>i; j--) left=left*10+number[j]; for(int j=i-1; j>=0; j--) right=right*10+number[j],t*=10; ///t用于乘上10的几次方 res+=left*t; if(number[i]==1)res+=right+1; else if(number[i]>1)res+=t; } return res; } };

    推荐阅读


    上一篇：为了给我治病，老爸倾其所有

    下一篇：A1-可能吗，AI（）