3月2日LeetCode刷题

# 跳跃游戏

55. 跳跃游戏

给定一个非负整数数组 nums
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
示例：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ，所以永远不可能到达最后一个下标。

贪心思路：找到一个下标，这个下标刚好可以到达最后下一个下标。

从下标 i 出发可达区间 (i, i + nums[i] ] ，当然， i < nums.length 。
前 n 个下标会有一个最大可达下标 max = max(max, i + nums[i])） 。
当 max >= nums.length - 1 时，这个数组的最后一个下标是可达的。
下标 i 不会超过最大可达下标： i <= max

	public boolean canJump(int[] nums) {
	int len = nums.length;
	int max = 0;
	for(int i = 0; i < len && i<=max; i++) {
	max = Math.max(nums[i] + i, max);
	if(max >= len-1) {
	return true;
	}
	}
	return false;
	}

# 最长有效括号

32. 最长有效括号

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

动态规划 + 双指针

max 记录最长括号子串括号数。
left 和 right 在遍历时记录左括号和右括号数。
当 right == left 时说明括号匹配，记录 max = Math.max(right,max) 。
right > left 说明子串中有括号匹配不了， left 和 right 置 0。

这时候就有一个问题：以上操作只能判断 ) 无法匹配的情况，如何解决 ( 无法匹配的情况？

可以反转字符串重复以上步骤

	public int longestValidParentheses(String s) {
	if (s == null \|\| "".equals(s)) {
	return 0;
	}
	int left = 0;
	int right = 0;
	int max = 0;
	for(Character c : s.toCharArray()) {
	if( c == '('){
	left++;
	} else {
	right++;
	}
	if(left == right) {
	max = Math.max(right,max);
	}else if(right > left) {
	right = 0;
	left = 0;
	}
	}
	left = 0;
	right = 0;
	// 翻转字符串再次操作
	for(Character c : new StringBuilder(s).reverse().toString().toCharArray()) {
	if( c == '('){
	left++;
	} else {
	right++;
	}
	if(left == right) {
	max = Math.max(left,max);
	// 反转后需要判断 left > right
	}else if(left > right) {
	right = 0;
	left = 0;
	}
	}
	return max << 1;
	}

# 最长公共前缀

14. 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 "" 。
输入：strs = ["flower","flow","flight"]
输出："fl"

边界条件太多，要判断。

	public String longestCommonPrefix(String[] strs) {
	// 长度为 0 直接返回
	if(strs.length == 0) {
	return "";
	}
	// 包含一个 “ ” 直接返回
	if(strs.length == 1 \|\| strs[0].equals("")){
	return strs[0];
	}
	String base = strs[0];
	int res = base.length();
	for(String str : strs) {
	if(str.equals(base)){
	continue;
	}
	// 有一个 " " 字符串或者两字符串第一个字母不相同直接返回
	if(str.equals("") \|\| str.charAt(0) != str.charAt(0)){
	return "";
	}
	int index = 0;
	int count = 0;
	while(index < base.length() && index < str.length()) {
	if(str.charAt(index) == base.charAt(index)){
	count++;
	index++;
	}else {
	break;
	}
	}
	res = Math.min(count,res);
	}
	return base.substring(0,res);
	}

# 两数组交集

349. 两个数组的交集

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是唯一的。我们可以 不考虑输出结果的顺序 。

直接用 HashSet 解决

	public int[] intersection(int[] nums1, int[] nums2) {
	HashSet<Integer> set1 = new HashSet<>();
	HashSet<Integer> set2 = new HashSet<>();
	for(int i : nums1) {
	set1.add(i);
	}
	for (int i : nums2){
	if(set1.contains(i)) {
	set2.add(i);
	}
	}
	int [] res = new int[set2.size()];
	int index = 0;
	for(int i : set2) {
	res[index++] = i;
	}
	return res;
	}

LeetCode 跳跃游戏最长有效括号两数组交集最长公共前缀贪心

# 跳跃游戏

# 最长有效括号

# 最长公共前缀

# 两数组交集

LeetCode刷题-LRU