img

肖申克赫本

网络空间安全/java 后台开发/联邦学习/...

肖申克赫本

stay hungry,stay foolish~

欢迎来到我的个人站~

牛客网算法精进直播讲座（2017）---第一章

| 阅读：次 |本站总访问量次 | 本站访客数人

题目一

1、已知一个字符串都是由左括号(和右括号)组成，判断该字符串是否是有效的括号组合。
例子：
有效的括号组合:()(),(()),(()())
无效的括号组合:(,()),((),()(()
2、题目进阶： 已知一个字符串都是由左括号(和右括号)组成，返回最长有效括号子串的长度。

public class Problem_01_ParenthesesProblem {

	public static boolean isValid(String str) {
		if (str == null || str.equals("")) {
			return false;
		}
		char[] chas = str.toCharArray();
		int status = 0;
		for (int i = 0; i < chas.length; i++) {
			if (chas[i] != ')' && chas[i] != '(') {
				return false;
			}
			if (chas[i] == ')' && --status < 0) {
				return false;
			}
			if (chas[i] == '(') {
				status++;
			}
		}
		return status == 0;
	}

	public static int maxLength(String str) {
		if (str == null || str.equals("")) {
			return 0;
		}
		char[] chas = str.toCharArray();
		int[] dp = new int[chas.length];
		int pre = 0;
		int res = 0;
		for (int i = 1; i < chas.length; i++) {
			if (chas[i] == ')') {
				pre = i - dp[i - 1] - 1;
				if (pre >= 0 && chas[pre] == '(') {
					dp[i] = dp[i - 1] + 2 + (pre > 0 ? dp[pre - 1] : 0);
				}
			}
			res = Math.max(res, dp[i]);
		}
		return res;
	}

	public static void main(String[] args) {
		String str1 = "((())())";
		System.out.println(isValid(str1));
		System.out.println(maxLength(str1));

		String str2 = "(())(()(()))";
		System.out.println(isValid(str2));
		System.out.println(maxLength(str2));

		String str3 = "()(()()(";
		System.out.println(isValid(str3));
		System.out.println(maxLength(str3));

	}
}

题目二

1、给定一个数组，值全是正数，请返回累加和为给定值k的最长子数组长度。
2、给定一个数组，值可以为正、负和0，请返回累加和为给定值k的最长子数组长度。
3、给定一个数组，值可以为正、负和0，请返回累加和小于等于k的最长子数组长度。

public class Problem_02_LongestSubarrayLessSumAwesomeSolution {

// So great, first time, my book need modify, add this solution into book
public static int maxLengthAwesome(int[] arr, int k) {
	if (arr == null || arr.length == 0) {
		return 0;
	}
	int[] sums = new int[arr.length];
	HashMap<Integer, Integer> ends = new HashMap<Integer, Integer>();
	sums[arr.length - 1] = arr[arr.length - 1];
	ends.put(arr.length - 1, arr.length - 1);
	for (int i = arr.length - 2; i >= 0; i--) {
		if (sums[i + 1] < 0) {
			sums[i] = arr[i] + sums[i + 1];
			ends.put(i, ends.get(i + 1));
		} else {
			sums[i] = arr[i];
			ends.put(i, i);
		}
	}
	int end = 0;
	int sum = 0;
	int res = 0;
	for (int i = 0; i < arr.length; i++) {
		while (end < arr.length && sum + sums[end] <= k) {
			sum += sums[end];
			end = ends.get(end) + 1;
		}
		sum -= end > i ? arr[i] : 0;
		res = Math.max(res, end - i);
		end = Math.max(end, i + 1);
	}
	return res;
}

public static int maxLength(int[] arr, int k) {
	int[] h = new int[arr.length + 1];
	int sum = 0;
	h[0] = sum;
	for (int i = 0; i != arr.length; i++) {
		sum += arr[i];
		h[i + 1] = Math.max(sum, h[i]);
	}
	sum = 0;
	int res = 0;
	int pre = 0;
	int len = 0;
	for (int i = 0; i != arr.length; i++) {
		sum += arr[i];
		pre = getLessIndex(h, sum - k);
		len = pre == -1 ? 0 : i - pre + 1;
		res = Math.max(res, len);
	}
	return res;
}

public static int getLessIndex(int[] arr, int num) {
	int low = 0;
	int high = arr.length - 1;
	int mid = 0;
	int res = -1;
	while (low <= high) {
		mid = (low + high) / 2;
		if (arr[mid] >= num) {
			res = mid;
			high = mid - 1;
		} else {
			low = mid + 1;
		}
	}
	return res;
}

// for test
public static int[] generateRandomArray(int len, int maxValue) {
	int[] res = new int[len];
	for (int i = 0; i != res.length; i++) {
		res[i] = (int) (Math.random() * maxValue) - (maxValue / 3);
	}
	return res;
}

public static void main(String[] args) {
	for (int i = 0; i < 1000000; i++) {
		int[] arr = generateRandomArray(10, 20);
		int k = (int) (Math.random() * 20) - 5;
		if (maxLengthAwesome(arr, k) != maxLength(arr, k)) {
			System.out.println("oops!");
		}
	}

}
}





public class Problem_02_LongestSumSubArrayLength {

public static int maxLength(int[] arr, int k) {
	if (arr == null || arr.length == 0) {
		return 0;
	}
	HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
	map.put(0, -1); // important
	int len = 0;
	int sum = 0;
	for (int i = 0; i < arr.length; i++) {
		sum += arr[i];
		if (map.containsKey(sum - k)) {
			len = Math.max(i - map.get(sum - k), len);
		}
		if (!map.containsKey(sum)) {
			map.put(sum, i);
		}
	}
	return len;
}

public static int[] generateArray(int size) {
	int[] result = new int[size];
	for (int i = 0; i != size; i++) {
		result[i] = (int) (Math.random() * 11) - 5;
	}
	return result;
}

public static void printArray(int[] arr) {
	for (int i = 0; i != arr.length; i++) {
		System.out.print(arr[i] + " ");
	}
	System.out.println();
}

public static void main(String[] args) {
	int[] arr = generateArray(20);
	printArray(arr);
	System.out.println(maxLength(arr, 10));

}

}

题目三 纸牌博弈问题

有一排正数，玩家A和玩家B都可以看到。 每位玩家在拿走数字的时候，都只能从最左和最右的数中选择一个。
玩家A先拿，玩家B再拿，两人交替拿走所有的数字， 两人都力争自己拿到的数的总和比对方多。请返回最后获胜者的分数。
例如： 5,2,3,4
玩家A先拿，当前他只能拿走5或者4。 如果玩家A拿走5，那么剩下2，3，4。轮到玩家B，此时玩家B可以选择2或4中的一个，…
如果玩家A拿走4，那么剩下5，2，3。轮到玩家B，此时玩家B可以选择5或3中的一个

public class Problem_03_CardsInLine {

public static int win1(int[] arr) {
	if (arr == null || arr.length == 0) {
		return 0;
	}
	return Math.max(f(arr, 0, arr.length - 1), s(arr, 0, arr.length - 1));
}
//先发者
public static int f(int[] arr, int i, int j) {
	if (i == j) {
		return arr[i];
	}
	//两种决策，拿最左边或者最右边
	return Math.max(arr[i] + s(arr, i + 1, j), arr[j] + s(arr, i, j - 1));
}
//后发者
public static int s(int[] arr, int i, int j) {
//i==j时代表只有一个数据，被先发者拿走，值为0
	if (i == j) {
		return 0;
	}
	//假定两者绝对理想，后发者肯定是得到剩下的值的小的那一个
	return Math.min(f(arr, i + 1, j), f(arr, i, j - 1));
}

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

public static int win3(int[] arr) {
	if (arr == null || arr.length == 0) {
		return 0;
	}
	int sum = 0;
	for (int i = 0; i < arr.length; i++) {
		sum += arr[i];
	}
	int scores = p(arr, 0, arr.length - 1);
	return Math.max(sum - scores, scores);
}

public static int p(int[] arr, int i, int j) {
	if (i == j) {
		return arr[i];
	}
	if (i + 1 == j) {
		return Math.max(arr[i], arr[j]);
	}
	return Math.max(arr[i] + Math.min(p(arr, i + 2, j), p(arr, i + 1, j - 1)),
			arr[j] + Math.min(p(arr, i + 1, j - 1), p(arr, i, j - 2)));
}

public static int win4(int[] arr) {
	if (arr == null || arr.length == 0) {
		return 0;
	}
	if (arr.length == 1) {
		return arr[0];
	}
	if (arr.length == 2) {
		return Math.max(arr[0], arr[1]);
	}
	int sum = 0;
	for (int i = 0; i < arr.length; i++) {
		sum += arr[i];
	}
	int[][] dp = new int[arr.length][arr.length];
	for (int i = 0; i < arr.length - 1; i++) {
		dp[i][i] = arr[i];
		dp[i][i + 1] = Math.max(arr[i], arr[i + 1]);
	}
	dp[arr.length - 1][arr.length - 1] = arr[arr.length - 1];
	for (int k = 2; k < arr.length; k++) {
		for (int j = k; j < arr.length; j++) {
			int i = j - k;
			//i+1....j
			dp[i][j] = Math.max(arr[i] + Math.min(dp[i + 2][j], dp[i + 1][j - 1]),
					//i.....j-1
					arr[j] + Math.min(dp[i + 1][j - 1], dp[i][j - 2]));
		}
	}
	return Math.max(dp[0][arr.length - 1], sum - dp[0][arr.length - 1]);
}

public static int[] generateRondomArray() {
	int[] res = new int[(int) (Math.random() * 20) + 1];
	for (int i = 0; i < res.length; i++) {
		res[i] = (int) (Math.random() * 20) + 1;
	}
	return res;
}

public static void main(String[] args) {
	int testTime = 50000;
	boolean err = false;
	for (int i = 0; i < testTime; i++) {
		//对数器
		int[] arr = generateRondomArray();
		int r1 = win1(arr);
		int r2 = win2(arr);
		int r3 = win3(arr);
		int r4 = win4(arr);
		if (r1 != r2 || r1 != r3 || r1 != r4) {
			err = true;
		}
	}
	if (err) {
		System.out.println("2333333333");
	} else {
		System.out.println("6666666666");
	}
}

}

题目四：

设计一个针对全球的、访问量极大的id生成系统。
必须保证用户每次从该系统得到的id是唯一的，而且在概率上毫无碰撞可能。

待续。。。