class038 经典递归解析【算法】-摩杜云开发者社区

class038 经典递归解析

class038 经典递归解析【算法】_Stack

code1 字符串的全部子序列

// 字符串的全部子序列
// 子序列本身是可以有重复的，只是这个题目要求去重
// 测试链接 : https://www.nowcoder.com/practice/92e6247998294f2c933906fdedbc6e6a

package class038;

import java.util.HashSet;

// 字符串的全部子序列
// 子序列本身是可以有重复的，只是这个题目要求去重
// 测试链接 : https://www.nowcoder.com/practice/92e6247998294f2c933906fdedbc6e6a
public class Code01_Subsequences {

	public static String[] generatePermutation1(String str) {
		char[] s = str.toCharArray();
		HashSet<String> set = new HashSet<>();
		f1(s, 0, new StringBuilder(), set);
		int m = set.size();
		String[] ans = new String[m];
		int i = 0;
		for (String cur : set) {
			ans[i++] = cur;
		}
		return ans;
	}

	// s[i...]，之前决定的路径path，set收集结果时去重
	public static void f1(char[] s, int i, StringBuilder path, HashSet<String> set) {
		if (i == s.length) {
			set.add(path.toString());
		} else {
			path.append(s[i]); // 加到路径中去
			f1(s, i + 1, path, set);
			path.deleteCharAt(path.length() - 1); // 从路径中移除
			f1(s, i + 1, path, set);
		}
	}

	public static String[] generatePermutation2(String str) {
		char[] s = str.toCharArray();
		HashSet<String> set = new HashSet<>();
		f2(s, 0, new char[s.length], 0, set);
		int m = set.size();
		String[] ans = new String[m];
		int i = 0;
		for (String cur : set) {
			ans[i++] = cur;
		}
		return ans;
	}

	public static void f2(char[] s, int i, char[] path, int size, HashSet<String> set) {
		if (i == s.length) {
			set.add(String.valueOf(path, 0, size));
		} else {
			path[size] = s[i];
			f2(s, i + 1, path, size + 1, set);
			f2(s, i + 1, path, size, set);
		}
	}

}

code2 90. 子集 II

// 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的组合
// 答案不能包含重复的组合。返回的答案中，组合可以按任意顺序排列
// 注意其实要求返回的不是子集，因为子集一定是不包含相同元素的，要返回的其实是不重复的组合
// 比如输入：nums = [1,2,2]
// 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
// 测试链接 : https://leetcode.cn/problems/subsets-ii/

package class038;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

// 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的组合
// 答案 不能 包含重复的组合。返回的答案中，组合可以按 任意顺序 排列
// 注意其实要求返回的不是子集，因为子集一定是不包含相同元素的，要返回的其实是不重复的组合
// 比如输入：nums = [1,2,2]
// 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
// 测试链接 : https://leetcode.cn/problems/subsets-ii/
public class Code02_Combinations {

	public static List<List<Integer>> subsetsWithDup(int[] nums) {
		List<List<Integer>> ans = new ArrayList<>();
		Arrays.sort(nums);
		f(nums, 0, new int[nums.length], 0, ans);
		return ans;
	}

	public static void f(int[] nums, int i, int[] path, int size, List<List<Integer>> ans) {
		if (i == nums.length) {
			ArrayList<Integer> cur = new ArrayList<>();
			for (int j = 0; j < size; j++) {
				cur.add(path[j]);
			}
			ans.add(cur);
		} else {
			// 下一组的第一个数的位置
			int j = i + 1;
			while (j < nums.length && nums[i] == nums[j]) {
				j++;
			}
			// 当前数x，要0个
			f(nums, j, path, size, ans);
			// 当前数x，要1个、要2个、要3个...都尝试
			for (; i < j; i++) {
				path[size++] = nums[i];
				f(nums, j, path, size, ans);
			}
		}
	}

}

code3 46. 全排列

// 没有重复项数字的全排列
// 测试链接 : https://leetcode.cn/problems/permutations/

package class038;

import java.util.ArrayList;
import java.util.List;

// 没有重复项数字的全排列
// 测试链接 : https://leetcode.cn/problems/permutations/
public class Code03_Permutations {

