LeetCode——回溯篇（二）

这篇具有很好参考价值的文章主要介绍了LeetCode——回溯篇（二）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

刷题顺序及思路来源于代码随想录，网站地址：https://programmercarl.com

131. 分割回文串

93. 复原 IP 地址

78. 子集

90. 子集 II

491. 递增子序列

131. 分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @author light
 * @Description 分割回文串
 * @create 2023-08-28 17:07
 */
public class PartitionTest {
	public static void main(String[] args) {
		Scanner input=new Scanner(System.in);
		String s=input.nextLine();
		System.out.println(partition(s));
	}

	public static List<List<String>> res=new ArrayList<>();
	public static List<String> path=new ArrayList<>();

	public static List<List<String>> partition(String s) {
		backtracking(s,0);
		return  res;
	}

	private static void backtracking(String s, int startIndex) {
		//终止条件
		if(startIndex>=s.length()){
			//收获结果
			res.add(new ArrayList<>(path));
			return;
		}

		for (int i = startIndex; i <s.length() ; i++) {
			//判断是否回文，如果是，则加入到path中
			if(isPalindrome(s,startIndex,i)){
				String str=s.substring(startIndex,i+1);
				path.add(str);
			}else {
				continue;
			}
			backtracking(s,i+1);
			//回溯
			path.remove(path.size()-1);
		}
	}

	private static boolean isPalindrome(String s, int left, int right) {
		for (int i = left,j=right; i <j ; i++,j--) {
			if(s.charAt(i)!=s.charAt(j)){
				return false;
			}
		}
		return true;
	}
}

93. 复原 IP 地址

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

例如："0.1.2.201" 和 "192.168.1.1" 是有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你不能重新排序或删除 s 中的任何数字。你可以按任何顺序返回答案。

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @author light
 * @Description 复原IP地址
 * @create 2023-08-28 21:21
 */
public class RestoreIpAddressesTest {
	public static void main(String[] args) {
		Scanner input=new Scanner(System.in);
		String s=input.nextLine();
		System.out.println(restoreIpAddresses(s));
	}
	public static List<String> res=new ArrayList<>();
	public static List<String> restoreIpAddresses(String s) {
		if(s.length()>12){ //剪枝
			return res;
		}
		//采用StringBuilder,不用重复重复重复创建字符串
		StringBuilder sb=new StringBuilder(s);
		backtracking(sb,0,0);
		return res;
	}

	private static void backtracking(StringBuilder sb, int startIndex, int pointCount) {
		//终止条件
		if(pointCount==3){
			// 判断第四段子字符串是否合法，如果合法就放进result中
			if(isValid(sb,startIndex,sb.length()-1)){
				res.add(sb.toString());
			}
			return;
		}
		for (int i = startIndex; i < sb.length(); i++) {
			//判断字段是否合法
			if(isValid(sb,startIndex,i)){
				//如果合法添加"." sb.insert（）方法，该方法是在索引的前面添加字符串
				sb.insert(i+1,".");
				pointCount++;
				//将i+2的位置作为下一个字符串的起始位置，因为多添加了一个"."
				backtracking(sb,i+2,pointCount);
				//回溯
				sb.deleteCharAt(i+1);
				pointCount--;
			}else {
				break;
			}
		}
	}

	/*
	判断是否合法IP段：
		1.每个整数位于0到255之间组成
		2.段位以0为开头的数字不合法
		3.段位里有非正整数字符不合法
	 */
	private static boolean isValid(StringBuilder sb, int start, int end) {
		if(start>end){
			return false;
		}
		//3.段位里有非正整数字符不合法
		for (int i = start; i <=end ; i++) {
			if(sb.charAt(i)<'0'||sb.charAt(i)>'9'){
				return false;
			}
		}
		//1.每个整数位于0到255之间组成
		int num=Integer.parseInt(sb.substring(start,end+1));
		if(num<0||num>255){
			return false;
		}
		//2.段位以0为开头的数字不合法
		if(sb.charAt(start)=='0'&&start!=end){
			return false;
		}
		return true;
	}

}

