java常见算法-蓝桥杯每日一题冲刺国赛
1.
一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
'A' -> "1"
'B' -> "2"
...
'Z' -> "26"
要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：
"AAJF" ，将消息分组为 (1 1 10 6)
"KJF" ，将消息分组为 (11 10 6)
注意，消息不能分组为 (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。
给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。
题目数据保证答案肯定是一个 32 位 的整数。
示例 1：
输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。
示例 2：
输入：s = "226"
输出：3
解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
示例 3：
输入：s = "0"
输出：0
解释：没有字符映射到以 0 开头的数字。
含有 0 的有效映射是 'J' -> "10" 和 'T'-> "20" 。
由于没有字符，因此没有有效的方法对此进行解码，因为所有数字都需要映射。
class Solution { public int numDecodings(String s) { int len = s.length(); int[] f = new int[len + 1]; f[0] = 1; for (int i = 1; i 1 && s.charAt(i - 2) != '0' && ((s.charAt(i - 2)-'0')*10 + (s.charAt(i - 1) - '0') <= 26)) { f[i] += f[i - 2]; } } return f[len]; }}2.
给你一个字符串 licensePlate 和一个字符串数组 words ，请你找出 words 中的 最短补全词 。
补全词 是一个包含 licensePlate 中所有字母的单词。忽略 licensePlate 中的 数字和空格 。不区分大小写。如果某个字母在 licensePlate 中出现不止一次，那么该字母在补全词中的出现次数应当一致或者更多。
例如：licensePlate = "aBc 12c"，那么它的补全词应当包含字母 'a'、'b' （忽略大写）和两个 'c' 。可能的 补全词 有 "abccdef"、"caaacab" 以及 "cbca" 。
请返回 words 中的 最短补全词 。题目数据保证一定存在一个最短补全词。当有多个单词都符合最短补全词的匹配条件时取 words 中 第一个 出现的那个。
示例 1：
输入：licensePlate = "1s3 PSt", words = ["step", "steps", "stripe", "stepple"]
输出："steps"
解释：最短补全词应该包括 "s"、"p"、"s"（忽略大小写） 以及 "t"。
"step" 包含 "t"、"p"，但只包含一个 "s"，所以它不符合条件。
"steps" 包含 "t"、"p" 和两个 "s"。
"stripe" 缺一个 "s"。
"stepple" 缺一个 "s"。
因此，"steps" 是唯一一个包含所有字母的单词，也是本例的答案。
示例 2：
输入：licensePlate = "1s3 456", words = ["looks", "pest", "stew", "show"]
输出："pest"
解释：licensePlate 只包含字母 "s" 。所有的单词都包含字母 "s" ，其中 "pest"、"stew"、和 "show" 三者最短。答案是 "pest" ，因为它是三个单词中在 words 里最靠前的那个。
class Solution { public String shortestCompletingWord(String licensePlate, String[] words) { int length = licensePlate.length(); int len = words.length; int[] a = new int[26]; for (int i = 0; i < length; i++) { if (Character.isLetter(licensePlate.charAt(i))) { char e = licensePlate.charAt(i); ++a[Character.toLowerCase(e) - 'a']; } } int index = -1; for (int i = 0; i < len; i++) { int paa = words[i].length(); int[] b = new int[26]; for (int j = 0; j < paa; j++) { char m = words[i].charAt(j); ++b[m-'a']; } boolean isSuccess = true; for (int j = 0; j < 26; j++) { if (b[j] words[i].length())) { index = i; } } return words[index]; }}3.
给你一个 m x n 的矩阵 matrix 。如果这个矩阵是托普利茨矩阵，返回 true ；否则，返回 false 。
如果矩阵上每一条由左上到右下的对角线上的元素都相同，那么这个矩阵是 托普利茨矩阵 。
4.
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间
class Solution { public int[][] merge(int[][] intervals) { int n = intervals.length; if (n == 0) return new int[0][2]; Arrays.sort(intervals, new Comparator() { @Override public int compare(int[] o1, int[] o2) { return o1[0] - o2[0]; } }); ArrayList list = new ArrayList(); for (int i = 0; i < n; i++) { int l = intervals[i][0]; int r = intervals[i][1]; if (list.size() == 0 || list.get(list.size() - 1)[1] < l) { list.add(new int[]{l,r}); }else { list.get(list.size() - 1)[1] = Math.max(list.get(list.size() - 1)[1],r); } } return list.toArray(new int[list.size()][2]); }}5.
class Solution { public boolean isToeplitzMatrix(int[][] matrix) { int n = matrix.length; int m = matrix[0].length; for (int i = 0; i < m - 1; i++) { int j = 0; while (j < n - 1 && i < m - 1) { if (matrix[j][i] != matrix[j + 1][i + 1]) return false; j++; } } for (int i = 0; i < n - 1; i++) { int j = 0; while (j < m - 1 && i < n - 1) { if (matrix[i][j] != matrix[i + 1][j + 1]) return false; j++; } } return true; }}