2022-8-31 每日一题-栈模拟-剑指offer-二分查找

946. 验证栈序列

给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。

 1 class Solution {
 2     public boolean validateStackSequences(int[] pushed, int[] popped) {
 3         Deque<Integer> stack=new ArrayDeque<>();
 4         int index=0;
 5         for (int x:pushed){
 6             stack.push(x);
 7             while (!stack.isEmpty()&&stack.peek()==popped[index]){
 8                 stack.pop();
 9                 index++;
10             }
11         }
12         return stack.isEmpty();
13     }
14 }

思路：用栈模拟，检测看对不对。

剑指 Offer II 070. 排序数组中只出现一次的数字

给定一个只包含整数的有序数组 nums ，每个元素都会出现两次，唯有一个数只会出现一次，请找出这个唯一的数字。

你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。

 1 class Solution {
 2     public int singleNonDuplicate(int[] nums) {
 3         int l=0,r=nums.length-1;
 4         while (l<r){
 5             int mid=(l+r)/2;
 6             if (mid==0||mid==nums.length) return nums[mid];
 7             if (mid%2==0){
 8                 if (nums[mid]==nums[mid-1]) r=mid-1;
 9                 else if (nums[mid]==nums[mid+1]) l=mid+1;
10                 else return nums[mid];
11             }else{
12                 if (nums[mid]==nums[mid-1]) l=mid+1;
13                 else if (nums[mid]==nums[mid+1]) r=mid-1;
14             }
15         }
16         return nums[l];
17     }
18 }

思路：二分查找的变种思路。