数据结构与算法转载

原文地址

1 暴力递归、动态规划

1.1 暴力递归思维

==暴力递归实质就是尝试==

概念解释：

回溯-表示大问题被拆解为小问题，小问题返回给大问题信息，就是回溯

分治：大问题被拆解成小的子问题，就是分治

1、把问题转化为规模缩小了的同类问题的子问题

2、有明确的不需要继续进行递归的条件（base case）

3、有当得到了子问题的结果之后的决策过程

4、不记录每个子问题的解（如果记录每个子问题的解，就是我们熟悉的动态规划）

1.1.1 暴力递归下的尝试

1.1.1.1 例一：汉诺塔问题

打印n层汉诺塔从最左边移动到最右边的全部过程

汉诺塔圆盘移动，如果杆子上没有圆盘，可以移动到该杆，如果有圆盘则必须移动比该圆盘小的圆盘到该圆盘上

思路1：1、先想办法把1到N-1层圆盘移动到中间杆 2、再把N层的圆盘移动到最右侧的杆上 3、把1到N-1个圆盘从中间杆移动到最右侧。结束

思路2：忘掉左中右，理解为从from移动到to，from和to都有可能是左中右。所以定义from，to，other三个杆子。1、把1到N-1移动到other上。2、把第N层移动到to上。3、把1到N层从other移动到to上。结束

思路3：递归改非递归实现

N层汉诺塔，从左移动到右最优步数是2^N - 1 步。递归公式 T(N) = T(N-1) + 1 + T(N-1)。化简为等比数列，高中数学内容

尝试是有优劣之分的，譬如思路1和思路二。在动态规划章节，可以用动态规划优化我们的尝试到最优版本

package class11;

import java.util.Stack;

public class Code01_Hanoi {

        // 按照思路1的方法
	public static void hanoi1(int n) {
		leftToRight(n);
	}

	// 请把1~N层圆盘 从左 -> 右
	public static void leftToRight(int n) {
		if (n == 1) {
			System.out.println("Move 1 from left to right");
			return;
		}
		leftToMid(n - 1);
		System.out.println("Move " + n + " from left to right");
		midToRight(n - 1);
	}

	// 请把1~N层圆盘 从左 -> 中
	public static void leftToMid(int n) {
		if (n == 1) {
			System.out.println("Move 1 from left to mid");
			return;
		}
		leftToRight(n - 1);
		System.out.println("Move " + n + " from left to mid");
		rightToMid(n - 1);
	}

	public static void rightToMid(int n) {
		if (n == 1) {
			System.out.println("Move 1 from right to mid");
			return;
		}
		rightToLeft(n - 1);
		System.out.println("Move " + n + " from right to mid");
		leftToMid(n - 1);
	}

	public static void midToRight(int n) {
		if (n == 1) {
			System.out.println("Move 1 from mid to right");
			return;
		}
		midToLeft(n - 1);
		System.out.println("Move " + n + " from mid to right");
		leftToRight(n - 1);
	}

	public static void midToLeft(int n) {
		if (n == 1) {
			System.out.println("Move 1 from mid to left");
			return;
		}
		midToRight(n - 1);
		System.out.println("Move " + n + " from mid to left");
		rightToLeft(n - 1);
	}

	public static void rightToLeft(int n) {
		if (n == 1) {
			System.out.println("Move 1 from right to left");
			return;
		}
		rightToMid(n - 1);
		System.out.println("Move " + n + " from right to left");
		midToLeft(n - 1);
	}

        // 思路二：暴力递归 from to other
	public static void hanoi2(int n) {
		if (n > 0) {
			func(n, "left", "right", "mid");
		}
	}

	// 1~i 圆盘 目标是from -> to， other是另外一个
	public static void func(int N, String from, String to, String other) {
		if (N == 1) { // base
			System.out.println("Move 1 from " + from + " to " + to);
		} else {
			func(N - 1, from, other, to);
			System.out.println("Move " + N + " from " + from + " to " + to);
			func(N - 1, other, to, from);
		}
	}

