#牛客堂直播视频#常见面试题精讲（一）（2015.5.27）

求C++版

大牛你讲的太逗了，新书一定顶

如何实现顺时针旋转矩阵？ package chapter_8_arrayandmatrix; public class Problem_01_PrintMatrixSpiralOrder { public static void spiralOrderPrint(int[][] matrix) { int tR = 0; int tC = 0; int dR = matrix.length - 1; int dC = matrix[0].length - 1; while (tR <= dR && tC <= dC) { printEdge(matrix, tR++, tC++, dR--, dC--); } } public static void printEdge(int[][] m, int tR, int tC, int dR, int dC) { if (tR == dR) { // 子矩阵只有一行时 for (int i = tC; i <= dC; i++) { System.out.print(m[tR][i] + " "); } } else if (tC == dC) { // 子矩阵只有一列时 for (int i = tR; i <= dR; i++) { System.out.print(m[i][tC] + " "); } } else { // 一般情况 int curC = tC; int curR = tR; while (curC != dC) { System.out.print(m[tR][curC] + " "); curC++; } while (curR != dR) { System.out.print(m[curR][dC] + " "); curR++; } while (curC != tC) { System.out.print(m[dR][curC] + " "); curC--; } while (curR != tR) { System.out.print(m[curR][tC] + " "); curR--; } } } public static void main(String[] args) { int[][] matrix = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } }; spiralOrderPrint(matrix); } }

如何实现“之”字形打印矩阵？ package chapter_8_arrayandmatrix; public class Problem_03_ZigZagPrintMatrix { public static void printMatrixZigZag(int[][] matrix) { int tR = 0; int tC = 0; int dR = 0; int dC = 0; int endR = matrix.length - 1; int endC = matrix[0].length - 1; boolean fromUp = false; while (tR != endR + 1) { printLevel(matrix, tR, tC, dR, dC, fromUp); tR = tC == endC ? tR + 1 : tR; tC = tC == endC ? tC : tC + 1; dC = dR == endR ? dC + 1 : dC; dR = dR == endR ? dR : dR + 1; fromUp = !fromUp; } System.out.println(); } public static void printLevel(int[][] m, int tR, int tC, int dR, int dC, boolean f) { if (f) { while (tR != dR + 1) { System.out.print(m[tR++][tC--] + " "); } } else { while (dR != tR - 1) { System.out.print(m[dR--][dC++] + " "); } } } public static void main(String[] args) { int[][] matrix = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 } }; printMatrixZigZag(matrix); } }

视频怎么无法放大？

根据最长回⽂⼦序列处理字符串  public String getPalindrome(String str, String strlps) { if (str == null || str.equals("")) { return ""; } char[] chas = str.toCharArray(); char[] lps = strlps.toCharArray(); char[] res = new char[2 * chas.length - lps.length]; int chasl = 0; int chasr = chas.length - 1; int lpsl = 0; int lpsr = lps.length - 1; int resl = 0; int resr = res.length - 1; int tmpl = 0; int tmpr = 0; while (lpsl <= lpsr) { tmpl = chasl; tmpr = chasr; while (chas[chasl] != lps[lpsl]) { chasl++; } while (chas[chasr] != lps[lpsr]) { chasr--; } set(res, resl, resr, chas, tmpl, chasl, chasr, tmpr); resl += chasl - tmpl + tmpr - chasr; resr -= chasl - tmpl + tmpr - chasr; res[resl++] = chas[chasl++]; res[resr--] = chas[chasr--]; lpsl++; lpsr--; } return String.valueOf(res); } public void set(char[] res, int resl, int resr, char[] chas, int ls, int le, int rs, int re) { for (int i = ls; i < le; i++) { res[resl++] = chas[i]; res[resr--] = chas[i]; } for (int i = re; i > rs; i--) { res[resl++] = chas[i]; res[resr--] = chas[i]; } }

1、折纸问题 package chapter_9_others; public class Problem_06_PaperFolding { public static void printAllFolds(int N) { printProcess(1, N, true); } public static void printProcess(int i, int N, boolean down) { if (i > N) { return; } printProcess(i + 1, N, true); System.out.println(down ? "down " : "up "); printProcess(i + 1, N, false); } public static void main(String[] args) { int N = 3; printAllFolds(N); } }

好期待，正好有算法问题等大神解答~ 

看下代码

顶 一个

题目答案代码

求Java版的代码，左老师讲的真棒

class FoldPaper { public:     vector<string> foldPaper(int n) {         // write code here         vector<string> res;         foldProcess(n, true, res); // 第一次的对折，形成的折现向下         return res;     }     void foldProcess(int n, bool down, vector<string>& res){     /*  n: 还要对折多少次     down: 这一次的线是否向下         res: 用来存放结果的引用     */         if(n==0) return;                  foldProcess(n-1, true, res); // 上一次折痕上方的折痕一定向下         res.push_back((down?"down":"up"));         foldProcess(n-1, false, res); // 上一次折痕的下方的折痕一定向上     } };     折纸问题的c++代码附带注释，思想是一样的，每次不断的求一条线的上面的上面的上面的...那条线，然后打印本条线，然后求出下边的那条线后返回给上一次的一条线，对大牛的代码做了修改，不使用额外的 i，n是剩余的还要对折的次数。这个题目用递归真是好舒服！！

看看

我晕，牛客网练习题里的题目给的例子跟老师说的不一样。。那个顺时针打印矩阵和打印之字形矩阵的例子都给错了。。。而且我根据例子理解题目以后，写的代码还通过了测试。。看了老师的视频才发现理解错了题目。。。

膜拜中。。。。。

折纸代码，如果有错误请指正啊，我也是初学者。。 #include<iostream> #include<stdlib.h> #include <stdio.h> #include <stdarg.h> using namespace std; typedef struct Tree{ int data; struct Tree *left; struct Tree *right; }Tree; int creat_tree(Tree *&tree,int n){ if(n<=0) return 0; if(n==1){ Tree *p,*q; p=(Tree*)malloc(sizeof(Tree)); q=(Tree*)malloc(sizeof(Tree)); p->data=0; p->left=p->right=NULL; q->data=1; q->left=q->right=NULL; tree->left=p; tree->right=q; return 0; } creat_tree(tree->left,n-1); creat_tree(tree->right,n-1); return 0; } int init_tree(Tree *&tree,int n){ if(n>0){ tree=(Tree*)malloc(sizeof(Tree)); tree->data=0; tree->left=NULL; tree->right=NULL; } for(int i=1;i<n;i++){ creat_tree(tree,i); } return 0; } int zhongxu(Tree *&tree){ if(tree){ zhongxu(tree->left); cout<<tree->data<<" "; zhongxu(tree->right); } return 0; } int main(){ Tree *tree; init_tree(tree,4); zhongxu(tree); return 0; }

怎样才能看啊

太棒了，居然是Java版代码，真是我的福利啊

对牛客网简直太赞了