目录
第一题
题目来源
题目内容
解决方法
方法一：二分+贪心
根据题目描述，我们可以使用二分查找和贪心思路来解决这个问题。
首先，我们定义一个函数check用于判断给定的窃取能力是否满足条件。在该函数中，我们使用贪心策略。我们遍历房屋金额数组nums，对于每个房屋，如果其金额小于等于给定的窃取能力，我们将计数器count加1，并且跳过下一个房屋（因为相邻房屋不能被同时窃取）。最后，如果count大于等于k，说明当前的窃取能力满足条件，返回true；否则，返回false。
接下来，我们要找到满足条件的最小窃取能力。我们可以进行二分查找。我们初始化左边界left为0，右边界right为数组中的最大值。然后，我们不断进行二分查找，直到left和right相邻为止。在每次查找中，我们计算中间值mid，并调用check函数来判断给定的窃取能力是否满足条件。如果满足条件，说明我们可以尝试更小的窃取能力，所以我们将right更新为mid；否则，说明窃取能力太小，我们需要尝试更大的值，所以我们将left更新为mid。最后，返回right作为结果。
public class Solution {
public int minCapability(int[] nums, int k) {
int left = 0, right = 0;
for (int x : nums) {
right = Math.max(right, x);
}
while (left + 1 < right) {
int mid = (left + right) >>> 1;
if (check(nums, k, mid)) {
right = mid;
} else {
left = mid;
}
}
return right;
}
private boolean check(int[] nums, int k, int mx) {
int count = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] <= mx) {
count++;
i++;
}
}
return count >= k;
}
}
复杂度分析：
- 时间复杂度：二分查找的时间复杂度是O(log m)，其中m为最大的房屋金额。在每次二分查找中，我们需要遍历房屋金额数组nums计算满足条件的房屋数量，时间复杂度是O(n)，其中n为房屋的数量。因此，总时间复杂度是O(n log m)。
- 空间复杂度：我们只需要常数级别的额外空间存储一些变量。因此，总空间复杂度是O(1)。
LeetCode运行结果：
方法二：二分+DP
首先，我们初始化窃取能力的范围，将 left 设置为 0，将 right 设置为 nums 数组中的最大值。
然后，在每次循环中，我们计算 mid 作为窃取能力的候选值，使用二分查找的思想，将窃取能力的范围从 (left, right] 缩小到 (left, mid] 或 (mid, right]。
接着，我们调用 check 方法判断以 mid 作为窃取能力是否满足条件。在 check 方法中，我们使用两个变量 f0 和 f1 来表示前一间房屋被窃取和当前房屋被窃取的情况下，窃贼已窃取的房屋数目。我们遍历给定的 nums 数组，根据房屋的价值和窃取能力来更新 f0 和 f1。如果房屋的价值大于窃取能力，则窃贼必须从前一间房屋开始才能窃取当前房屋，因此更新 f0 为 f1（即当前房屋不被窃取）。如果房屋的价值不大于窃取能力，则窃贼可以选择窃取当前房屋或不窃取，取决于哪种情况下窃贼窃取的房屋数目更多，即选择较大的值更新 f1。最后，我们判断 f1 是否大于等于 k，如果是则返回 true，表示窃取能力满足条件，否则返回 false。
class Solution {
public int minCapability(int[] nums, int k) {
int left = 0, right = 0;
for (int x : nums) {
right = Math.max(right, x);
}
while (left + 1 < right) { // 开区间写法
int mid = (left + right) >>> 1;
if (check(nums, k, mid)) {
right = mid;
} else {
left = mid;
}
}
return right;
}
private boolean check(int[] nums, int k, int mx) {
int f0 = 0, f1 = 0;
for (int x : nums) {
if (x > mx) {
f0 = f1;
} else {
int tmp = f1;
f1 = Math.max(f1, f0 + 1);
f0 = tmp;
}
}
return f1 >= k;
}
}
复杂度分析：
- 时间复杂度：在 minCapability 方法中，我们使用二分查找来确定窃取能力的范围，时间复杂度为 O(log m)，其中 m 是 nums 数组中的最大值。在 check 方法中，我们遍历给定的 nums 数组，时间复杂度为 O(n)，其中 n 是 nums 数组的长度。综合起来，时间复杂度为 O(n log m)。
- 空间复杂度：只使用了常数级别的额外空间来存储变量，因此空间复杂度为 O(1)。
LeetCode运行结果：
第二题
题目来源
题目内容
解决方法
方法一：双指针
这个问题可以使用双指针来解决。首先，对数组进行排序。
然后，我们可以使用三个指针i，left和right来表示三个整数的位置。我们固定指针i，并使用左右指针left和right去寻找与target最接近的和。具体的算法如下：
- 初始化一个变量closestSum来保存与target最接近的和。
- 对数组进行排序。
- 遍历数组，对于每个元素nums[i]，使用左右指针left和right从i+1和数组末尾开始向中间移动。
- 计算当前三个数的和sum = nums[i] + nums[left] + nums[right]。
- 如果sum与target相等，说明找到了与target相等的和，直接返回sum。
- 如果sum与target的差的绝对值小于closestSum与target的差的绝对值，更新closestSum为sum。
- 如果sum大于target，右指针左移一位。
- 如果sum小于target，左指针右移一位。
- 返回closestSum作为结果。
import java.util.Arrays;
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int n = nums.length;
int closestSum = nums[0] + nums[1] + nums[2]; // 初始化closestSum
for (int i = 0; i < n - 2; i++) {
int left = i + 1;
int right = n - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == target) {
return sum;
}
if (Math.abs(sum - target) < Math.abs(closestSum - target)) {
closestSum = sum;
}
if (sum > target) {
right--;
} else {
left++;
}
}
}
return closestSum;
}
}
复杂度分析：
- 该算法的时间复杂度为O(N^2)，其中N为数组的长度。主要是因为需要遍历一次数组，并且在每个位置使用双指针去寻找与target最接近的和，因此时间复杂度为O(N^2)。
- 该算法的空间复杂度为O(1)，因为只需要使用常数个变量来存储结果，不需要额外的空间。
综上所述，该算法的时间复杂度为O(N^2)，空间复杂度为O(1)。
LeetCode运行结果：
方法二：暴力搜索
除了使用双指针的方法外，我们还可以考虑使用暴力搜索的方法来解决这个问题。具体的算法如下：
- 初始化一个变量closestSum来保存与target最接近的和，初始值为一个较大的数。
- 遍历数组，对于每个元素nums[i]，再嵌套两层循环分别遍历剩余的元素nums[j]和nums[k]（j和k不等于i）。
- 计算当前三个数的和sum = nums[i] + nums[j] + nums[k]。
- 如果sum与target相等，说明找到了与target相等的和，直接返回sum。
- 如果sum与target的差的绝对值小于closestSum与target的差的绝对值，更新closestSum为sum。
- 继续遍历，直到数组遍历完毕。
- 返回closestSum作为结果。
class Solution {
public int threeSumClosest(int[] nums, int target) {
int n = nums.length;
int closestSum = Integer.MAX_VALUE; // 初始化closestSum
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
for (int k = j + 1; k < n; k++) {
int sum = nums[i] + nums[j] + nums[k];
if (sum == target) {
return sum;
}
if (Math.abs(sum - target) < Math.abs(closestSum - target)) {
closestSum = sum;
}
}
}
}
return closestSum;
}
}
复杂度分析：
- 时间复杂度为O(N^3)，其中N为数组的长度。因为需要三重循环来搜索所有的可能组合，所以时间复杂度较高。
- 空间复杂度为O(1)，因为只需要使用常数个变量来存储结果，不需要额外的空间。
综上所述，使用暴力搜索的方法的时间复杂度为O(N^3)，空间复杂度为O(1)。如果数组规模较小，这种方法也是可行的。但是当数组规模较大时，双指针的方法效率更高。
LeetCode运行结果：
方法三：排序
除了双指针和暴力搜索的方法，还可以考虑利用排序来优化算法。具体思路如下：
- 对数组进行排序，将数组按非递减顺序排列。
- 初始化一个变量closestSum来保存与target最接近的和，初始值为一个较大的数。
- 遍历排序后的数组，对于每个元素nums[i]，使用双指针的方法在剩余的元素中寻找与target-nums[i]最接近的和。
- 计算当前三个数的和sum = nums[i] + nums[left] + nums[right]。
- 如果sum与target相等，说明找到了与target相等的和，直接返回sum。
- 如果sum与target的差的绝对值小于closestSum与target的差的绝对值，更新closestSum为sum。
- 如果sum比target大，将right指针左移一位；如果sum比target小，将left指针右移一位。
- 继续遍历，直到遍历完成或left和right指针相遇。
- 返回closestSum作为结果。
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums); // 排序数组
int n = nums.length;
int closestSum = nums[0] + nums[1] + nums[2]; // 初始化closestSum
for (int i = 0; i < n - 2; i++) {
int left = i + 1;
int right = n - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == target) {
return sum;
}
if (Math.abs(sum - target) < Math.abs(closestSum - target)) {
closestSum = sum;
}
if (sum > target) {
right--;
} else {
left++;
}
}
}
return closestSum;
}
}
复杂度分析：
- 时间复杂度为O(N^2logN)，其中N为数组的长度。排序需要O(NlogN)的时间复杂度，而遍历数组和双指针操作需要O(N^2)的时间复杂度。
- 空间复杂度为O(1)，只需要使用常数个变量来存储结果，不需要额外的空间。
综上所述，利用排序来优化的方法的时间复杂度为O(N^2logN)，空间复杂度为O(1)。该方法在处理较大规模的问题时效率更高。
LeetCode运行结果：
第三题
题目来源
题目内容
解决方法
方法一：回溯算法
这个问题可以使用回溯算法来解决。回溯算法是一种通过不断尝试所有可能的解决方案来求解问题的方法。
我们可以将数字和字母的映射关系存储在一个哈希表中，然后定义一个递归函数来生成所有可能的字母组合。具体步骤如下：
- 定义一个哈希表，将数字和字母的映射关系存储起来。
- 定义一个结果列表用于存储所有的字母组合。
- 编写一个递归函数，接受两个参数：当前数字索引和当前组合字符串。
- 如果当前数字索引等于输入字符串的长度，说明已经遍历完所有数字，将当前组合字符串加入结果列表。
- 否则，获取当前数字对应的字母集合，遍历字母集合，递归调用函数，将当前字母加到组合字符串的末尾，同时将数字索引加1。
- 调用递归函数，开始生成所有的字母组合。
- 返回结果列表。
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
class Solution {
private Map<Character, String> letters = new HashMap<>();
public List<String> letterCombinations(String digits) {
List<String> combinations = new ArrayList<>();
if (digits == null || digits.length() == 0) {
return combinations;
}
letters.put('2', "abc");
letters.put('3', "def");
letters.put('4', "ghi");
letters.put('5', "jkl");
letters.put('6', "mno");
letters.put('7', "pqrs");
letters.put('8', "tuv");
letters.put('9', "wxyz");
backtrack(combinations, digits, 0, new StringBuilder());
return combinations;
}
private void backtrack(List<String> combinations, String digits, int index, StringBuilder current) {
if (index == digits.length()) {
combinations.add(current.toString());
return;
}
char digit = digits.charAt(index);
String letter = letters.get(digit);
for (int i = 0; i < letter.length(); i++) {
current.append(letter.charAt(i));
backtrack(combinations, digits, index + 1, current);
current.deleteCharAt(current.length() - 1);
}
}
}
复杂度分析：
- 该算法的时间复杂度为O(3^N * 4^M)，其中N是digits字符串中对应3个字母的数字的个数，M是digits字符串中对应4个字母的数字的个数。对于每个数字，最坏情况下需要尝试4个字母。
- 空间复杂度为O(N+M)，存储结果所需的空间和递归调用栈的空间。
因此，使用回溯算法可以解决这个问题，并且时间复杂度和空间复杂度都是较优的。
LeetCode运行结果：
方法二：队列
除了回溯算法之外，还可以使用队列（或者广度优先搜索）来解决这个问题。
我们可以将数字和字母的映射关系存储在一个哈希表中，然后从左到右遍历输入字符串的每个数字。对于每个数字，将其对应的字母集合中的每个字母与之前已经生成的所有组合进行拼接，形成新的组合，并将新的组合加入队列中。重复这个过程直到遍历完所有数字。
具体步骤如下：
- 定义一个哈希表，将数字和字母的映射关系存储起来。
- 定义一个队列，用于存储当前生成的所有组合。
- 如果输入字符串为空，则直接返回空列表。
- 将输入字符串的第一个数字对应的字母集合中的每个字母依次加到队列中作为初始组合。
- 从第二个数字开始遍历输入字符串，每次取出队列中的头部元素（即当前已经生成的组合），将当前数字对应的字母集合中的每个字母与已有组合进行拼接，并将新的组合加入队列。
- 重复步骤5，直到遍历完所有数字。
- 返回队列中的所有组合作为结果列表。
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
class Solution {
private Map<Character, String> letters = new HashMap<>();
public List<String> letterCombinations(String digits) {
List<String> combinations = new ArrayList<>();
if (digits == null || digits.length() == 0) {
return combinations;
}
letters.put('2', "abc");
letters.put('3', "def");
letters.put('4', "ghi");
letters.put('5', "jkl");
letters.put('6', "mno");
letters.put('7', "pqrs");
letters.put('8', "tuv");
letters.put('9', "wxyz");
Queue<String> queue = new LinkedList<>();
queue.offer("");
for (int i = 0; i < digits.length(); i++) {
char digit = digits.charAt(i);
String letter = letters.get(digit);
int size = queue.size();
while (size > 0) {
String curr = queue.poll();
for (int j = 0; j < letter.length(); j++) {
queue.offer(curr + letter.charAt(j));
}
size--;
}
}
while (!queue.isEmpty()) {
combinations.add(queue.poll());
}
return combinations;
}
}
复杂度分析：
- 该算法的时间复杂度为O(3^N * 4^M)，其中N是digits字符串中对应3个字母的数字的个数，M是digits字符串中对应4个字母的数字的个数。对于每个数字，最坏情况下需要尝试4个字母。
- 空间复杂度为O(3^N * 4^M)，存储结果所需的空间。
这种解法相比回溯算法而言，更利于处理大量输入，因为它不需要递归调用，而是使用队列进行遍历和拼接。
LeetCode运行结果：
方法三：递归
除了回溯算法、队列，我们还可以使用递归来解决这个问题。
我们可以将问题划分为子问题，每次递归都处理当前数字对应的字母集合中的一个字母，并将递归结果与其他数字的组合进行拼接，形成最终的结果。具体步骤如下：
- 定义一个哈希表，将数字和字母的映射关系存储起来。
- 定义一个递归函数，参数包括当前数字的索引、输入字符串、当前字母组合和最终结果列表。
- 递归函数的停止条件为当前数字索引等于字符串长度，即已经处理完所有数字。
- 在递归函数中，获取当前数字对应的字母集合。
- 遍历字母集合，对于每个字母，将其与当前字母组合拼接，并调用递归函数处理下一个数字。
- 当递归函数返回时，将当前字母组合添加到最终结果列表中。
- 返回最终结果列表作为结果。
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
class Solution {
private Map<Character, String> letters = new HashMap<>();
public List<String> letterCombinations(String digits) {
List<String> combinations = new ArrayList<>();
if (digits == null || digits.length() == 0) {
return combinations;
}
letters.put('2', "abc");
letters.put('3', "def");
letters.put('4', "ghi");
letters.put('5', "jkl");
letters.put('6', "mno");
letters.put('7', "pqrs");
letters.put('8', "tuv");
letters.put('9', "wxyz");
backtrack(0, digits, new StringBuilder(), combinations);
return combinations;
}
private void backtrack(int index, String digits, StringBuilder current, List<String> combinations) {
if (index == digits.length()) {
combinations.add(current.toString());
return;
}
char digit = digits.charAt(index);
String letter = letters.get(digit);
for (char c : letter.toCharArray()) {
current.append(c);
backtrack(index + 1, digits, current, combinations);
current.deleteCharAt(current.length() - 1);
}
}
}
复杂度分析：
- 该算法的时间复杂度为O(3^N * 4^M)，其中N是digits字符串中对应3个字母的数字的个数，M是digits字符串中对应4个字母的数字的个数。对于每个数字，最坏情况下需要尝试4个字母。
- 空间复杂度为O(N+M)，其中N是digits字符串中对应3个字母的数字的个数，M是digits字符串中对应4个字母的数字的个数。除了存储结果所需的空间，递归调用栈的空间复杂度为O(N+M)。
这种解法利用了递归的思想，将问题划分为子问题，并通过不断拼接字母来构建最终结果。递归方法简洁直观，但在处理大量输入时可能会导致栈溢出。因此，在实际应用中，需要注意输入规模的限制。
LeetCode运行结果：
方法四：迭代
除了前面提到的回溯算法、队列和递归，还可以使用迭代的方法来解决这个问题。
迭代的思路是，从左到右依次处理输入字符串中的每个数字，并利用一个临时列表来保存当前位置之前的所有字母组合。对于每个新的数字，将其对应的字母与临时列表中的每个字母组合进行拼接，形成新的字母组合，并更新临时列表。重复这个过程，直到处理完所有数字，最终得到的临时列表中即为结果。
具体步骤如下：
- 定义一个哈希表，将数字和字母的映射关系存储起来。
- 初始化一个临时列表，将第一个数字对应的字母集合中的每个字母作为初始的字母组合，并加入到临时列表中。
- 从第二个数字开始遍历输入字符串的每个数字。
- 获取当前数字对应的字母集合。
- 遍历字母集合，对于每个字母，将其与临时列表中的每个字母组合拼接，形成新的字母组合，并将其添加到临时列表中。
- 更新临时列表，将其中的元素作为下一轮的参考，供下一个数字使用。
- 最终得到的临时列表即为结果。
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
class Solution {
private Map<Character, String> letters = new HashMap<>();
public List<String> letterCombinations(String digits) {
List<String> combinations = new ArrayList<>();
if (digits == null || digits.length() == 0) {
return combinations;
}
letters.put('2', "abc");
letters.put('3', "def");
letters.put('4', "ghi");
letters.put('5', "jkl");
letters.put('6', "mno");
letters.put('7', "pqrs");
letters.put('8', "tuv");
letters.put('9', "wxyz");
combinations.add("");
for (int i = 0; i < digits.length(); i++) {
String letter = letters.get(digits.charAt(i));
int size = combinations.size();
for (int j = 0; j < size; j++) {
String prev = combinations.remove(0);
for (char c : letter.toCharArray()) {
combinations.add(prev + c);
}
}
}
return combinations;
}
}
复杂度分析：
- 该算法的时间复杂度为O(3^N * 4^M)，其中N是digits字符串中对应3个字母的数字的个数，M是digits字符串中对应4个字母的数字的个数。对于每个数字，最坏情况下需要尝试4个字母。
- 空间复杂度为O(3^N * 4^M)，存储结果所需的空间。
迭代方法是一种非常高效的解法，它避免了递归调用栈的开销，适用于处理大量输入的情况。
LeetCode运行结果：
