第一题暴力过的
package exam; import java.util.ArrayList; import java.util.List; import java.util.Scanner; /** * @author kelvin * @create 2021-08-21 15:12 */ public class WY_1 { public static void main(String[] args) { Scanner in = new Scanner(System.in); List<Integer> list = new ArrayList<>(); while (in.hasNextInt()) { list.add(in.nextInt()); } int m = list.get(list.size() - 1); int n = list.size() - 1; int cnt = 0; for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { if (list.get(i) + list.get(j) <= m) { cnt++; } } } System.out.println(cnt); } }第二题 直接按着题意模拟
package exam; import java.util.Collections; /** * @author kelvin * @create 2021-08-21 15:18 */ public class WY_2 { public char findKthBit (int n, int k) { // write code here String s = getString(n); return s.charAt(k - 1); } private String getString(int n) { if (n == 1) { return "a"; } String pre = getString(n - 1); return pre + (char) ('a' + n - 1) + reverse(invert(pre)); } private String reverse(String s) { char[] chs = s.toCharArray(); int left = 0, right = chs.length - 1; while (left <= right) { char tmp = chs[left]; chs[left] = chs[right]; chs[right] = tmp; left++; right--; } return String.valueOf(chs); } private String invert(String s) { char[] chs = s.toCharArray(); for (int i = 0; i < chs.length; i++) { int n = chs[i] - 'a'; n = 26 - n; chs[i] = (char) ('a' + n - 1); } return String.valueOf(chs); } public static void main(String[] args) { WY_2 wy_2 = new WY_2(); // for (int i = 1; i <= 4; i++) { // System.out.println(wy_2.getString(i)); // } System.out.println(wy_2.findKthBit(4, 11)); } }
用的贪心思想
package exam; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.Scanner; /** * @author kelvin * @create 2021-08-21 15:37 */ public class WY_3 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); List<Integer> ages = new ArrayList<>(); while (sc.hasNextInt()) { ages.add(sc.nextInt()); } int[] papers = new int[ages.size()]; Arrays.fill(papers, 1); int n = papers.length; if (n == 1) { System.out.println(1); return; } for (int i = 0; i < n; i++) { if (i == 0) { if (ages.get(i) > ages.get(n - 1)) { papers[i] = Math.max(papers[n - 1] + 1, papers[i]); } if (ages.get(i) > ages.get(i + 1)) { papers[i] = Math.max(papers[i + 1] + 1, papers[i]); } } else if (i == n - 1) { if (ages.get(i) > ages.get(0)) { papers[i] = Math.max(papers[0] + 1, papers[i]); } if (ages.get(i) > ages.get(i - 1)) { papers[i] = Math.max(papers[i - 1] + 1, papers[i]); } } else { if (ages.get(i) > ages.get(i + 1)) { papers[i] = Math.max(papers[i + 1] + 1, papers[i]); } if (ages.get(i) > ages.get(i - 1)) { papers[i] = Math.max(papers[i - 1] + 1, papers[i]); } } } int sum = 0; for (int i = 0; i < n; i++) { sum += papers[i]; } System.out.println(sum); } }第四题 用的动态规划/
我这里为了方便先把起点也计算进去, 然后最后再减去起点.
但是要注意起点是2(障碍物)也可以走, 因为题目说了只计算每段路径的终点, 所以起点是什么都无所谓.
我这里为了处理起点是2的情况, 将其改成了1.
package exam; import java.util.Arrays; /** * @author kelvin * @create 2021-08-21 15:56 */ public class WY_4 { public int minSailCost (int[][] input) { if (input == null || input.length == 0 || input[0].length == 0) { return -1; } if (input[0][0] == 2) { input[0][0] = 1; // 更改起点 } int m = input.length, n = input[0].length; int[][] dp = new int[m][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (input[i][j] == 1) { dp[i][j] = 1; } else if (input[i][j] == 0) { dp[i][j] = 2; } else if (input[i][j] == 2) { dp[i][j] = -1; continue; } if (i == 0 && j == 0) { continue; } int min = -1; if (i - 1 >= 0) { if (dp[i - 1][j] != -1) { min = dp[i - 1][j]; } } if (j - 1 >= 0) { if (dp[i][j - 1] != -1) { min = min == -1 ? dp[i][j - 1] : Math.min(min, dp[i][j - 1]); } } dp[i][j] = min == -1 ? -1 : min + dp[i][j]; } } // for (int[] row : dp) { // System.out.println(Arrays.toString(row)); // } if (dp[m - 1][n - 1] == -1) { return -1; } else { return dp[m - 1][n - 1] - dp[0][0]; } } public static void main(String[] args) { WY_4 wy_4 = new WY_4(); // int[][] matrix = { // {1, 1, 1, 1, 0}, // {0, 1, 0, 1, 0}, // {1, 1, 2, 1, 1}, // {0, 2, 0, 0, 1} // }; int[][] matrix = { {0}, {0}, {2} }; System.out.println(wy_4.minSailCost(matrix)); } }
全部评论
(3) 回帖