13. 机器人运动的范围
地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
示例 1：
输入：m = 2, n = 3, k = 1
输出：3
注意这里求的是机器人走的范围，而不是路径，所以每走一个新的格都要加1
boolean[][] vis;
int m , n , k;
int max = 1;
public int movingCount(int m, int n, int k) {
vis = new boolean[m][n];
this.m = m;
this.n = n;
this.k = k;
dfs(0,0);
return max;
}
int[][] next = {{0,1},{0,-1},{1,0},{-1,0}};
public void dfs(int x, int y){
vis[x][y] = true;
for(int i=0;i<4;i++){
int xx = x + next[i][0];
int yy = y + next[i][1];
int x_1 = xx / 10;
int x_0 = xx % 10;
int y_1 = yy / 10;
int y_0 = yy % 10;
if(xx < 0 || xx >=m || yy < 0 || yy >= n ||
x_0 + x_1 + y_0 + y_1 > k){
continue;
}
if(!vis[xx][yy]){
dfs(xx,yy);
max++;
}
}
}
从（0，0） 统计所有访问的点，可以同时进行dfs两个方向，避免已经访问过的点，从上向下进行dfs
boolean[][] vis;
int m , n , k;
// 这道题可以简化为，调用dfs,同时想两个方向进行dfs i+1, j+1
public int movingCount(int m, int n, int k) {
vis = new boolean[m][n];
this.m = m;
this.n = n;
this.k = k;
return dfs(0,0,0,0);
}
public int dfs(int x, int y, int s1, int s2){
if(x >=m || y >= n || s1 + s2 > k || vis[x][y]){
return 0;
}
vis[x][y] = true;
return 1 + dfs(x+1,y, (x+1) % 10 + (x + 1)/10, s2) + dfs(x,y+1,s1, (y+1)/10 + (y+1)%10);
}
79.单词搜索
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
给定 word = "ABCCED", 返回 true
// 采用回溯，
boolean[][] vis;
int m,n;
char[][] board;
public boolean exist(char[][] board, String word) {
this.m = board.length;
this.n = board[0].length;
this.board = board;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(board[i][j] == word.charAt(0)){
vis = new boolean[m][n];
vis[i][j] = true;
boolean flag = dfs(word,i,j,1);
if(flag){
return true;
}
}
}
}
return false;
}
int[][] next = {{0,1},{0,-1},{-1,0},{1,0}};
public boolean dfs(String word,int x, int y, int k){
if(k >= word.length()){
return true;
}
for(int i=0;i<4;i++){
int xx = x + next[i][0];
int yy = y + next[i][1];
if(xx < 0 || xx >= m || yy < 0 || yy >= n || vis[xx][yy] || word.charAt(k)
!= board[xx][yy]){
continue;
}
vis[xx][yy] = true;
boolean flag = dfs(word,xx,yy,k+1);
if(flag){
return true;
}
//这里必须回溯，实质上还是走路径的问题
vis[xx][yy] = false;
}
return false;
}
38. 分割回文串
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例:
输入: "aab"
输出:
[
["aa","b"],
["a","a","b"]
]
// 采用回溯， s.substring(i) s.substring(i,len)， 如果分割的两个正好都是回文添加结果集，否则递归
public List<List<String>> partition(String s) {
List<List<String>> res = new ArrayList<>();
if(s == null || s.length() == 0){
return res;
}
backTrack(0,s,new LinkedList<String>(),res);
return res;
}
public void backTrack(int j,String s,LinkedList<String> list,List<List<String>> res){
if(j == s.length()){
res.add(new ArrayList<>(list));
return;
}
for(int i=j;i<s.length();i++){
String first = s.substring(j,i+1);
if(check(first)){
list.offer(first);
backTrack(i+1,s,list,res);
list.removeLast();
}
}
}
public boolean check(String str){
int i,j;
for(i=0,j=str.length()-1;i<j;i++,j--){
if(str.charAt(i)!=str.charAt(j)){
return false;
}
}
return true;
}
47. 全排列2
给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例:
输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
数组中有相同的数，可以使用canSwap 进行判断是否相同
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
if(nums == null || nums.length == 0){
return res;
}
permutition(nums,0);
return res;
}
public void permutition(int[] nums, int cur){
if(cur == nums.length){
List<Integer> list = new ArrayList<>();
for(int i=0;i<nums.length;i++){
list.add(nums[i]);
}
res.add(list);
return;
}else{
for(int i=cur;i<nums.length;i++){
if(canSwap(nums,cur,i)){
swap(nums,cur,i);
permutition(nums,cur+1);
swap(nums,cur,i);
}
}
}
}
public boolean canSwap(int[] nums, int start, int end){
for(int i=start;i < end;i++){
if(nums[i] == nums[end]){
return false;
}
}
return true;
}
public void swap(int[] nums, int i, int j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
46. 全排列
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
// 没有重复数的全排列
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {
if(nums == null || nums.length == 0){
return res;
}
permutition(nums,0);
return res;
}
public void permutition(int[] nums, int cur){
if(cur == nums.length){
List<Integer> list = new ArrayList<>();
for(int x: nums){
list.add(x);
}
res.add(list);
return;
}else{
for(int i=cur;i<nums.length;i++){
swap(nums,cur,i);
permutition(nums,cur+1);
swap(nums,cur,i);
}
}
}
public void swap(int[] nums , int i , int j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
39. 组合总和
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
示例 1:
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
if(candidates == null || candidates.length == 0){
return res;
}
Arrays.sort(candidates);
combination(candidates,target,0,new Stack<Integer>());
return res;
}
public void combination(int[] num,int target, int cur, Stack<Integer> stack){
if(target == 0){
res.add(new ArrayList<>(stack));
return;
}
for(int i=cur;i<num.length && target - num[i] >= 0;i++){
stack.add(num[i]);
// 这里传i， 数组里面的数可以重复使用
combination(num,target-num[i],i,stack);
stack.pop();
}
}
40. 组合总和2
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
// 数组中有重复的数，和排列一样进行筛选
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
if(candidates == null || candidates.length == 0){
return res;
}
Arrays.sort(candidates);
combination(0,candidates,target,new LinkedList<Integer>());
return res;
}
public void combination(int cur, int[] candidates, int target, LinkedList<Integer> list ){
if(target == 0){
res.add(new ArrayList<>(list));
return;
}
for(int i=cur;i<candidates.length && target - candidates[i] >=0 ; i++){
if(check(candidates,cur,i)){
list.add(candidates[i]);
// 这里 i + 1 是数组里面的数不可以重复使用 combination(i+1,candidates,target-candidates[i],list);
list.removeLast();
}
}
}
public boolean check(int[] nums, int cur, int end){
for(int i=cur;i<end;i++){
if(nums[i] == nums[end]){
return false;
}
}
return true;
}
90. 子集2
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
Set<List<Integer>> set = new HashSet<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if(nums == null || nums.length == 0){
return res;
}
Arrays.sort(nums);
int len = nums.length;
int max = 1 << len;
for(int i=0;i<max;i++){
List<Integer> list = new ArrayList<>();
for(int j=0;j<nums.length;j++){
if(((i >> j) & 1) == 1){
list.add(nums[j]);
}
}
set.add(list);
}
for(List<Integer> l : set){
res.add(l);
}
return res;
}
/// 子集
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
if(nums == null || nums.length == 0){
return res;
}
Arrays.sort(nums);
subsets(0,nums,new LinkedList<Integer>());
return res;
}
public void subsets(int cur, int[] nums, LinkedList<Integer> list){
res.add(new ArrayList<>(list));
for(int i=cur;i<nums.length;i++){
if(i > cur && nums[i] == nums[i-1]){
continue;
}
list.add(nums[i]);
subsets(i+1,nums,list);
list.removeLast();
}
}
78. 子集
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if(nums == null || nums.length == 0){
return res;
}
int len = nums.length;
int max = 1 << len;
for(int i=0;i<max;i++){
List<Integer> list = new ArrayList<>();
for(int j=0;j<nums.length;j++){
if(((i >> j) & 1) == 1){
list.add(nums[j]);
}
}
res.add(list);
}
return res;
}
子集就是组合
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
if(nums == null || nums.length == 0){
return res;
}
subsets(0,nums,new LinkedList<Integer>());
return res;
}
public void subsets(int cur, int[] nums, LinkedList<Integer> list){
res.add(new ArrayList<>(list));
for(int i = cur;i<nums.length;i++){
list.add(nums[i]);
subsets(i+1,nums,list);
list.removeLast();
}
}
494. 目标和
给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
示例：
输入：nums: [1, 1, 1, 1, 1], S: 3
输出：5
int count = 0;
public int findTargetSumWays(int[] nums, int S) {
findTarget(0,nums,S,0);
return count;
}
public void findTarget(int cur, int[] nums, int S,int sum){
if(cur == nums.length){
if(sum == S)
count++;
return;
}
findTarget(cur+1,nums,S, sum-nums[cur]);
findTarget(cur+1,nums,S, sum+nums[cur]);
}
网友评论