1. 组合总和 🌟🌟

2. 缺失的第一个正数 🌟🌟🌟

3. 单词搜索 II 🌟🌟🌟

🌟 每日一练刷题专栏 🌟

Golang每日一练专栏

Python每日一练专栏

C/C++每日一练专栏

Java每日一练专栏

1. 组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

所有数字（包括 target）都是正整数。
解集不能包含重复的组合。

示例 1：

输入：candidates = [2,3,6,7], target = 7,
输出：[[7],[2,2,3]]

示例 2：

输入：candidates = [2,3,5], target = 8,
输出：[[2,2,2,2],[2,3,3],[3,5]]

提示：

1 <= candidates.length <= 30
1 <= candidates[i] <= 200
candidate 中的每个元素都是独一无二的。
1 <= target <= 500

出处：

https://edu.csdn.net/practice/27223965

代码：

import java.util.*;
public class combinationSum {public static class Solution {public List<List<Integer>> combinationSum(int[] candiates, int target) {List<List<Integer>> resultList = new ArrayList<>();List<Integer> result = new ArrayList<>();Arrays.sort(candiates);dfs(candiates, resultList, result, 0, target);return resultList;}private void dfs(int[] candiates, List<List<Integer>> resultList, List<Integer> result, int start, int target) {if (target < 0) {return;} else if (target == 0) {resultList.add(new ArrayList<>(result));} else {for (int i = start; i < candiates.length; i++) {result.add(candiates[i]);dfs(candiates, resultList, result, i, target - candiates[i]);result.remove(result.size() - 1);}}}}public static void main(String[] args) {Solution s = new Solution();int[] candidates = {2, 3, 6, 7};int target = 7;List<List<Integer>> res = s.combinationSum(candidates, target);System.out.println(res.toString());int[] candidates2 = {2, 3, 5};target = 8;res = s.combinationSum(candidates2, target);System.out.println(res.toString());}
}

输出：

[[2, 2, 3], [7]]
[[2, 2, 2, 2], [2, 3, 3], [3, 5]]

2. 缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

进阶：你可以实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案吗？

示例 1：

输入：nums = [1,2,0]
输出：3

示例 2：

输入：nums = [3,4,-1,1]
输出：2

示例 3：

输入：nums = [7,8,9,11,12]
输出：1

提示：

0 <= nums.length <= 300
-2^31 <= nums[i] <= 2^31 - 1

以下程序实现了这一功能，请你填补空白处内容：

```Java
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
int contains = 0;
for (int i = 0; i < n; i++) {
if (nums[i] == 1) {
contains++;
break;
}
}
if (contains == 0) {
return 1;
}
for (int i = 0; i < n; i++) {
_________________;
}
for (int i = 0; i < n; i++) {
int a = Math.abs(nums[i]);
nums[a - 1] = -Math.abs(nums[a - 1]);
}
for (int i = 0; i < n; i++) {
if (nums[i] > 0) {
return i + 1;
}
}
return n + 1;
}
}
```

出处：

https://edu.csdn.net/practice/27223966

代码：

import java.util.*;
public class firstMissingPositive {public static class Solution {public int firstMissingPositive(int[] nums) {int n = nums.length;int contains = 0;for (int i = 0; i < n; i++) {if (nums[i] == 1) {contains++;break;}}if (contains == 0) {return 1;}for (int i = 0; i < n; i++) {if ((nums[i] <= 0) || (nums[i] > n)) {nums[i] = 1;}}for (int i = 0; i < n; i++) {int a = Math.abs(nums[i]);nums[a - 1] = -Math.abs(nums[a - 1]);}for (int i = 0; i < n; i++) {if (nums[i] > 0) {return i + 1;}}return n + 1;}}public static void main(String[] args) {Solution s = new Solution();int[] nums = {1,2,0}; System.out.println(s.firstMissingPositive(nums));int[] nums2 = {3,4,-1,1}; System.out.println(s.firstMissingPositive(nums2));int[] nums3 = {7,8,9,11,12}; System.out.println(s.firstMissingPositive(nums3));}
}

输出：

3
2
1

3. 单词搜索 II

给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words，找出所有同时在二维网格和字典中出现的单词。

单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

示例 1：

输入：board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
输出：["eat","oath"]

示例 2：

输入：board = [["a","b"],["c","d"]], words = ["abcb"]
输出：[]

提示：

m == board.length
n == board[i].length
1 <= m, n <= 12
board[i][j] 是一个小写英文字母
1 <= words.length <= 3 * 104
1 <= words[i].length <= 10
words[i] 由小写英文字母组成
words 中的所有字符串互不相同

出处：

https://edu.csdn.net/practice/27223967

代码：

import java.util.*;
public class findWords {public static class Solution {static int[][] d = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };static Map<String, Boolean> notExistWords = new HashMap<>();public List<String> findWords(char[][] board, String[] words) {List<String> ans = new ArrayList<>();Arrays.sort(words);notExistWords.clear();for (int i = 0; i < words.length; i++) {String word = words[i];if (i > 0 && word.equals(words[i - 1]))continue;boolean notExistFlag = false;for (int j = 1; j < word.length(); j++) {if (notExistWords.containsKey(word.substring(0, j + 1))) {notExistFlag = true;break;}}if (notExistFlag)continue;if (exist(board, word)) {ans.add(word);} else {notExistWords.put(word, false);}}return ans;}public boolean exist(char[][] board, String word) {int m = board.length;if (m == 0)return false;int n = board[0].length;if (n == 0)return false;if (word.equals(""))return true;boolean[][] f = new boolean[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (word.charAt(0) == board[i][j]) {f[i][j] = true;boolean flag = dfs(i, j, 1, board, word, m, n, f);if (flag)return true;f[i][j] = false;}}}return false;}private boolean dfs(int i, int j, int k, char[][] board, String word, int m, int n, boolean[][] f) {if (k == word.length()) {return true;}for (int l = 0; l < 4; l++) {if (i + d[l][0] < m && j + d[l][1] < n && i + d[l][0] >= 0 && j + d[l][1] >= 0&& board[i + d[l][0]][j + d[l][1]] == word.charAt(k) && !f[i + d[l][0]][j + d[l][1]]) {f[i + d[l][0]][j + d[l][1]] = true;boolean flag = dfs(i + d[l][0], j + d[l][1], k + 1, board, word, m, n, f);if (flag)return true;f[i + d[l][0]][j + d[l][1]] = false;}}return false;}}public static void main(String[] args) {Solution s = new Solution();char[][] board1 = {{'o', 'a', 'a', 'n'},{'e', 't', 'a', 'e'},{'i', 'h', 'k', 'r'},{'i', 'f', 'l', 'v'}};String[] words1 = {"oath", "pea", "eat", "rain"};System.out.println(s.findWords(board1, words1));char[][] board2 = {{'a', 'b'}, {'c', 'd'}};String[] words2 = {"abcb"};System.out.println(s.findWords(board2, words2)); }
}

输出：

[eat, oath]
[]