	public static class Record {
		public boolean finish1;
		public int base;
		public String from;
		public String to;
		public String other;

		public Record(boolean f1, int b, String f, String t, String o) {
			finish1 = false;
			base = b;
			from = f;
			to = t;
			other = o;
		}
	}

        // 思路三：非递归实现
	public static void hanoi3(int N) {
		if (N < 1) {
			return;
		}
		Stack<Record> stack = new Stack<>();
		stack.add(new Record(false, N, "left", "right", "mid"));
		while (!stack.isEmpty()) {
			Record cur = stack.pop();
			if (cur.base == 1) {
				System.out.println("Move 1 from " + cur.from + " to " + cur.to);
				if (!stack.isEmpty()) {
					stack.peek().finish1 = true;
				}
			} else {
				if (!cur.finish1) {
					stack.push(cur);
					stack.push(new Record(false, cur.base - 1, cur.from, cur.other, cur.to));
				} else {
					System.out.println("Move " + cur.base + " from " + cur.from + " to " + cur.to);
					stack.push(new Record(false, cur.base - 1, cur.other, cur.to, cur.from));
				}
			}
		}
	}

	public static void main(String[] args) {
		int n = 3;
		hanoi1(n);
		System.out.println("============");
		hanoi2(n);
		System.out.println("============");
		hanoi3(n);
	}

}

1.1.1.2 例二：字符串子序列问题

1、打印一个字符串的全部子序列

子串：必须是连续的，用for循环就行

子序列：比子串自由，在原始序列的基础上，以此拿字符但是可以不连续

• 见process1方法代码

2、打印一个字符串的全部子序列，要求不要出现重复字面值的子序列

比如aaabcccc就会得到很多相同字面值的子序列，我们把重复字面值的子序列只要一个

• 见process2方法代码

package class11;

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

public class Code02_PrintAllSubsquences {

	public static List<String> subs(String s) {
		char[] str = s.toCharArray();
		String path = "";
		List<String> ans = new ArrayList<>();
		process1(str, 0, ans, path);
		return ans;
	}

	// str固定，不变
	// index此时来到的位置, 要  or 不要
	// 如果index来到了str中的终止位置，把沿途路径所形成的答案，放入ans中
	// 之前做出的选择，就是沿途路径path
	public static void process1(char[] str, int index, List<String> ans, String path) {
		if (index == str.length) {
			ans.add(path);
			return;
		}
		String no = path;
		process1(str, index + 1, ans, no);
		String yes = path + String.valueOf(str[index]);
		process1(str, index + 1, ans, yes);
	}

	public static List<String> subsNoRepeat(String s) {
		char[] str = s.toCharArray();
		String path = "";
		HashSet<String> set = new HashSet<>();
		process2(str, 0, set, path);
		List<String> ans = new ArrayList<>();
		for (String cur : set) {
			ans.add(cur);
		}
		return ans;
	}

	// str  index  用set去重
	public static void process2(char[] str, int index,
			HashSet<String> set, String path) {
		if (index == str.length) {
			set.add(path);
			return;
		}
		String no = path;
		process2(str, index + 1, set, no);
		String yes = path + String.valueOf(str[index]);
		process2(str, index + 1, set, yes);
	}

	public static void main(String[] args) {
		String test = "aacc";
		List<String> ans1 = subs(test);
		List<String> ans2 = subsNoRepeat(test);

		for (String str : ans1) {
			System.out.println(str);
		}
		System.out.println("=================");
		for (String str : ans2) {
			System.out.println(str);
		}
		System.out.println("=================");

	}

}

1.1.1.3 例四：字符串全排列问题

1、打印一个字符串的全部排列,process