	public static List<List<Integer>> permute(int[] nums) {
		List<List<Integer>> ans = new ArrayList<>();
		f(nums, 0, ans);
		return ans;
	}

	public static void f(int[] nums, int i, List<List<Integer>> ans) {
		if (i == nums.length) {
			List<Integer> cur = new ArrayList<>();
			for (int num : nums) {
				cur.add(num);
			}
			ans.add(cur);
		} else {
			for (int j = i; j < nums.length; j++) {
				swap(nums, i, j);
				f(nums, i + 1, ans);
				swap(nums, i, j); // 特别重要，课上进行了详细的图解
			}
		}
	}

	public static void swap(int[] nums, int i, int j) {
		int tmp = nums[i];
		nums[i] = nums[j];
		nums[j] = tmp;
	}

	public static void main(String[] args) {
		int[] nums = { 1, 2, 3 };
		List<List<Integer>> ans = permute(nums);
		for (List<Integer> list : ans) {
			for (int num : list) {
				System.out.print(num + " ");
			}
			System.out.println();
		}
	}

}

code4 47. 全排列 II

// 有重复项数组的去重全排列
// 测试链接 : https://leetcode.cn/problems/permutations-ii/

package class038;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

// 有重复项数组的去重全排列
// 测试链接 : https://leetcode.cn/problems/permutations-ii/
public class Code04_PermutationWithoutRepetition {

	public static List<List<Integer>> permuteUnique(int[] nums) {
		List<List<Integer>> ans = new ArrayList<>();
		f(nums, 0, ans);
		return ans;
	}

	public static void f(int[] nums, int i, List<List<Integer>> ans) {
		if (i == nums.length) {
			List<Integer> cur = new ArrayList<>();
			for (int num : nums) {
				cur.add(num);
			}
			ans.add(cur);
		} else {
			HashSet<Integer> set = new HashSet<>();
			for (int j = i; j < nums.length; j++) {
				// nums[j]没有来到过i位置，才会去尝试
				if (!set.contains(nums[j])) {
					set.add(nums[j]);
					swap(nums, i, j);
					f(nums, i + 1, ans);
					swap(nums, i, j);
				}
			}
		}
	}

	public static void swap(int[] nums, int i, int j) {
		int tmp = nums[i];
		nums[i] = nums[j];
		nums[j] = tmp;
	}

}

code5 用递归函数逆序栈

// 用递归函数排序栈
// 栈只提供push、pop、isEmpty三个方法
// 请完成无序栈的排序，要求排完序之后，从栈顶到栈底从小到大
// 只能使用栈提供的push、pop、isEmpty三个方法、以及递归函数
// 除此之外不能使用任何的容器，数组也不行
// 就是排序过程中只能用：
// 1) 栈提供的push、pop、isEmpty三个方法
// 2) 递归函数，并且返回值最多为单个整数

package class038;

import java.util.Stack;

// 用递归函数逆序栈
public class Code05_ReverseStackWithRecursive {

	public static void reverse(Stack<Integer> stack) {
		if (stack.isEmpty()) {
			return;
		}
		int num = bottomOut(stack);
		reverse(stack);
		stack.push(num);
	}

	// 栈底元素移除掉，上面的元素盖下来
	// 返回移除掉的栈底元素
	public static int bottomOut(Stack<Integer> stack) {
		int ans = stack.pop();
		if (stack.isEmpty()) {
			return ans;
		} else {
			int last = bottomOut(stack);
			stack.push(ans);
			return last;
		}
	}

	public static void main(String[] args) {
		Stack<Integer> stack = new Stack<Integer>();
		stack.push(1);
		stack.push(2);
		stack.push(3);
		stack.push(4);
		stack.push(5);
		reverse(stack);
		while (!stack.isEmpty()) {
			System.out.println(stack.pop());
		}
	}

}

code6 用递归函数排序栈

package class038;

import java.util.Stack;

// 用递归函数排序栈
// 栈只提供push、pop、isEmpty三个方法
// 请完成无序栈的排序，要求排完序之后，从栈顶到栈底从小到大
// 只能使用栈提供的push、pop、isEmpty三个方法、以及递归函数
// 除此之外不能使用任何的容器，数组也不行
// 就是排序过程中只能用：
// 1) 栈提供的push、pop、isEmpty三个方法
// 2) 递归函数，并且返回值最多为单个整数
public class Code06_SortStackWithRecursive {

