1. 最大间距
给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。
如果数组元素个数小于 2，则返回 0。
示例 1:
输入: [3,6,9,1]
输出: 3
解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。
示例 2:
输入: [10]
输出: 0
解释: 数组元素个数小于 2，因此返回 0。
说明:
你可以假设数组中所有元素都是非负整数，且数值在 32 位有符号整数范围内。
请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。
出处：
https://edu.csdn.net/practice/27637463
代码：
import java.util.*; public class maximumGap { public static class Solution { public int maximumGap(int[] nums) { int len = nums.length; Arrays.sort(nums); int temp = 0; int res = 0; if (len < 2) return 0; for (int i = 0; i < len - 1; i++) { temp = nums[i + 1] - nums[i]; res = Math.max(res, temp); } return res; } } public static void main(String[] args) { Solution s = new Solution(); int[] nums = {3,6,9,1}; System.out.println(s.maximumGap(nums)); int[] nums2 = {10}; System.out.println(s.maximumGap(nums2)); } }
输出：
3
0
2. 串联所有单词的子串
给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。
示例 1：
输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。输出的顺序不重要, [9,0] 也是有效答案。
示例 2：
输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：[]
以下程序实现了这一功能，请你填补空白处内容：
```Java
class Solution { public List<Integer> findSubstring(String s, String[] words) { List<Integer> res = new ArrayList<>(); if (s == null || s.length() == 0 || words == null || words.length == 0) return res; HashMap<String, Integer> map = new HashMap<>(); int one_word = words[0].length(); int word_num = words.length; int all_len = one_word * word_num; for (String word : words) { map.put(word, map.getOrDefault(word, 0) + 1); } for (int i = 0; i < one_word; i++) { int left = i, right = i, count = 0; HashMap<String, Integer> tmp_map = new HashMap<>(); while (right + one_word <= s.length()) { String w = s.substring(right, right + one_word); right += one_word; if (!map.containsKey(w)) { count = 0; left = right; tmp_map.clear(); } else { tmp_map.put(w, tmp_map.getOrDefault(w, 0) + 1); count++; while (tmp_map.getOrDefault(w, 0) > map.getOrDefault(w, 0)) { ______________________; } if (count == word_num) res.add(left); } } } return res; } } ```
出处：
https://edu.csdn.net/practice/27637464
代码：
import java.util.*; public class findSubstring { public static class Solution { public List<Integer> findSubstring(String s, String[] words) { List<Integer> res = new ArrayList<>(); if (s == null || s.length() == 0 || words == null || words.length == 0) return res; HashMap<String, Integer> map = new HashMap<>(); int one_word = words[0].length(); int word_num = words.length; int all_len = one_word * word_num; for (String word : words) { map.put(word, map.getOrDefault(word, 0) + 1); } for (int i = 0; i < one_word; i++) { int left = i, right = i, count = 0; HashMap<String, Integer> tmp_map = new HashMap<>(); while (right + one_word <= s.length()) { String w = s.substring(right, right + one_word); right += one_word; if (!map.containsKey(w)) { count = 0; left = right; tmp_map.clear(); } else { tmp_map.put(w, tmp_map.getOrDefault(w, 0) + 1); count++; while (tmp_map.getOrDefault(w, 0) > map.getOrDefault(w, 0)) { String t_w = s.substring(left, left + one_word); count--; tmp_map.put(t_w, tmp_map.getOrDefault(t_w, 0) - 1); left += one_word; } if (count == word_num) res.add(left); } } } return res; } } public static void main(String[] args) { Solution sol = new Solution(); String s = "barfoothefoobarman"; String[] words = {"foo","bar"}; System.out.println(sol.findSubstring(s, words)); String s2 = "wordgoodgoodgoodbestword"; String[] words2 = {"word","good","best","word"}; System.out.println(sol.findSubstring(s2, words2)); } }
输出：
[0, 9]
[]
3. 最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
示例 3：
输入：s = "a"
输出："a"
示例 4：
输入：s = "ac"
输出："a"
提示：
1 <= s.length <= 1000
s 仅由数字和英文字母（大写和/或小写）组成
出处：
https://edu.csdn.net/practice/27637465
代码：
import java.util.*; public class longestPalindrome { public static class Solution { public String longestPalindrome(String s) { int ti = 0, maxlen = 0, i, t; for (i = 0; i < s.length(); i++) { t = 1; while (t <= i && i + t < s.length()) { if (s.charAt(i + t) == s.charAt(i - t)) t++; else break; } t--; if (2 * t + 1 > maxlen) { ti = i - t; maxlen = 2 * t + 1; } } for (i = 0; i < s.length(); i++) { t = 1; while (t <= i + 1 && i + t < s.length()) { if (s.charAt(i - t + 1) == s.charAt(i + t)) t++; else break; } t--; if (2 * t > maxlen) { ti = i - t + 1; maxlen = 2 * t; } } return s.substring(ti, ti + maxlen); } } public static void main(String[] args) { Solution sol = new Solution(); String s = "babad"; System.out.println(sol.longestPalindrome(s)); String s2 = "cbbd"; System.out.println(sol.longestPalindrome(s2)); } }
输出：
bab
bb