2、打印一个字符串的全部排列，要求不要出现重复的排列.process2。方法1，可以用HashSet最后去重，该方式是把递归的所有结果进行筛选。方法2可以抛弃重复元素，例如a在0位置已经尝试完毕，再有一个元素也是a要到0位置，那么禁止，该方法是递归的时候事先判断要不要进行下一步递归，更快一点。该方法又叫分支限界

package class11;

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

public class Code03_PrintAllPermutations {

	public static ArrayList<String> permutation(String str) {
		ArrayList<String> res = new ArrayList<>();
		if (str == null || str.length() == 0) {
			return res;
		}
		char[] chs = str.toCharArray();
		process(chs, 0, res);
		return res;
	}

	// str[0..i-1]已经做好决定的
	// str[i...]都有机会来到i位置
	// i到达终止位置，str当前的样子，就是一种结果 -> ans
	public static void process(char[] str, int i, ArrayList<String> ans) {
	        // i来到终点，返回该种答案
		if (i == str.length) {
			ans.add(String.valueOf(str));
		}
		// 如果i没有终止，i...  都可以来到i位置
		for (int j = i; j < str.length; j++) { // i后面所有的字符都有机会来到i位置
			swap(str, i, j);
			process(str, i + 1, ans);
			// 恢复交换之前的现场
			swap(str, i, j);
		}
	}
	

	public static ArrayList<String> permutationNoRepeat(String str) {
		ArrayList<String> res = new ArrayList<>();
		if (str == null || str.length() == 0) {
			return res;
		}
		char[] chs = str.toCharArray();
		process2(chs, 0, res);
		return res;
	}

	// str[0..i-1]已经做好决定的
	// str[i...]都有机会来到i位置
	// i终止位置，str当前的样子，就是一种结果 -> ans
	public static void process2(char[] str, int i, ArrayList<String> res) {
		if (i == str.length) {
			res.add(String.valueOf(str));
			return;
		}
		boolean[] visit = new boolean[26]; // visit[0 1 .. 25] 代表a-z的字符有没有在当前出现过
		// i右边的字符都有机会
		for (int j = i; j < str.length; j++) {
			// str[j] = 'a'   -> 0   visit[0] -> 'a'
			
			// str[j] = 'z'   -> 25   visit[25] -> 'z'
			// 如果没出现过就没有机会
			if (!visit[str[j] - 'a']) {
				
				visit[str[j] - 'a'] = true;
				swap(str, i, j);
				process2(str, i + 1, res);
				swap(str, i, j);
				
			}
		}
	}

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

	public static void main(String[] args) {
		String s = "aac";
		List<String> ans1 = permutation(s);
		for (String str : ans1) {
			System.out.println(str);
		}
		System.out.println("=======");
		List<String> ans2 = permutationNoRepeat(s);
		for (String str : ans2) {
			System.out.println(str);
		}

	}

}

1.1.1.4 例六：用递归逆序一个栈(考验脑回路)

给你一个栈，请你逆序这个栈，不能申请额外的数据结构，只能使用递归函数。如何实现？

思路，先不要想着逆序它，实现一个f函数，f函数的作用是把栈传进去，想办法拿到栈低元素并返回。

package class11;

import java.util.Stack;

public class Code04_ReverseStackUsingRecursive {

	public static void reverse(Stack<Integer> stack) {
		if (stack.isEmpty()) {
			return;
		}
		// i是栈底元素，f调整之后的栈成为去掉栈底元素后的栈
		int i = f(stack);
		// 递归调用
		reverse(stack);
		// 经过base case之后，栈为空，此时压入的就是当前的栈底
		stack.push(i);
	}

	public static int f(Stack<Integer> stack) {
	        // 弹出栈顶，用result临时变量记住这个栈顶元素
		int result = stack.pop();
		// 如果栈为空，向上返回弹出的result，此时result就是栈底元素
		if (stack.isEmpty()) {
			return result;
		} else {
		        // 此时栈不为空，让子问题给我一个临时变量，临时变量就是子问题base case返回的result
			int last = f(stack);
			// 把我弹出的result再压入栈，向上返回子问题给我的result
			stack.push(result);
			return last;
		}
	}

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

	}

}

