1.栈的压入与压出 /* 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。n<=100000 用一个栈作辅助，顺序描述压入序列和弹出序列，如果当前位置上压入序列和弹出序列值相等，直接都向后移一个元素；比较栈顶元素和弹出序列当前值，如果相等，出栈，弹出序列后移一个元素；其余情况，将压入序列当前值压栈，压入序列后移一个元素。如果到最后，弹出序列都处理不完，说明弹出序列不合法。时间复杂度为O(n)。 */ #include <stdio.h> #include <stack> using namespace std; int qin[100005]; int qout[100005]; int main(void) { int n; int i,j; while(scanf("%d", &n) == 1) { for(i=0; i<n; ++i) scanf("%d", &qin[i]); for(i=0; i<n; ++i) scanf("%d", &qout[i]); stack<int> s; i = 0; j = 0; while(i<n || j<n) { if(i<n && j<n && qin[i]==qout[j]) { ++i; ++j; } else { if(s.empty()) { if(i<n) s.push(qin[i++]); } else if(s.top() == qout[j]) { s.pop(); ++j; } else if(i<n) { s.push(qin[i++]); } else { break; } } } if(j==n) printf("Yes\n"); else printf("No\n"); } return 0; }
2.二叉搜索书的后续遍历序列
/* 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。n<=10000。 二叉搜索树的性质之一为：根结点值大于左子树，小于右子树。设后序遍历顺序为 A B C，则有A<C<B。因此，从根结点（遍历的最后一个结点）出发，向前找到所有连续的大于根结点的值作为右子树，再往前的所有连续小于根结点的作为左子树，如果往前还有大于根结点的，则不是二叉搜索树的后序遍历结果。递归处理左子树和右子树。时间复杂度约为O(nlogn)。 */ #include <stdio.h> int seq[10005]; bool valid(int x, int y) { if(x >= y) return true; int i=y-1; while(i>=x && seq[i]>seq[y]) { --i; } int j = i; while(i>=x && seq[i]<seq[y]) { --i; } if(i>=x) return false; if(!valid(x, j)) return false; if(!valid(j+1, y-1)) return false; return true; } int main(void) { int n; while(scanf("%d", &n) == 1) { for(int i=0; i<n; ++i) scanf("%d", &seq[i]); if(valid(0, n-1)) printf("Yes\n"); else printf("No\n"); } return 0; }
3.数组中出现次数超过一半的数字
/* 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。n<=100000 将出现一半的数与其他数两两抵消，剩余的最后一个数即是答案。具体做法是每次选两个不同的数两两抵消，要么会抵消一个答案数字和一个非答案数字，要么抵消两个非答案数字，到最后剩余的一定是答案。时间复杂度为O(n)。 */ #include <stdio.h> int f[100005]; int main(void) { int i,n; while(scanf("%d", &n) == 1) { int ans = 0; int count = 0; for(i=0; i<n; ++i) { scanf("%d", &f[i]); if(count == 0) { ans = f[i]; count = 1; } else if(f[i] == ans) { ++count; } else { --count; } } count = 0; for(i=0; i<n; ++i) { if(f[i] == ans) ++count; } if(count > n/2) printf("%d\n", ans); else printf("-1\n"); } return 0; }
4.整数中1出现的次数
/* 求两个整数间的数，10进制各个位上1出现的总次数，0<=a,b<=1,000,000,000 按位统计，统计每位上1出现的次数。当前位刚好是1和刚好是0需要单独考虑。 */ #include <stdio.h> long long CountOne(long long x) { long long base = 1; long long ans = 0; long long temp; long long rec = 0; while(x) { temp = x/10; ans += temp * base; if(x%10 > 1) ans += base; else if(x%10 == 1) { ans += rec + 1; } rec += x%10 * base; base *= 10; x /= 10; } return ans; } int main(void) { long long a,b; while(scanf("%lld%lld", &a, &b) == 2) { long long sa = 0, sb = 0; if(a>b) { a += b; b = a - b; a = a - b; } if(a>0) sa = CountOne(a-1); sb = CountOne(b); printf("%lld\n", sb-sa); } return 0; }
5.数组中的逆袭对
/* 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。 归并排序，在merge的时候统计逆序对，设需要merge的数组为A，B，A大小为n，B大小为m。如果A[i]>B[j]，则逆序数将增加n-i。 */ #include <stdio.h> int f[100005]; int g[100005]; long long ans; void Sort(int x, int y) { if(x >= y) return ; int mid = (x+y)>>1; Sort(x, mid); Sort(mid+1, y); int i = x; int j = mid+1; int k = x; while(i<=mid || j<=y) { if(i>mid) { g[k++] = f[j++]; } else if(j>y) { g[k++] = f[i++]; } else if(f[i]<=f[j]) { g[k++] = f[i++]; } else if(f[i]>f[j]) { ans += mid - i + 1; g[k++] = f[j++]; } } for(k=x; k<=y; ++k) f[k] = g[k]; } int main(void) { int n; while(scanf("%d", &n) == 1) { for(int i=0; i<n; ++i) scanf("%d", &f[i]); ans = 0; Sort(0, n-1); printf("%lld\n", ans); } return 0; }
6.和为s的两个数字
/* 输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S。n<=1000000 用两个游标，一个从头开始A[i]，一个从尾开始A[j]，如果A[i]+A[j]<S，则i后移一格，否则j前移一格，如果相等，则记录结果。算法复杂度为O(n)。 */ #include <stdio.h> long long num[1000005]; int main(void) { int n; long long m; while(scanf("%d%lld", &n, &m) == 2) { int i,j; for(i=0; i<n; ++i) scanf("%lld", &num[i]); i = 0; j = n-1; long long x=-1, y=-1; long long v; long long res = num[j]*num[j]; while(i<j) { v = num[i] + num[j]; if(v == m) { if(num[i]*num[j] <= res) { x = num[i]; y = num[j]; res = num[i]*num[j]; } ++i; --j; } else if(v < m) { ++i; } else { --j; } } printf("%lld %lld\n", x, y); } return 0; }
7.猜数字游戏
/* 给定n个骰子，每个骰子点数为m，求按概率排序前3的点数和。 概率值按 4 舍 5 入要求保留 2 位小数， n(0<=n<=10),m(6<=m<=8)。 递推，令f[i][j]表示前i个骰子，点数和为j的次数。有f[i][j] = f[i-1][j-1]+....+f[i-1][j-m]。也可直接用一维的轮换数组进行计算，即g[j] = f[j-1]+...+f[j-m], f=g。 */ #include <stdio.h> #include <algorithm> #include <vector> using namespace std; struct T { int id; double v; }; bool cmp(const T &a, const T &b) { if(a.v>b.v) return true; else if(a.v<b.v) return false; else return a.id<b.id; } int main(void) { int n,m; bool first = true; while(scanf("%d", &n)==1 && n) { scanf("%d", &m); int f[85] = {0}; int g[85] = {0}; int i,j,k; for(i=1; i<=m; ++i) f[i] = 1; for(i=1; i<n; ++i) { for(j=0; j<=80; ++j) g[j] = 0; for(j=1; j<=80; ++j) { for(k=1; k<=m; ++k) { if(j-k>0) { g[j] += f[j-k]; } } } for(j=0; j<=80; ++j) f[j] = g[j]; } int sum = 0; vector<T> ans; T t; for(i=1; i<=80; ++i) { if(f[i] > 0) { sum += f[i]; t.id = i; t.v = f[i]; ans.push_back(t); } } for(i=0; i<ans.size(); ++i) { ans[i].v = ((int)(100.0*ans[i].v/sum+0.5))/100.0; } sort(ans.begin(), ans.end(), cmp); if(first) first = false; else printf("\n"); for(i=0; i<3; i++) { printf("%d %.2lf\n", ans[i].id, ans[i].v); } } return 0; }