6. 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。
http://ac.jobdu.com/problem.php?pid=1385
记录：postIdx每个case前记得要初始化；post数组填充的位置应该在子树填充完之后；如何in中找不到root证明无法构建返回错误。
#include<cstdio> int pre[1005]; int in[1005]; int post[1005]; int postIdx=0; int build(int pre[], int in[],int n){ if(n<=0) return 1; int rootVal = pre[0]; int rootIdx = -1; for(int i=0;i<n;i++){ if(in[i]==rootVal){ rootIdx = i; break; } } if(rootIdx==-1) return 0; int left = build(pre+1,in,rootIdx); int right = build(pre+1+rootIdx,in+1+rootIdx,n-1-rootIdx); post[postIdx++]=rootVal; return left&&right; } int main(){ // freopen("data.in","r",stdin); // freopen("data.out","w",stdout); int n; while(scanf("%d",&n)!=EOF){ postIdx=0; for(int i=0;i<n;i++) scanf("%d",&pre[i]); for(int i=0;i<n;i++) scanf("%d",&in[i]); int res = build(pre,in,n); if(res){ for(int i=0;i<n;i++){ printf("%d ",post[i]); } printf(" "); }else{ printf("No "); } } return 0; }
8. 旋转数组的最小数字
http://ac.jobdu.com/problem.php?pid=1386
记录：此题是二分查找的变体，需要考虑各种边界情况，注意重复元素。 可以以1,2,3,4,5和1,1,2,2等例子旋转后进行分析。
#include<stdio.h> int a[1000005]; int getMin(int l, int r) { int min = 0x7fffffff; int i; for (i = l; i <= r; i++) if (a[i] < min) { min = a[i]; } return min; } int main() { // freopen("in.txt", "r", stdin); int n; while (scanf("%d", &n) != EOF) { int i; for (i = 0; i < n; i++) scanf("%d", &a[i]); if (a[0] < a[n - 1]) { //no pivot printf("%d ", a[0]); } else { int l = 0; int r = n - 1; int mid; int breakOut = 0; while (r - l > 1) { mid = (l + r) / 2; if (a[mid] == a[l] && a[mid] == a[r]) { printf("%d ", getMin(l, r)); breakOut = 1; break; } if (a[mid] > a[l]) { l = mid; } else { r = mid; } } if (!breakOut) printf("%d ", a[r]); } } return 0; }
10. 二进制中1的个数。
扩展：
1. 如何判断一个数是2的幂。
2. 计算需要改变多少位能把m变成n。
int numberOfOne(int n){ int count =0; while(n){ count++; n = n&(n-1); } return count; }
11. 数值的整数次方
注意各种异常情况的处理。
学习设置flag这种标记错误的方式。
注意求幂的时候二分的运用。
注意double的比较 return a-b>-0.0000001&&a-b<0.0000001;
#include<stdio.h> #define NO_MEANING 1 int equal(double a, double b) { if (a - b > -0.0000001 && a - b < 0.0000001) return 1; else return 0; } double recursivePow(double base, unsigned int exp) { if (exp == 0) return 1.0; else if (exp == 1) return base; if (exp % 2 == 0) { double half = recursivePow(base, exp / 2); return half * half; } else { double half = recursivePow(base, (exp - 1) / 2); return half * half * base; } } double myPow(double base, int exp, int* flag) { if (equal(base, 0.0)) { if (exp <= 0) { *flag = NO_MEANING; return 0.0; } else return 0.0; } if (exp == 0) return 1.0; else if (exp == 1) return base; double res = 1; int neg = 0; if (exp < 0) { exp = -exp; neg = 1; } res = recursivePow(base, (unsigned int) exp); if (neg) res = 1 / res; return res; } int main() { // freopen("in.txt", "r", stdin); int n; scanf("%d", &n); double base; int exp; while (n--) { scanf("%lf%d", &base, &exp); int flag = 0; double res = myPow(base, exp, &flag); if (!flag) printf("%.2ef ", res); else printf("INF "); } return 0; } /************************************************************** Problem: 1514 User: jdflyfly Language: C++ Result: Accepted Time:80 ms Memory:1020 kb ****************************************************************/
12. 打印1到最大的n位数：考察大数问题。
1. 字符串处理。
2. 递归生成permutation，注意leading 0的处理。
#include<stdio.h> int a[1000]; void print(int n,int cur){ if(cur==n){ //print the res, be careful with the leading 0 int meetNonZero =0; for(int i=0;i<n;i++){ if(meetNonZero){ printf("%d",a[i]); continue; } if(a[i]!=0){ meetNonZero=1; printf("%d",a[i]); } } if(meetNonZero) printf(" "); return; } for(int i=0;i<10;i++){ a[cur]=i; print(n,cur+1); } } int main(){ freopen("data.in","r",stdin); freopen("data.out","w",stdout); int n; while(scanf("%d",&n)!=EOF){ print(n,0); } return 0; }
14 调整数组顺序使奇数位于偶数前面
16. 反转链表
注意null等各种边界情况。
记录：学会用pre,cur,post等临时变量
#include<stdio.h> struct Node { int val; Node*next; Node(int v) : val(v), next(NULL) { } }; Node* reverse(Node* head) { Node* newHead = NULL; Node* pre = NULL; Node* cur = head; Node* post = NULL; while (cur != NULL) { post = cur->next; if (post == NULL) newHead = cur; cur->next = pre; pre = cur; cur = post; } return newHead; } void printList(Node* head) { if (head == NULL) { printf("NULL "); return; } Node* p = head; while (p != NULL) { if (p != head) printf(" "); printf("%d", p->val); p = p->next; } printf(" "); } int main() { // freopen("my.in", "r", stdin); // freopen("my.out", "w", stdout); int n; while (scanf("%d", &n) != EOF) { Node* dummyHead = new Node(-1); Node* p = dummyHead; int tmp; for (int i = 0; i < n; i++) { scanf("%d", &tmp); p->next = new Node(tmp); p = p->next; } Node* revHead = reverse(dummyHead->next); printList(revHead); } return 0; }
22 栈的压入、弹出序列
#include<stdio.h> #include<stdlib.h> #include<stack> using namespace std; int in[100005]; int out[100005]; int main() { // freopen("my.in", "r", stdin); // freopen("my.out", "w", stdout); int n; while (scanf("%d", &n) != EOF) { for (int i = 0; i < n; i++) scanf("%d", &in[i]); for (int i = 0; i < n; i++) scanf("%d", &out[i]); int i = 0, j = 0; stack<int> stack; int ok = 1; while (j < n) { if (!stack.empty() && stack.top() == out[j]) { stack.pop(); j++; } else { if (i < n) { stack.push(in[i++]); } else { ok = 0; break; } } } if (ok) printf("Yes "); else printf("No "); } return 0; }
34 丑数生成。
记录：分别维护3个指针，每次选取其中最小的，选完之后更新其他指针，小于当前值
#include<stdio.h> int uglyNum[1505]; int getMin(int a, int b, int c) { int min = a; if (b < min) min = b; if (c < min) min = c; return min; } int main() { // freopen("my.in", "r", stdin); // freopen("my.out", "w", stdout); int n; while (scanf("%d", &n) != EOF) { uglyNum[0] = 1; int p = 1; int p2 = 0; int p3 = 0; int p5 = 0; int min; while (p < n) { min = getMin(uglyNum[p2] * 2, uglyNum[p3] * 3, uglyNum[p5] * 5); uglyNum[p] = min; while (uglyNum[p2] * 2 <= min) p2++; while (uglyNum[p3] * 3 <= min) p3++; while (uglyNum[p5] * 5 <= min) p5++; p++; } printf("%d ", uglyNum[n - 1]); } return 0; }
36 数组中的逆序对
利用mergesort，复杂度nlogn。
注意每次统计merge的时候如何统计count。
注意count比较大，超出了int范围，应该用long long
#include<stdio.h> #include<stdlib.h> int a[100005]; long long count; void merge(int a[], int b[], int left, int mid, int right) { int p1 = left; int p2 = mid + 1; int p = left; while (p1 <= mid && p2 <= right) { if (a[p1] <= a[p2]) { b[p++] = a[p1++]; } else { b[p++] = a[p2++]; //p1~mid范围都比p2大，所以count要增加mid-p1+1; count += mid - p1 + 1; } } while (p1 <= mid) b[p++] = a[p1++]; while (p2 <= right) b[p++] = a[p2++]; for (int i = left; i <= right; i++) a[i] = b[i]; } void mergeSort(int a[], int b[], int left, int right) { if (left < right) { int mid = left + (right - left) / 2; mergeSort(a, b, left, mid); mergeSort(a, b, mid + 1, right); merge(a, b, left, mid, right); } } int main() { // freopen("my.in", "r", stdin); // freopen("my.out", "w", stdout); int n; while (scanf("%d", &n) != EOF) { for (int i = 0; i < n; i++) scanf("%d", &a[i]); count = 0; int* b = (int*) malloc(sizeof(int) * n); mergeSort(a, b, 0, n - 1); //不要忘记了free掉 free(b); printf("%lld ", count); } return 0; }
43 n个骰子的点数
n个骰子，每个数值1~m，求所有情况的概率。
思路1：递归生成，一次枚举每个扇子的m中情况。
思路2：递推法，对于新加的一个骰子，此时和为n的骰子出现的次数应该等于上一次循环中点数和为n-1,n-2,n-3,n-4,n-5,n-6的次数的和。
思路1代码：
int maxValue; void calcuHelper(int number, int count, int sum, int*pro) { if (count == number) { pro[sum - number]++; return; } for (int i = 1; i <= maxValue; i++) { calcuHelper(number, count + 1, sum + i, pro); } } void calcu(int number, int* pro) { calcuHelper(number, 0, 0, pro); } void printProbability(int number) { if (number < 1) return; int maxSum = maxValue * number; int* pProbability = new int[maxSum - number + 1]; for (int i = number; i <= maxSum; i++) pProbability[i - number] = 0; calcu(number, pProbability); int total = pow(maxValue, number); for (int i = number; i <= maxSum; i++) { double ratio = (double) pProbability[i - number] / total; printf("%d:%.2lf ", i, ratio); } delete[] pProbability; }
44 扑克牌的顺子
记录：先排序，然后统计0的个数和间隔的个数，看0是否能填满。
#include<stdio.h> #include<math.h> #include<algorithm> using namespace std; bool isContinuous(int* numbers, int n) { if (numbers == NULL || n <= 0) return false; sort(numbers, numbers + n); int numOfZero = 0; int numOfGap = 0; int idx = 0; for (; idx < n; idx++) { if (numbers[idx] == 0) { numOfZero++; } else break; } int pre = idx; int cur = pre + 1; while (cur < n) { if (numbers[pre] == numbers[cur]) return false; numOfGap += numbers[cur] - numbers[pre] - 1; pre = cur; cur++; } return (numOfGap > numOfZero) ? false : true; } int a[20]; int main() { //freopen("my.in", "r", stdin); //freopen("my.out", "w", stdout); int n; while (scanf("%d", &n) != EOF) { if (n == 0) break; for (int i = 0; i < n; i++) scanf("%d", &a[i]); if (isContinuous(a, n)) printf("So Lucky! "); else printf("Oh My God! "); } return 0; }
45 约瑟夫环问题，n个数字组成的环，从数字0开始每次删除第m个，求最后删除的数字。
记录：递推公式 f(n,m)=[f(n-1,m)+m]%n，初始值：f(1,m)=0;
#include<stdio.h> #include<math.h> #include<algorithm> using namespace std; int lastRemaining(int n, int m) { if (n < 1 || m < 1) return -1; int last = 0; for (int i = 2; i <= n; i++) last = (last + m) % i; return last + 1; } int main() { //freopen("my.in", "r", stdin); //freopen("my.out", "w", stdout); int n, m; while (scanf("%d", &n) != EOF) { if (n == 0) break; scanf("%d", &m); printf("%d ", lastRemaining(n, m)); } return 0; }