算法：【深度搜索（回溯）】
一、数字字符串转化成IP地址
现在有一个只包含数字的字符串，将该字符串转化成IP地址的形式，返回所有可能的情况。
例如：
给出的字符串为"25525522135",
返回["255.255.22.135", "255.255.221.35"]. (顺序没有关系)输入:
"25525522135"
返回值:
["255.255.22.135","255.255.221.35"]
import java.util.*;
public class Solution {
ArrayList<String> res = new ArrayList<String>();
public ArrayList<String> restoreIpAddresses (String s) {
// 深搜
ArrayList<String> ip = new ArrayList<String>();//存放中间结果
dfs(s, ip, 0);
return res;
}
public void dfs(String s, ArrayList<String> ip, int start){
if(ip.size() == 4 && start == s.length()){ // 找到一个合法解
res.add(ip.get(0) + '.' + ip.get(1) + '.' + ip.get(2) + '.' + ip.get(3));
return;
}
if(s.length() - start > 3*(4-ip.size()))
return;
if(s.length() - start < (4-ip.size()))
return;
int num = 0;
for(int i=start; i<start + 3 && i<s.length(); i++){
num = num*10 + (s.charAt(i) - '0');
if(num < 0 || num > 255)
continue;
ip.add(s.substring(start, i+1));
dfs(s, ip, i+1);
ip.remove(ip.size()-1);
if(num == 0) //不允许前缀0
break;
}
}
} 二、字符串的排列
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入:
"ab"
返回值:
["ab","ba"]
import java.util.ArrayList;
import java.util.*;
public class Solution {
ArrayList<String> res = new ArrayList<String>();
public ArrayList<String> Permutation(String str) {
if(str.length() == 0)
return res;
char[] ch = str.toCharArray();
Arrays.sort(ch);
process(ch, new boolean[ch.length], new StringBuffer());
return res;
}
public void process(char[] ch, boolean[] maked, StringBuffer str){
if(str.length() == ch.length){
res.add(str.toString());
return;
}
for(int i=0; i<ch.length; i++){
if(maked[i])
continue;
if(i != 0 && ch[i] == ch[i-1] && !maked[i-1]){
continue;
}
maked[i] = true;
str.append(ch[i]);
process(ch, maked, str);
maked[i] = false;
str.deleteCharAt(str.length() -1);
}
}
} class Solution {
public:
//分字符串长度奇偶性讨论，模拟两个滑动窗口，一开始的最大长度是字符串的一半，从左往右滑动比较
//右端窗口滑到字符串末尾后，两个窗口长度同时减一，并从字符串左端从头开始扫描
//只要扫描过程中第一次匹配到两个窗口内的字符串相同，那么答案就是2*窗口长度
int solve(string a) {
if(a.size()%2==0){//字符串长度是偶数
int l1(0),r1(a.size()/2-1);
int l2(a.size()/2),r2(a.size()-1);
while(l1<=r1&&l2<=r2&&a.substr(l1,r1-l1+1)!=a.substr(l2,r2-l2+1)){
int wlen = r1-l1;//窗口缩小1格
l1=0,r1=l1+wlen-1,l2=r1+1,r2=l2+wlen-1;
while(r2<a.size()&&a.substr(l1,r1-l1+1)!=a.substr(l2,r2-l2+1)){
l1++,r1++;
l2++,r2++;
}
if(a.substr(l1,r1-l1+1)==a.substr(l2,r2-l2+1)) return 2*(r1-l1+1);
}
return 2*(r1-l1+1);
}
else{//字符串长度是奇数
int l1(0),r1(a.size()/2-1);
int l2(a.size()/2),r2(a.size()-2);
while(l1<=r1&&l2<=r2&&a.substr(l1,r1-l1+1)!=a.substr(l2,r2-l2+1)){
while(r2<a.size()&&a.substr(l1,r1-l1+1)!=a.substr(l2,r2-l2+1)){
l1++,r1++;
l2++,r2++;
}
if(a.substr(l1,r1-l1+1)==a.substr(l2,r2-l2+1)) return 2*(r1-l1+1);
int wlen = r1-l1;//窗口缩小1格
l1=0,r1=l1+wlen-1,l2=r1+1,r2=l2+wlen-1;
}
return 2*(r1-l1+1);
}
return 0;
}
};三、1. 组合总和
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[[7],[2,2,3]]
class Solution {
List<List<Integer>> res = new LinkedList<List<Integer>>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
if(candidates == null || candidates.length == 0)
return res;
List<Integer> tmp = new LinkedList<Integer>();
Arrays.sort(candidates);
backtracking(candidates, tmp, 0, target);
return res;
}
// start 是控制的关键
public void backtracking(int[] candidates, List<Integer> tmp, int start, int target){
if(target == 0 && !res.contains(tmp)){
res.add(new LinkedList<Integer>(tmp));
return;
}
for(int i=start; i<candidates.length; i++){
// 减枝，数组已经从小到大排序好了，如果当前的数已经大于target，后面的数必定大于target。
if(candidates[i] > target)
break;
tmp.add(candidates[i]);
backtracking(candidates, tmp, i, target-candidates[i]);
tmp.remove(tmp.size()-1);
}
}
} 三、2. 组合总和 II
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
- 所有数字（包括目标数）都是正整数。
- 解集不能包含重复的组合。
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
class Solution {
// 回溯法
List<List<Integer>> res = new LinkedList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
if(candidates == null || candidates.length == 0)
return res;
Arrays.sort(candidates);
List<Integer> tmp = new LinkedList<>();
backtracking(candidates, 0, tmp, target);
return res;
}
public void backtracking(int[] candidates, int start, List<Integer> tmp, int target){
// 减枝，数组已经从小到大排序好了，如果当前的数已经大于target，后面的数必定大于target。
if(target == 0 && !res.contains(tmp)){
res.add(new LinkedList(tmp));
return;
}
for(int i=start; i<candidates.length; i++){
if(target - candidates[i] < 0)
break;
tmp.add(candidates[i]);
backtracking(candidates, i+1, tmp, target-candidates[i]);
tmp.remove(tmp.size()-1);
}
}
}来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
四、岛屿的最大面积
给定一个包含了一些 0 和 1 的非空二维数组 grid 。
一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。)示例 1:
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]
对于上面这个给定矩阵应返回 6。注意答案不应该是 11 ，因为岛屿只能包含水平或垂直的四个方向的 1 。
class Solution {
public int maxAreaOfIsland(int[][] grid) {
int res = 0;
// 遍历整个数组
for(int i=0; i<grid.length; i++)
for(int j=0; j<grid[0].length; j++){
res = Math.max(res, process(grid, i, j));
}
return res;
}
public int process(int[][] grid, int curi, int curj){
if(curi<0 || curj<0 || curi>=grid.length || curj>=grid[0].length || grid[curi][curj] != 1)
return 0;
// 置为0，防止重复遍历
grid[curi][curj] = 0;
// 上下左右变换
int[] di = {0,0,1,-1};
int[] dj = {1,-1,0,0};
int ans = 1;
// 深度遍历
for(int i=0; i<4; i++){
ans += process(grid, curi+di[i], curj+dj[i]);
}
return ans;
}
} 