力扣爆刷第96天之hot100五连刷66-70
文章目录
一、33. 搜索旋转排序数组
题目链接：https://leetcode.cn/problems/search-in-rotated-sorted-array/description/?envType=study-plan-v2&envId=top-100-liked
思路：很简单，只需要先遍历找到数组旋转的中点，然后左右区间分别进行二分查找。
class Solution {
public int search(int[] nums, int target) {
if(nums.length == 1) return nums[0] == target ? 0 : -1;
int slow = 0;
for(int i = 1; i < nums.length; i++) {
if(nums[i] > nums[slow]) {
slow++;
}else{
int a = fun(nums, 0, slow, target);
int b = fun(nums, i, nums.length-1, target);
if(a != -1) return a;
if(b != -1) return b;
return -1;
}
}
return fun(nums, 0, nums.length-1, target);
}
int fun(int[] nums, int left, int right, int target) {
int a = left, b = right;
while(left <= right) {
int mid = left + (right - left) / 2;
if(nums[mid] == target) {
return mid;
} else if(nums[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
}
二、153. 寻找旋转排序数组中的最小值
题目链接：https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/description/?envType=study-plan-v2&envId=top-100-liked
思路：仔细看会发现不管旋转多少次，旋转之后都是下面的这种情况，即左边整体高于右边，那么要寻找最小值，只需要二分逐段缩小区间，至于如何缩小，请注意nums[right]一定小于nums[left]，求出中值后，如果nums[right]>nums[mid]就说明中值靠左，右边不要了，更新right=mid，如果nums[right]<=nums[mid]说明中值靠右，只有nums[mid]小于nums[right]才可能出现最小值，所以更新left=mid+1.
class Solution {
public int findMin(int[] nums) {
int left = 0, right = nums.length-1;
while(left < right) {
int mid = left + (right - left) / 2;
if(nums[mid] < nums[right]) {
right = mid;
}else {
left = mid + 1;
}
}
return nums[left];
}
}
三、4. 寻找两个正序数组的中位数
题目链接：https://leetcode.cn/problems/median-of-two-sorted-arrays/description/?envType=study-plan-v2&envId=top-100-liked
思路：本题只需要两个索引在两个数组上遍历，第三个索引作为计数使用，当数量达到中值时停止，期间使用两个变量记录中值附近的值，最后通过长度奇偶来确定结果。
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length, n = nums2.length, len = m + n;
int i = 0, j = 0;
int left = -1, right = -1;
for(int k = 0; k <= len / 2; k++) {
left = right;
if(i < m && (j >= n || nums1[i] < nums2[j])) {
right = nums1[i++];
}else {
right = nums2[j++];
}
}
if(len % 2 == 0) {
return (left + right) / 2.0;
}else{
return right;
}
}
}
四、20. 有效的括号
题目链接：https://leetcode.cn/problems/valid-parentheses/description/?envType=study-plan-v2&envId=top-100-liked
思路：反向思维，如果是左括号，不添加左括号，而是添加右括号，然后利用栈。
class Solution {
public boolean isValid(String s) {
Deque<Character> stack = new LinkedList<>();
for(int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if(c == '(') {
stack.push(')');
}else if(c == '[') {
stack.push(']');
}else if(c == '{') {
stack.push('}');
}else if(stack.isEmpty() || stack.peek() != c) {
return false;
}else{
stack.pop();
}
}
return stack.isEmpty();
}
}
五、155. 最小栈
题目链接：https://leetcode.cn/problems/min-stack/description/?envType=study-plan-v2&envId=top-100-liked
思路：最小栈要求一个常规栈，能够在常数时间内返回最小值，其实很简单，栈是先进后出的，只要要进入的值大于栈顶值，要进入的值就没必要记录了，一定不是最小值，所以，使用两个栈，一个栈正常进栈出栈，另一个栈只让最小值或者栈顶元素进栈。
class MinStack {
Deque<Integer> stack1 = new LinkedList<>();
Deque<Integer> stack2 = new LinkedList<>();
public MinStack() {
stack2.push(Integer.MAX_VALUE);
}
public void push(int val) {
stack1.push(val);
stack2.push(Math.min(stack2.peek(), val));
}
public void pop() {
stack1.pop();
stack2.pop();
}
public int top() {
return stack1.peek();
}
public int getMin() {
return stack2.peek();
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(val);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
