526互联

递归问题——算法复习随笔

发布时间 2023-03-26 15:32:13作者: TfiyuenLau

递归问题——算法复习随笔

递归是一种将问题分解成更小的子问题来解决问题的思维方式，其中子问题具有与原问题相同的结构，只是规模更小。
递归思维常常用于解决具有递归结构的问题，例如树形结构、分治算法、动态规划等，因为递归思维可以使问题更加简单明了，易于理解和实现。
但是递归思维也有一些缺点，例如递归过程中会产生大量的函数调用，导致额外的空间开销和时间开销，同时递归深度也可能受限于栈空间的大小。因此，在使用递归思维时，需要注意选择适当的递归边界条件、避免重复计算和进行剪枝等优化措施，以提高效率和减少空间开销。
——ChatGPT

一、全排列问题

全排列问题是指给定一个序列，求出该序列所有可能的排列方式。例如：全排列

给定一个由不同的小写字母组成的字符串，输出这个字符串的所有全排列。我们假设对于小写字母有 \(a<b<…<y<z\) 而且给定的字符串中的字母已经按照从小到大的顺序排列。

输入样例：

abc

输出样例：

abc
acb
bac
bca
cab
cba

Ⅰ、交换法

交换法是一种递归的方法。对于全排列问题，可以将序列看作两部分：已经排好的部分和未排好的部分。

首先将未排好的部分的第一个元素与已经排好的部分的最后一个元素交换，然后将未排好的部分的第一个元素插入到已经排好的部分的最后，得到一个新的已经排好的部分。

然后对剩余的未排好的部分进行同样的操作，直到所有元素都已经排好。

ArrayList<String> res = new ArrayList<String>();

/**
    * 交换法：不保证字典序
    * 
    * @param s 输入的字符序列
    * @return
    */
private ArrayList<String> getPermuataion(String s) {
    char[] arr = s.toCharArray();
    getPermuatationCode(arr, 0);
    return res;
}

private void getPermuatationCode(char[] arr, int k) {
    if (k == arr.length) {
        res.add(new String(arr));
    }
    
    for (int i = k; i < arr.length; i++) {
        swap(arr, k, i);//交换值
        getPermuatationCode(arr, k+1);
        swap(arr, k, i);//状态回溯
    }
}

