/*暴风影音校园招聘笔试题目-技术D卷.6. m*n的网格从左上角A点走到右下角B点，每次可走一格，只能往右或下走。输出有多少种走法和所有路线数。*/#include <cstring>#include <cstdio>#include <algorithm>using namespace std;int m = 2, n = 3;int* path;void printPath(){int i;for( i=0; i<m+n-1; i++) {printf("%s->", path[i] ? "right" : "down"); }printf("%s\n", path[m+n-1] ? "right" : "down");}// 方法一 // 数学排列int A(int a, int b){int sum = 1;while(b--) {sum *= a--;}return sum;}void solve1(){printf("%d*%d的网格A到B的路径数：%d\n", m, n, A(m+n, n) / A(n, n));int i;for( i=0; i<m; i++) {path[i] = 0; //0表示down}for( i=m; i<m+n; i++) {path[i] = 1; //1表示right}do {printPath();} while(next_permutation(path, path+m+n)); //生成全排列}// 方法二 int dfs(int cur, int x, int y){if(cur == m+n) {printPath();return 1;}int cnt = 0;if(x < m) { //可以向下走path[cur] = 0;cnt += dfs(cur+1, x+1, y);}if(y < n) {path[cur] = 1;cnt += dfs(cur+1, x, y+1);}return cnt;}void solve2(){//0表示down, 1表示rightint cnt = dfs(0, 0, 0);printf("%d\n", cnt);}// 方法三： 动态规划来计算路径个数void dp(){const int MAXN = 100, MAXM = 100; // 假设 m,n<100 int d[MAXM][MAXN];memset(d, 0, sizeof(d));d[0][0] = 1;for(int i=0; i<m+1; i++) {for(int j=0; j<n+1; j++) {if(i!=0) d[i][j] += d[i-1][j];if(j!=0) d[i][j] += d[i][j-1];}}printf("A-B的路径数：%d \n", d[m][n]);}int main(){path = new int[m+n];/*数学方法：A到B需要m+n步，其中m步向下，n步向右。所有路径数为m个down和n个right的排列个数。所以 A(m+n, m+n) / ( A(m, m) * A(n, n) ) = A(m+n, n) / A(n, n);*///solve1(); /*由于需要打印路径，可以考虑使用回溯法*///solve2();/*动态规划*/dp();return 0;}/*暴风第5题， 从一个表达式字符串中找到最深层圆括号内的表达式.如从x+(y*z)-(m-(3+4)) 中找到3+4*/#include <cstring>#include <cstdio>#include <algorithm>using namespace std;int main(){char str[] = "x+(y*z)+(m-(3-4)+(1+(2-0))+(m-(3+4))";char *pa =0, *pe = 0;int m = 0, lvl = 0;char *p = str;while(*p) {if(*p == '(') {lvl++;if(lvl > m) { pa = p+1;m = lvl;pe = 0;}} else if(*p == ')') {if(pe == 0) pe = p;lvl--;}p++;}while(pa < pe) {putchar(*pa++);}return 0;}/*暴风第4题.二叉树节点定义：struct TBinaryTree {TBinaryTree *m_pLeft;TBinaryTree *m_pRight;char m_chElement;};将两个二叉树合并：a) 不能改变两个二叉树原有的内部结构b) 只可以将其中一个二叉树的根节点，挂到另一个二叉树的非满节点下c) 使得合并后树高度最小d) 最优合并方式有很多种，给出一种就可以了*/#include <cstring>#include <cstdio>#include <algorithm>#include <queue>#define MAX(a, b) ((a) > (b) ? (a) : (b))const int MAXN = 20;using namespace std;struct TBinaryTree {TBinaryTree *m_pLeft;TBinaryTree *m_pRight;char m_chElement;};TBinaryTree tbt1[MAXN];TBinaryTree tbt2[MAXN];TBinaryTree * init_tree(TBinaryTree *tbt1) {int n, i;scanf("%d", &n);int idx, left, right;char key;for(i=1; i<=n; i++) {scanf("%d %c%d%d", &idx, &key, &left, &right);//printf("%d%c%d%d\n", idx, key, left, right);tbt1[i].m_chElement = key;if(left) tbt1[i].m_pLeft = &tbt1[left];else tbt1[i].m_pLeft = 0;if(right) tbt1[i].m_pRight = &tbt1[right];else tbt2[i].m_pRight = 0;}return &tbt1[1];}//获得树的深度int getHight(TBinaryTree *root){if(root == NULL) return 0;return MAX(getHight(root->m_pLeft), getHight(root->m_pRight)) + 1;}//找到深度最小、非度为2的节点//采用广度遍历树，（深度遍历也可以，但是效率差）void getRightNode(int &l, TBinaryTree *&pNode, TBinaryTree *root){queue<TBinaryTree *> q;q.push(root);l = 1; //根深度为1int cnt = 1; //当深度节点数while(!q.empty()) {int temp = 0; // temp记录下个深度中的节点数while(cnt--) {root = q.front(); q.pop();if(root->m_pLeft==0 || root->m_pRight==0) {pNode = root;return;}q.push(root->m_pLeft);q.push(root->m_pRight);temp += 2;}cnt = temp;l++;}}// 层序遍历树void print(TBinaryTree *root){printf("\n");queue<TBinaryTree *> q;q.push(root);int cnt = 1; //当深度节点数while(!q.empty()) {int temp = 0; // temp记录下个深度中的节点数while(cnt--) {root = q.front(); q.pop();printf("%c ", root->m_chElement);if(root->m_pLeft) {q.push(root->m_pLeft);++temp;}if(root->m_pRight) {q.push(root->m_pRight);++temp;}}cnt = temp;printf("\n");}}/*输入41 A 2 32 B 0 43 C 0 04 D 0 061 a 2 32 b 4 53 c 6 04 d 0 05 e 0 06 f 0 0*/int main(){//freopen("in.txt", "r", stdin);TBinaryTree *pTree1, *pTree2;pTree1 = init_tree(tbt1);pTree2 = init_tree(tbt2);print(pTree1);print(pTree2);int h1, h2;h1 = getHight(pTree1);h2 = getHight(pTree2);printf("tree1 height：%d， tree2 height： %d\n", h1, h2);TBinaryTree *pNode1, *pNode2;int l1, l2;getRightNode(l1, pNode1, pTree1);getRightNode(l2, pNode2, pTree2);printf("%d %c\n", l1, pNode1->m_chElement);printf("%d %c\n", l2, pNode2->m_chElement);int L1 = MAX(h1, l1+h2);int L2 = MAX(h2, l2+h1);if(L2 < L1) {swap(pNode1, pNode2);swap(pTree1, pTree2);}if(pNode1->m_pLeft == NULL) {pNode1->m_pLeft = pTree2;} else {pNode1->m_pRight = pTree2;}print(pTree1);return 0;}
