辽宁省建设科学研究院网站本科自考需要考哪些科目

当前位置： 首页 > news >正文

辽宁省建设科学研究院网站,本科自考需要考哪些科目,网站建设与管理维护的答案李建青,深圳网页定做文章目录 剑指 Offer 32 - I. 从上到下打印二叉树题意#xff1a;解#xff1a;代码#xff1a; 剑指 Offer 32 - II. 从上到下打印二叉树 II题意#xff1a;解#xff1a;代码#xff1a; 剑指 Offer 32 - III. 从上到下打印二叉树 III题意#xff1a;解#xff1a;代… 文章目录 剑指 Offer 32 - I. 从上到下打印二叉树题意解代码 剑指 Offer 32 - II. 从上到下打印二叉树 II题意解代码 剑指 Offer 32 - III. 从上到下打印二叉树 III题意解代码 剑指 Offer 26. 树的子结构题意解代码 剑指 Offer 27. 二叉树的镜像-08题意解代码 剑指 Offer 28. 对称的二叉树题意解代码 剑指 Offer 12. 矩阵中的路径题意解代码 剑指 Offer 13. 机器人的运动范围题意解代码 剑指 Offer 34. 二叉树中和为某一值的路径题意解代码 剑指 Offer 36. 二叉搜索树与双向链表-09题意解代码 剑指 Offer 54. 二叉搜索树的第k大节点题意解代码 剑指 Offer 55 - I. 二叉树的深度题意解代码 剑指 Offer 55 - II. 平衡二叉树题意解代码 剑指 Offer 64. 求12…n题意解代码 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先-10题意解代码 剑指 Offer 68 - II. 二叉树的最近公共祖先题意解代码 剑指 Offer 37. 序列化二叉树题意解代码 剑指 Offer 38. 字符串的排列-11题意解代码 剑指 Offer 32 - I. 从上到下打印二叉树 题意 剑指 Offer 32 - I. 从上到下打印二叉树 解 BFS板子 代码 #includebits/stdc.h using namespace std; struct TreeNode {int val;TreeNode *left;TreeNode right;TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; vectorint levelOrder(TreeNode root) {vectorintret;if(rootnullptr) return ret; queueTreeNode*qe;qe.push(root);while(true){queueTreeNodenext;while(!qe.empty()){TreeNode nowqe.front();qe.pop();ret.push_back(now-val);if(now-left) next.push(now-left);if(now-right) next.push(now-right);}qenext;if(qe.empty()) break;}return ret; } int main() {return 0; }剑指 Offer 32 - II. 从上到下打印二叉树 II 题意 剑指 Offer 32 - II. 从上到下打印二叉树 II 解 第一题基础上分层存储- 代码 #includebits/stdc.h using namespace std; struct TreeNode {int val;TreeNode *left;TreeNode right;TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; vectorvectorint levelOrder(TreeNode root) {vectorvectorintret;if(rootnullptr) return ret; queueTreeNode*qe;qe.push(root);while(true){queueTreeNodenext;vectorinttemp; while(!qe.empty()){TreeNode nowqe.front();qe.pop();temp.push_back(now-val);if(now-left) next.push(now-left);if(now-right) next.push(now-right);}ret.push_back(temp);qenext;if(qe.empty()) break;}return ret; } int main() {return 0; }剑指 Offer 32 - III. 从上到下打印二叉树 III 题意 剑指 Offer 32 - III. 从上到下打印二叉树 III 解 奇变偶不变 代码 #includebits/stdc.h using namespace std; struct TreeNode {int val;TreeNode *left;TreeNode right;TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; vectorvectorint levelOrder(TreeNode root) {vectorvectorintret;bool zt0;if(rootnullptr) return ret; queueTreeNode*qe;qe.push(root);while(true){queueTreeNodenext;vectorinttemp; while(!qe.empty()){TreeNode nowqe.front();qe.pop();temp.push_back(now-val);if(now-left) next.push(now-left);if(now-right) next.push(now-right);}if(zt) reverse(temp.begin(),temp.end());ret.push_back(temp);qenext;if(qe.empty()) break;zt!zt;}return ret; } int main() {return 0; }剑指 Offer 26. 树的子结构 题意 剑指 Offer 26. 树的子结构 求树B是不是A的子结构 解 卡了一下47案例看了半天原来是判断是否相等Cmp的时候不能看A有没有子节点而是要看B有没有子节点铸币了 递归DFS判断相等两个函数很像但是初始值不同有趣的 代码 #includeiostream using namespace std; struct TreeNode {int val;TreeNode *left;TreeNode right;TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; bool myCmp(TreeNode A, TreeNode* B) {bool rettrue;if(Anullptr||Bnullptr) return false;if(A-val!B-val) return false;if(B-left!nullptr) retmyCmp(A-left,B-left);if(B-right!nullptr) retmyCmp(A-right,B-right);/* WA 47/48if(A-left!nullptr||B-left!nullptr) retmyCmp(A-left,B-left);if(A-right!nullptr||B-right!nullptr) retmyCmp(A-right,B-right);/return ret; } bool isSubStructure(TreeNode A, TreeNode* B) {if(Anullptr||Bnullptr) return false;bool ansfalse;if(A-valB-val) ans|myCmp(A,B);if(ans) return ans;if(A-left!nullptr) ans|isSubStructure(A-left,B);if(A-right!nullptr) ans|isSubStructure(A-right,B);return ans; } int main() {return 0; }剑指 Offer 27. 二叉树的镜像-08 题意 剑指 Offer 27. 二叉树的镜像 构造镜像树 解 基本操作 代码 #includeiostream using namespace std; struct TreeNode {int val;TreeNode *left;TreeNode right;TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; void treeCopy(TreeNode newRoot,TreeNode* root) {if(root-left!nullptr){newRoot-rightnew TreeNode(root-left-val);treeCopy(newRoot-right,root-left);}if(root-right!nullptr){newRoot-leftnew TreeNode(root-right-val);treeCopy(newRoot-left,root-right);} } TreeNode* mirrorTree(TreeNode* root) {if(rootnullptr) return nullptr;TreeNode* newRootnew TreeNode(root-val);treeCopy(newRoot,root);return newRoot; } int main() {return 0; }剑指 Offer 28. 对称的二叉树 题意 剑指 Offer 28. 对称的二叉树 判断是否是对称的二叉树 解 直接在26题WA代码的基础上改自己和自己比 代码 #includeiostream using namespace std; struct TreeNode {int val;TreeNode *left;TreeNode right;TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; bool myCmp(TreeNode A, TreeNode* B) {bool rettrue;if(Anullptr||Bnullptr) return false;if(A-val!B-val) return false;if(A-left!nullptr||B-right!nullptr) retmyCmp(A-left,B-right);if(A-right!nullptr||B-left!nullptr) retmyCmp(A-right,B-left);return ret; } bool isSymmetric(TreeNode* root) {if(rootnullptr) return false;bool ansfalse;ans|myCmp(root,root);return ans; } int main() {return 0; }剑指 Offer 12. 矩阵中的路径 题意 剑指 Offer 12. 矩阵中的路径 找字符矩阵中是否有一条线路能构成给定字符串 解 DFS 代码 #includebits/stdc.h using namespace std; bool check(int i,int j,const vectorvectorbool book,const int n,const int m) {if(i0||in) return false;if(j0||jm) return false;if(book[i][j]1) return false;return true; } bool dfs(int i,int j,int mao,const vectorvectorchar board,vectorvectorbool book,const string word,const int n,const int m) {bool ansfalse;if(maoword.size()) return true;if(check(i1,j,book,n,m) board[i1][j]word[mao]){book[i1][j]1;ans|dfs(i1,j,mao1,board,book,word,n,m);book[i1][j]0;}if(check(i-1,j,book,n,m) board[i-1][j]word[mao]){book[i-1][j]1;ans|dfs(i-1,j,mao1,board,book,word,n,m);book[i-1][j]0;}if(check(i,j1,book,n,m) board[i][j1]word[mao]){book[i][j1]1;ans|dfs(i,j1,mao1,board,book,word,n,m);book[i][j1]0;}if(check(i,j-1,book,n,m) board[i][j-1]word[mao]){book[i][j-1]1;ans|dfs(i,j-1,mao1,board,book,word,n,m);book[i][j-1]0;}return ans; } bool exist(vectorvectorchar board, string word) {int nboard.size(),mboard[0].size();vectorvectorboolbook(n,vectorbool(m));bool ansfalse;for(int i0;in;i){for(int j0;jm;j){if(board[i][j]word[0]){book[i][j]1;if(ans) break;ans|dfs(i,j,1,board,book,word,n,m);book[i][j]0;}}}return ans; } int main() {string word;int n,m;cinnm;vectorvectorchar board(n,vectorchar(m));for(int i0;in;i){for(int j0;jm;j){cinboard[i][j];}}cinword;bool ansexist(board,word);coutboolalphaansendl;return 0; }剑指 Offer 13. 机器人的运动范围 题意 剑指 Offer 13. 机器人的运动范围 坐标各位和大于K的格子禁止机器人今日机器人每次只能走相邻的格子求有多少个格子可以到达 解 DFS 代码 #includebits/stdc.h using namespace std; int pointTonum(int i,int j) {int ret0;while(i) { reti%10;i/10; }while(j) { retj%10;j/10; }return ret; } bool check(int i,int j,const int m,const int n,const int k,const vectorvectorbool book) {if(i0||im) return false;if(j0||jn) return false;if(book[i][j]1) return false;return true; } void dfs(intans,int i,int j,const int m,const int n,const int k,vectorvectorbool book) {ans;book[i][j]1;if(check(i1,j,m,n,k,book)) dfs(ans,i1,j,m,n,k,book);if(check(i,j1,m,n,k,book)) dfs(ans,i,j1,m,n,k,book);if(check(i-1,j,m,n,k,book)) dfs(ans,i-1,j,m,n,k,book);if(check(i,j-1,m,n,k,book)) dfs(ans,i,j-1,m,n,k,book); } int movingCount(int m, int n, int k) {int ans0;vectorvectorboolbook(m,vectorbool(n));for(int i0;im;i){for(int j0;jn;j){int tpointTonum(i,j);if(tk) book[i][j]1;}}dfs(ans,0,0,m,n,k,book);return ans; } int main() {int n,m,k;cinnmk;int ansmovingCount(n,m,k);coutansendl;return 0; }剑指 Offer 34. 二叉树中和为某一值的路径 题意 剑指 Offer 34. 二叉树中和为某一值的路径 一条路径需要从根节点到叶子结点求和为K的所有路径 解 DFS 代码 #includebits/stdc.h using namespace std; struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode() : val(0), left(nullptr), right(nullptr) {}TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}TreeNode(int x, TreeNode *left, TreeNode right) : val(x), left(left), right(right) {} }; void dfs(TreeNode now,int target,vectorvectorint ans,vectorinttempvectorint()) {temp.push_back(now-val);target-now-val;if(target0now-leftnullptrnow-rightnullptr){ans.push_back(temp);return;}if(now-left!nullptr) dfs(now-left,target,ans,temp);if(now-right!nullptr) dfs(now-right,target,ans,temp); } vectorvectorint pathSum(TreeNode* root, int target) {vectorvectorintans;if(rootnullptr) return ans;dfs(root,target,ans);return ans; } int main() {return 0; }剑指 Offer 36. 二叉搜索树与双向链表-09 题意 剑指 Offer 36. 二叉搜索树与双向链表 将一个二层搜索树变成有序双向链表 解 中序遍历链表操作 代码 #includebits/stdc.h using namespace std; class Node { public:int val;Node* left;Node* right;Node() {}Node(int _val) {val _val;left NULL;right NULL;}Node(int _val, Node* _left, Node* _right) {val _val;left _left;right _right;} }; Node* head,last; void dfs(Node root) {if(root-left!nullptr) dfs(root-left);if(headnullptr){headroot;lastroot;}else{last-rightroot;root-leftlast;lastroot;}if(root-right!nullptr) dfs(root-right); } Node* treeToDoublyList(Node* root) {if(rootnullptr) return root;dfs(root);head-leftlast;last-righthead;return head; } int main() {return 0; }剑指 Offer 54. 二叉搜索树的第k大节点 题意 剑指 Offer 54. 二叉搜索树的第k大节点 如题 解 倒序的中序遍历 代码 #includeiostream using namespace std; struct TreeNode {int val;TreeNode *left;TreeNode right;TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; int dfs(TreeNode root,int t,const int k) {int ret0;if(root-left!nullptr) retdfs(root-left,t,k);t;if(tk) return root-val;if(root-right!nullptr) retdfs(root-right,t,k); } int kthLargest(TreeNode* root, int k) {int t0;int ansdfs(root,t,k);return ans; } int main() {return 0; }剑指 Offer 55 - I. 二叉树的深度 题意 剑指 Offer 55 - I. 二叉树的深度 如题 解 DFS/BFS都行 代码 #includeiostream using namespace std; struct TreeNode {int val;TreeNode *left;TreeNode right;TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; int dfs(TreeNode root) {int ret0;if(root-left!nullptr) retmax(ret,dfs(root-left));if(root-right!nullptr) retmax(ret,dfs(root-right));return ret1; } int maxDepth(TreeNode* root) {if(rootnullptr) return 0;int ansdfs(root);return ans; } int main() {return 0; }剑指 Offer 55 - II. 平衡二叉树 题意 剑指 Offer 55 - II. 平衡二叉树 判断一颗二叉树是否平衡 解 DFS和55差不多做一个不合法跳出就行 代码 #includeiostream using namespace std; struct TreeNode {int val;TreeNode *left;TreeNode right;TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; int dfs(TreeNode root) {int left0,right0;if(root-left!nullptr) leftdfs(root-left);if(root-right!nullptr) rightdfs(root-right);if(left-99||right-99) return -99;if(abs(left-right)1) return -99;return max(left,right)1; } bool isBalanced(TreeNode* root) {if(rootnullptr) return true;int ansdfs(root);if(ans!-99) return true;else return false; } int main() {return 0; }剑指 Offer 64. 求12…n 题意 剑指 Offer 64. 求12…n 如题不允许循环和条件 解 妙用的短路现象 代码 #includeiostream using namespace std; int sumNums(int n) {int sum0;n (sumnsumNums(n-1));return sum; } int main() {int n;cinn;int anssumNums(n);coutansendl;return 0; }剑指 Offer 68 - I. 二叉搜索树的最近公共祖先-10 题意 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先 给一颗二叉搜索树和在树中的两个值求他们的最近公共祖先 解 对于一个节点如果两个值一左一右那么这个值就是他们的最近公共祖先否则就往那一支里面找 一个节点也可以是它自己的祖先所以遍历到其中一个的时候就是他们的最近公共祖先 代码 #includeiostream using namespace std; struct TreeNode {int val;TreeNode *left;TreeNode right;TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; TreeNode lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(p-valq-val) swap(p,q);if(root-valp-val||root-valq-val) return root;if(root-valp-valroot-valp-val) return root;if(root-valp-valroot-valp-val) return lowestCommonAncestor(root-left,p,q);if(root-valp-valroot-valp-val) return lowestCommonAncestor(root-right,p,q); } int main() {return 0; }剑指 Offer 68 - II. 二叉树的最近公共祖先 题意 剑指 Offer 68 - II. 二叉树的最近公共祖先 给一颗二叉树和在树中的两个值求他们的最近公共祖先 解 不是二叉搜索树不能直接判断数字是否在左右两边所以改成dfs获取是否在子树 然后同样两种情况1.如果一个节点是p或q它的子树有一支为真含p或q则返回该节点 2.若递归途中有一个节点左右两支均为真则返回该节点 代码 #includeiostream using namespace std; struct TreeNode {int val;TreeNode *left;TreeNode right;TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; TreeNode ansnullptr; bool dfs(TreeNode* root,const TreeNode*const p,const TreeNodeconst q) {if(ans!nullptr) return false;//已经有答案了 bool ret1false,ret2false;if(root-left!nullptr) ret1|dfs(root-left,p,q);//左支 if(root-right!nullptr) ret2|dfs(root-right,p,q);//右支 if(rootp||rootq)//pq子树pq {if(ret1||ret2) ansroot;else return true;}if(ret1ret2) ansroot;//子树p子树q //coutroot-val ret1 ret2endl;return ret1||ret2;//合并分支信息 } TreeNode lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {bool tempdfs(root,p,q);return ans; } int main() {return 0; }剑指 Offer 37. 序列化二叉树 题意 剑指 Offer 37. 序列化二叉树 二叉树变字符串字符串再变回二叉树 解 hard题就是步骤和debug麻烦写了一坨屎 200ms 30mb- 能用就行 代码 #includeiostream using namespace std; struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; string int2string(int x) {string ret;if(x0) return 0;while(x){retchar(0x%10)ret;x/10;}return ret; } int string2int(string s) {int ret0;for(auto ch:s){retret10int(ch-0);}return ret; } void node2string(string s,TreeNode root) {s.append(int2string(root-val));if(root-left!nullptr){s.append(,);node2string(s,root-left);}else s.append(,N);if(root-right!nullptr){s.append(,);node2string(s,root-right);}else s.append(,N); } string serialize(TreeNode* root) {string tree;if(rootnullptr) return tree;node2string(tree,root);//couttree:treeendl; return tree; } void string2node(TreeNode* root,string data) {string s;int r0;while(rdata.size() data[r]!,) r;sdata.substr(0,r);data.erase(0,min(r1,int(data.size())));if(sN) root-leftnullptr;else{root-leftnew TreeNode(string2int(s));string2node(root-left,data);}r0;while(rdata.size() data[r]!,) r;sdata.substr(0,r);data.erase(0,min(r1,int(data.size())));if(sN) root-rightnullptr;else{root-rightnew TreeNode(string2int(s));string2node(root-right,data);} } TreeNode* deserialize(string data) {TreeNode* newHeadnullptr;if(data.empty()) return newHead;string s;int r0;while(rdata.size() data[r]!,) r;sdata.substr(0,r);data.erase(0,min(r1,int(data.size())));newHeadnew TreeNode(string2int(s));string2node(newHead,data);return newHead; } int main() {return 0; }剑指 Offer 38. 字符串的排列-11 题意 剑指 Offer 38. 字符串的排列 输出字符串的全排序去重 解 全排列板子题set去重 代码 #includebits/stdc.h using namespace std; void qp(int l,string temp,vectorbool book,setstring ss,const string s) {if(ls.size()){//coutinsert:tempendl;ss.insert(temp);}for(int i0;is.size();i){if(book[i]0){book[i]1;qp(l1,temps[i],book,ss,s);book[i]0;}} } vectorstring permutation(string s) {int l0;int lgs.length();vectorstringans;setstringss;vectorboolbook(lg);qp(l,,book,ss,s);for(auto tempss:ss) ans.push_back(tempss);return ans; } int main() {string s;cins;vectorstringanspermutation(s);for(auto a:ans) coutaendl;return 0; }