yeskery

面试手写代码题目

二分查找

  1. private static int binarySearch(int a[], int target) {
  2. if (a == null || a.length == 0) return -1;
  3. int left = 0, right = a.length - 1;
  4. while (left <= right) {
  5. int mid = (left + right) / 2;
  6. if (a[mid] == target) return mid;
  7. else if (a[mid] > target) right = mid - 1;
  8. else left = mid + 1;
  9. }
  10. return -1;
  11. }

KMP

  1. private static int[] getNext(char[] pattern) {
  2. int[] next = new int[pattern.length + 1];
  3. int i = 0, j = -1, len = pattern.length;
  4. next[0] = -1;
  5. while (i < len) {
  6. if (j == -1 || pattern[i] == pattern[j]) {
  7. i++;
  8. j++;
  9. next[i] = j;
  10. } else {
  11. j = next[j];
  12. }
  13. }
  14. return next;
  15. }
  16. private static int kmp(char[] text, char[] pattern) {
  17. if (text == null || text.length == 0
  18. || pattern == null || pattern.length == 0) return -1;
  19. int[] next = getNext(pattern);
  20. int i = 0, j = 0, len1 = text.length, len2 = pattern.length;
  21. while (i < len1 && j < len2) {
  22. if (j == -1 || text[i] == pattern[j]) {
  23. i++;
  24. j++;
  25. } else {
  26. j = next[j];
  27. }
  28. if (j == len2) {
  29. // 返回出现模式串位置
  30. return i - len2 + 1;
  31. // 统计出现的次数
  32. // j=next[j];
  33. // ans++;
  34. }
  35. }
  36. return -1;
  37. }

堆排序

  1. private static void swap(int a[], int x, int y) {
  2. int tmp = a[x];
  3. a[x] = a[y];
  4. a[y] = tmp;
  5. }
  6. private static void sift(int a[], int root, int hight) {
  7. if (root >= hight) return;
  8. int left = root * 2, right = left + 1;
  9. if (left < hight && a[root] < a[left]) {
  10. swap(a, root, left);
  11. sift(a, left, hight);
  12. }
  13. if (right < hight && a[root] < a[right]) {
  14. swap(a, root, right);
  15. sift(a, right, hight);
  16. }
  17. }
  18. private static void heapSort(int a[]) {
  19. if (a == null || a.length == 0) return;
  20. // init
  21. int b[] = new int[a.length + 1];
  22. for (int i = 1, len = b.length; i < len; i++) {
  23. b[i] = a[i - 1];
  24. }
  25. // build max heap
  26. for (int i = b.length / 2; i >= 1; i--) {
  27. sift(b, i, b.length);
  28. }
  29. // sort
  30. for (int i = 1, len = b.length; i < len; i++) {
  31. swap(b, 1, len - i);
  32. a[i-1] = b[len - i];
  33. sift(b, 1, len - i);
  34. }
  35. }

快速排序

  1. private static void swap(int a[], int x, int y) {
  2. int tmp = a[x];
  3. a[x] = a[y];
  4. a[y] = tmp;
  5. }
  6. private static void quickSort(int[] a) {
  7. if (a == null || a.length == 0) return;
  8. quickSort(a, 0, a.length - 1);
  9. }
  10. private static void quickSort(int[] a, int left, int right) {
  11. if (left < right) {
  12. int i = left, j = right;
  13. int key = a[left];
  14. while (i < j) {
  15. while (i < j && a[j] >= key) {
  16. j--;
  17. }
  18. if (i < j) {
  19. swap(a, i, j);
  20. i++;
  21. }
  22. while (i < j && a[i] <= key) {
  23. i++;
  24. }
  25. if (i < j) {
  26. swap(a, i, j);
  27. j--;
  28. }
  29. }
  30. a[i] = key;
  31. quickSort(a, left, i - 1);
  32. quickSort(a, i + 1, right);
  33. }
  34. }
  35. private void quickSort(int a[]) {
  36. if (a == null || a.length == 0) return;
  37. quickSort(a, 0, a.length - 1);
  38. }

