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]
[]
