网站数据库建设方案,微应用和微网站的区别,建设企业网站费用,网站推广优化的方法力扣爆刷第111天之CodeTop100五连刷41-45 文章目录 力扣爆刷第111天之CodeTop100五连刷41-45一、232. 用栈实现队列二、4. 寻找两个正序数组的中位数三、31. 下一个排列四、69. x 的平方根五、8. 字符串转换整数 (atoi) 一、232. 用栈实现队列
题目链接#xff1a;https://le…力扣爆刷第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 {DequeInteger s1 new LinkedList();DequeInteger 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内完成两个数组的遍历避免ilen1 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 mn;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[i1]) 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, i1, 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 mid1;}}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;}
}