	public static void sort(Stack<Integer> stack) {
		int deep = deep(stack);
		while (deep > 0) {
			int max = max(stack, deep);
			int k = times(stack, deep, max);
			down(stack, deep, max, k);
			deep -= k;
		}
	}

	// 返回栈的深度
	// 不改变栈的数据状况
	public static int deep(Stack<Integer> stack) {
		if (stack.isEmpty()) {
			return 0;
		}
		int num = stack.pop();
		int deep = deep(stack) + 1;
		stack.push(num);
		return deep;
	}

	// 从栈当前的顶部开始，往下数deep层
	// 返回这deep层里的最大值
	public static int max(Stack<Integer> stack, int deep) {
		if (deep == 0) {
			return Integer.MIN_VALUE;
		}
		int num = stack.pop();
		int restMax = max(stack, deep - 1);
		int max = Math.max(num, restMax);
		stack.push(num);
		return max;
	}

	// 从栈当前的顶部开始，往下数deep层，已知最大值是max了
	// 返回，max出现了几次，不改变栈的数据状况
	public static int times(Stack<Integer> stack, int deep, int max) {
		if (deep == 0) {
			return 0;
		}
		int num = stack.pop();
		int restTimes = times(stack, deep - 1, max);
		int times = restTimes + (num == max ? 1 : 0);
		stack.push(num);
		return times;
	}

	// 从栈当前的顶部开始，往下数deep层，已知最大值是max，出现了k次
	// 请把这k个最大值沉底，剩下的数据状况不变
	public static void down(Stack<Integer> stack, int deep, int max, int k) {
		if (deep == 0) {
			for (int i = 0; i < k; i++) {
				stack.push(max);
			}
		} else {
			int num = stack.pop();
			down(stack, deep - 1, max, k);
			if (num != max) {
				stack.push(num);
			}
		}
	}

	// 为了测试
	// 生成随机栈
	public static Stack<Integer> randomStack(int n, int v) {
		Stack<Integer> ans = new Stack<Integer>();
		for (int i = 0; i < n; i++) {
			ans.add((int) (Math.random() * v));
		}
		return ans;
	}

	// 为了测试
	// 检测栈是不是从顶到底依次有序
	public static boolean isSorted(Stack<Integer> stack) {
		int step = Integer.MIN_VALUE;
		while (!stack.isEmpty()) {
			if (step > stack.peek()) {
				return false;
			}
			step = stack.pop();
		}
		return true;
	}

	// 为了测试
	public static void main(String[] args) {
		Stack<Integer> test = new Stack<Integer>();
		test.add(1);
		test.add(5);
		test.add(4);
		test.add(5);
		test.add(3);
		test.add(2);
		test.add(3);
		test.add(1);
		test.add(4);
		test.add(2);
		sort(test);
		while (!test.isEmpty()) {
			System.out.println(test.pop());
		}

		// 随机测试
		int N = 20;
		int V = 20;
		int testTimes = 20000;
		System.out.println("测试开始");
		for (int i = 0; i < testTimes; i++) {
			int n = (int) (Math.random() * N);
			Stack<Integer> stack = randomStack(n, V);
			sort(stack);
			if (!isSorted(stack)) {
				System.out.println("出错了!");
				break;
			}
		}
		System.out.println("测试结束");
	}

}

code7 打印n层汉诺塔问题的最优移动轨迹

// 打印n层汉诺塔问题的最优移动轨迹

package class038;

// 打印n层汉诺塔问题的最优移动轨迹
public class Code07_TowerOfHanoi {

	public static void hanoi(int n) {
		if (n > 0) {
			f(n, "左", "右", "中");
		}
	}

	public static void f(int i, String from, String to, String other) {
		if (i == 1) {
			System.out.println("移动圆盘 1 从 " + from + " 到 " + to);
		} else {
			f(i - 1, from, other, to);
			System.out.println("移动圆盘 " + i + " 从 " + from + " 到 " + to);
			f(i - 1, other, to, from);
		}
	}

	public static void main(String[] args) {
		int n = 3;
		hanoi(n);
	}

}