前言：java編寫，代碼盡可能帶注釋，部分題目附上解題思路。力求方便，所以不寫如有錯誤，請指出，謝謝。

查找排序

• 1、百錢買百雞問題
• 2、統(tǒng)計每個月兔子總數(shù)
• 3、查找組成一個偶數(shù)最接近的兩個素數(shù)
• 4、公共字串計算
• 5、成績排序
• 6、Redraiment的走法
• 7、字符統(tǒng)計
• 8、迷宮問題
• 9、字符串排序
• 10、質(zhì)數(shù)因子
• 11、自守數(shù)
• 12、多線程

1、百錢買百雞問題

題目描述 公元前五世紀(jì)，我國古代數(shù)學(xué)家張丘建在《算經(jīng)》一書中提出了“百雞問題”：雞翁一值錢五，雞母一值錢三，雞雛三值錢一。百錢買百雞，問雞翁、雞母、雞雛各幾何？ 詳細(xì)描述： 接口說明 原型： int GetResult(vector &list) 輸入?yún)?shù)：無 輸出參數(shù)（指針指向的內(nèi)存區(qū)域保證有效）：list 雞翁、雞母、雞雛組合的列表 返回值：-1 失敗 0 成功 import java.util.Scanner; public class Main{public static void main(String[] args){Scanner sc = new Scanner(System.in);while(sc.hasNext() ){int n = sc.nextInt(); // 將輸入的1放入n，雖然沒用// n1、n2、n3分別表示吉翁、繼母、雞雛int n1 = 0, n2 = 0, n3 = 0;//7x +4y = 100,兩種思路：一、兩層遍歷；二、一層遍歷for(n1 = 0; n1 <=14; n1++ ){for(n2 = 25; n2 >=0; n2--){int sum = 7 * n1 + 4 * n2;if(sum == 100){n3 = 100-n1-n2;System.out.println(n1 +" "+n2 + " "+n3);}}}for(n1 = 0; n1 <= 14; n1++){double j;if(n1 == 0){j = 25;}else{j = (100-7*n1)/4.0;}if(Math.abs(j- Math.round(j)) < 1e-6){n2 = (int)j;n3 = 100 - n1 - n2;System.out.println(n1 +" "+n2 + " "+n3);}}}} }

2、統(tǒng)計每個月兔子總數(shù)

題目描述 有一只兔子，從出生后第3個月起每個月都生一只兔子，小兔子長到第三個月后每個月又生一只兔子，假如兔子都不死，問每個月的兔子總數(shù)為多少？/*** 統(tǒng)計出兔子總數(shù)。* * @param monthCount 第幾個月* @return 兔子總數(shù)*/public static int getTotalCount(int monthCount){return 0;} import java.util.Scanner; public class Main{public static void main(String[] args){Scanner sc = new Scanner(System.in);while(sc.hasNext() ){int month = sc.nextInt();System.out.println(Main.getTotalCount(month));}}// 統(tǒng)計兔子總數(shù)public static int getTotalCount(int monthCount){if(monthCount < 0)return 0;// 初始化三個月份的兔子int oneMonthOld = 1;int twoMonthOld = 0;int threeMonthOld = 0;// 第一個月剛出生，所以月份要減一for(int i = 0; i < monthCount-1; i++){// 分別都長大一個月threeMonthOld += twoMonthOld;// 三月份的兔子要加上從二月份發(fā)育過來的twoMonthOld = oneMonthOld;oneMonthOld = threeMonthOld;}return oneMonthOld+twoMonthOld+threeMonthOld;} }

3、查找組成一個偶數(shù)最接近的兩個素數(shù)

注：這里動態(tài)規(guī)劃，比較不好懂

題目描述 任意一個偶數(shù)（大于2）都可以由2個素數(shù)組成，組成偶數(shù)的2個素數(shù)有很多種情況，本題目要求輸出組成指定偶數(shù)的兩個素數(shù)差值最小的素數(shù)對 import java.util.Scanner; public class Main{public static void main(String[] args){Scanner sc = new Scanner(System.in);while(sc.hasNext() ){int even = sc.nextInt();// 思路：從even/2向2查找質(zhì)數(shù)，若另一個數(shù)也為質(zhì)數(shù)滿足條件int max = even/2;for(int i = max; i >=2; i--){if(Main.judge(i) && Main.judge(even-i)){System.out.println(i);System.out.println(even-i);break;}}}}// 判斷是否為質(zhì)數(shù)public static boolean judge(int number){if(number <= 1){return false;}for(int i = 2; i < number; i++){// 若區(qū)間除了1和number外存在能整除number的數(shù)，則說明不是質(zhì)數(shù)if((number % i) == 0){return false;}}return true;} }

4、公共字串計算

題目描述 題目標(biāo)題： 計算兩個字符串的最大公共字串的長度，字符不區(qū)分大小寫 詳細(xì)描述： 接口說明 原型： int getCommonStrLength(char * pFirstStr, char * pSecondStr); 輸入?yún)?shù)：char * pFirstStr //第一個字符串char * pSecondStr//第二個字符串 import java.util.Scanner; public class Main{public static void main(String[] args){Scanner sc = new Scanner(System.in);while(sc.hasNext() ){String str1 = sc.next();String str2 = sc.next();System.out.println(Main.getCommonStrLength(str1, str2));}}// 常規(guī)解法public static int getCommonStrLength(String str1, String str2){// 空值判斷以及空指針異常if(str1 == null || str1.length() == 0 || str2 == null || str2.length()==0){return 0;}int len1 = str1.length();int len2 = str2.length();int max = 0;// 初始化兩個字符串的標(biāo)志位，以及最大公共子串的長度for(int i = 0; i < len1;){for(int j = 0; j < len2;){// 找到第一個重復(fù)的字符，試圖遍歷公共子串if(str1.charAt(i) == str2.charAt(j)){// 當(dāng)出現(xiàn)相等時候，要保證后面一串盡可能相等，但需要找出最長的公共子串// 出現(xiàn)相等則兩個標(biāo)志位一起走int p1 = i, p2 = j;int count = 0;//System.out.println(p1 + " " + p2);while(p1 < len1 && p2 < len2 && str1.charAt(p1) == str2.charAt(p2)){//System.out.println(""+str1.charAt(p1));p1++;p2++;count++;}// 走完公共子串后保存最大長度if(count > max){max = count;}}//str2中當(dāng)前字符與str1中當(dāng)前字符不相等的，str2當(dāng)前字符標(biāo)志后移一位j++;}// 遍歷str2字符串都沒找到與str1中當(dāng)前字符相等，str1當(dāng)前字符標(biāo)志后移一位i++;}return max;}// 動態(tài)規(guī)劃的解法public static int getCommonStrLength(String str1, String str2) {int len1 = str1.length();int len2 = str2.length();int[][] dp = new int[len1 + 1][len2 + 1];// 默認(rèn)初始化為0for (int i = 1; i <= len1; i++) {for (int j = 1; j <= len2; j++) {if (str1.charAt(i - 1) == str2.charAt(j - 1)) {// 兩層遍歷，找出每一次字符相等位置，若找到公共子串，那么在二維數(shù)組中走向?qū)⒁恢毙毕蛳?/span>dp[i][j] = dp[i - 1][j - 1] + 1;} }}int max = 0;for (int i = 0; i <= len1; i++) {for (int j = 0; j <= len2; j++) {if (max < dp[i][j])max = dp[i][j];}}return max;} }

5、成績排序

注意：感覺同樣分?jǐn)?shù)同樣成績這里L(fēng)inkedHashMap怕不合適吧

題目描述 查找和排序 題目：輸入任意（用戶，成績）序列，可以獲得成績從高到低或從低到高的排列,相同成績 都按先錄入排列在前的規(guī)則處理。 例示： jack 70 peter 96 Tom 70 smith 67從高到低 成績 peter 96 jack 70 Tom 70 smith 67從低到高 smith 67 jack 70 Tom 70 peter 96注：0代表從高到低，1代表從低到高 // 名字可能相同，分?jǐn)?shù)可能相同，要想唯一鍵，則利用名字加分?jǐn)?shù) import java.util.*; public class Main{public static void main(String[] args) {Scanner sc = new Scanner(System.in);while(sc.hasNext() ){String name;Integer score;List<Integer> scoreList = new ArrayList<>();Map<String, Integer> map = new LinkedHashMap<>(); // 存放score與name+" "+score的映射int sortNum = sc.nextInt();int sortMethod = sc.nextInt(); // 0 表示升序，1表示降序for(int i = 0; i < sortNum; i++){name = sc.next();score = sc.nextInt();scoreList.add(score);map.put(name+" "+score, score);}Collections.sort(scoreList);if(sortMethod == 0){// 降序Collections.reverse(scoreList);}int pre = -1;for(int s : scoreList){if(pre == s){// scoreList中不用查找重復(fù)值continue;}for(String key : map.keySet()){if(map.get(key).equals(s)){// 第一次找到System.out.println(key);}}pre = s;}}} }

6、Redraiment的走法

注意：最長遞增序列

題目描述Redraiment是走梅花樁的高手。Redraiment總是起點(diǎn)不限，從前到后，往高的樁子走，但走的步數(shù)最多，不知道為什么？你能替Redraiment研究他最多走的步數(shù)嗎？ 樣例輸入 6 2 5 1 5 4 5 樣例輸出 3 提示Example: 6個點(diǎn)的高度各為 2 5 1 5 4 5 如從第1格開始走,最多為3步, 2 4 5 從第2格開始走,最多只有1步,5 而從第3格開始走最多有3步,1 4 5 從第5格開始走最多有2步,4 5所以這個結(jié)果是3。 import java.util.*;public class Main {public static void main(String[] args) {Scanner input = new Scanner(System.in);while (input.hasNextInt()) {int n = input.nextInt();int[] a = new int[n];for (int i = 0; i < n; i++)a[i] = input.nextInt();System.out.println(getMaxSteps(a, n));}}// 轉(zhuǎn)化成求最長遞增子序列public static int getMaxSteps(int [] arr ,int n) {int[] dp = new int[n];for(int i = 0; i < n; i++){dp[i] = 1;for(int j = 0; j < i; j++){if(arr[j] < arr[i]){dp[i] = Math.max(dp[i], dp[j]+1);}}}// 遍歷數(shù)組找出最大值int max = 0;for(int i = 0; i < n; i++){if(dp[i] > max){max = dp[i];}}return max;} }

7、字符統(tǒng)計

題目描述 如果統(tǒng)計的個數(shù)相同，則按照ASCII碼由小到大排序輸出 。如果有其他字符，則對這些字符不用進(jìn)行統(tǒng)計。 實(shí)現(xiàn)以下接口： 輸入一個字符串，對字符中的各個英文字符，數(shù)字，空格進(jìn)行統(tǒng)計（可反復(fù)調(diào)用） 按照統(tǒng)計個數(shù)由多到少輸出統(tǒng)計結(jié)果，如果統(tǒng)計的個數(shù)相同，則按照ASII碼由小到大排序輸出 清空目前的統(tǒng)計結(jié)果，重新統(tǒng)計 調(diào)用者會保證： 輸入的字符串以‘\0’結(jié)尾。 package zTestDay;import java.util.*;public class Main {// 方法一，hashMap加treeMappublic static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {Map<Character, Integer> map = new HashMap<>();String str = sc.next();for(int i = 0; i < str.length(); i++){Character key = str.charAt(i);// 只對英文字符，數(shù)字，空格統(tǒng)計if((key >= '0' && key <= '9') || (key >= 'A' && key <='Z') || (key >= 'a' && key <='z') || key == ' '){if(map.containsKey(key) ){map.put(key, map.get(key)+1);}else{map.put(key, 1);}}}Map<Integer, Character> treeMap = new TreeMap<>();for(Character key :map.keySet()){// 有相同次數(shù)key，無相同的val, 所以利用map的key與val構(gòu)造treeMap新的唯一keytreeMap.put(map.get(key) * 128 + 128 - key , key); // 這里必須是-key,才能使得出現(xiàn)相同的次數(shù)的字母按照assic降序排列}StringBuilder sb = new StringBuilder();for(Integer i : treeMap.keySet()){sb.append(treeMap.get(i));}System.out.println(sb.reverse().toString());}}// 方法二、treeMap與次數(shù)降序查找，能夠運(yùn)用主要是因?yàn)樽址疃?56public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {Map<Character, Integer> map = new TreeMap<>(); // 必須用treeMapSet<Integer> set = new HashSet<>();String str = sc.next();for(int i = 0; i < str.length(); i++){Character key = str.charAt(i);// 只對英文字符，數(shù)字，空格統(tǒng)計if((key >= '0' && key <= '9') || (key >= 'A' && key <='Z') || (key >= 'a' && key <='z') || key == ' '){if(map.containsKey(key) ){map.put(key, map.get(key)+1);}else{map.put(key, 1);}set.add(map.get(key)); // 保存出現(xiàn)的次數(shù)，去重}}List<Integer> count = new ArrayList<>();for(Integer i :set){count.add(i);}Collections.reverse(count); // 將出現(xiàn)次數(shù)降序StringBuilder sb = new StringBuilder();for(Integer i : count){for(Character key : map.keySet()){// 這里hashmap里面存儲字符，所以數(shù)據(jù)不會太多，要不然不能兩層循環(huán)if(map.get(key) == i){sb.append(key);}}}System.out.println(sb.toString());}} }

8、迷宮問題

題目描述 定義一個二維數(shù)組N*M（其中2<=N<=10;2<=M<=10），如5 × 5數(shù)組下所示： int maze[5][5] = {0, 1, 0, 0, 0,0, 1, 0, 1, 0,0, 0, 0, 0, 0,0, 1, 1, 1, 0,0, 0, 0, 1, 0, };它表示一個迷宮，其中的1表示墻壁，0表示可以走的路，只能橫著走或豎著走，不能斜著走，要求編程序找出從左上角到右下角的最短路線。入口點(diǎn)為[0,0],既第一空格是可以走的路。 Input 一個N × M的二維數(shù)組，表示一個迷宮。數(shù)據(jù)保證有唯一解,不考慮有多解的情況，即迷宮只有一條通道。 Output 左上角到右下角的最短路徑，格式如樣例所示。Sample Input 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0Sample Output (0, 0) (1, 0) (2, 0) (2, 1) (2, 2) (2, 3) (2, 4) (3, 4) (4, 4) import java.util.LinkedList; import java.util.Scanner; public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while(sc.hasNext()){int rows = sc.nextInt();int cols = sc.nextInt();int[][] maze = new int[rows][cols]; // 0表示未訪問，1表示以訪問，-1表示無法訪問for(int i = 0; i < rows; i++){for(int j = 0; j < cols; j++){int val = sc.nextInt();if(val == 1){maze[i][j]=-1;}}}//System.out.println(rows+" "+ cols);LinkedList<String> list = new LinkedList<>();findRoute(maze, 0, 0, rows, cols, list);for(String step : list){System.out.println(step);}}}private static boolean findRoute(int[][] maze, int i, int j, int rows, int cols, LinkedList<String> list) {if(i >= 0 && j >= 0 && i < rows && j < cols && maze[i][j] == 0){// 能訪問（i,j)這位置maze[i][j] = 1;list.add("("+i+","+j+")");if(i == rows-1 && j == cols-1){// 已經(jīng)找到了出口點(diǎn)return true;}if(findRoute(maze, i+1, j, rows, cols, list)|| findRoute(maze, i-1, j, rows, cols, list)|| findRoute(maze, i, j+1, rows, cols, list)|| findRoute(maze, i, j-1, rows, cols, list)){// 能繼續(xù)訪問下一步return true;}else{// 恢復(fù)未訪問的狀態(tài)maze[i][j] = 0;list.removeLast();return false;}}else{// 不能訪問此位置return false;}} }

9、字符串排序

注：思路不夠簡潔

題目描述 編寫一個程序，將輸入字符串中的字符按如下規(guī)則排序。規(guī)則 1 ：英文字母從 A 到 Z 排列，不區(qū)分大小寫。 如，輸入： Type 輸出： epTy規(guī)則 2 ：同一個英文字母的大小寫同時存在時，按照輸入順序排列。 如，輸入： BabA 輸出： aABb規(guī)則 3 ：非英文字母的其它字符保持原來的位置。 如，輸入： By?e 輸出： Be?y import java.util.*;// 利用treeMap的鍵排序，利用hashMap保存位置映射關(guān)系 public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {String input = sc.nextLine();TreeMap<Character, String> map = new TreeMap<>(); // 利用treemap的key排序，//ArrayList<Character> list = new ArrayList<>();HashMap<Integer, Character> hashMap = new HashMap<>(); // 非英文字母位置映射for (int i = 0; i < input.length(); i++) {char c = input.charAt(i); // 字符if (Character.isLetter(c)) {// 字符為字母char lower = Character.toLowerCase(c);if (map.containsKey(lower)) {map.put(lower, map.get(lower) + c); // 將小寫字母作為key，小寫后相同的字母按順序排列為value} else {map.put(lower, c + "");}//list.add(c); // 列表添加字符} else {// 若字符不為字母，保存位置映射關(guān)系hashMap.put(i, c);}}// 這里同時可以利用集合排序，那么也不需要利用hashMap保存非字母位置，遍歷輸入字符串，非字母字符位置就知道了 /* Collections.sort(list, new Comparator<Character>() {@Overridepublic int compare(Character o1, Character o2) {return Character.toLowerCase(o1) - Character.toLowerCase(o2);}});*/StringBuilder sb = new StringBuilder(); // 存儲字符為字母的數(shù)組，并按照小寫字母排序for (Character key : map.keySet()) {sb.append(map.get(key));}StringBuilder sb2 = new StringBuilder();int i = 0, j = 0;while (i < input.length()) {if (hashMap.containsKey(i)) {sb2.append(hashMap.get(i));} else if (j < sb.length()) {sb2.append(sb.charAt(j++));}i++;}System.out.println(sb2.toString());}} }

10、質(zhì)數(shù)因子

題目描述 功能:輸入一個正整數(shù)，按照從小到大的順序輸出它的所有質(zhì)因子（重復(fù)的也要列舉）（如180的質(zhì)因子為2 2 3 3 5 ） 最后一個數(shù)后面也要有空格 import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {Long input = sc.nextLong();ArrayList<Integer> list = new ArrayList<>();int n = 2;while(input >= 2){if(input % n == 0){// 若能整除,添加質(zhì)數(shù)因子input = input / n;list.add(n);}else{// 找下一個質(zhì)數(shù)//n = getNext(n);n++; // 這里壓根不需要找下一個質(zhì)數(shù)，而是加一就行，和質(zhì)數(shù)定義有關(guān)}}for(Integer i : list){System.out.print(i + " ");}}}// 找出下一位質(zhì)數(shù)private static int getNext(int n) {while(true){n++;if(judge(n)){return n;}}}// 判斷是否為質(zhì)數(shù)private static boolean judge(int n) {for(int i = 2; i < n; i++){if(n % i == 0){return false;}}return true;} }

11、自守數(shù)

題目描述 自守數(shù)是指一個數(shù)的平方的尾數(shù)等于該數(shù)自身的自然數(shù)。 例如：25^2 = 625，76^2 = 5776，9376^2 = 87909376。請求出n以內(nèi)的自守數(shù)的個數(shù) import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {Long input = sc.nextLong();int cnt = 1;for(int i = 1; i <= input; i++){// 0 也算自守數(shù)if(judge(i)){cnt++;}}System.out.println(cnt);}}// 判斷是否自守數(shù)private static boolean judge(long i) {int count = 1; // 統(tǒng)計是幾位數(shù)if(i <= 0)return false;while(i >= (long)Math.pow(10, count)){count++;}long square = i * i;long divisor = (long)Math.pow(10, count); //若尾數(shù)部分全部相同，相減后整除10次方位數(shù)，如25就是兩位數(shù)，除以100if((square - i) % divisor == 0){return true;}return false;} }

12、多線程

注意：?？蜕峡吹降耐ㄟ^案列Java不對，只能本地通過，?？筒煌ㄟ^

題目描述 問題描述：有4個線程和1個公共的字符數(shù)組。線程1的功能就是向數(shù)組輸出A，線程2的功能就是向字符輸出B，線程3的功能就是向數(shù)組輸出C，線程4的功能就是向數(shù)組輸出D。要求按順序向數(shù)組賦值A(chǔ)BCDABCDABCD import java.util.Scanner;public class Main {public static void main(String[] args) throws Exception{Object a = new Object();Object b = new Object();Object c = new Object();Object d = new Object();Scanner sc = new Scanner(System.in);while (sc.hasNext()){int count = sc.nextInt();Runnable pa = new MyRunnable("A", d, a, count);Runnable pb = new MyRunnable("B", a, b, count);Runnable pc = new MyRunnable("C", b, c, count);Runnable pd = new MyRunnable("D", c, d, count);new Thread(pa).start();Thread.sleep(1);new Thread(pb).start();Thread.sleep(1);new Thread(pc).start();Thread.sleep(1);new Thread(pd).start();}} }class MyRunnable implements Runnable{private String name;private Object prev;private Object self;private int count;MyRunnable(String name, Object prev, Object self, int count) {this.name = name;this.prev = prev;this.self = self;this.count = count;}@Overridepublic void run() {// int count = 10;while (count > 0) {synchronized (prev){synchronized (self){System.out.print(name);count--;self.notify();}try {prev.wait();} catch (InterruptedException e) {e.printStackTrace();}}}} }

總結(jié)

以上是生活随笔為你收集整理的牛客华为机试-查找排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。