#牛客堂直播视频#常见面试题精讲（一）（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); } }

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

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); } }

根据最长回⽂⼦序列处理字符串  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]; } }

视频怎么无法放大？

qq群满员了，腾讯视频看不了，还能在哪里看到回放

讲的真好

讲的好，大牛啊

请问上面这些题目的代码在哪里可以看到

如何实现转圈打印矩阵？ package chapter_8_arrayandmatrix; public class Problem_02_RotateMatrix { public static void rotate(int[][] matrix) { int tR = 0; int tC = 0; int dR = matrix.length - 1; int dC = matrix[0].length - 1; while (tR < dR) { rotateEdge(matrix, tR++, tC++, dR--, dC--); } } public static void rotateEdge(int[][] m, int tR, int tC, int dR, int dC) { int times = dC - tC; // times就是总共的组数 int tmp = 0; for (int i = 0; i != times; i++) { // 一次循环就是一组占据调整 tmp = m[tR][tC + i]; m[tR][tC + i] = m[dR - i][tC]; m[dR - i][tC] = m[dR][dC - i]; m[dR][dC - i] = m[tR + i][dC]; m[tR + i][dC] = tmp; } } public static void printMatrix(int[][] matrix) { for (int i = 0; i != matrix.length; i++) { for (int j = 0; j != matrix[0].length; j++) { System.out.print(matrix[i][j] + " "); } System.out.println(); } } public static void main(String[] args) { int[][] matrix = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } }; printMatrix(matrix); rotate(matrix); System.out.println("========="); printMatrix(matrix); } }

字符串旋转问题  public static void reverse(char[] chas, int start, int end) { char tmp = 0; while (start < end) { tmp = chas[start]; chas[start] = chas[end]; chas[end] = tmp; start++; end--; } } public static void rotate1(char[] chas, int size) { if (chas == null || size <= 0 || size >= chas.length) { return; } reverse(chas, 0, size - 1); reverse(chas, size, chas.length - 1); reverse(chas, 0, chas.length - 1); } public static void rotate2(char[] chas, int size) { if (chas == null || size <= 0 || size >= chas.length) { return; } int start = 0; int end = chas.length - 1; int lpart = size; int rpart = chas.length - size; int s = Math.min(lpart, rpart); int d = lpart - rpart; while (true) { exchange(chas, start, end, s); if (d == 0) { break; } else if (d > 0) { start += s; lpart = d; } else { end -= s; rpart = -d; } s = Math.min(lpart, rpart); d = lpart - rpart; } } public static void exchange(char[] chas, int start, int end, int size) { int i = end - size + 1; char tmp = 0; while (size-- != 0) { tmp = chas[start]; chas[start] = chas[i]; chas[i] = tmp; start++; i++; } }

管理员 后面还要一段代码没贴呀

package chapter_8_arrayandmatrix; import java.util.HashMap; import java.util.LinkedList; import java.util.List; import java.util.Map.Entry; public class Problem_06_FindKMajority { public static void printHalfMajor(int[] arr) { int cand = 0; int times = 0; for (int i = 0; i != arr.length; i++) { if (times == 0) { cand = arr[i]; times = 1; } else if (arr[i] == cand) { times++; } else { times--; } } times = 0; for (int i = 0; i != arr.length; i++) { if (arr[i] == cand) { times++; } } if (times > arr.length / 2) { System.out.println(cand); } else { System.out.println("no such number."); } } public static void printKMajor(int[] arr, int K) { if (K < 2) { System.out.println("the value of K is invalid."); return; } HashMap<Integer, Integer> cands = new HashMap<Integer, Integer>(); for (int i = 0; i != arr.length; i++) { if (cands.containsKey(arr[i])) { cands.put(arr[i], cands.get(arr[i]) + 1); } else { if (cands.size() == K - 1) { allCandsMinusOne(cands); } else { cands.put(arr[i], 1); } } } HashMap<Integer, Integer> reals = getReals(arr, cands); boolean hasPrint = false; for (Entry<Integer, Integer> set : cands.entrySet()) { Integer key = set.getKey(); if (reals.get(key) > arr.length / K) { hasPrint = true; System.out.print(key + " "); } } System.out.println(hasPrint ? "" : "no such number."); } public static void allCandsMinusOne(HashMap<Integer, Integer> map) { List<Integer> removeList = new LinkedList<Integer>(); for (Entry<Integer, Integer> set : map.entrySet()) { Integer key = set.getKey(); Integer value = set.getValue(); if (value == 1) { removeList.add(key); } map.put(key, value - 1); } for (Integer removeKey : removeList) { map.remove(removeKey); } } public static HashMap<Integer, Integer> getReals(int[] arr, HashMap<Integer, Integer> cands) { HashMap<Integer, Integer> reals = new HashMap<Integer, Integer>(); for (int i = 0; i != arr.length; i++) { int curNum = arr[i]; if (cands.containsKey(curNum)) { if (reals.containsKey(curNum)) { reals.put(curNum, reals.get(curNum) + 1); } else { reals.put(curNum, 1); } } } return reals; } public static void main(String[] args) { int[] arr = { 1, 2, 3, 1, 1, 2, 1 }; printHalfMajor(arr); int K = 4; printKMajor(arr, K); } }

讲的真的很好

大牛撒

老师讲得真好，很深入

书出来吗？