1. 搜索旋转排序数组
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
示例 3：
输入：nums = [1], target = 0
输出：-1
提示：
1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
nums 中的每个值都 独一无二
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-10^4 <= target <= 10^4
进阶：你可以设计一个时间复杂度为 O(log n) 的解决方案吗？
出处：
https://edu.csdn.net/practice/26740299
代码：
import java.util.*; class search { public static class Solution { public int search(int[] nums, int target) { int start = 0; int end = nums.length - 1; while (start <= end) { int mid = start + (end - start) / 2; if (nums[mid] == target) { return mid; } if (nums[start] <= nums[mid]) { if (target >= nums[start] && target <= nums[mid]) { end = mid - 1; } else { start = start + 1; } } if (nums[mid] <= nums[end]) { if (target >= nums[mid] && target <= nums[end]) { start = mid + 1; } else { end = end - 1; } } } return -1; } } public static void main(String[] args) { Solution s = new Solution(); int[] nums = {4,5,6,7,0,1,2}; System.out.println(s.search(nums, 0)); System.out.println(s.search(nums, 3)); } }
输出：
4
-1
2. 用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：
你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
进阶：
你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。
示例：
输入： ["MyQueue", "push", "push", "peek", "pop", "empty"] [[], [1], [2], [], [], []] 输出： [null, null, null, 1, 1, false] 解释： MyQueue myQueue = new MyQueue(); myQueue.push(1); // queue is: [1] myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue) myQueue.peek(); // return 1 myQueue.pop(); // return 1, queue is [2] myQueue.empty(); // return false
提示：
1 <= x <= 9- 最多调用
100次push、pop、peek和empty - 假设所有操作都是有效的 （例如，一个空的队列不会调用
pop或者peek操作）
出处：
https://edu.csdn.net/practice/26740300
代码：
class MyQueue { Stack<Integer> s1; Stack<Integer> s2; /** Initialize your data structure here. */ public MyQueue() { s1 = new Stack<Integer>(); s2 = new Stack<Integer>(); } /** Push element x to the back of queue. */ public void push(int x) { while (!s1.empty()) s2.push(s1.pop()); s1.push(x); while (!s2.empty()) s1.push(s2.pop()); return; } /** Removes the element from in front of queue and returns that element. */ public int pop() { return s1.pop(); } /** Get the front element. */ public int peek() { int ret = s1.pop(); s1.push(ret); return ret; } /** Returns whether the queue is empty. */ public boolean empty() { return s1.empty(); } } /** * Your MyQueue object will be instantiated and called as such: * MyQueue obj = new MyQueue(); * obj.push(x); * int param_2 = obj.pop(); * int param_3 = obj.peek(); * boolean param_4 = obj.empty(); */
输出：
略
3. x 的平方根
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
出处：
https://edu.csdn.net/practice/26740301
代码：
import java.util.*; class mySqrt { public static class Solution { public int mySqrt(int x) { int left = 0, right = 46340; while (left < right) { int mid = (left + right) / 2; if (mid * mid < x) left = mid + 1; else if (mid * mid > x) if ((mid - 1) * (mid - 1) <= x) return mid - 1; else right = mid - 1; else return mid; } if (left * left > x) return left - 1; return left; } } public static void main(String[] args) { Solution s = new Solution(); System.out.println(s.mySqrt(4)); System.out.println(s.mySqrt(8)); } }
输出：
2
2
