主要的题目
简单题
145. 二叉树的后序遍历
94. 二叉树的中序遍历
496. 下一个更大元素 I
682. 棒球比赛
589. N 叉树的前序遍历
590. N 叉树的后序遍历
844. 比较含退格的字符串
897. 递增顺序搜索树
1047. 删除字符串中的所有相邻重复项
中等题
150. 逆波兰表达式求值
394. 字符串解码
难题
剑指 Offer II 022. 链表中环的入口节点（无题解）
面试题 02.08. 环路检测（无题解）
题解
145. 二叉树的后序遍历
void visit(struct TreeNode *root,int *ans,int *ansnum){ if(root){ if(root->left) visit(root->left,ans,ansnum); if(root->right) visit(root->right,ans,ansnum); ans[(*ansnum)++] = root->val; } }//后序遍历 保存到栈 int* postorderTraversal(struct TreeNode* root, int* returnSize){ int *ans= malloc(sizeof(int)*101),ansnum = 0; visit(root,ans,&ansnum); *returnSize = ansnum; return ans; }
94. 二叉树的中序遍历
void inorder(struct TreeNode* root,int *a,int *b); int* inorderTraversal(struct TreeNode* root, int* returnSize){ int *ans= malloc(sizeof(int)*100),anssize= 0; *returnSize = 0; inorder(root,ans,returnSize); return ans; } void inorder(struct TreeNode* root,int *a,int *b){ if(root){ inorder(root->left,a,b); a[(*b)++] = root->val; inorder(root->right,a,b); } }//后续遍历 直接保存
496. 下一个更大元素 I
int* nextGreaterElement(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){ int *ans = malloc(sizeof(int)*100010); for(int i = 0;i < nums1Size;i++){ ans[i] = nums1[i]; int j = 0; while(j<nums2Size&&nums2[j]!=ans[i]) j++; for(;j <nums2Size;j++) if(ans[i] < nums2[j]) { ans[i] = nums2[j]; break; } if(ans[i] == nums1[i]) ans[i] = -1; } *returnSize = nums1Size; return ans; }
682. 棒球比赛
int calPoints(char ** ops, int opsSize){ int stack[10000],top = 0,ans = 0;//top指向下一个元素 for(int i = 0;i <opsSize;i++){ if(ops[i][0] == '+') {//弹栈计算 int num2 = stack[top - 1],num1 = stack[top - 2]; stack[top++] = num1 + num2; } else if(ops[i][0] == 'C') top--; //出栈一个 else if(ops[i][0] == 'D'){ int num2 = stack[top - 1]; stack[top++] = num2 * 2; } else{//数字入栈 int j = 0,flag = 0,num = 0; if(ops[i][0] == '-') flag = 1,j++; for(;ops[i][j];j++){ num *= 10; num += ops[i][j] - '0'; } if(!flag) stack[top++] = num; else stack[top++] = -num; } } for(int i = 0;i < top;i++) ans+=stack[i]; return ans; //最后栈内只剩最终结果 }
589. N 叉树的前序遍历
void preord(struct Node* root,int *ans,int *num){ if(root){ ans[(*num)++] = root->val; for(int i =0;i<root->numChildren;i++) preord(root->children[i],ans,num); } } int* preorder(struct Node* root, int* returnSize) { int *ans = malloc(sizeof(int)*10000); *returnSize = 0; preord(root,ans,returnSize); return ans; }
590. N 叉树的后序遍历
void preord(struct Node* root,int *ans,int *num){ if(root){ for(int i =0;i<root->numChildren;i++) preord(root->children[i],ans,num); ans[(*num)++] = root->val; } } int* postorder(struct Node* root, int* returnSize) { int *ans = malloc(sizeof(int)*10000); *returnSize = 0; preord(root,ans,returnSize); return ans; }
844. 比较含退格的字符串
bool backspaceCompare(char * s, char * t){ char ans1[210],ans2[210],top1 = 0,top2 = 0; for(int i = 0;s[i];i++) if(s[i] == '#'){ if(top1) top1--; } else ans1[top1++] = s[i]; for(int i = 0;t[i];i++){ if(t[i] == '#'){ if(top2) top2--; } else ans2[top2++] = t[i]; } ans1[top1] = 0; ans2[top2] = 0; return !strcmp(ans1,ans2); }
897. 递增顺序搜索树
void zhongxu(struct TreeNode *root,struct TreeNode **ans,int *top){ if(root){ zhongxu(root->left,ans,top); ans[(*top)++] = root; //插入队列中 zhongxu(root->right,ans,top); } } struct TreeNode* increasingBST(struct TreeNode* root){ struct TreeNode* ans[101]; memset(ans,0,sizeof(ans)); int top =0; zhongxu(root,ans,&top); for(int i = 0;i < top;i++){ ans[i]->left = 0; ans[i]->right = ans[i+1]; } return ans[0]; }
1047. 删除字符串中的所有相邻重复项
int sremove(char *s){ int ans = 0; char temp[100100]; int top = 0; for(int i = 0;s[i];i++) if(top&&s[i] == temp[top - 1]) top--,ans++; else temp[top++] = s[i]; int size = 0; for(int i = 0;i <top;i++) s[size++] = temp[i]; s[size] = 0; return ans; } char * removeDuplicates(char * s){ sremove(s); return s; }
150. 逆波兰表达式求值
int evalRPN(char ** tokens, int tokensSize){ for(int i = 0;i <tokensSize;i++){ if(top) printf("%d",stack[top-1]); if(tokens[i][0] == '+') {//弹栈计算 int num2 = stack[--top],num1 = stack[--top]; stack[top++] = num1 + num2; } else if(tokens[i][0] == '-' && !tokens[i][1]){ int num2 = stack[--top],num1 = stack[--top]; stack[top++] = num1 - num2; } else if(tokens[i][0] == '*'){ int num2 = stack[--top],num1 = stack[--top]; stack[top++] = num1 * num2; } else if(tokens[i][0] == '/'){ int num2 = stack[--top],num1 = stack[--top]; stack[top++] = num1 / num2; } else{//数字入栈 int j = 0,flag = 0,num = 0; if(tokens[i][0] == '-') flag = 1,j++; for(;tokens[i][j];j++){ num *= 10; num += tokens[i][j] - '0'; } if(!flag) stack[top++] = num; else stack[top++] = -num; } } return stack[0]; //最后栈内只剩最终结果 }
394. 字符串解码
char * decodeString(char * s){ char *stack =malloc(sizeof(char)*100000); int top = 0; for(int i = 0;s[i];i++){ if(s[i] ==']'){ //出栈 char temp[10000]; int tempnum = 0; while(stack[--top]!='[') temp[tempnum++] = stack[top]; unsigned char k = stack[--top];//个数弹出来 这里有个坑，这玩意是有符号的。。。离谱！ while(k--) for(int m = tempnum - 1;m>=0;m--) stack[top++] = temp[m]; } else if(s[i] >='0'&&s[i]<='9'){ int temp = 0; while(s[i] >='0'&&s[i]<='9'){ temp *= 10; temp+=s[i] - '0'; i++; } stack[top++] = temp; i--; } else stack[top++] = s[i];//入栈 } stack[top] = 0; return stack; }
