1题 数组arr中两个数和不大于给定值m的对数。
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); List<Integer> numList = new ArrayList<>(); while(sc.hasNextInt()) { numList.add(sc.nextInt()); } int n = numList.size() - 1; int m = numList.get(numList.size() - 1); int count = 0; for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { if (numList.get(i) + numList.get(j) <= m) { count++; } } } System.out.println(count); } }
2 字符串生成公式S_n= S_(n-1) + Li + reverse(invert(S_(n-1)),其中S_1 = "a",求第n个串的第k个字符。我在推导如何降低空间复杂度,花了些时间,打算先交一发看下一题,没想到暴力可以过。
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 返回Sn的第k位字符 * @param n int整型 Sn的n * @param k int整型 需要返回的字符下标位 * @return char字符型 */ public char findKthBit(int n, int k) { StringBuilder s = new StringBuilder(); s.append("a"); for (int i = 2; i <= n; ++i) { String pre = s.toString(); s.append(getLi(i)).append(invert(pre)); } return s.charAt(k-1); } private char getLi(int i) { return (char)('a' + (i - 1)); } private String invert(String x) { StringBuilder res = new StringBuilder(); for (int i = 0; i < x.length(); ++i) { res.append((char)('z' - (x.charAt(i) - 'a'))); } return res.reverse().toString(); } }3 题 分发糖果
leetcode 135
4 题 BFS求最短路
4 题 BFS求最短路
import java.util.LinkedList; import java.util.Queue; public class Solution { public static void main(String[] args) { int res = new Solution().minSailCost(new int[][]{{1, 1, 1, 1, 0}, {0, 1, 0, 1, 0}, {1, 1, 2, 1, 1}, {0, 2, 0, 0, 1}}); System.out.println(res); } /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * <p> * 计算最小航行费用 * * @param input int整型二维数组 二维网格 * @return int整型 */ public int minSailCost(int[][] input) { if (input.length == 0 || input[0].length == 0) return 0; int n = input.length, m = input[0].length; Queue<Position> que = new LinkedList<>(); int[][] dp = new int[n][m]; int MAXV = 0x7f7f7f7f; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { dp[i][j] = MAXV; } } dp[0][0] = 0; que.add(new Position(0, 0)); int[][] dir = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; while (!que.isEmpty()) { Position point = que.remove(); int cost = dp[point.x][point.y]; for (int i = 0; i < 4; ++i) { int xx = point.x + dir[i][0]; int yy = point.y + dir[i][1]; if (xx >= 0 && xx < n && yy >= 0 && yy < m && input[xx][yy] != 2 && cost + (2 - input[xx][yy]) < dp[xx][yy]) { dp[xx][yy] = cost + (2 - input[xx][yy]); que.add(new Position(xx, yy)); } } } return dp[n-1][m-1] == MAXV ? -1: dp[n-1][m-1]; } static class Position { int x, y; public Position(int x, int y) { this.x = x; this.y = y; } } }
全部评论
(1) 回帖