一、Map的应用篇
乒 乓球筐
小白代码
import java.util.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别 while (in.hasNext()) { // 注意 while 处理多个 case String A = in.next(); String B = in.next(); Map<Character, Integer> map = new HashMap<>(); for (int i = 0; i < A.length(); ++i) { if (!map.containsKey(A.charAt(i))) { map.put(A.charAt(i), 1); } else { int temp = map.get(A.charAt(i)); map.put(A.charAt(i), temp + 1); } } int[] arrB = new int[100]; for (int i = 0; i < B.length(); ++i) { // System.out.println(B.charAt(i) - 'A'); arrB[B.charAt(i) - 'A']++; } int flag = 1; for (int i = 0; i < B.length(); ++i) { if (map.containsKey(B.charAt(i))) { int j = B.charAt(i) - 'A'; if (arrB[j] <= map.get(B.charAt(i))) { // 符合要求什么也不做 } else { // 不符合要求就改变flag flag = 0; } } else { flag = 0; } } if (flag == 1) { System.out.println("Yes"); } else { System.out.println("No"); } } } }
扩展做法
// write your code here // write your code here import java.util.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别 while (in.hasNext()) { // 注意 while 处理多个 case String temp = in.next(); StringBuilder A = new StringBuilder(temp); String B = in.next(); char[] find = B.toCharArray(); int flag = 1; for (char ch : find) { // 不等于-1，说明该字符在A中 int index = A.indexOf(String.valueOf(ch)); if (index != -1) { // 题目要求的是B中的字符在A中都有，并且在B中的数量不多于在A中的数量 // 我们就在遍历B中的过程，逐步的删除A中与B中相同的字符，如果从头到尾B中的字符都在A中 // 删除就是防止A中虽然有B中的字符，但没有B中的字符数量多 A.deleteCharAt(index); } else { flag = 0; } } if (flag == 1) { System.out.println("Yes"); } else { System.out.println("No"); } } } }
简单的错误记录
思路：
将每一个数据都存入到HashMap中，最后输出的时候只输出8个即可
代码如下
import java.io.IOException; import java.util.HashMap; import java.util.LinkedHashMap; import java.util.Scanner; import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); HashMap<String, Integer> map = new LinkedHashMap<String, Integer>(); String str = null; while ((str = bf.readLine()) != null) { String[] strs = str.split(" "); String[] split = strs[0].split("\\\\"); //根据\分割 int LineNum = Integer.parseInt(strs[1]); String FileName = split[split.length - 1]; //只保留最后16位 if (FileName.length() > 16) FileName = FileName.substring(FileName.length() - 16); String key = FileName + " " + LineNum; //放入到HashMap中 int Number = 1; if (map.containsKey(key)) map.put(key, map.get(key) + 1); else { map.put(key, Number); } } int count = 0; for (String string : map.keySet()) { count++; if (count > (map.keySet().size() - 8)) //输出最后八个记录 System.out.println(string + " " + map.get(string)); } } }
二、动态规划篇
计算字符串的编辑距离
import java.io.*; // BufferedReader需要用 import java.util.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) throws IOException{ BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); String strA = null; // 注意 hasNext 和 hasNextLine 的区别 while ((strA = bf.readLine()) != null) { String strB = bf.readLine(); // f[i][j]表示把A字符串的前i个字符转换成字符串B的前j个字符，需要进行的编辑距离 int lenA = strA.length(); int lenB = strB.length(); int[][] ret = new int[lenA + 1][lenB + 1]; ret[0][0] = 0; for (int i = 0; i <= lenA; ++i) { ret[i][0] = i; } for (int j = 0; j <= lenB; ++j) { ret[0][j] = j; } // 状态转移方程：ret[i][j] = ret[i][j - 1] + 1 || ret[i][j] = ret[i - 1][j] + 1; /// ret[i][j] = ret[i - 1][j - 1] + 1; for (int i = 1; i <= lenA; ++i) { for (int j = 1; j <= lenB; ++j) { // 这里有些特殊，因为我们的字符真正的数据是从0，下标开始的——》即0下标和我们的ret[1][1]对应 // 但我们这个ret[0][0] if (strA.charAt(i - 1) == strB.charAt(j - 1)) { // 说明我们字符串A的第一个字符和我们字符串B的第一个字符相同ret[1][1] = 0; ret[i][j] = ret[i - 1][j - 1]; } else { ret[i][j] = Math.min(Math.min(ret[i - 1][j], ret[i][j - 1]), ret[i - 1][j - 1]) + 1; } } } System.out.println(ret[lenA][lenB]); } } }
年终奖
import java.util.*; /** 这个计算过程中有三个特殊情况 情况1：如果是起点，那么直接忽略即可 情况2：如果处在第一行，那么由于是第一行，所以从起点走，它只可能是向右不断走得到的 情况3：如果处在第一列，那么由于是第一列，所以从起点走，它只可能是向下不断走的到的 */ public class Bonus { // 建立一个相同的矩阵board,board[i][j]表示从起点到i,j这一点中某条路径代表的礼物价值值总和 // 但要注意我们这里一开始传的参数board只是表示这一点的礼物价值，还不是到达这一点的路径总价值——》是经过不断构建才形成的礼物价值总和数组board[i][j]; public int getMost(int[][] board) { // write code here int row = board.length; // 行数 int col = board[0].length;// 每一行有多少列 // 先要把borad[0][j]第一行、board[i][0]第一列给构建好了,使得borad[i][0]、board[0][j]就代表从起点到这一列这个位置或者这一行这个位置的所获得的礼物总价值 for (int i = 1; i < row; ++i) { board[i][0] = board[i - 1][0] + board[i][0]; } for (int j = 1; j < col; ++j) { board[0][j] = board[0][j - 1] + board[0][j]; } // 此时，第一行borad[i][0]、board[0][j]就代表从起点到这一列或者这一行的总价值 // 接下来我们要构建中间的了（在第一行和第一列的基础上） for (int i = 1; i < row; ++i) { for (int j = 1; j < col; ++j) { // 对于这样一个棋盘，到达(i,j)这一点要么是上一行(i-1,j)向下移动一行得到，要么是前一列(i,j-1)向右移动一列得到 board[i][j] = Math.max(board[i - 1][j], board[i][j - 1]) + board[i][j]; // board[i][j]代表了此时从起点到board[i][j]位置所经过路径所获得的礼物总价值 } } return board[row - 1][col - 1]; } }
如果你对上面的board[i][j]代表的究竟是这一点的礼物价值，还是从起点到这一点所经过的路径的总价值不太清楚的话。
我们不妨另外构建一个矩阵gifts[i][j]来专门表示从起点到i,j这一点中某条路径代表的礼物价值值总和。