快速排序非递归版

  1. private static void swap(int a[], int x, int y) {
  2. int tmp = a[x];
  3. a[x] = a[y];
  4. a[y] = tmp;
  5. }
  6. private static int quickSort(int[] a, int left, int right) {
  7. int i = left, j = right;
  8. int key = a[left];
  9. while (i < j) {
  10. while (i < j && a[j] >= key) {
  11. j--;
  12. }
  13. if (i < j) {
  14. swap(a, i, j);
  15. i++;
  16. }
  17. while (i < j && a[i] <= key) {
  18. i++;
  19. }
  20. if (i < j) {
  21. swap(a, i, j);
  22. j--;
  23. }
  24. }
  25. a[i] = key;
  26. return i;
  27. }
  28. private static class Status {
  29. int left, right;
  30. public Status(int left, int right) {
  31. this.left = left;
  32. this.right = right;
  33. }
  34. public int getLeft() {
  35. return left;
  36. }
  37. public int getRight() {
  38. return right;
  39. }
  40. }
  41. private static void quickSort(int a[]) {
  42. if (a == null || a.length == 0) return;
  43. Stack<Status> stack = new Stack<>();
  44. int left = 0, right = a.length - 1;
  45. stack.push(new Status(left, right));
  46. while (!stack.empty()) {
  47. Status currStatus = stack.pop();
  48. int partitionPos = -1;
  49. if (currStatus.getLeft() >= currStatus.getRight()) continue;
  50. partitionPos = quickSort(a, currStatus.getLeft(), currStatus.getRight());
  51. if (partitionPos == -1) continue;
  52. if (currStatus.getLeft() < partitionPos - 1) {
  53. stack.push(new Status(currStatus.getLeft(), partitionPos - 1));
  54. }
  55. if (partitionPos + 1 < currStatus.getRight()) {
  56. stack.push(new Status(partitionPos + 1, currStatus.getRight()));
  57. }
  58. }
  59. }

Dijkstra

  1. private static int Dijkstra(int map[][], int start, int end) {
  2. if (map == null || map.length == 0 || map[0].length == 0) return -1;
  3. int dis[] = new int[map.length];
  4. boolean vis[] = new boolean[map.length];
  5. for (int i = 0, len = map.length; i < len; i++) {
  6. dis[i] = map[start][i];
  7. vis[i] = false;
  8. }
  9. for (int i = 0, len = map.length; i < len - 1; i++) {
  10. int minx = Integer.MAX_VALUE, k = -1;
  11. for (int j = 0; j < len; j++) {
  12. if (!vis[j] && dis[j] < minx) {
  13. minx = dis[j];
  14. k = j;
  15. }
  16. }
  17. if (k == -1) return -1;
  18. else {
  19. vis[k] = true;
  20. for (int j = 0; j < len; j++) {
  21. if (!vis[j] && dis[j] < dis[k] + map[k][j]) {
  22. dis[j] = dis[k] + map[k][j];
  23. }
  24. }
  25. }
  26. }
  27. return dis[end] == Integer.MAX_VALUE ? -1 : dis[end];
  28. }

Floyd

  1. private static int Floyd(int map[][], int start, int end) {
  2. if (map == null || map.length == 0 || map[0].length == 0) return -1;
  3. int dp[][] = new int[map.length][map[0].length];
  4. for (int i = 0, len = map.length; i < len; i++) {
  5. for (int j = i; j < len; j++) {
  6. dp[i][j] = map[i][j] == -1 ? Integer.MAX_VALUE : map[i][j];
  7. }
  8. }
  9. for (int k = 0, len = map.length; k < len; k++) {
  10. for (int i = 0; i < len; i++) {
  11. for (int j = 0; j < len; j++) {
  12. dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]);
  13. }
  14. }
  15. }
  16. return dp[start][end];
  17. }

