首页 > 代码库 > 面经笔记
面经笔记
1.
输入一串用空格隔开的数字串，对于数字串的奇数位按升序排序，偶数位按降序排序。
示例输入：
4 6 2 3 6 7 8 1
处理过程：
奇数位：4 2 6 8 升序排序结果： 2 4 6 8
偶数位：6 3 7 1 降序排序结果： 7 6 3 1
结果输出：2 7 4 6 6 3 8 1
1 import java.util.ArrayList; 2 import java.util.PriorityQueue; 3 import java.util.Scanner; 4 5 /** 6 * Created by Mingxiao on 10/14/2016. 7 * Time: O(N*logN) 8 * Space: O(N) 9 */10 public class Main {11 12 public int[] sort(int[] arr) {13 if (arr == null || arr.length <= 1) {14 return arr;15 }16 17 PriorityQueue<Integer> increaseQueue = new PriorityQueue<>();18 PriorityQueue<Integer> decreaseQueue = new PriorityQueue<>();19 int[] result = new int[arr.length];20 21 int oddIndex = 1;22 int evenIndex = 0;23 24 while (oddIndex < arr.length) {25 decreaseQueue.offer(arr[oddIndex]);26 increaseQueue.offer(arr[evenIndex]);27 28 oddIndex += 2;29 evenIndex += 2;30 }31 32 oddIndex -= 2;33 evenIndex = 0;34 35 while (evenIndex < arr.length && oddIndex > 0) {36 result[evenIndex] = increaseQueue.poll();37 result[oddIndex] = decreaseQueue.poll();38 evenIndex += 2;39 oddIndex -= 2;40 }41 42 return result;43 }44 45 public static void main(String[] args) {46 47 Scanner cin = new Scanner(System.in);48 ArrayList<Integer> list = new ArrayList<>();49 while (cin.hasNext()) {50 list.add(cin.nextInt());51 }52 53 54 int[] testArr = new int[list.size()];55 for (int i = 0; i < list.size(); i++) {56 testArr[i] = list.get(i);57 }58 int[] result = new Main().sort(testArr);59 for (int i = 0; i < result.length; i++) {60 System.out.print(result[i] + ", ");61 }62 }63 }
2.
某个字符串只存在三种格式字符分别是0~9、A~Z和a~z，请按照数字在前、大写字母次之、小写字母最后的方式排序，字符串长度不超过100。
例如：CBA321zyx
123ABCxyz
1 import java.util.Scanner; 2 3 /** 4 * Created by Mingxiao on 10/14/2016. 5 * Time: O(N) 6 * Space: O(N) 7 */ 8 public class Main { 9 10 public static String sort(String str) {11 char[] sortArr = new char[128];12 StringBuilder sb = new StringBuilder();13 14 for (int i = 0; i < str.length(); i++) {15 sortArr[str.charAt(i) - 0]++;16 }17 18 for (int i = 48; i < sortArr.length; i++) {19 if (sortArr[i] != 0) {20 char temp = (char)i;21 for (int j = 0; j < sortArr[i]; j++) {22 sb.append(temp);23 }24 }25 }26 27 return sb.toString();28 }29 30 31 public static void main(String[] args) {32 33 Scanner cin = new Scanner(System.in);34 String str = "";35 while (cin.hasNext()) {36 str = cin.nextLine();37 }38 39 System.out.print(sort(str));40 }41 }
3.
给出两个字串A，B。将A字串转化为B字串，转化一共有两种方式:删除连续的n个字符，一次操作费用为2。增加连续的n个字符(增加的字符是什么由你决定)，一次操作费用为n+2。求把A变为B最小费用。
dsafsadfadf -> fdfd : 7aaaaaaaa -> bbbbbbbb: 12
提示：
"dsafsadfadf" 变成 "fdfd" 最少的代价的一种方法是：
1. "dsafsadfadf" -> "f" 删除连续的10个，代价2
2. "f" -> "fdfd" 增加连续的3个（”dfd”），代价为3 ＋ 2 ＝ 5
总共的最小代价为2 ＋ 5 ＝ 7，其他方法的代价都不小于7
"aaaaaaaa" 变成 “bbbbbbbb” 最小代价的一种方法是：
1. "aaaaaaaa" 全部删除，代价2
2. 增加8个连续的‘b‘，代价10
总共的最小代价为2 ＋ 10 ＝ 12
注意，有些最优的方案可能要做多次的删除和增加操作，不限于两次。
1 import java.util.Scanner; 2 3 /** 4 * Created by Mingxiao on 10/14/2016. 5 * dp 6 * Time: O(N^3) 7 */ 8 public class Main { 9 10 private static final int BOUND = 2000;11 private static final int INF = Integer.MAX_VALUE;12 13 public static int minCost(String a, String b) {14 int l1 = a.length();15 int l2 = b.length();16 int[][] first = new int[BOUND][BOUND];17 int[][] second = new int[BOUND][BOUND];18 int[][] third = new int[BOUND][BOUND];19 20 for (int i = 0; i <= l1; i++) {21 first[0][i] = 2; second[0][i] = third[0][i] = INF;22 }23 for (int i = 0; i <= l2; i++) {24 second[i][0] = i + 2; first[i][0] = third[i][0] = INF;25 }26 third[0][0] = 0;27 for (int j = 1; j <= l2; j++) {28 for (int i = 1; i <= l1; i++) {29 third[j][i] = a.charAt(i - 1) == b.charAt(j - 1) ? Math.min(Math.min(third[j - 1][i - 1], second[j - 1][i - 1]), first[j - 1][i - 1]) : INF;30 second[j][i] = first[j][i] = INF;31 for (int k = 1; k <= j; k++) {32 second[j][i] = Math.min(second[j][i], Math.min(second[j - k][i] + k, Math.min(first[j - k][i] + k + 2, third[j - k][i] + k + 2)));33 }34 for (int k = 1; k <= i; k++) {35 first[j][i] = Math.min(first[j][i], Math.min(first[j][i - k], Math.min(second[j][i - k] + 2, third[j][i - k] + 2)));36 }37 }38 }39 return Math.min(Math.min(third[l2][l1], second[l2][l1]), first[l2][l1]);40 }41 42 public static void main(String[] args) {43 44 int counter = 0;45 46 Scanner cin = new Scanner(System.in);47 if (cin.hasNext()) {48 counter = cin.nextInt();49 }50 51 String[] strArr = new String[counter * 2];52 int index = 0;53 while (cin.hasNext()) {54 strArr[index] = cin.nextLine();55 }56 57 for (int i = 0; i < strArr.length; i++) {58 System.out.println(minCost(strArr[i],strArr[++i]));59 }60 61 }62 }
面经笔记
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。