static void swap(char[] arr, int i, int j) {
    char temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

Ⅱ、前缀法

/**
    * 前缀法：保证字典序
    * 
    * @param prefix
    * @param arr
    */
private static void permuatation(String prefix, char[] arr) {
    //当前缀长度等于数组排列长度时，意味着一次排列完成
    if (prefix.length() == arr.length) {
        System.out.println(prefix);
    }
    
    //每次递归从头扫描，将可用的字符添加到前缀后
    for (int i = 0; i < arr.length; i++) {
        char ch = arr[i];
        if (count(prefix.toCharArray(), ch) < count(arr, ch)) {
            permuatation(prefix + ch, arr);
        }
    }
}

private static int count(char[] arr, char ch) {
    int cnt=0;
    for (char c:arr) {
        if (c == ch) {
            cnt++;
        }
    }
    return cnt;
}

Ⅲ、回溯法

回溯法是解决排列、组合、子集等问题的一种常见方法，因为这些问题的解空间较小，适合使用深度优先遍历实现回溯。

对于全排列问题，我们可以使用递归回溯的方法，具体思路如下：

  1. 构建一个布尔型数组 used，表示每个字符是否已经在当前排列中出现过。
  2. 对字符串进行遍历，对于每个字符，如果这个字符没有在当前排列中出现过，就将它加入排列，并将 used 数组中对应的位置设为 true。
  3. 当排列的长度等于字符串长度时，说明已经生成了一个排列，将其输出或保存。
  4. 对于还没有使用的字符，递归调用步骤 2 和步骤 3，生成下一个字符加入排列。
  5. 生成排列后，回溯到上一层，将上一层的字符移除，并将 used 数组中对应的位置设为 false，再尝试其他未使用的字符。
class Solution {
    List<String> res = new ArrayList<>();
    boolean[] used;

    public String[] permutation(String s) {
        if (s == null || s.length() == 0) {
            return new String[0];
        }

        used = new boolean[s.length()];

        backtrack(s, new StringBuilder());

        return res.toArray(new String[0]);
    }

	
	/**
	 * 回溯法dfs方法
	 * 
	 * @param s
	 * @param cur
	 */
    private void backtrack(String s, StringBuilder cur) {
        if (cur.length() == s.length()) {
            res.add(cur.toString());
            return;
        }

        for (int i = 0; i < s.length(); i++) {
            if (!used[i]) {
                used[i] = true;
                cur.append(s.charAt(i));
                backtrack(s, cur);//递归调用
                cur.deleteCharAt(cur.length() - 1);//状态回溯
                used[i] = false;
            }
        }
    }
}

二、DFS例题——数独游戏

数独是一种传统益智游戏，你需要把一个 9×9 的数独补充完整，使得图中每行、每列、每个 3×3 的九宫格内数字 1∼9 均恰好出现一次。请编写一个程序填写数独。数独简单版

输入样例：

.2738..1.
.1...6735
.......29
3.5692.8.
.........
.6.1745.3
64.......
9518...7.
.8..6534.

输出样例：

527389416
819426735
436751829
375692184
194538267
268174593
643217958
951843672
782965341

下面是使用 Java 语言实现的代码示例：

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		char[][] table = new char[9][];
		for (int i = 0; i < 9; i++) {
			table[i] = sc.nextLine().toCharArray();
		}
		sc.close();
		dfs(table, 0, 0);
	}

	/**
	 * 1613.数独简单版
	 * 
	 * @param table
	 * @param x
	 * @param y
	 */
	static void dfs(char[][] table, int x, int y) {
		if (x == 9) {
			print(table);
			System.exit(0);
		}
		if (table[x][y] == '.') {// 判断单元格是否为空
			for (int k = 1; k < 10; k++) {
				if (check(table, x, y, k)) {
					table[x][y] = (char) ('0' + k);
					dfs(table, x + (y + 1) / 9, (y + 1) % 9);// 处理下一状态
				}
			}
			table[x][y] = '.';// 回溯状态
		} else {
			dfs(table, x + (y + 1) / 9, (y + 1) % 9);
		}

	}

	private static boolean check(char[][] table, int i, int j, int k) {
		// 判断同行同列数字是否重复
		for (int l = 0; l < 9; l++) {
			if (table[i][l] == (char) ('0' + k)) {
				return false;
			}
			if (table[l][j] == (char) ('0' + k)) {
				return false;
			}
		}
		// 判断九宫格数字是否重复
		for (int l = (i / 3) * 3; l < (i / 3 + 1) * 3; l++) {
			for (int m = (j / 3 * 3); m < (j / 3 + 1) * 3; m++) {
				if (table[l][m] == (char) ('0' + k)) {
					return false;
				}
			}
		}
		return true;
	}

	private static void print(char table[][]) {
		for (int i = 0; i < table.length; i++) {
			System.out.println(table[i]);
		}
	}
}

三、DFS例题——部分和问题

部分和问题是指给定一个正整数集合 \(a_1, a_2, \ldots, a_n\) 和目标值 \(k\)，判断是否可以从集合中选取若干个数，使它们的和等于 \(k\)。这个问题可以用深度优先搜索（DFS）来解决。

DFS 的基本思路是从集合的第一个数开始，分别考虑是否选择该数，进入下一层递归。在递归到最后一层时，判断当前的和是否等于 \(k\)。如果等于，说明已经找到了一个满足条件的方案，返回 true；否则返回 false。

需要注意的是，在搜索过程中，如果已经确定了选择的数的和已经超过了目标值 \(k\)，则直接返回 false，因为后面的搜索只会让和变得更大，不可能满足要求。

下面是使用 Java 语言实现的代码示例：

class Solution {
    boolean dfs(int[] nums, int index, int target, int sum) {
        if (sum == target) {
            return true;
        }
        if (index == nums.length || sum > target) {
            return false;
        }
        return dfs(nums, index + 1, target, sum) || dfs(nums, index + 1, target, sum + nums[index]);
    }

    boolean canPartition(int[] nums, int target) {
        int sum = Arrays.stream(nums).sum();
        if (sum < target || sum % 2 == 1) {
            return false;
        }
        return dfs(nums, 0, target, 0);
    }
}