1.2 动态规划模型

以下代码有些已经实现了动态递归，看不懂没关系，下一章详细解释。可以先不管，回过头再看

1.2.1 从左往右尝试模型

1.2.1.1 数字字符转化问题

注：facebook面试题

1、规定1和A对应，2和B对应，3和C对应...。那么一个数字字符比如"111"就可以转化为："AAA","KA","AK"。

给定一个只有数字字符组成的字符串str,返回有多少种转化结果

思路：根据从左往右，我们划分多大，来尝试，比如111，我们尝试一个1，为"A",剩下两个1去继续尝试。如果我们两个1尝试，就是"K"。三个1超过26字符，无法尝试。继续如此周而复始

package class11;

public class Code06_ConvertToLetterString {

	public static int number(String str) {
		if (str == null || str.length() == 0) {
			return 0;
		}
		// i初始为0，表示0位置往后有多少中转化结果
		return process(str.toCharArray(), 0);
	}

	// str[0...i-1]已经转化完了，固定了
	// i之前的位置，如何转化已经做过决定了, 不用再关心
	// i... 有多少种转化的结果
	public static int process(char[] str, int i) {
	        // i和字符串长度一样大，右侧没有字符了。找到1中转化是0~n-1位置的转化
		if (i == str.length) { // base case
			return 1;
		}
		// i之前的决策，让当前i位置单独面对一个0字符，那么之前决策错误，返回0
		// 例如10先转化为A，2位置是0字符无法转化，当前决策无效
		// 而10直接转化为J,直接到终止位置，返回一种转化J
		if (str[i] == '0') {
			return 0;
		}
		
		// i位置如果是1或者2，有可能和下一个位置共同转化，因为字符数为0~26
		// 反之3~9超过26不需要决策
		
		// str[i] 如果是1，总是有两个选择，因为最大为19，不超过26
		if (str[i] == '1') {
			int res = process(str, i + 1);
			if (i + 1 < str.length) {
				res += process(str, i + 2);
			}
			return res;
		}
		// str[i] 如果是2，那么有可能有两种选择，需要看是否朝贡国26
		if (str[i] == '2') {
			int res = process(str, i + 1);
			if (i + 1 < str.length && (str[i + 1] >= '0' && str[i + 1] <= '6')) {
				res += process(str, i + 2); // (i和i+1)作为单独的部分，后续有多少种方法
			}
			return res;
		}
		// str[i] 在3~9的位置，下个位置必须决策一种选择
		return process(str, i + 1);
	}
	
	public static int dpWays2(String s) {
		if (s == null || s.length() == 0) {
			return 0;
		}
		char[] str = s.toCharArray();
		int N = str.length;
		int[] dp = new int[N+1];
		dp[N] = 1;
		for(int i = N-1; i >= 0; i--) {
			if (str[i] == '0') {
				dp[i] = 0;
			}
			if (str[i] == '1') {
				dp[i] = dp[i + 1];
				if (i + 1 < str.length) {
					dp[i] += dp[i + 2];
				}
			}
			if (str[i] == '2') {
				dp[i] = dp[i + 1];
				if (i + 1 < str.length && (str[i + 1] >= '0' && str[i + 1] <= '6')) {
					dp[i] += dp[i + 2]; // (i和i+1)作为单独的部分，后续有多少种方法
				}
			}
		}
		return dp[0];
	}
	

	public static int dpWays(String s) {
		if (s == null || s.length() == 0) {
			return 0;
		}
		char[] str = s.toCharArray();
		int N = str.length;
		int[] dp = new int[N + 1];
		dp[N] = 1;
		for (int i = N - 1; i >= 0; i--) {
			if (str[i] == '0') {
				dp[i] = 0;
			} else if (str[i] == '1') {
				dp[i] = dp[i + 1];
				if (i + 1 < N) {
					dp[i] += dp[i + 2];
				}
			} else if (str[i] == '2') {
				dp[i] = dp[i + 1]; 
				if (i + 1 < str.length && (str[i + 1] >= '0' && str[i + 1] <= '6')) {
					dp[i] += dp[i + 2];
				}
			} else {
				dp[i] = dp[i + 1];
			}
		}
		return dp[0];
	}

