数据类型和引用类型在OJ题中的应用

数据类型和引用类型是Java中的概念,对应的是C语言中的值传递和指针传递。

基本数据类型包括 boolean(布尔型)、char(字符型)、byte(字节型)、short(短整型)、int(整型)、long(长整型)、float(单精度浮点型)、和 double(双精度浮点型)共8种。

引用数据类型建立在基本数据类型的基础上,包括数组、类(String属于类)、接口(包括各种集合类型)、枚举、注解。所有引用类型的默认值都是null。

 

leetcode526题:优美的排列

https://leetcode-cn.com/problems/beautiful-arrangement/

数据类型和引用类型在OJ题中的应用

 

 基本思路是用回溯算法实现,先看下面代码:

class Solution {
    public int countArrangement(int n) {
        //理解题意,全排列问题
        int[] visit = new int[n];
        int res=0,num=0;
        for(int i=1;i!=n+1;i++)
            dfs(visit,i,num,n,res);
        return res;
    }
    public void dfs(int[] visit,int i,int num,int n,int res){   //此处函数传递的是数据类型
        if(i%(num+1)!=0 && (num+1)%i!=0)    return ;
        visit[i-1] = 1;num++;
        if(num != n){
            for(int j=1;j!=n+1;j++){
                if(visit[j-1] == 0)
                    dfs(visit,j,num,n,res);
            }
        }
        else
            res++;     //关键步骤res+1
        visit[i-1] = 0;num--;
    }
}

  

本例中用dfs函数实现深度优先遍历,逻辑上来讲每得到一个优美的排列res就会+1。但是函数接收的是基本数据类型,在dfs中对res做的所有操作不会改变主函数中的res,所以运行结果永远是0。

对上述代码进行修改,dfs返回int参数即可解决问题。

class Solution {
    public int countArrangement(int n) {
        //理解题意,全排列问题
        int[] visit = new int[n];
        int res=0,num=0;
        for(int i=1;i!=n+1;i++)
            res += dfs(visit,i,num,n);
        return res;
    }
    public int dfs(int[] visit,int i,int num,int n){   //易错点,函数传递的是数值类型,不会改变引用类型
        if(i%(num+1)!=0 && (num+1)%i!=0)    return 0;
        int res=0;
        visit[i-1] = 1;num++;
        if(num != n){
            for(int j=1;j!=n+1;j++){
                if(visit[j-1] == 0)
                    res += dfs(visit,j,num,n);
            }
        }
        else
            res = 1;
        visit[i-1] = 0;num--;
        return res;
    }
}

  

leetcode797题:所有可能的路径

https://leetcode-cn.com/problems/all-paths-from-source-to-target/

数据类型和引用类型在OJ题中的应用

 

 同上一题,还是用回溯算法实现,不同的是此例返回的是一个List接口,先看下面代码:

class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        dfs(res,path,graph,graph.length,0);
        return res;
    }
    public void dfs(List<List<Integer>> res,List<Integer> path,int[][] graph,int n,int src){
        path.add(src);
        if(src==n-1){
            res.add(path);      //关键代码
            path.remove(path.size()-1);return;
        }
        for(int item:graph[src])
            dfs(res,path,graph,n,item);
        path.remove(path.size()-1);
    }
}

  

在dfs函数中将path集合加入res,最后返回res,但是运行结果显示res为空。原因是res添加的是path集合的深拷贝,每次对path的修改也会导致res的改变。所以对代码进行以下修改:

class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        dfs(res,path,graph,graph.length,0);
        return res;
    }
    public void dfs(List<List<Integer>> res,List<Integer> path,int[][] graph,int n,int src){
        path.add(src);
        if(src==n-1){
            res.add(new ArrayList<Integer>(path));path.remove(path.size()-1);return;
        }
        for(int item:graph[src])
            dfs(res,path,graph,n,item);
        path.remove(path.size()-1);
    }
}

  

 

数据类型和引用类型在OJ题中的应用

上一篇:mount --bind 挂载目录


下一篇:mybatis快速入门