Java知识点
//Arrays.fill()
Arrays.fill(array, content)；
//StringBuilder删除某个位置的字符
sb.deleteCharAt(index)
一 题目列表
其实就是在做深度优先搜索（遍历）遍历保存路径 然后随时检查当前路径是否符合条件 满足就加在结果中
1 组合
39 Combination Sum
40 Combination Sum II
216 Combination Sum III
78 Subsets
90 Subsets II
lt680. Split String
2 排列
46 Permutations
47 Permutations II
lt10 String Permutation II
51 N-Queens
52 N-Queens II
3 记忆化搜索
44 Wildcard Matching
10 Regular Expression Matching
140 Word Break II
二 组合
39. Combination Sum
元素可以重复使用 求和是target组合
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(candidates);
helper(candidates, 0, new ArrayList<Integer>(), result, target);
return result;
}
private void helper(int[] candidates, int index, List<Integer> subset, List<List<Integer>> result, int target){
//深度拷贝
if(target==0)
result.add(new ArrayList<Integer>(subset));
if(index==candidates.length)
return;
for(int i=index; i<candidates.length; i++){
//去重
if(i>0 && candidates[i]==candidates[i-1])
continue;
if(candidates[i]>target)
return;
subset.add(candidates[i]);
//可以重复使用 所以i不更新
helper(candidates, i, subset, result, target-candidates[i]);
subset.remove(subset.size()-1);
}
}
}
40. Combination Sum II
元素不可以重复使用 求和是target组合
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
if(candidates==null || candidates.length==0)
return result;
Arrays.sort(candidates);
helper(candidates, 0, new ArrayList<Integer>(), result, target);
return result;
}
private void helper(int[] candidates, int index, List<Integer> subset, List<List<Integer>> result, int target){
if(target==0)
result.add(new ArrayList<Integer>(subset));
if(index==candidates.length)
return;
for(int i=index; i<candidates.length; i++){
//同层去重 不同层不去重
if(i>index && candidates[i]==candidates[i-1])
continue;
if(target<candidates[i])
return;
subset.add(candidates[i]);
helper(candidates, i+1, subset, result, target-candidates[i]);
subset.remove(subset.size()-1);
}
}
}
216. Combination Sum III
求k个1-9不同的数组合 和是n
class Solution {
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> result = new ArrayList<>();
if(n>45 || k>9 || k<=0)
return result;
helper(1, new ArrayList<Integer>(), result, n, k);
return result;
}
private void helper(int index, List<Integer> subset, List<List<Integer>> result, int target, int k){
if(target==0 && k==0)
result.add(new ArrayList<Integer>(subset));
if(index==10)
return;
for(int i=index; i<=9; i++){
if(target<i)
return;
subset.add(i);
helper(i+1, subset, result, target-i, k-1);
subset.remove(subset.size()-1);
}
}
}
78. Subsets
没有重复
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if(nums==null || nums.length==0)
return result;
helper(nums, 0, new ArrayList<Integer>(), result);
return result;
}
private void helper(int[] nums, int index, ArrayList<Integer> subset, List<List<Integer>> result){
result.add(new ArrayList<>(subset));
if(index>=nums.length)
return;
for(int i=index; i<nums.length; i++){
subset.add(nums[i]);
helper(nums, i+1, subset, result);
subset.remove(subset.size()-1);
}
}
}
90. Subsets II
又重复
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if(nums==null || nums.length==0)
return result;
Arrays.sort(nums);
helper(nums, 0, new ArrayList<Integer>(), result);
return result;
}
private void helper(int[] nums, int index, List<Integer> subset, List<List<Integer>> result){
result.add(new ArrayList<Integer>( subset));
if(index==nums.length)
return;
for(int i=index; i<nums.length; i++){
//同层去重 不同层不去重
if(i>index && nums[i]==nums[i-1])
continue;
subset.add(nums[i]);
helper(nums, i+1, subset, result);
subset.remove(subset.size()-1);
}
}
}
lt680. Split String
Given the string "123"
return [["1","2","3"],["12","3"],["1","23"]]
public class Solution {
/*
* @param : a string to be split
* @return: all possible split string array
*/
public List<List<String>> splitString(String s) {
// write your code here
List<List<String>> result = new ArrayList<>();
if(s==null )
return result;
helper(s, 0, new ArrayList<String>(), result);
return result;
}
private void helper(String s, int index, ArrayList<String> subset, List<List<String>> result){
if(index==s.length()){
result.add(new ArrayList<String>(subset));
return;
}
for(int i=index; i<index+2 && i<s.length(); i++){
subset.add(s.substring(index, i+1));
helper(s, i+1, subset, result);
subset.remove(subset.size()-1);
}
}
}
组合
46. Permutations
无重复元素
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if(nums==null || nums.length==0)
return result;
boolean[] visited = new boolean[nums.length];
helper(nums, visited, new ArrayList<>(), result);
return result;
}
private void helper(int[] nums, boolean[] visited, List<Integer> subset, List<List<Integer>> result){
if(subset.size()==nums.length){
result.add(new ArrayList<Integer>(subset));
return;
}
for(int i=0; i<nums.length; i++){
if(visited[i])
continue;
visited[i]=true;
subset.add(nums[i]);
helper(nums, visited, subset, result);
subset.remove(subset.size()-1);
visited[i]=false;
}
}
}
47. Permutations II
有重复元素
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if(nums==null || nums.length==0)
return result;
Arrays.sort(nums);
boolean[] visited = new boolean[nums.length];
helper(nums, visited, new ArrayList<>(), result);
return result;
}
private void helper(int[] nums, boolean[] visited, List<Integer> subset, List<List<Integer>> result){
if(subset.size()==nums.length){
result.add(new ArrayList<Integer>(subset));
return;
}
for(int i=0; i<nums.length; i++){
if(i>0 && nums[i]==nums[i-1] && !visited[i-1])
continue;
if(visited[i])
continue;
visited[i]=true;
subset.add(nums[i]);
helper(nums, visited, subset, result);
subset.remove(subset.size()-1);
visited[i]=false;
}
}
}
lt10. String Permutation II
public class Solution {
//Given "aabb", return ["aabb", "abab", "baba", "bbaa", "abba", "baab"].
/**
* @param str: A string
* @return: all permutations
*/
public List<String> stringPermutation2(String str) {
public List<String> stringPermutation2(String str) {
// write your code here
List<String> results = new ArrayList<>();
str = sort(str);
boolean[] visited = new boolean[str.length()];
helper(str, visited, new StringBuilder(), results);
return results;
}
private String sort(String str){
char[] chars = str.toCharArray();
Arrays.sort(chars);
return new String(chars);
}
private void helper(String str, boolean[] visited, StringBuilder sb, List<String> results){
if(sb.length()==str.length()){
results.add(new String(sb.toString()));
return;
}
for(int i=0; i<str.length(); i++){
if(visited[i])
continue;
if(i>0 && str.charAt(i)==str.charAt(i-1) && visited[i-1]==false)
continue;
sb.append(str.charAt(i));
visited[i] = true;
helper(str, visited, sb, results);
visited[i] = false;
sb.deleteCharAt(sb.length()-1);
}
}
}
51. N-Queens
返回所有棋盘布局
//先用0 - (n-1)的排列表示一个棋盘布局
//0 - (n-1)的排列 index代表row 值代表col
//优点在于 只用考虑斜线冲突 不会有同行或同列冲突
//相当于在找所有排列 只不过每次添加的时候考察是否存在冲突
//然后把这些排列转成棋盘布局
class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<Integer>> numListLists = new ArrayList<>();
Set<Integer> cols = new HashSet<Integer>();
Set<Integer> left = new HashSet<Integer>();
Set<Integer> right = new HashSet<Integer>();
helper(n, cols, left, right, new ArrayList<Integer>(), numListLists);
return toChessBoards(numListLists, n);
}
private void helper(int n, Set<Integer> cols, Set<Integer> left, Set<Integer> right, List<Integer> list, List<List<Integer>> lists){
if(list.size() == n){
lists.add(new ArrayList<Integer>(list));
return;
}
for(int i=1; i<=n; i++){
if(cols.contains(i))
continue;
if(left.contains(list.size()+i))
continue;
if(right.contains(list.size()-i))
continue;
left.add(list.size()+i);
right.add(list.size()-i);
cols.add(i);
list.add(i);
helper(n, cols, left, right, list, lists);
list.remove(list.size()-1);
left.remove(list.size()+i);
right.remove(list.size()-i);
cols.remove(i);
}
}
private List<List<String>> toChessBoards(List<List<Integer>> numListLists, int n){
List<List<String>> results = new ArrayList<>();
char[] chars = new char[n];
Arrays.fill(chars, '.');
for(List<Integer> numList: numListLists){
List<String> result = new ArrayList<>();
for(Integer col: numList){
chars[col-1] = 'Q';
String temp = new String(chars);
result.add(temp);
chars[col-1] = '.';
}
results.add(result);
}
return results;
}
}
52. N-Queens II
求可能的布局个数
// \冲突 差相等 n*n 可能的值 -(n-1) - (n-1) 所以加n对应到2n长度的d1
// /冲突 和相等 n*n 可能的值 0-2(n-1) 直接对应长度2n的d2
public class Solution {
int count = 0;
public int totalNQueens(int n) {
Set<Integer> cols = new HashSet<Integer>();
Set<Integer> left = new HashSet<Integer>();
Set<Integer> right = new HashSet<Integer>();
helper(n, cols, left, right, new ArrayList<Integer>());
return count;
}
private void helper(int n, Set<Integer> cols, Set<Integer> left, Set<Integer> right, List<Integer> list){
if(list.size() == n){
count++;
}
for(int i=1; i<=n; i++){
if(cols.contains(i) || left.contains(list.size()+i) || right.contains(list.size()-i))
continue;
left.add(list.size()+i);
right.add(list.size()-i);
cols.add(i);
list.add(i);
helper(n, cols, left, right, list);
list.remove(list.size()-1);
left.remove(list.size()+i);
right.remove(list.size()-i);
cols.remove(i);
}
}
}
记忆化搜索
44. Wildcard Matching
(0,0)->(1,1)(1,0)(0,1)
(1,0)->(2,1)(1,1)(2,0)
(0,1)->(1,2)(1,1)(0,2)
可以发现已经有重复 所以使用记忆化搜索避免重复
本质上是在搜索过程中会遇到已访问过的节点
'?' Matches any single character.
'' Matches any sequence of characters (including the empty sequence).
时间复杂度为O(s.length()p.length())
//时间复杂度为O(s.length()*p.length())
class Solution {
public boolean isMatch(String s, String p) {
if (s == null || p == null) {
return false;
}
boolean[][] memo = new boolean[s.length()][p.length()];
boolean[][] visited = new boolean[s.length()][p.length()];
return isMatchHelper(s, 0, p, 0, memo, visited);
}
private boolean isMatchHelper(String s, int sIndex,
String p, int pIndex,
boolean[][] memo,
boolean[][] visited) {
// 如果 p 从pIdex开始是空字符串了，那么 s 也必须从 sIndex 是空才能匹配上
if (pIndex == p.length()) {
return sIndex == s.length();
}
// 如果 s 从 sIndex 是空，那么p 必须全是 *
if (sIndex == s.length()) {
return allStar(p, pIndex);
}
if (visited[sIndex][pIndex]) {
return memo[sIndex][pIndex];
}
char sChar = s.charAt(sIndex);
char pChar = p.charAt(pIndex);
boolean match;
if (pChar == '*') {
match = isMatchHelper(s, sIndex, p, pIndex + 1, memo, visited) ||
isMatchHelper(s, sIndex + 1, p, pIndex, memo, visited);
} else {
match = charMatch(sChar, pChar) &&
isMatchHelper(s, sIndex + 1, p, pIndex + 1, memo, visited);
}
visited[sIndex][pIndex] = true;
memo[sIndex][pIndex] = match;
return match;
}
private boolean charMatch(char sChar, char pChar) {
return (sChar == pChar || pChar == '?');
}
private boolean allStar(String p, int pIndex) {
for (int i = pIndex; i < p.length(); i++) {
if (p.charAt(i) != '*') {
return false;
}
}
return true;
}
}
10. Regular Expression Matching
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
class Solution {
public boolean isMatch(String s, String p) {
boolean[][] visited = new boolean[s.length()][p.length()];
boolean[][] memo = new boolean[s.length()][p.length()];
return helper(s, 0, p, 0, visited, memo);
}
public boolean helper(String s,
int indexS,
String p,
int indexP,
boolean[][] visited,
boolean[][] memo){
if(indexS==s.length()){
return checkEmpty(p, indexP);
}
if(indexP==p.length()){
return indexS==s.length();
}
if(visited[indexS][indexP]){
return memo[indexS][indexP];
}
boolean match = false;
if(indexP<p.length()-1 && p.charAt(indexP+1)=='*'){
match = helper(s, indexS, p, indexP+2, visited, memo) || (helper(s, indexS+1, p, indexP, visited, memo)&&isMatch(s, indexS, p, indexP));
}else{
match = isMatch(s, indexS, p, indexP) && helper(s, indexS+1, p, indexP+1, visited, memo);
}
visited[indexS][indexP] = true;
memo[indexS][indexP] = match;
return match;
}
private boolean checkEmpty(String p, int index){
for(int i=index; i<p.length(); i++){
if(p.charAt(i)!='*'){
if(i==p.length()-1 || p.charAt(i+1)!='*')
return false;
}
}
return true;
}
private boolean isMatch(String s, int indexS, String p, int indexP){
return s.charAt(indexS)==p.charAt(indexP) || p.charAt(indexP)=='.';
}
}
131. Palindrome Partitioning
求把一个字符串切割成所有字串都是回文串的所有方式
Input: "aab"
Output:
[ ["aa","b"], ["a","a","b"] ]
abaxxxx
如果不用memo xxxx重复计算
如果用了memo 在第一次迭代xxxx的结果已经计算出来 下次遇到直接返回结果就可以
Time complexity: O(n(2^n))
For a string with length n, there will be (n - 1) intervals between chars.
For every interval, we can cut it or not cut it, so there will be 2^(n - 1) ways to partition the string.
For every partition way, we need to check if it is palindrome, which is O(n).
So the time complexity is O(n(2^n))
解的个数*构造一个解的时间
class Solution {
public List<List<String>> partition(String s) {
// return withMemo(s);
return withoutMemo(s);
}
public List<List<String>> withMemo(String s) {
List<List<String>> result = new ArrayList<>();
if(s==null || s.length()==0)
return result;
Map<Integer, List<List<String>>> map = new HashMap<>();
return help(s, 0, map);
}
private List<List<String>> help(String s, int index, Map<Integer, List<List<String>>> memo){
if(index==s.length()){
List<List<String>> result = new ArrayList<>();
result.add(new ArrayList<>());
return result;
}
if(memo.containsKey(index)){
return memo.get(index);
}
List<List<String>> results = new ArrayList<>();
for(int i=index; i<s.length(); i++){
String prefix = s.substring(index, i+1);
if(!isPalindrome(prefix)){
continue;
}
List<List<String>> suffixs = help(s, i+1, memo);
for(List<String> list: suffixs){
List<String> result = new ArrayList<>(list);
result.add(0, prefix);
results.add(result);
}
}
memo.put(index, results);
return results;
}
public List<List<String>> withoutMemo(String s) {
List<List<String>> result = new ArrayList<>();
if(s==null || s.length()==0)
return result;
helper(s, 0, new ArrayList<String>(), result);
return result;
}
private void helper(String s, int index, List<String> subset, List<List<String>> result){
if(index==s.length()){
result.add(new ArrayList<String>(subset));
return;
}
for(int i=index; i<s.length(); i++){
String temp = s.substring(index, i+1);
if(!isPalindrome(temp)){
continue;
}
subset.add(temp);
helper(s, i+1, subset, result);
subset.remove(subset.size()-1);
}
}
private boolean isPalindrome(String s){
int left = 0;
int right = s.length()-1;
while(left<right){
if(s.charAt(left)!=s.charAt(right))
return false;
left++;
right--;
}
return true;
}
}
140. Word Break II
最坏情况 所有拆法都符合要求 一共2^(n-1)种拆法 所以最坏时间复杂度O(2^n)
记忆化的优点在于
"aaaaab", with wordDict = ["a", "aa", "aaa", "aaaa", "aaaaa", "aaaaa"],
map中 key
在第一次迭代之后 aaab的分割方案已经求过 在第二次迭代可以使用结果
class Solution {
public List<String> wordBreak(String s, List<String> wordDict) {
List<String> result = new ArrayList<>();
if(s==null || wordDict==null)
return result;
//key是string value是所有这个string能够被拆分成的词组组合list
Map<String, List<String>> memo = new HashMap<>();
return helper(s, wordDict, memo);
}
private List<String> helper(String s, List<String> wordDict, Map<String, List<String>> memo){
if(memo.containsKey(s))
return memo.get(s);
List<String> result = new ArrayList<>();
if(s.length()==0)
return result;
if(wordDict.contains(s))
result.add(s);
for (int len = 1; len < s.length(); ++len){
String word = s.substring(0, len);
if (!wordDict.contains(word)) {
continue;
}
String suffix = s.substring(len);
List<String> segmentations = helper(suffix, wordDict, memo);
for (String segmentation: segmentations){
result.add(word + " " + segmentation);
}
}
memo.put(s, result);
return result;
}
}
139. Word Break
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> set = new HashSet<>();
for(String string : wordDict)
set.add(string);
return bfsMethod(s, set);
// return dfsMethod(s, set);
}
public boolean dfsMethod(String s, Set<String> dict) {
// DFS
Set<Integer> set = new HashSet<Integer>();
return dfs(s, 0, dict, set);
}
private boolean dfs(String s, int index, Set<String> dict, Set<Integer> set){
// base case
if(index == s.length()) return true;
// check memory
//原理是如果曾经访问过 这里再次访问 说明后面的结果肯定是false
if(set.contains(index)) return false;
// recursion
for(int i = index+1;i <= s.length();i++){
String t = s.substring(index, i);
if(dict.contains(t))
if(dfs(s, i, dict, set))
return true;
else
set.add(i);
}
set.add(index);
return false;
}
public boolean bfsMethod(String s, Set<String> dict) {
if (dict.contains(s)) return true;
Queue<Integer> queue = new LinkedList<Integer>();
queue.offer(0);
// use a set to record checked index to avoid repeated work.
// This is the key to reduce the running time to O(N^2).
Set<Integer> visited = new HashSet<Integer>();
visited.add(0);
while (!queue.isEmpty()) {
int curIdx = queue.poll();
for (int i = curIdx+1; i <= s.length(); i++) {
if (visited.contains(i))
continue;
if (dict.contains(s.substring(curIdx, i))) {
if (i == s.length())
return true;
queue.offer(i);
visited.add(i);
}
}
}
return false;
}
}
网友评论