	public static void main(String[] args) {
		System.out.println(number("11111"));
		System.out.println(dpWays2("11111"));
	}

}

1.2.1.2 背包价值问题

2、给定两个长度都为N的数组weights和values，weight[i]和values[i]分别代表i号物品的重量和价值。

给定一个正数bag，表示一个载重bag的袋子，你装的物品不能超过这个重量。返回你能装下最多的价值是多少？

package class11;

public class Code07_Knapsack {

	public static int getMaxValue(int[] w, int[] v, int bag) {
		return process(w, v, 0, 0, bag);
	}

        // 第一种尝试
	// 不变 ： w[] 重量数组  v[] 价值数组  bag 袋子的总载重
	// index... 最大价值
	// 0..index-1上做了货物的选择，使得你已经达到的重量是多少 alreadyW
	// 如果返回-1，认为没有方案
	// 如果不返回-1，认为返回的值是真实价值
	public static int process(int[] w, int[] v, int index, int alreadyW, int bag) {
	        // base case
		if (alreadyW > bag) {
			return -1;
		}
		// 重量没超
		if (index == w.length) {
			return 0;
		}
		// 当前不选择index的货物情况下，后续的价值
		// 无需传递当前index的重量，且p1就是总价值
		int p1 = process(w, v, index + 1, alreadyW, bag);
		// 当前选择了index的货物，把重量加上，继续向下递归
		int p2next = process(w, v, index + 1, alreadyW + w[index], bag);
		// p2表示要了当前货物之后总价值应该是后续价值加上当前价值
		int p2 = -1;
		if (p2next != -1) {
			p2 = v[index] + p2next;
		}
		return Math.max(p1, p2);

	}

	public static int maxValue(int[] w, int[] v, int bag) {
		return process(w, v, 0, bag);
	}

        // 第二种尝试。更经典
	// 只剩下rest的空间了，
	// index...货物自由选择，但是剩余空间不要小于0
	// 返回 index...货物能够获得的最大价值
	public static int process(int[] w, int[] v, int index, int rest) {
	        // base case 1 无效方案
		if (rest < 0) { 
			return -1;
		}
		// rest >=0。index来到终止位置，当前返回0价值
		// base case 2
		if (index == w.length) { 
			return 0;
		}
		// 有货也有空间。当前index不选择，得到p1总价值
		int p1 = process(w, v, index + 1, rest);
		int p2 = -1;、
		// 选择了index位置，剩余空间减去当前重量
		int p2Next = process(w, v, index + 1, rest - w[index]);
		// 选择index的总价值，是index...的价值加上个当前index的价值
		if(p2Next!=-1) {
			p2 = v[index] + p2Next;
		}
		return Math.max(p1, p2);
	}

	public static int dpWay(int[] w, int[] v, int bag) {
		int N = w.length;
		int[][] dp = new int[N + 1][bag + 1];
		for (int index = N - 1; index >= 0; index--) {
			for (int rest = 1; rest <= bag; rest++) {
				dp[index][rest] = dp[index + 1][rest];
				if (rest >= w[index]) {
					dp[index][rest] = Math.max(dp[index][rest], v[index] + dp[index + 1][rest - w[index]]);
				}
			}
		}
		return dp[0][bag];
	}

	public static void main(String[] args) {
		int[] weights = { 3, 2, 4, 7 };
		int[] values = { 5, 6, 3, 19 };
		int bag = 11;
		System.out.println(maxValue(weights, values, bag));
		System.out.println(dpWay(weights, values, bag));
	}

}

1.2.2 范围上的尝试模型

1.2.2.1 玩家抽取纸牌问题