最长公共子序列

  1. private static int LCS(String a, String b) {
  2. if (a == null || b == null || "".equals(a) || "".equals(b)) return -1;
  3. int dp[][] = new int[a.length()][b.length()];
  4. for (int i = 1, lena = a.length(); i <= lena; i++) {
  5. for (int j = 1, lenb = b.length(); j <= lenb; j++) {
  6. char cha = a.charAt(i - 1);
  7. char chb = b.charAt(j - 1);
  8. if (cha == chb) {
  9. dp[i][j] = dp[i - 1][j - 1] + 1;
  10. } else {
  11. dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
  12. }
  13. }
  14. }
  15. return dp[a.length()][b.length()];
  16. }
  1. public class LCS {
  2. public int findLCS(String A, int n, String B, int m) {
  3. // write code here
  4. int dp[][] = new int[n + 1][m + 1];
  5. for (int i = 0; i <= n; i++) {
  6. for (int j = 0; j <= m; j++) {
  7. dp[i][j] = 0;
  8. }
  9. }
  10. for (int i = 1; i <= n; i++) {
  11. for (int j = 1; j <= m; j++) {
  12. if (A.charAt(i - 1) == B.charAt(j - 1)) {
  13. dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
  14. } else {
  15. dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
  16. }
  17. }
  18. }
  19. return dp[n][m];
  20. }
  21. }

最小编辑距离

  1. private static int Levenshtein(String a, String b) {
  2. if (a == null || b == null || "".equals(a) || "".equals(b)) return -1;
  3. int dp[][] = new int[a.length()][b.length()];
  4. for (int i = 0, lena = a.length(); i < lena; i++) {
  5. dp[i][0] = i;
  6. }
  7. for (int i = 0, lenb = b.length(); i < lenb; i++) {
  8. dp[0][i] = i;
  9. }
  10. for (int i = 1, lena = a.length(); i <= lena; i++) {
  11. for (int j = 1, lenb = b.length(); j <= lenb; j++) {
  12. char cha = a.charAt(i - 1);
  13. char chb = b.charAt(j - 1);
  14. int cost = 1;
  15. if (cha == chb) {
  16. cost = 0;
  17. }
  18. dp[i][j] = Math.min(Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1] + cost);
  19. }
  20. }
  21. return dp[a.length()][b.length()];
  22. }

最长回文子串

  1. public class Palindrome {
  2. public int getLongestPalindrome(String A, int n) {
  3. // write code here
  4. boolean isPalindrome[][] = new boolean[n][n];
  5. int ans = 0;
  6. for (int i = n - 1; i >= 0; i--) {
  7. isPalindrome[i][i] = true;
  8. for (int j = i + 1; j < n; j++) {
  9. if (j == i + 1) {
  10. isPalindrome[i][j] = A.charAt(i) == A.charAt(j);
  11. } else {
  12. isPalindrome[i][j] = isPalindrome[i + 1][j - 1] && A.charAt(i) == A.charAt(j);
  13. }
  14. if (isPalindrome[i][j]) {
  15. ans = Math.max(ans, j - i + 1);
  16. }
  17. }
  18. }
  19. return ans;
  20. }
  21. }

最长递增子序列

  1. private static int solve(int a[]) {
  2. int dp[] = new int[a.length];
  3. for (int i = 0, len = a.length; i < len; i++) {
  4. dp[i] = 1;
  5. for (int j = i - 1; j >= 0; j--) {
  6. if (a[j] < a[i]) {
  7. dp[i] = Math.max(dp[i], dp[j] + 1);
  8. }
  9. }
  10. }
  11. int ans = 0;
  12. for (int i = 0, len = a.length; i < len; i++) {
  13. ans = Math.max(dp[i], ans);
  14. }
  15. return ans;
  16. }

评论

发表评论 点击刷新验证码

提示

该功能暂未开放