【算法合集】学习算法第五天（递归/回溯篇）

た入场券 2024-05-23 18:59 72阅读 0赞

> ✅?个人主页：[程序猿追][Link 1]
> 
> ✅?系列专栏：[算法合集][Link 2]
> 
> ✅?目前状态：创建Java学习之路（零基础到就业实战）系列，目前更新到JAVAWEB开发
> 
> ✅?作者简介：大家好，我是程序猿追，全栈领域新星创作者，算法爱好者，常在作者周榜排名前30，某不知名的 ACMer
> 
> ✅?推荐一款刷题面试找工作三不误的网站——[牛客网][Link 3]
> 
> ✅?个人名言：不积跬步无以至千里，趁年轻，使劲拼，给未来的自己一个交代！

**目录**

没有重复项数字的全排列

题解代码

岛屿数量

题解代码

N皇后问题

题解代码

括号生成

题解代码

--------------------

## 没有重复项数字的全排列 ##

> **描述**
> 
> 给出一组数字，返回该组数字的所有排列
> 
> **例如：**
> 
> \[1,2,3\]的所有排列如下  
> \[1,2,3\],\[1,3,2\],\[2,1,3\],\[2,3,1\],\[3,1,2\], \[3,2,1\].  
> （以数字在数组中的位置靠前为优先级，按字典序排列输出。）
> 
> 数据范围：数字个数0<n≤6
> 
> 要求：空间复杂度 O(n!) ，时间复杂度 O(n!）
> 
> **示例1**
> 
> 输入：
> 
> \[1,2,3\]
> 
> 返回值：
> 
> \[\[1,2,3\],\[1,3,2\],\[2,1,3\],\[2,3,1\],\[3,1,2\],\[3,2,1\]\]
> 
> **示例2**
> 
> 输入：
> 
> \[1\]
> 
> 返回值：
> 
> \[\[1\]\]

### 题解代码 ###

import java.util.*;
    public class Solution {
        //交换位置函数 fast-template
        private void swap(ArrayList<Integer> num, int i1, int i2){
            int temp = num.get(i1);
            num.set(i1, num.get(i2));
            num.set(i2, temp);
        }
        public void recursion(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> num, int index){
            //分枝进入结尾，找到一种排列
            if(index == num.size() - 1){
                res.add(num);
            }
            else{
                //遍历后续的元素
                for(int i = index; i < num.size(); i++){
                    //交换二者
                    swap(num, i, index);
                    //继续往后找
                    recursion(res, num, index + 1);
                     //回溯
                    swap(num, i, index);
                }
            }
        }
        public ArrayList<ArrayList<Integer>> permute(int[] num) {
            //先按字典序排序
            Arrays.sort(num);
            ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer>>();
            ArrayList<Integer> nums = new ArrayList<Integer>();
            //数组转ArrayList
            for(int i = 0; i < num.length; i++)
                nums.add(num[i]);
            recursion(res, nums, 0);
            return res; }
    }

## 岛屿数量 ##

> **描述**
> 
> 给一个01矩阵，1代表是陆地，0代表海洋， 如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。
> 
> 岛屿: 相邻陆地可以组成一个岛屿（相邻:上下左右） 判断岛屿个数。
> 
> **例如：**
> 
> 输入
> 
> \[
> 
> \[1,1,0,0,0\],
> 
> \[0,1,0,1,1\],
> 
> \[0,0,0,1,1\],
> 
> \[0,0,0,0,0\],
> 
> \[0,0,1,1,1\]
> 
> \]
> 
> 对应的输出为3
> 
> (注：存储的01数据其实是字符'0','1')
> 
> **示例1**
> 
> 输入：
> 
> \[\[1,1,0,0,0\],\[0,1,0,1,1\],\[0,0,0,1,1\],\[0,0,0,0,0\],\[0,0,1,1,1\]\]
> 
> 复制返回值：
> 
> 3
> 
> **示例2**
> 
> 输入：
> 
> \[\[0\]\]
> 
> 返回值：
> 
> 0
> 
> **示例3**
> 
> 输入：
> 
> \[\[1,1\],\[1,1\]\]
> 
> 返回值：
> 
> 1
> 
> 备注：
> 
> 01矩阵范围<=200\*200

### 题解代码 ###

import java.util.*;
    public class Solution {
        //深度优先遍历与i，j相邻的所有1 fast-template
        public void dfs(char[][] grid, int i, int j) {
            int n = grid.length;
            int m = grid[0].length;
            // 置为0
            grid[i][j] = '0';
            //后续四个方向遍历
            if(i - 1 >= 0 && grid[i - 1][j] == '1')
                dfs(grid, i - 1, j);
            if(i + 1 < n && grid[i + 1][j] == '1')
                dfs(grid, i + 1,j);
            if(j - 1 >= 0 && grid[i][j - 1] == '1')
                dfs(grid, i, j - 1);
            if(j + 1 < m && grid[i][j + 1] == '1')
                dfs(grid, i, j + 1);
        }
        public int solve (char[][] grid) {
            int n = grid.length;
            //空矩阵的情况
            if (n == 0)
                return 0;
            int m = grid[0].length;
            //记录岛屿数
            int count = 0;
            // 遍历矩阵
            for(int i = 0; i < n; i++){
                for(int j = 0; j < m; j++){
                    //遍历到1的情况
                    if(grid[i][j] == '1'){
                        //计数
                        count++;
                        //将与这个1相邻的所有1置为0
                        dfs(grid, i, j);
                    }
                }
            }
            return count;}
    }

## N皇后问题 ##

> **描述**
> 
> N 皇后问题是指在 n \* n 的棋盘上要摆 n 个皇后，  
> 要求：任何两个皇后不同行，不同列也不在同一条斜线上，  
> 求给一个整数 n ，返回 n 皇后的摆法数。
> 
> **数据范围: 1≤n≤9**
> 
> **要求：空间复杂度 O(1) ，时间复杂度 O(n!)**
> 
> 例如当输入4时，对应的返回值为2，
> 
> 对应的两种四皇后摆位如下图所示：
> 
> ![34be548a3da74f35ba0dd70b32f30926.png][]
> 
> **示例1**
> 
> 输入：
> 
> 1
> 
> 返回值：
> 
> 1
> 
> **示例2**
> 
> 输入：
> 
> 8
> 
> 返回值：
> 
> 92

### 题解代码 ###

import java.util.*;
    public class Solution {
        private int res;
         //判断皇后是否符合条件 fast-template
        public boolean isValid(int[] pos, int row, int col){
            //遍历所有已经记录的行
            for(int i = 0; i < row; i++){
                //不能同行同列同一斜线
                if(row == i || col == pos[i] || Math.abs(row - i) == Math.abs(col - pos[i]))
                    return false;
            }
            return true;
        }
        //递归查找皇后种类
        public void recursion(int n, int row, int[] pos){
            //完成全部行都选择了位置
            if(row == n){
                res++;
                return;
            }
            //遍历所有列
            for(int i = 0; i < n; i++){
                //检查该位置是否符合条件
                if(isValid(pos, row, i)){
                    //加入位置
                    pos[row] = i;
                    //递归继续查找
                    recursion(n, row + 1, pos);
                }
            }
        }
        public int Nqueen (int n) {
            res = 0;
            //下标为行号，元素为列号，记录皇后位置
            int[] pos = new int[n];
            Arrays.fill(pos, 0);
            //递归
            recursion(n, 0, pos);
            return res;}
    }

###  ###

## 括号生成 ##

> **描述**
> 
> 给出n对括号，请编写一个函数来生成所有的由n对括号组成的合法组合。
> 
> 例如，给出n=3，解集为：
> 
> "((()))", "(()())", "(())()", "()()()", "()(())"
> 
> **数据范围：0≤n≤10**
> 
> **要求：空间复杂度 O(n)，时间复杂度 O(2^n)**
> 
> **示例1**
> 
> 输入：
> 
> 1
> 
> 返回值：
> 
> \["()"\]
> 
> **示例2**
> 
> 输入：
> 
> 2
> 
> 返回值：
> 
> \["(())","()()"\]

### 题解代码 ###

import java.util.*;
    public class Solution {
        public void recursion(int left, int right, String temp, ArrayList<String> res, int n){
            //左右括号都用完了，就加入结果 fast-template
            if(left == n && right == n){
                res.add(temp);
                return;
            }
            //使用一次左括号
            if(left < n){
                recursion(left + 1, right, temp + "(", res, n);
            }
            //使用右括号个数必须少于左括号
            if(right < n && left > right){
                recursion(left, right + 1, temp + ")", res, n);
            }
        }
        public ArrayList<String> generateParenthesis (int n) {
            //记录结果
            ArrayList<String> res = new ArrayList<String>();
            //递归
            recursion(0, 0, "", res, n);
            return res;}
    }

> 算法对程序员来说及其重要，语言和开发平台不断变化，但是万变不离其宗的是那些算法和理论，依稀记得我那个玩的很好的一个学长（在大二就拿到了 offer），他告诉我想找一个好的工作，那刷题一定是必不可少的
> 
> 现在算法刷题平台还是蛮多的，给大家介绍一个我认为与大厂关联最深的平台——[牛客网][Link 3]

[Link 1]: https://blog.csdn.net/aasd23?spm=1000.2115.3001.5343
[Link 2]: https://blog.csdn.net/aasd23/category_11805404.html?spm=1001.2014.3001.5482
[Link 3]: https://www.nowcoder.com/link/pc_csdncpt_cxyz_sf
[34be548a3da74f35ba0dd70b32f30926.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/23/22c5b597ba5c47ad98b8fd3b4317f1a7.png