1. 搜索旋转排序数组 🌟🌟

2. 用栈实现队列 🌟

3. x 的平方根 🌟

🌟 每日一练刷题专栏 🌟

Golang每日一练专栏

Python每日一练专栏

C/C++每日一练专栏

Java每日一练专栏

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;elseright = mid - 1;elsereturn 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