力扣爆刷第111天之CodeTop100五连刷41-45
文章目录
- 力扣爆刷第111天之CodeTop100五连刷41-45
- 一、232. 用栈实现队列
- 二、4. 寻找两个正序数组的中位数
- 三、31. 下一个排列
- 四、69. x 的平方根
- 五、8. 字符串转换整数 (atoi)
一、232. 用栈实现队列
题目链接:https://leetcode.cn/problems/implement-queue-using-stacks/description/
思路:用两个栈来模拟队列,分别为s1和s2,入队只往s1加,出队,s2不空,s2出,s2空了把s1的全部出栈然后再压入s2中,再出队。
class MyQueue {
Deque<Integer> s1 = new LinkedList<>();
Deque<Integer> s2 = new LinkedList<>();
public MyQueue() {
}
public void push(int x) {
s1.push(x);
}
public int pop() {
if(!s2.isEmpty()) {
return s2.pop();
}
while(!s1.isEmpty()) {
s2.push(s1.pop());
}
return s2.pop();
}
public int peek() {
if(!s2.isEmpty()) {
return s2.peek();
}
while(!s1.isEmpty()) {
s2.push(s1.pop());
}
return s2.peek();
}
public boolean empty() {
return s1.isEmpty() && s2.isEmpty();
}
}
二、4. 寻找两个正序数组的中位数
题目链接:https://leetcode.cn/problems/median-of-two-sorted-arrays/description/
思路:类似于归并排序,但我们只需要归并到一半即可,然后控制条件在一个while内完成两个数组的遍历,避免i<len1 && j < len2的情况,这样需要遍历多次,外加多次判断。
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int left = 0, right = 0;
int i = 0, j = 0, m = nums1.length, n = nums2.length, len = m+n;
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 == 1) {
return right;
}else{
return (left + right) / 2.0;
}
}
}
三、31. 下一个排列
题目链接:https://leetcode.cn/problems/next-permutation/description/
思路:求下一个排列,要求下一个排列是所有排列结果中,比自己大的当中的,最小的那个。解题原理很简单,类似于折线图,
这个是我简单画的一个图,可以理解为一个折线图,要寻找下一个排列,我们只需要从右边开始往左找,找到第一个小于自己的值,这个值需要由右侧第一个大于他的值进行交换,然后右侧是降序的,只需要翻转即可正序。思想非常简单,4就是下一个排列与上一个排列不同的开头位置,与2交换后,只需要把5,3,2排列即可。
class Solution {
public void nextPermutation(int[] nums) {
if(nums.length == 1) return ;
int i = nums.length-2;
while(i >= 0 && nums[i] >= nums[i+1]) i--;
if(i >= 0) {
for(int j = nums.length-1; j > i; j--) {
if(nums[j] > nums[i]) {
swap(nums, i, j);
break;
}
}
}
reverse(nums, i+1, nums.length-1);
}
void swap(int[] nums, int x, int y) {
int t = nums[x];
nums[x] = nums[y];
nums[y] = t;
}
void reverse(int[] nums, int x, int y) {
while(x < y) {
swap(nums, x, y);
x++;
y--;
}
}
}
四、69. x 的平方根
题目链接:https://leetcode.cn/problems/sqrtx/description/
思路:利用二分法进行查找。
class Solution {
public int mySqrt(int x) {
if(x < 2) return x;
int left = 1, right = x/2;
while(left <= right) {
int mid = left + (right - left) / 2;
if(mid > (x/mid)) {
right = mid-1;
}else{
left = mid+1;
}
}
return right;
}
}
五、8. 字符串转换整数 (atoi)
题目链接:https://leetcode.cn/problems/string-to-integer-atoi/description/
思路:先去除前置空格,然后判断符号位,然后就是对于越界的判断,2的31次方减一就是Integer.MAX_VALUE,可以利用这个来判断是否越界。
class Solution {
public int myAtoi(String s) {
char[] c = s.toCharArray();
if(c.length == 0) return 0;
int res = 0, end = Integer.MAX_VALUE/10;
int i = 0, flag = 1, len = c.length;
while(i < len && c[i] == ' ') i++;
if(i == len) return 0;
if(c[i] == '-') flag = -1;
if(c[i] == '-' || c[i] == '+') i++;
for(int j = i; j < len; j++) {
if(c[j] < '0' || c[j] > '9') break;
if(res > end || res == end && c[j] > '7') return flag == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
res = res * 10 + (c[j] - '0');
}
return res * flag;
}
}