"逐步生成结果”类问题之非数值型
CC150—9_6合法括号
/** * 1.输出合法的括号组合 * 输入括号对数 * 输出所有合法组合 * 输入:3 * 输出:()()(),((())),(()()),()(()),(())(), * 2.判断一个字符串是否合法 */
//(())(())
public class _9_6合法括号 {
public static void main(String[] args) {
_9_6合法括号 obj = new _9_6合法括号();
Set<String> parenthesis = obj.parenthesis1(4);
System.out.println(parenthesis.size());
for (String s : parenthesis) {
System.out.println(s);
}
// boolean b = obj.chkParenthesis("()a()()", 7);
// System.out.println(b);
}
public boolean chkParenthesis(String A, int n) {
if (n % 2 != 0)
return false;
int cnt = 0;
for (int i = 0; i < A.length(); i++) {
if (A.charAt(i) == '(') {
cnt++;
} else if (A.charAt(i) == ')') {
cnt--;
} else return false;
if (cnt < 0) return false;
}
return true;
}
/*逐步生成之递归解法*/
public Set<String> parenthesis(int n) {
Set<String> s_n = new HashSet<>();
if (n == 1) {
s_n.add("()");
return s_n;
}
Set<String> s_n_1 = parenthesis(n - 1);
for (String eOfN_1 : s_n_1) {
s_n.add("()" + eOfN_1);//添左
s_n.add(eOfN_1 + "()");//添右
s_n.add("(" + eOfN_1 + ")");//添在外部
// 更正：在内部也可以添加
for (int i = 0; i < eOfN_1.length(); i++) {
char c = eOfN_1.charAt(i);//每一个字符
if (c == '(')//只要这个字符是左括号，我们就可以在其后插入一对括号
s_n.add(eOfN_1.substring(0, i + 1) + "()" + eOfN_1.substring(i + 1));
}
}
return s_n;
}
/*迭代形式*/
public Set<String> parenthesis1(int n) {
Set<String> res = new HashSet<>();//保存上次迭代的状态
res.add("()");
if (n == 1) {
return res;
}
for (int i = 2; i <= n; i++) {
Set<String> res_new = new HashSet<>();
for (String e : res) {
res_new.add(e + "()");
res_new.add("()" + e);
res_new.add("(" + e + ")");
// 更正：在内部也可以添加
// for (int j = 0; j < e.length(); j++) {
// char c = e.charAt(j);//每一个字符
// if (c=='(')//只要这个字符是左括号，我们就可以在其后插入一对括号
// res_new.add(e.substring(0,j+1)+"()"+e.substring(j+1));
// }
}
res = res_new;
}
return res;
}
}
- 使用set集合可以去重
CC150—9_4非空子集**
/** 请编写一个方法，返回某集合的所有非空子集。 给定一个int数组A和数组的大小int n，请返回A的所有非空子集。 保证A的元素个数小于等于20，且元素互异。 各子集内部从大到小排序,子集之间字典逆序排序 */
public class _9_4非空子集 {
public static void main(String[] args) {
int[] A = {1, 2, 3};
_9_4非空子集 obj = new _9_4非空子集();
Set<Set<Integer>> subsets3 = obj.getSubsets3(A, A.length);
System.out.println(subsets3);
Set<Set<Integer>> subsets2 = obj.getSubsets2(A, A.length);
System.out.println(subsets2);
ArrayList<ArrayList<Integer>> subsets = obj.getSubsets(A, A.length);
System.out.println(subsets);
}
/** * 二进制法,迭代法,或者逐步生成法 * @param A * @param n * @return */
public ArrayList<ArrayList<Integer>> getSubsets(int[] A, int n) {
Arrays.sort(A);//正序排序
ArrayList<ArrayList<Integer>> res = new ArrayList<>();//大集合
for (int i = Case11_NExponent.ex(2, n) - 1; i > 0; i--) {//大数字-1
ArrayList<Integer> s = new ArrayList<>();//对每个i建立一个集合
for (int j = n - 1; j >= 0; j--) {//检查哪个位上的二进制为1,从高位开始检查,高位对应着数组靠后的元素
if (((i >> j) & 1) == 1) {
s.add(A[j]);
}
}
res.add(s);
}
return res;
}
/*逐步生成迭代大法*/
public Set<Set<Integer>> getSubsets2(int[] A, int n) {
Set<Set<Integer>> res = new HashSet<>();
res.add(new HashSet<>());//初始化为空集
//从第一个元素开始处理
for (int i = 0; i < n; i++) {
Set<Set<Integer>> res_new = new HashSet<>();//新建一个大集合
res_new.addAll(res);//把原来集合中的每个子集都加入到新集合中
//遍历之前的集合,全部克隆一遍
for (Set e : res) {
Set clone = (Set) ((HashSet) e).clone();
clone.add(A[i]);//把当前元素加进去
res_new.add(clone);//把克隆的子集加到大集合中
}
res = res_new;
}
return res;
}
/** * 增量构造法 * @param A * @param n * @return */
public Set<Set<Integer>> getSubsets3(int[] A, int n) {
// Arrays.sort(A);
return getSubsets3Core(A, n, n - 1);
}
/** * 递归增量构造法 * @param A * @param n * @param cur * @return */
private Set<Set<Integer>> getSubsets3Core(int[] A, int n, int cur) {
Set<Set<Integer>> newSet = new HashSet<>();
if (cur == 0) {//处理第一个元素
Set<Integer> nil = new HashSet<>();//空集
Set<Integer> first = new HashSet<>();//包含第一个元素的集合
first.add(A[0]);
newSet.add(nil);
newSet.add(first);
return newSet;
}
Set<Set<Integer>> oldSet = getSubsets3Core(A, n, cur - 1);
for (Set<Integer> set : oldSet) {
//对于每个子集,cur这个元素可以加进去,也可以不加进去
newSet.add(set);//保留原样
Set<Integer> clone = (Set<Integer>) ((HashSet) set).clone();
clone.add(A[cur]);//添加当前元素
newSet.add(clone);
}
return newSet;
}
}
二进制方法的笔记
每个数组，都有2的n次方的情况
如[1,2,3]解和其2进制表示如下：
- []----------000
- [1]---------100
- [2]---------010
- [3]---------001
- [1,2]-------110
- [1,3]-------101
- [2,3]-------011
- [1,2,3]-----111
代码
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
int n = nums.length;
//每个都有2的n次方个子集
double count = Math.pow(2, n);
for (int i = 0; i < count; i++) {
List<Integer> s = new ArrayList<>();
for (int j = 0; j < n; j++) {
if ((i>>j&1)==1){
s.add(nums[j]);
}
}
res.add(s);
}
return res;
}
}
CC150—9_5全排列I
- 插入法
/** * 编写一个方法，确定某字符串的所有排列组合。 给定一个string A和一个int n,代表字符串和其长度，请返回所有该字符串字符的排列， 保证字符串长度小于等于11且字符串中字符均为大写英文字符， */
public class _9_5全排列I {
public static void main(String[] args) {
ArrayList<String> res = new _9_5全排列I().getPermutation0("abcd");
System.out.println(res.size());
System.out.println(res);
}
/*逐步生成大法-迭代法*/
public ArrayList<String> getPermutation0(String A) {
int n = A.length();
ArrayList<String> res = new ArrayList<>();
res.add(A.charAt(0) + "");//初始化,包含第一个字符
for (int i = 1; i < n; i++) {//第二个字符插入到前面生成集合的每个元素里面
ArrayList<String> res_new = new ArrayList<>();
char c = A.charAt(i);//新字符
for (String str : res) {//访问上一趟集合中的每个字符串
// 插入到每个位置,形成一个新串
String newStr = c + str;//加在前面
res_new.add(newStr);
newStr = str + c;//加在后面
res_new.add(newStr);
//加在中间
for (int j = 1; j < str.length(); j++) {
newStr = str.substring(0, j) + c + str.substring(j);
res_new.add(newStr);
}
}
res = res_new;//更新
}
return res;
}
}
- 回溯法–交换法
package org.lanqiao.algo.book.cc150;
public class _9_5全排列II {
public static void main(String[] args) {
ArrayList<String> res = new _9_5全排列II().getPermutation("12345");
System.out.println(res.size());
System.out.println(res);
}
ArrayList<String> res = new ArrayList<>();
public ArrayList<String> getPermutation(String A) {
char[] arr = A.toCharArray();
Arrays.sort(arr);//abc
getPermutationCore(arr, 0);
return res;
}
private void getPermutationCore(char[] arr, int k) {
if (k == arr.length) {//排好了一种情况,递归的支路走到底了
res.add(new String(arr));
}
//从k位开始的每个字符,都尝试放在新排列的k这个位置
for (int i = k; i < arr.length; i++) {
swap(arr, k, i);//把后面每个字符换到k位
getPermutationCore(arr, k + 1);
swap(arr, k, i);//回溯
}
}
//交换位置
static void swap(char[] arr, int i, int j) {
char tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
- 先纵后横
- 回溯回来后记得恢复状态
- 是否恢复，取决于会不会对下个结果造成影响
- 前缀法
/** * LeetCode60 n个数的排列组合找出字典序的第k个排列 * The set[1,2,3,…,n]contains a total of n! unique permutations. By listing and labeling all of the permutations in order, We get the following sequence (ie, for n = 3): "123" "132" "213" "231" "312" "321" Given n and k, return the k th permutation sequence. Note: Given n will be between 1 and 9 inclusive. */
public class _9_5全排列III第k个排列 {
public static void main(String[] args) {
String s = "123";
permutation("", s.toCharArray());
}
final static int k = 3;
static int count = 0;
private static void permutation(String prefix, char[] arr) {
if (prefix.length() == arr.length) {//前缀的长度==字符集的长度,一个排列就完成了
// System.out.println(prefix);
count++;
if (count == k) {
System.out.println("-------:" + prefix);
System.exit(0);
}
}
//每次都从头扫描,只要该字符可用,我们就附加到前缀后面,前缀变长了
for (int i = 0; i < arr.length; i++) {
char ch = arr[i];
//这个字符可用:在pre中出现次数<在字符集中的出现次数
if (count(prefix, ch) < count(arr, ch)) {
permutation(prefix + ch, arr);
}
}
}
private static int count(char[] arr, char ch) {
int cnt = 0;
for (char c : arr
) {
if (c == ch) cnt++;
}
return cnt;
}
private static int count(String str, char ch) {
int cnt = 0;
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == ch) cnt++;
}
return cnt;
}
}
京公网安备 11010502036488号