给定一个整形数组arr，代表数值不同的纸牌排成一条线，玩家A和玩家B依次拿走每张纸牌。规定玩家A先拿，玩家B后拿，但是每个玩家每次只能拿走最左或最右的纸牌，玩家A和玩家B都绝顶聪明。请赶回最后获胜者的分数

绝顶聪明学术上的解释：双方玩家都会使得对方玩家在当前单独改变策略时，不会获得更大的收益。

package class11;

public class Code08_CardsInLine {

        // 主函数
	public static int win1(int[] arr) {
		if (arr == null || arr.length == 0) {
			return 0;
		}
		// 先手在0~length-1和后手在0~length-1上，谁分数大就是获胜者的分数
		return Math.max(
				f(arr, 0, arr.length - 1),
				s(arr, 0, arr.length - 1)
				);
	}

	// L....R 先手函数
	// F  S  L+1..R
	// L..R-1
	public static int f(int[] arr, int L, int R) {
	        // base case 当只剩一张牌，且是先手
		if (L == R) {
			return arr[L];
		}
		
		// 当前是先手，选择最好的
		return Math.max(
				arr[L] + s(arr, L + 1, R),
				arr[R] + s(arr, L, R - 1)
				);
	}

        // 后手函数
	// arr[L..R]
	public static int s(int[] arr, int L, int R) {
	        // base case 当只剩一张牌，且为后手
		if (L == R) {
			return 0;
		}
		
		// 当前是后手，好的被绝顶聪明的先手选走了
		// 相当于是先手的决策剩下的当前牌，留下最差的min
		return Math.min(
				f(arr, L + 1, R), // 对手挑了 arr[i]
				f(arr, L, R - 1)  // 对手挑了 arr[j]
				);
	}

	public static int win2(int[] arr) {
		if (arr == null || arr.length == 0) {
			return 0;
		}
		int N = arr.length;
		int[][] f = new int[N][N];
		int[][] s = new int[N][N];
		for(int i = 0; i < N;i++) {
			f[i][i] = arr[i];
		}
		// s[i][i] = 0;
		for(int i = 1; i < N;i++) {
			int L =0;
			int R =i;
			while(L < N && R < N) {
				
				f[L][R] = Math.max(
						arr[L] + s[L + 1][ R],
						arr[R] + s[L][R - 1]
						); 
				s[L][R] = Math.min(
						f[L + 1][R], // arr[i]
						f[L][R - 1]  // arr[j]
						); 
				
				L++;
				R++;
				
			}
		}
		return Math.max(f[0][N-1], s[0][N-1]);
	}

	public static void main(String[] args) {
		int[] arr = { 4,7,9,5,19,29,80,4 };
		// A 4 9
		// B 7 5
		System.out.println(win1(arr));
		System.out.println(win2(arr));

	}

}

1.2.2.2 N皇后问题

N皇后问题是指在N*N的棋盘上要摆N个皇后，要求任何两个皇后不同行，不同列，也不在同一条斜线上。

给定一个整数n，返回n皇后的摆法有多少种。

n=1，返回1

n=2或3,2皇后和3皇后问题无论怎么摆都不行，返回0

n=8，返回92

最优的N皇后的尝试方法，时间复杂度为N^N，但是process2是用位运算加速了常数项的时间

package class11;

public class Code09_NQueens {

	public static int num1(int n) {
		if (n < 1) {
			return 0;
		}
		// record[0] ?  record[1]  ?  record[2]
		// record[i] -> i行的皇后，放在了第几列
		int[] record = new int[n]; 
		return process1(0, record, n);
	}

