东莞网站优化推广,市场调研模板,做蛋糕有哪些网站,衡阳市本地新闻头条刷题顺序及思路来源于代码随想录#xff0c;网站地址#xff1a;https://programmercarl.com
目录
131. 分割回文串
93. 复原 IP 地址
78. 子集
90. 子集 II
491. 递增子序列 131. 分割回文串
给你一个字符串 s#xff0c;请你将 s 分割成一些子串#xff0c;使每个…刷题顺序及思路来源于代码随想录网站地址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 inputnew Scanner(System.in);String sinput.nextLine();System.out.println(partition(s));}public static ListListString resnew ArrayList();public static ListString pathnew ArrayList();public static ListListString partition(String s) {backtracking(s,0);return res;}private static void backtracking(String s, int startIndex) {//终止条件if(startIndexs.length()){//收获结果res.add(new ArrayList(path));return;}for (int i startIndex; i s.length() ; i) {//判断是否回文如果是则加入到path中if(isPalindrome(s,startIndex,i)){String strs.substring(startIndex,i1);path.add(str);}else {continue;}backtracking(s,i1);//回溯path.remove(path.size()-1);}}private static boolean isPalindrome(String s, int left, int right) {for (int i left,jright; 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.1681.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 inputnew Scanner(System.in);String sinput.nextLine();System.out.println(restoreIpAddresses(s));}public static ListString resnew ArrayList();public static ListString restoreIpAddresses(String s) {if(s.length()12){ //剪枝return res;}//采用StringBuilder,不用重复重复重复创建字符串StringBuilder sbnew StringBuilder(s);backtracking(sb,0,0);return res;}private static void backtracking(StringBuilder sb, int startIndex, int pointCount) {//终止条件if(pointCount3){// 判断第四段子字符串是否合法如果合法就放进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(i1,.);pointCount;//将i2的位置作为下一个字符串的起始位置因为多添加了一个.backtracking(sb,i2,pointCount);//回溯sb.deleteCharAt(i1);pointCount--;}else {break;}}}/*判断是否合法IP段1.每个整数位于0到255之间组成2.段位以0为开头的数字不合法3.段位里有非正整数字符不合法*/private static boolean isValid(StringBuilder sb, int start, int end) {if(startend){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 numInteger.parseInt(sb.substring(start,end1));if(num0||num255){return false;}//2.段位以0为开头的数字不合法if(sb.charAt(start)0start!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 inputnew Scanner(System.in);int ninput.nextInt();int[] numsnew int[n];for (int i 0; i n; i) {nums[i]input.nextInt();}System.out.println(subsets(nums));}public static ListListInteger resnew ArrayList();public static ListInteger pathnew ArrayList();public static ListListInteger subsets(int[] nums) {backtracking(nums,0);return res;}private static void backtracking(int[] nums, int startIndex) {res.add(new ArrayList(path));//收集子集,要放在终止添加的上面,否则会漏掉自己//终止条件if(startIndexnums.length){return;}for (int i startIndex; i nums.length; i) {path.add(nums[i]);backtracking(nums,i1);//回溯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 inputnew Scanner(System.in);int ninput.nextInt();int[] numsnew int[n];for (int i 0; i n; i) {nums[i]input.nextInt();}System.out.println(subsetsWithDup(nums));}public static ListListInteger resnew ArrayList();public static ListInteger pathnew ArrayList();public static ListListInteger subsetsWithDup(int[] nums) {Arrays.sort(nums);int[] usednew 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(startIndexnums.length){return;}for (int i startIndex; i nums.length; i) {if(i0nums[i]nums[i-1]used[i-1]0){continue;}path.add(nums[i]);used[i]1;backtracking(nums,i1,used);//回溯path.remove(path.size()-1);used[i]0;}}
}491. 递增子序列
给你一个整数数组 nums 找出并返回所有该数组中不同的递增子序列递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
数组中可能含有重复元素如出现两个整数相等也可以视作递增序列的一种特殊情况。
输入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 inputnew Scanner(System.in);int ninput.nextInt();int[] numsnew int[n];for (int i 0; i n; i) {nums[i]input.nextInt();}System.out.println(findSubsequences(nums));}public static ListListInteger resnew ArrayList();public static ListInteger pathnew ArrayList();public static ListListInteger 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(startIndexnums.length){return;}SetInteger setnew 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,i1);//回溯path.remove(path.size()-1);}}
}
