java实现回溯算法,java基础面试笔试题

  • 时间:
  • 浏览:0
  • 来源:跟我学网络



我总结出了很多互联网公司的面试题及答案,并整理成了文档,以及各种学习的进阶学习资料,免费分享给大家。

扫描二维码或搜索下图红色VX号,加VX好友,拉你进【程序员面试学习交流群】免费领取。也欢迎各位一起在群里探讨技术。

推荐文章:Java 面试知识点解析;Mysql优化技巧(数据库设计、命名规范、索引优化

最近有在leetcode上面做算法题,已经遇到了两道回溯算法的题目,感觉一点思路都没有,现决定将java如何实现回溯算法做一次总结。

一、什么叫做回溯算法

(摘抄于百度百科)

回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的,规模较大的问题都可以使用回溯法,有“通用解题方法”的美称。

(摘抄于他人博客)

在包含问题的所有解的解空间树中,按照深度优先搜索的策略,从根结点出发深度探索解空间树。当探索到某一结点时,要先判断该结点是否包含问题的解,如果包含,就从该结点出发继续探索下去,如果该结点不包含问题的解,则逐层向其祖先结点回溯。(其实回溯法就是对隐式图的深度优先搜索算法)。 若用回溯法求问题的所有解时,要回溯到根,且根结点的所有可行的子树都要已被搜索遍才结束。 而若使用回溯法求任一个解时,只要搜索到问题的一个解就可以结束。

二、如何使用回溯算法

回溯我认为也就是一种递归,有以下四个参数,当然不一定是我所举例的类型,要看题目而定

一个全局变量集合保存所有满足条件的答案,举例:List<List<Integer>> list

一个集合保存一个满足条件的答案,举例:List<Integer> tempList

算法问题给所给的输入条件,这个可能是一个字符串,也可能是一个数组

附加参数(可有可无,视题目而定)

下面具体以leetcode上的一道题目为例,这样能更好的理解

import java.util.ArrayList;

import java.util.List;

public class Permutations {

    //题目描述:Given a collection of distinct integers, return all possible permutations.(给定一组不同的整数,返回其所有的可能组合)

    public List<List<Integer>> permute(int[] nums) {

        //一个全局变量,用于保存所有集合

        List<List<Integer>> list = new ArrayList<>();

        //传入三个参数,没有附加参数

        backtrack(list, new ArrayList<>(), nums);

        return list;

    }

    private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums){

        //一个终结条件,也就是满足条件的时候

        if(tempList.size() == nums.length){

            //全局变量添加一个满足条件的集合

            list.add(new ArrayList<>(tempList));

        } else{

            for(int i = 0; i < nums.length; i++){

                if(tempList.contains(nums[i])) continue;

                //如果tempList没有包含nums[i]才添加

                tempList.add(nums[i]);

                //递归调用,此时的tempList一直在变化,直到满足终结条件才结束

                backtrack(list, tempList, nums);

                System.out.println("tempList的内容:"+tempList+"-------"+"i的值:"+i);

                //它移除tempList最后一个元素的作用就是返回上一次调用时的数据,也就是希望返回之前的节点再去重新搜索满足条件。这样才能实现回溯

                tempList.remove(tempList.size() - 1);

            }

        }

    }

    public static void main(String[] args){

        int[] nums={1,2,3};

        (new Permutations()).permute(nums);

    }

}

main方法测试,输出语句的结果显示如下,可以观察出回溯的过程

tempList的内容:[1, 2, 3]-------i的值:2

tempList的内容:[1, 2]-------i的值:1

tempList的内容:[1, 3, 2]-------i的值:1

tempList的内容:[1, 3]-------i的值:2

tempList的内容:[1]-------i的值:0

tempList的内容:[2, 1, 3]-------i的值:2

tempList的内容:[2, 1]-------i的值:0

tempList的内容:[2, 3, 1]-------i的值:0

tempList的内容:[2, 3]-------i的值:2

tempList的内容:[2]-------i的值:1

tempList的内容:[3, 1, 2]-------i的值:1

tempList的内容:[3, 1]-------i的值:0

tempList的内容:[3, 2, 1]-------i的值:0

tempList的内容:[3, 2]-------i的值:1

tempList的内容:[3]-------i的值:2

我对这道题目的理解是从这个for循环的i=0开始就不断递归,然后在不断消除集合最末尾元素进行回溯,直到回溯完成。这样就产生了首位元素是1的各种情况。以此类推,之后再开始for循环i=1,产生首位元素是2的各种情况。

形象点就是一个根结点有1,2,3三个元素,第一次从1出发,寻找最低端满足条件的结点,然后再返回上一个结点寻找满足条件的结点,直到返回1,返回1之后再从2开始,以此类推。

leetcode上面有关回溯算法的一些题目的实现可查看这个链接:https://leetcode.com/problems/permutations/discuss/18239/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partioning)



转载:https://www.cnblogs.com/lzxin/p/9714133.html



推荐内容:

java面试Java入门篇(一)——如何编写一个简单的Java程序2018年Java后端面试经历三年半Java后端面试经历为什么说JAVA中要慎重使用继承十大经典排序算法最强总结(含JAVA代码实现)Java面试题乱笔15个顶级Java多线程面试题及答案面试的角度诠释Java工程师(二)浅谈Java中的深克隆和浅克隆(阿里面试)