栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

Java-算法-回溯<二>

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

Java-算法-回溯<二>

此篇承接上文:

">Java-算法-回溯<一>

 6. leetcode131 分割回文子串

        给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是 回文串 。返回 s 所有可能的分割方案。回文串 是正着读和反着读都一样的字符串。

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

class Solution {
    List> ans = new ArrayList<>();
    public List> partition(String s) {
        if(s == "") return ans;
        List path = new  ArrayList<>();
        dfs(0,s,path);
        return ans;
    }
    public void dfs(int index, String s, List path){
        if(index == s.length()){
            ans.add(new ArrayList(path));
            return;
        }
        for(int i = index; i < s.length(); i++){
            String temp = s.substring(index,i+1);
            if(!isPar(temp)){
                continue;
            }
            path.add(temp);
            dfs(i+1,s,path);
            path.remove(path.size()-1);
        }
    }
    public boolean isPar(String temp){
        int i = 0;
        int j = temp.length()-1;
        while(i < j){
            if(temp.charAt(i) != temp.charAt(j)){
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
}

本题小结:(1)index相当于分割的指针,index走到的地方即为分割位置

                (2)substring左闭右开,要向后一位

                (3)取过的不再取,i+1位置

 7. leetcode93 复原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"]

class Solution {
    List ans= new ArrayList<>();
    public List restoreIpAddresses(String s) {
        if(s.length() < 4 || s.length() > 12) return ans;
         for(int i = 0; i < s.length(); i++){
             if(s.charAt(i) < 48 || s.charAt(i) > 57){
                 return ans;
             }
         }
        dfs(0,0,s,"");
        return ans;
    }
    public void dfs(int index, int len,String s, String path){
        if(index == s.length() && len == 4){
            path = path.substring(0,path.length()-1);
            ans.add(path);
            return;
        }
        for(int i = index; i < s.length(); i++){
            String temp = s.substring(index, i+1);
            if(temp.length() > 3 || len >= 4) break;
            if(!islegal(temp)){
                continue;
            }
            path += temp;
            path += ".";
            dfs(i+1,len+1,s,path);
            path = path.substring(0,path.length()-1-temp.length());
        }

    }
    public boolean islegal(String temp){
        if(temp.equals("0")) return true;
        if(temp.charAt(0) == '0' && temp.length() >1) return false;
        int sum = 0;
        for(int i = temp.length()-1; i>=0; i--){
            sum += Math.pow(10,temp.length()-1-i)*(temp.charAt(i)-48);
        }
        if(sum >=1 && sum <= 255){
            return true;
        }
        else{
            return false;
        }  
    }
}

本题小结:(1)index相当于分割的指针,index走到的地方即为分割位置,和上题一样

                (2)if(temp.length() > 3 || len >= 4) 可以提前大剪枝

                (3)len == 4为递归深度,达到这一深度可终止

 8. leetcode78 子集

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

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

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

class Solution {
    List> ans = new ArrayList<>();
    public List> subsets(int[] nums) {
        List path = new ArrayList<>();
        dfs(0,nums,path);
        return ans;
    }
    public void dfs(int index, int[] nums, List path){
//         if(!ans.contains(path)){
//             ans.add(new ArrayList<>(path));
//         }
//         else{
//             return;
//         }
        ans.add(new ArrayList<>(path));
        for(int i = index; i < nums.length; i++){
            path.add(nums[i]);
            dfs(i+1,nums,path);
            path.remove(path.size()-1);
        }
    }
}

本题小结:(1)子集问题相当于求经过的所有路径的和

                (2)取过的不再取,取i+1,这样可以避免{1,2}{2,1}的重复情况

 9. leetcode90 子集II

        给你一个整数数组 nums ,其中可能包含重复元素,请你返回该数组所有可能的子集(幂集)。解集 不能 包含重复的子集。返回的解集中,子集可以按 任意顺序 排列。

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

class Solution {
    List> ans = new ArrayList<>();
    public List> subsetsWithDup(int[] nums) {
        List path = new ArrayList<>();
        Arrays.sort(nums);
        dfs(0,nums,path);
        return ans;
    }
    public void dfs(int index, int[] nums, List path){
        ans.add(new ArrayList<>(path));
        for(int i = index; i < nums.length; i++){
            if(i > index && nums[i] == nums[i-1]) continue;
            path.add(nums[i]);
            dfs(i+1,nums,path);
            path.remove(path.size()-1);
        }
    }
}

本题小结:(1)和第五题一个套路,通过i > index && nums[i] == nums[i-1]去重

                (2)沿路添加所有节点

10. leetcode491 递增子序列

        给你一个整数数组 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]]

class Solution {
    List> ans = new ArrayList<>();
    public List> findSubsequences(int[] nums) {
        List path = new ArrayList<>();
        dfs(0,nums,path);
        return ans;
    }
    public void dfs(int index, int[] nums, List path){
        if(path.size() > 1) ans.add(new ArrayList<>(path));
        int[] used = new int[201];
        for(int i = index; i < nums.length; i++){
            if(path.size() > 0 && nums[i] < path.get(path.size()-1) || used[nums[i] + 100] == 1) continue;
            used[nums[i] + 100] = 1;
            path.add(nums[i]);
            dfs(i+1,nums,path);
            path.remove(path.size()-1);    
        }
    }
}

本题小结:(1)添加的新的数字都不能小于path的最后一个数nums[i] < path.get(path.size()-1)

                (2)path.size()大于1就可以沿路添加所有path的值

                (3)i > index && nums[i] == nums[i-1]的判断不适用于本题目

                (4)在本层建立used数组来去重

 11. leetcode46 全排列

        给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

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

直接判断是否在path中

class Solution {
    List> ans = new ArrayList<>();
    public List> permute(int[] nums) {
        List path = new ArrayList<>();
        dfs(nums, path);
        return ans;
    }
    public void dfs(int[] nums, List path){
        if(path.size() == nums.length){
            ans.add(new ArrayList(path));
            return;
        }
        for(int i = 0; i < nums.length; i++){
            if(path.contains(nums[i]))  continue;
            path.add(nums[i]);
            dfs(nums, path);
            path.remove(path.size()-1);
        }
    }
}

 使用used数组判断

class Solution {
    List> ans = new ArrayList<>();
     int[] used = new int[21];
    public List> permute(int[] nums) {
        List path = new ArrayList<>();
        dfs(nums, path);
        return ans;
    }
    public void dfs(int[] nums, List path){
        if(path.size() == nums.length){
            ans.add(new ArrayList(path));
            return;
        }
        for(int i = 0; i < nums.length; i++){
            if(used[nums[i]+10] == 1)  continue;
            path.add(nums[i]);
            used[nums[i]+10] = 1;
            dfs(nums, path);
            path.remove(path.size()-1);
            used[nums[i]+10] = 0;
        }
    }
}

 

本题小结:(1)i从0开始,要把所有都考虑进去,不再需要index

                (2)path.size()等于数组值证明已经选取完所有的数,即可添加

                (3)既可使用used数组,也可以直接用contains方法判断是否选过这个数子

                (4)和题目10把不同的是这次的used数组需放在全局变量上,因为选过的不能再选且                           本题目无重复,而10有重复,有重复必须在本层去重。

 参考来源:

[1] 代码随想录 卡尔 回溯算法

 

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/951051.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号