	// 潜台词：record[0..i-1]的皇后，任何两个皇后一定都不共行、不共列，不共斜线
	// 目前来到了第i行，在i行准备放皇后
	// record[0..i-1]表示之前的行，放了的皇后位置
	// n代表整体一共有多少行  0~n-1行
	// 返回值是，摆完所有的皇后，合理的摆法有多少种
	// 尝试过程
	public static int process1(int i, int[] record, int n) {
		if (i == n) { // 终止行
			return 1;
		}
		// 没有到终止位置，还有皇后要摆
		int res = 0;
		// 当前行在i行，尝试i行所有的列  -> j
		for (int j = 0; j < n; j++) { 
			// 当前i行的皇后，放在j列，会不会和之前(0..i-1)的皇后，不共行共列共斜线，
			// 如果是，认为有效，当前可以摆在j列的位置
			// 如果不是，认为无效
			if (isValid(record, i, j)) {
			        // 当前存在i行的有效值为j列位置
				record[i] = j;
				res += process1(i + 1, record, n);
			}
		}
		return res;
	}

	// record[0..i-1]你需要看，record[i...]不需要看
	// 返回i行皇后，放在了j列，是否有效
	// a行b列的皇后，和c行d列的皇后会不会冲突，coding的条件是不共行
	// 共列的话b==d，共斜线的话|a-c|==|b-d|
	public static boolean isValid(int[] record, int i, int j) {
	        // 之前的某个k行的皇后	
		for (int k = 0; k < i; k++) { 
			// k, record[k]   i, j
			if (j == record[k] || Math.abs(record[k] - j) == Math.abs(i - k)) {
				return false;
			}
		}
		return true;
	}

	// 请不要超过32皇后问题
	public static int num2(int n) {
		if (n < 1 || n > 32) {
			return 0;
		}
		// 如果你是13皇后问题，limit 最右13个1，其他都是0
		int limit = n == 32 ? -1 : (1 << n) - 1;
		return process2(limit, 0, 0, 0);
	}

	// limit 划定了问题的规模 -> 固定
	
	// 用位运算加速常数项时间
	// colLim 列的限制，1的位置不能放皇后，0的位置可以
	// leftDiaLim 左斜线的限制，1的位置不能放皇后，0的位置可以
	// rightDiaLim 右斜线的限制，1的位置不能放皇后，0的位置可以
	public static int process2(
			int limit, 
			int colLim, 
			int leftDiaLim,
			int rightDiaLim) {
		if (colLim == limit) { // base case
			return 1;
		}
		// 所有可以放皇后的位置，都在pos上
		// colLim | leftDiaLim | rightDiaLim   -> 总限制
		// ~ (colLim | leftDiaLim | rightDiaLim) -> 左侧的一坨0干扰，右侧每个1，可尝试
	
		// 把左侧的去反后的一坨1，移除掉
		int pos = limit & ( ~(colLim | leftDiaLim | rightDiaLim) );
		int mostRightOne = 0;
		int res = 0;
		while (pos != 0) {
			// 提取出pos中，最右侧的1来，剩下位置都是0
			mostRightOne = pos & (~pos + 1);
			pos = pos - mostRightOne;
			res += process2(limit, 
					colLim | mostRightOne,
					(leftDiaLim | mostRightOne) << 1,
					(rightDiaLim | mostRightOne) >>> 1);
		}
		return res;
	}

	public static void main(String[] args) {
		int n = 15;

		long start = System.currentTimeMillis();
		System.out.println(num2(n));
		long end = System.currentTimeMillis();
		System.out.println("cost time: " + (end - start) + "ms");

		start = System.currentTimeMillis();
		System.out.println(num1(n));
		end = System.currentTimeMillis();
		System.out.println("cost time: " + (end - start) + "ms");

	}
}

1.3 如何尝试一件事？

1、有经验但是没有方法论

2、怎么判断一个尝试

3、难道尝试这件事真的只能拼天赋么，该怎么搞定面试？

4、动态规划是啥？好高端的样子，和尝试有什么关系？

请见下一章，暴力递归到动态规划的转移套路，解决面试中动态规划的问题。

本站文章除注明转载/出处外，均为作者原创或翻译，转载前请务必署名,转载请标明出处
最后编辑时间为: 2022/11/02 00:36