63. 搜索插入位置（二分查找/35）

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
假设：
1 <= nums.length <= $(10)^4$；
$(-10)^4$ <= nums[i] <= $(10)^4$；
nums 为 无重复元素 的 升序 排列数组；
$(-10)^4$ <= target <= $(10)^4$。
示例：输入: nums = [1,3,5,6], target = 5；输出: 2。

【分析】
解法：二分法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution{
	public int SearchInsert(int[] nums, int target){
		//定义两个指针
		int left = 0;
		int right = nums.Length-1;
		while(left<=right){
			int mid=left+(right-left)/2;//转整数
			if(nums[mid]==target){
				return mid;
			}else if(nums[mid]<target){
				left=mid+1;
			}else{
				right=mid-1;
			}
		}
		return left;
	}
}

69. 有效的括号（栈/20）

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
1.左括号必须用相同类型的右括号闭合。
2.左括号必须以正确的顺序闭合。
3.每个右括号都有一个对应的相同类型的左括号。
假设：
1 <= s.length <= $(10)^4$；
s 仅由括号 ‘()[]{}’ 组成。
示例：输入：s = “(]”；输出：false。

【分析】
解法：使用栈数据结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution{
	public bool IsValid(string s){
		Stack<char> stack=new Stack<char>();
		Dictionary<char,char> map=new Dictionary<char,char>(){
			{')','('},
			{'}','{'},
			{']','['}
		};
		
		foreach(char c in s){
			if(c=='(' || c=='{' || c=='['){
				stack.Push(c);
			}else if(c==')' || c=='}' || c==']'){
				if(stack.Count==0 || stack.Pop()!=map[c]){//或条件：第一个条件判断为true即返回false出去，第一个条件判断为false则走第二个条件，第二个条件要Pop也必然stack.Count!=0，第二个条件判断的同时也是执行stack.Pop()。
					return false;
				}
			}
		}
		return stack.Count==0;
	}
}