78. 子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按 任意顺序 返回解集。

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

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @author light
 * @Description 子集
 *
 * (思路：如果把 子集问题、组合问题、分割问题都抽象为一棵树的话，
 * 那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！
 *
 * 其实子集也是一种组合问题，因为它的集合是无序的，子集{1,2} 和 子集{2,1}是一样的。
 * @create 2023-08-29 10:25
 */
public class SubsetsTest {
	public static void main(String[] args) {
		Scanner input=new Scanner(System.in);
		int n=input.nextInt();
		int[] nums=new int[n];
		for (int i = 0; i < n; i++) {
			nums[i]=input.nextInt();
		}
		System.out.println(subsets(nums));
	}

	public static List<List<Integer>> res=new ArrayList<>();
	public static List<Integer> path=new ArrayList<>();
	public static List<List<Integer>> subsets(int[] nums) {
		backtracking(nums,0);
		return res;
	}

	private static void backtracking(int[] nums, int startIndex) {
		res.add(new ArrayList<>(path));//收集子集,要放在终止添加的上面,否则会漏掉自己
		//终止条件
		if(startIndex>=nums.length){
			return;
		}
		for (int i = startIndex; i < nums.length; i++) {
			path.add(nums[i]);
			backtracking(nums,i+1);
			//回溯
			path.remove(path.size()-1);
		}
	}
}

90. 子集 II

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

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

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

/**
 * @author light
 * @Description 子集II
 * @create 2023-08-29 11:03
 */
public class SubsetsWithDupTest {
	public static void main(String[] args) {
		Scanner input=new Scanner(System.in);
		int n=input.nextInt();
		int[] nums=new int[n];
		for (int i = 0; i < n; i++) {
			nums[i]=input.nextInt();
		}
		System.out.println(subsetsWithDup(nums));
	}

	public static List<List<Integer>> res=new ArrayList<>();
	public static List<Integer> path=new ArrayList<>();

	public static List<List<Integer>> subsetsWithDup(int[] nums) {
		Arrays.sort(nums);
		int[] used=new int[nums.length];
		Arrays.fill(used,0);
		backtracking(nums,0,used);
		return res;
	}

	private static void backtracking(int[] nums, int startIndex, int[] used) {
		res.add(new ArrayList<>(path));
		//终止条件
		if(startIndex>=nums.length){
			return;
		}

		for (int i = startIndex; i < nums.length; i++) {
			if(i>0&&nums[i]==nums[i-1]&&used[i-1]==0){
				continue;
			}
			path.add(nums[i]);
			used[i]=1;
			backtracking(nums,i+1,used);
			//回溯
			path.remove(path.size()-1);
			used[i]=0;

		}

	}
}

491. 递增子序列

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。文章来源地址https://www.toymoban.com/news/detail-680882.html

输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

import java.util.*;

/**
 * @author light
 * @Description 递增子序列
 * @create 2023-08-29 15:01
 */
public class FindSubsequencesTest {
	public static void main(String[] args) {
		Scanner input=new Scanner(System.in);
		int n=input.nextInt();
		int[] nums=new int[n];
		for (int i = 0; i < n; i++) {
			nums[i]=input.nextInt();
		}
		System.out.println(findSubsequences(nums));
	}
	public static List<List<Integer>> res=new ArrayList<>();
	public static List<Integer> path=new ArrayList<>();
	public static List<List<Integer>> findSubsequences(int[] nums) {
		backtracking(nums,0);
		return res;
	}

	private static void backtracking(int[] nums, int startIndex) {
		if(path.size()>1){
			res.add(new ArrayList<>(path));  //注意不要加return，要收集树上的所有节点
		}
		if(startIndex>=nums.length){
			return;
		}
		Set<Integer> set=new HashSet<>();//记录本层元素是否重复使用
		for (int i = startIndex; i < nums.length; i++) {
			//如果队列不为空，但要添加的元素小于path中的最后一个元素---不是递增的---不满足条件
			//或者集合中已经含有nums[i]---本层有重复元素----不满足条件
			if((!path.isEmpty()&&nums[i]<path.get(path.size()-1))||set.contains(nums[i])){
				continue;
			}
			set.add(nums[i]); //每层都创建一个---不需要回溯
			path.add(nums[i]);
			backtracking(nums,i+1);
			//回溯
			path.remove(path.size()-1);
		}

	}
}

到了这里，关于LeetCode——回溯篇（二）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！