LeetCode热门100题算法和思路（day9）
LeetCode347 前K个高频元素
题目详情
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
提示：
1 <= nums.length <= 105
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的
进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。
代码
public class LeetCode347 {
public static void main(String[] args) {
System.out.println(Arrays.toString(new Solution().topKFrequent(new int[]{1, 1, 1, 2, 2, 3}, 2)));
System.out.println(Arrays.toString(new Solution2().topKFrequent(new int[]{1, 1, 1, 2, 2, 3}, 2)));
System.out.println(Arrays.toString(new Solution3().topKFrequent(new int[]{1, 1, 1, 2, 2, 3}, 2)));
}
/*
堆
*/
static class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> occurrences = new HashMap<Integer, Integer>();
for (int num : nums) {
occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);
}
// int[] 的第一个元素代表数组的值，第二个元素代表了该值出现的次数
PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
public int compare(int[] m, int[] n) {
return m[1] - n[1];
}
});
for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {
int num = entry.getKey(), count = entry.getValue();
if (queue.size() == k) {
if (queue.peek()[1] < count) {
queue.poll();
queue.offer(new int[]{num, count});
}
} else {
queue.offer(new int[]{num, count});
}
}
int[] ret = new int[k];
for (int i = 0; i < k; ++i) {
ret[i] = queue.poll()[0];
}
return ret;
}
}
static class Solution2 {
public int[] topKFrequent(int[] nums, int k) {
// key: 元素，value: 出现的次数
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
int times = map.getOrDefault(num, 0);
map.put(num, times + 1);
}
// 最大堆
Queue<Integer> pq = new PriorityQueue<>((o1, o2) -> (map.get(o2) - map.get(o1)));
for (int key : map.keySet()) {
pq.add(key);
}
int[] ans = new int[k];
int index = 0;
while (index < k) {
ans[index++] = pq.poll();
}
return ans;
}
}
/*
基于快速排序
*/
static class Solution3 {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> occurrences = new HashMap<Integer, Integer>();
for (int num : nums) {
occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);
}
List<int[]> values = new ArrayList<int[]>();
for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {
int num = entry.getKey(), count = entry.getValue();
values.add(new int[]{num, count});
}
int[] ret = new int[k];
qsort(values, 0, values.size() - 1, ret, 0, k);
return ret;
}
public void qsort(List<int[]> values, int start, int end, int[] ret, int retIndex, int k) {
int picked = (int) (Math.random() * (end - start + 1)) + start;
Collections.swap(values, picked, start);
int pivot = values.get(start)[1];
int index = start;
for (int i = start + 1; i <= end; i++) {
if (values.get(i)[1] >= pivot) {
Collections.swap(values, index + 1, i);
index++;
}
}
Collections.swap(values, start, index);
if (k <= index - start) {
qsort(values, start, index - 1, ret, retIndex, k);
} else {
for (int i = start; i <= index; i++) {
ret[retIndex++] = values.get(i)[0];
}
if (k > index - start + 1) {
qsort(values, index + 1, end, ret, retIndex, k - (index - start + 1));
}
}
}
}
}
LeetCode394 字符串解码
题目详情
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
示例 1：
输入：s = "3[a]2[bc]"
输出："aaabcbc"
示例 2：
输入：s = "3[a2[c]]"
输出："accaccacc"
示例 3：
输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"
示例 4：
输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"
提示：
1 <= s.length <= 30
s 由小写英文字母、数字和方括号 '[]' 组成
s 保证是一个 有效 的输入。
s 中所有整数的取值范围为 [1, 300]
代码
public class LeetCode394 {
public static void main(String[] args) {
System.out.println(new Solution().decodeString("2[abc]3[cd]ef"));
System.out.println(new Solution2().decodeString("2[abc]3[cd]ef"));
}
/*
栈操作
*/
static class Solution {
int ptr;
public String decodeString(String s) {
LinkedList<String> stk = new LinkedList<String>();
ptr = 0;
while (ptr < s.length()) {
char cur = s.charAt(ptr);
if (Character.isDigit(cur)) {
// 获取一个数字并进栈
String digits = getDigits(s);
stk.addLast(digits);
} else if (Character.isLetter(cur) || cur == '[') {
// 获取一个字母并进栈
stk.addLast(String.valueOf(s.charAt(ptr++)));
} else {
++ptr;
LinkedList<String> sub = new LinkedList<String>();
while (!"[".equals(stk.peekLast())) {
sub.addLast(stk.removeLast());
}
Collections.reverse(sub);
// 左括号出栈
stk.removeLast();
// 此时栈顶为当前 sub 对应的字符串应该出现的次数
int repTime = Integer.parseInt(stk.removeLast());
StringBuffer t = new StringBuffer();
String o = getString(sub);
// 构造字符串
while (repTime-- > 0) {
t.append(o);
}
// 将构造好的字符串入栈
stk.addLast(t.toString());
}
}
return getString(stk);
}
public String getDigits(String s) {
StringBuffer ret = new StringBuffer();
while (Character.isDigit(s.charAt(ptr))) {
ret.append(s.charAt(ptr++));
}
return ret.toString();
}
public String getString(LinkedList<String> v) {
StringBuffer ret = new StringBuffer();
for (String s : v) {
ret.append(s);
}
return ret.toString();
}
}
/*
递归
*/
static class Solution2 {
String src;
int ptr;
public String decodeString(String s) {
src = s;
ptr = 0;
return getString();
}
public String getString() {
if (ptr == src.length() || src.charAt(ptr) == ']') {
// String -> EPS
return "";
}
char cur = src.charAt(ptr);
int repTime = 1;
String ret = "";
if (Character.isDigit(cur)) {
// String -> Digits [ String ] String
// 解析 Digits
repTime = getDigits();
// 过滤左括号
++ptr;
// 解析 String
String str = getString();
// 过滤右括号
++ptr;
// 构造字符串
while (repTime-- > 0) {
ret += str;
}
} else if (Character.isLetter(cur)) {
// String -> Char String
// 解析 Char
ret = String.valueOf(src.charAt(ptr++));
}
return ret + getString();
}
public int getDigits() {
int ret = 0;
while (ptr < src.length() && Character.isDigit(src.charAt(ptr))) {
ret = ret * 10 + src.charAt(ptr++) - '0';
}
return ret;
}
}
}
LeetCode399 除法求值
题目详情
给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。
另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。
返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。
注意：输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。
示例 1：
输入：equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
输出：[6.00000,0.50000,-1.00000,1.00000,-1.00000]
解释：
条件：a / b = 2.0, b / c = 3.0
问题：a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
结果：[6.0, 0.5, -1.0, 1.0, -1.0 ]
示例 2：
输入：equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
输出：[3.75000,0.40000,5.00000,0.20000]
示例 3：
输入：equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
输出：[0.50000,2.00000,-1.00000,-1.00000]
提示：
1 <= equations.length <= 20
equations[i].length == 2
1 <= Ai.length, Bi.length <= 5
values.length == equations.length
0.0 < values[i] <= 20.0
1 <= queries.length <= 20
queries[i].length == 2
1 <= Cj.length, Dj.length <= 5
Ai, Bi, Cj, Dj 由小写英文字母与数字组成
代码
public class LeetCode399 {
public static void main(String[] args) {
System.out.println(Arrays.toString(new Solution().calcEquation(
new LinkedList<List<String>>() {{
add(new LinkedList<String>() {{
add("a");
add("b");
}});
add(new LinkedList<String>() {{
add("b");
add("c");
}});
}}, new double[]{2.0,3.0},
new LinkedList<List<String>>() {{
add(new LinkedList<String>() {{
add("a");
add("c");
}});
add(new LinkedList<String>() {{
add("b");
add("a");
}});
add(new LinkedList<String>() {{
add("a");
add("e");
}});
add(new LinkedList<String>() {{
add("a");
add("a");
}});
add(new LinkedList<String>() {{
add("x");
add("x");
}});
}}
)));
}
/*
并查集
*/
static class Solution {
public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
int equationsSize = equations.size();
UnionFind unionFind = new UnionFind(2 * equationsSize);
// 第 1 步：预处理，将变量的值与 id 进行映射，使得并查集的底层使用数组实现，方便编码
Map<String, Integer> hashMap = new HashMap<>(2 * equationsSize);
int id = 0;
for (int i = 0; i < equationsSize; i++) {
List<String> equation = equations.get(i);
String var1 = equation.get(0);
String var2 = equation.get(1);
if (!hashMap.containsKey(var1)) {
hashMap.put(var1, id);
id++;
}
if (!hashMap.containsKey(var2)) {
hashMap.put(var2, id);
id++;
}
unionFind.union(hashMap.get(var1), hashMap.get(var2), values[i]);
}
// 第 2 步：做查询
int queriesSize = queries.size();
double[] res = new double[queriesSize];
for (int i = 0; i < queriesSize; i++) {
String var1 = queries.get(i).get(0);
String var2 = queries.get(i).get(1);
Integer id1 = hashMap.get(var1);
Integer id2 = hashMap.get(var2);
if (id1 == null || id2 == null) {
res[i] = -1.0d;
} else {
res[i] = unionFind.isConnected(id1, id2);
}
}
return res;
}
private class UnionFind {
private int[] parent;
/**
* 指向的父结点的权值
*/
private double[] weight;
public UnionFind(int n) {
this.parent = new int[n];
this.weight = new double[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
weight[i] = 1.0d;
}
}
public void union(int x, int y, double value) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) {
return;
}
parent[rootX] = rootY;
// 关系式的推导请见「参考代码」下方的示意图
weight[rootX] = weight[y] * value / weight[x];
}
/**
* 路径压缩
*
* @param x
* @return 根结点的 id
*/
public int find(int x) {
if (x != parent[x]) {
int origin = parent[x];
parent[x] = find(parent[x]);
weight[x] *= weight[origin];
}
return parent[x];
}
public double isConnected(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) {
return weight[x] / weight[y];
} else {
return -1.0d;
}
}
}
}
}
LeetCode406 根据身高重建队列
题目详情
假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。
请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。
示例 1：
输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解释：
编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。
示例 2：
输入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
输出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]
提示：
1 <= people.length <= 2000
0 <= hi <= 106
0 <= ki < people.length
题目数据确保队列可以被重建
代码
public class LeetCode406 {
public static void main(String[] args) {
System.out.println(Arrays.deepToString(new Solution().reconstructQueue(new int[][]{{7, 0}, {4, 4}, {7, 1}, {5, 0}, {6, 1}, {5, 2}})));
System.out.println(Arrays.deepToString(new Solution2().reconstructQueue(new int[][]{{7, 0}, {4, 4}, {7, 1}, {5, 0}, {6, 1}, {5, 2}})));
}
/*
从低到高考虑
*/
static class Solution {
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people, new Comparator<int[]>() {
public int compare(int[] person1, int[] person2) {
if (person1[0] != person2[0]) {
return person1[0] - person2[0];
} else {
return person2[1] - person1[1];
}
}
});
int n = people.length;
int[][] ans = new int[n][];
for (int[] person : people) {
int spaces = person[1] + 1;
for (int i = 0; i < n; ++i) {
if (ans[i] == null) {
--spaces;
if (spaces == 0) {
ans[i] = person;
break;
}
}
}
}
return ans;
}
}
/*
从高到低考虑
*/
static class Solution2 {
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people, new Comparator<int[]>() {
public int compare(int[] person1, int[] person2) {
if (person1[0] != person2[0]) {
return person2[0] - person1[0];
} else {
return person1[1] - person2[1];
}
}
});
List<int[]> ans = new ArrayList<int[]>();
for (int[] person : people) {
ans.add(person[1], person);
}
return ans.toArray(new int[ans.size()][]);
}
}
}
LeetCode416 分割等和子集
题目详情
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。
提示：
1 <= nums.length <= 200
1 <= nums[i] <= 100
代码
class LeetCode416 {
public static void main(String[] args) {
System.out.println(new Solution().canPartition(new int[]{1, 5, 11, 5}));
}
/*
关于 0-1 背包问题的介绍，大家可以在互联网上搜索《背包九讲》进行相关知识的学习。本题解有些地方使用了 0-1 背包问题的描述，因此会不加解释的使用“背包”、“容量”这样的名词。
本题解按照动态规划的一般思考方向进行讲解（仅供参考，本人水平有限，大概觉得是这几个方面），它们是：
1、状态定义；
2、状态转移方程；
3、初始化；
4、输出；
5、思考状态压缩。
这 5 个部分是本题解的结构。其它类似的动态规划问题也可以按照这样的方向去思考、解释和理解。
事实上，这是一个典型的“动态规划”问题，并且它的“原形”是“0-1 背包问题”。使用“动态规划”解决问题的思路是“以空间换时间”，“规划”这个词在英文中就是“填表格”的意思，代码执行的过程，也可以称之为“填表格”。
“动态规划”的方法可以认为是为我们提供了一个思考问题的方向，我们不是直接面对问题求解，而是去找原始问题（或者说和原始问题相关的问题）的最开始的样子，通过“状态转移方程”（这里没法再解释了，可以结合下文理解）记录下每一步求解的结果，直到最终问题解决。
而直接面对问题求解，就是我们熟悉的“递归”方法，由于有大量重复子问题，我们就需要加缓存，这叫“记忆化递归”，这里就不给参考代码了，感兴趣的朋友可以自己写一下，比较一下它们两种思考方式的不同之处和优缺点。
做这道题需要做这样一个等价转换：是否可以从这个数组中挑选出一些正整数，使得这些数的和等于整个数组元素的和的一半。前提条件是：数组的和一定得是偶数，即数组的和一定得被 22 整除，这一点是特判。
*/
static class Solution {
public boolean canPartition(int[] nums) {
int len = nums.length;
if (len == 0) {
return false;
}
int sum = 0;
for (int num : nums) {
sum += num;
}
// 特判：如果是奇数，就不符合要求
if ((sum & 1) == 1) {
return false;
}
int target = sum / 2;
// 创建二维状态数组，行：物品索引，列：容量（包括 0）
boolean[][] dp = new boolean[len][target + 1];
// 先填表格第 0 行，第 1 个数只能让容积为它自己的背包恰好装满
if (nums[0] <= target) {
dp[0][nums[0]] = true;
}
// 再填表格后面几行
for (int i = 1; i < len; i++) {
for (int j = 0; j <= target; j++) {
// 直接从上一行先把结果抄下来，然后再修正
dp[i][j] = dp[i - 1][j];
if (nums[i] == j) {
dp[i][j] = true;
continue;
}
if (nums[i] < j) {
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
}
}
}
return dp[len - 1][target];
}
}
}
LeetCode437 路径总和-三
题目详情
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
示例 1：
输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。
示例 2：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3
提示:
二叉树的节点个数的范围是 [0,1000]
-109 <= Node.val <= 109
-1000 <= targetSum <= 1000
代码
public class LeetCode437 {
public static void main(String[] args) {
System.out.println(new Solution().pathSum(TreeNode.buildBinaryTree(new Integer[]{10, 5, -3, 3, 2, null, 11, 3, -2, null, 1}), 8));
System.out.println(new Solution2().pathSum(TreeNode.buildBinaryTree(new Integer[]{10, 5, -3, 3, 2, null, 11, 3, -2, null, 1}), 8));
}
static class Solution {
public int pathSum(TreeNode root, int sum) {
return pathSum(root, sum, new int[1000], 0);
}
public int pathSum(TreeNode root, int sum, int[] array/*保存路径*/, int p/*指向路径终点*/) {
if (root == null) {
return 0;
}
int tmp = root.val;
int n = root.val == sum ? 1 : 0;
for (int i = p - 1; i >= 0; i--) {
tmp += array[i];
if (tmp == sum) {
n++;
}
}
array[p] = root.val;
int n1 = pathSum(root.left, sum, array, p + 1);
int n2 = pathSum(root.right, sum, array, p + 1);
return n + n1 + n2;
}
}
static class Solution2 {
/*
* 求以 root 为根的二叉树，所有和为 sum 的路径；
* 路径的开头不一定是 root，结尾也不一定是叶子节点；
*
* @param root
* @param sum
* @return
*/
public int pathSum(TreeNode root, int sum) {
if (root == null) {
return 0;
}
return paths(root, sum)
+ pathSum(root.left, sum)
+ pathSum(root.right, sum);
}
private int paths(TreeNode root, int sum) {
if (root == null) {
return 0;
}
int res = 0;
if (root.val == sum) {
res += 1;
}
res += paths(root.left, sum - root.val);
res += paths(root.right, sum - root.val);
return res;
}
}
}
LeetCode438 找到字符串中所有字母异位词
题目详情
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
示例 1:
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
示例 2:
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
提示:
1 <= s.length, p.length <= 3 * 104
s 和 p 仅包含小写字母
代码
public class LeetCode438 {
public static void main(String[] args) {
System.out.println(new Solution().findAnagrams("cbaebabacd", "abc"));
}
/*
滑动窗口
*/
static class Solution {
public List<Integer> findAnagrams(String s, String p) {
// 用于返回字母异位词的起始索引
List<Integer> res = new ArrayList<>();
// 用 map 存储目标值中各个单词出现的次数
HashMap<Character, Integer> map = new HashMap<>();
for (Character c : p.toCharArray()) map.put(c, map.getOrDefault(c, 0) + 1);
// 用另外一个 map 存储滑动窗口中有效字符出现的次数
HashMap<Character, Integer> window = new HashMap<>();
int left = 0; // 左指针
int right = 0; // 右指针
int valid = p.length(); // 只有当 valid == 0 时，才说明 window 中包含了目标子串
while (right < s.length()) {
// 如果目标子串中包含了该字符，才存入 window 中
if (map.containsKey(s.charAt(right))) {
window.put(s.charAt(right), window.getOrDefault(s.charAt(right), 0) + 1);
// 只有当 window 中该有效字符数量不大于map中该字符数量，才能算一次有效包含
if (window.get(s.charAt(right)) <= map.get(s.charAt(right))) {
valid--;
}
}
// 如果 window 符合要求，即两个 map 存储的有效字符相同，就可以移动左指针了
// 但是只有二个map存储的数据完全相同，才可以记录当前的起始索引，也就是left指针所在位置
while (valid == 0) {
if (right - left + 1 == p.length()) res.add(left);
// 如果左指针指的是有效字符,需要更改 window 中的 key 对应的 value
// 如果 有效字符对应的数量比目标子串少，说明无法匹配了
if (map.containsKey(s.charAt(left))) {
window.put(s.charAt(left), window.get(s.charAt(left)) - 1);
if (window.get(s.charAt(left)) < map.get(s.charAt(left))) {
valid++;
}
}
left++;
}
right++;
}
return res;
}
}
}
LeetCode448 找到所有数组中消失的数字
题目详情
给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。
示例 1：
输入：nums = [4,3,2,7,8,2,3,1]
输出：[5,6]
示例 2：
输入：nums = [1,1]
输出：[2]
提示：
n == nums.length
1 <= n <= 105
1 <= nums[i] <= n
进阶：你能在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。
代码
public class LeetCode448 {
public static void main(String[] args) {
System.out.println(new Solution().findDisappearedNumbers(new int[]{4, 3, 2, 7, 8, 2, 3, 1}));
System.out.println(new Solution2().findDisappearedNumbers(new int[]{4, 3, 2, 7, 8, 2, 3, 1}));
System.out.println(new Solution3().findDisappearedNumbers(new int[]{4, 3, 2, 7, 8, 2, 3, 1}));
}
static class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
HashMap<Integer, Boolean> hashTable = new HashMap<Integer, Boolean>();
for (int i = 0; i < nums.length; i++) {
hashTable.put(nums[i], true);
}
List<Integer> result = new LinkedList<Integer>();
for (int i = 1; i <= nums.length; i++) {
if (!hashTable.containsKey(i)) {
result.add(i);
}
}
return result;
}
}
static class Solution2 {
public List<Integer> findDisappearedNumbers(int[] nums) {
// 遍历原始数组中的每个元素
for (int i = 0; i < nums.length; i++) {
// 将值视为新索引
int newIndex = Math.abs(nums[i]) - 1;
// 检查这个新索引处值的大小如果大小为正，则将其设为负，从而表明数字 nums[i] 已出现或已被访问。
if (nums[newIndex] > 0) {
nums[newIndex] *= -1;
}
}
// 包含缺失数字的响应数组
List<Integer> result = new LinkedList<Integer>();
// 遍历从 1 到 N 的数字，并将所有具有正大小的数字添加到数组中
for (int i = 1; i <= nums.length; i++) {
if (nums[i - 1] > 0) {
result.add(i);
}
}
return result;
}
}
/*
原地修改
*/
static class Solution3 {
public List<Integer> findDisappearedNumbers(int[] nums) {
int n = nums.length;
for (int num : nums) {
int x = (num - 1) % n;
nums[x] += n;
}
List<Integer> ret = new ArrayList<Integer>();
for (int i = 0; i < n; i++) {
if (nums[i] <= n) {
ret.add(i + 1);
}
}
return ret;
}
}
}
LeetCode461 汉明距离
题目详情
两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。
给你两个整数 x 和 y，计算并返回它们之间的汉明距离。
示例 1：
输入：x = 1, y = 4
输出：2
解释：
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
上面的箭头指出了对应二进制位不同的位置。
示例 2：
输入：x = 3, y = 1
输出：1
提示：
0 <= x, y <= 231 - 1
代码
public class LeetCode461 {
public static void main(String[] args) {
System.out.print(new Solution().hammingDistance(1, 4));
}
static class Solution {
public int hammingDistance(int x, int y) {
int i = x ^ y;
int count = 0;
while (i != 0) {
if ((i & 1) == 1) {
count++;
}
i = i >> 1;
}
return count;
}
}
}
LeetCode494 目标和
题目详情
给你一个整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
示例 1：
输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
示例 2：
输入：nums = [1], target = 1
输出：1
提示：
1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000
代码
public class LeetCode494 {
public static void main(String[] args) {
System.out.println(new Solution().findTargetSumWays(new int[]{1, 1, 1, 1, 1}, 3));
System.out.println(new Solution2().findTargetSumWays(new int[]{1, 1, 1, 1, 1}, 3));
System.out.println(new Solution3().findTargetSumWays(new int[]{1, 1, 1, 1, 1}, 3));
}
/*
回溯
*/
static class Solution {
int count = 0;
public int findTargetSumWays(int[] nums, int target) {
backtrack(nums, target, 0, 0);
return count;
}
public void backtrack(int[] nums, int target, int index, int sum) {
if (index == nums.length) {
if (sum == target) {
count++;
}
} else {
backtrack(nums, target, index + 1, sum + nums[index]);
backtrack(nums, target, index + 1, sum - nums[index]);
}
}
}
/*
动态规划
*/
static class Solution2 {
public int findTargetSumWays(int[] nums, int target) {
int sum = 0;
for (int num : nums) {
sum += num;
}
int diff = sum - target;
if (diff < 0 || diff % 2 != 0) {
return 0;
}
int n = nums.length, neg = diff / 2;
int[][] dp = new int[n + 1][neg + 1];
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
int num = nums[i - 1];
for (int j = 0; j <= neg; j++) {
dp[i][j] = dp[i - 1][j];
if (j >= num) {
dp[i][j] += dp[i - 1][j - num];
}
}
}
return dp[n][neg];
}
}
/*
动态规划-优化
*/
static class Solution3 {
public int findTargetSumWays(int[] nums, int target) {
int sum = 0;
for (int num : nums) {
sum += num;
}
int diff = sum - target;
if (diff < 0 || diff % 2 != 0) {
return 0;
}
int neg = diff / 2;
int[] dp = new int[neg + 1];
dp[0] = 1;
for (int num : nums) {
for (int j = neg; j >= num; j--) {
dp[j] += dp[j - num];
}
}
return dp[neg];
}
}
}
