文章目录
- 第一题: 剑指 Offer II 072. 求平方根
- 解题思路:
- 代码实现:
- 第二题: 剑指 Offer II 074. 合并区间
- 解题思路:
- 代码实现:
- 第三题: 剑指 Offer II 075. 数组相对排序
- 解题思路:
- 代码实现:
- 第四题: 剑指 Offer II 076. 数组中的第 k 大的数字
- 解题思路:
- 代码实现:
- 第五题: 剑指 Offer II 035. 最小时间差
- 解题思路:
- 代码实现:
- 第六题: 剑指 Offer II 034. 外星语言是否排序
- 解题思路:
- 代码实现:
第一题: 剑指 Offer II 072. 求平方根
LeetCode: 剑指 Offer II 072. 求平方根
描述:
给定一个非负整数 x ,计算并返回 x 的平方根,即实现 int sqrt(int x) 函数。
正数的平方根有两个,只输出其中的正数平方根。
如果平方根不是整数,输出只保留整数的部分,小数部分将被舍去。
解题思路:
- 这里使用二分法
- 每次比较 mid * mid 是否小于等于 x
- 如果当前小于等于x, 让left = mid+1;
- 如果当前大于x, 让right = mid -1;
- 最终返回left-1;
代码实现:
class Solution {public int mySqrt(int x) {int left = 0;int right = x;while(left <= right) {int mid = left + (right - left) / 2;if ((long)mid * mid <= x) {left = mid + 1;}else {right = mid - 1;}}return left-1;}}
第二题: 剑指 Offer II 074. 合并区间
LeetCode: 剑指 Offer II 074. 合并区间
描述:
以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi]
。请你合并所有重叠的区间,并返回一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间。
解题思路:
- 首先根据左边界进行排序.
- 如果下一个范围的左边界, 大于当前范围的右边界, 就把当前记录的left和right加入到结果集中. 并标记当前left 为下一个范围的左边界
- 让right标记, 当前右边界, 和下一个范围的右边界的最大值,
- 遍历结束返回结果集
代码实现:
class Solution {public int[][] merge(int[][] intervals) {// 先排序Arrays.sort(intervals,(o1,o2)->o1[0]-o2[0]);List<int[]> res = new ArrayList<>();// 先记录left和rightint left = intervals[0][0];int right = intervals[0][1];for(int i = 1; i < intervals.length; i++) {if (right < intervals[i][0]) {// 当下一范围的左边界大于前一范围的有边界的时候, 加入结果集, 并重新标记左边界的位置.res.add(new int[]{left,right});left = intervals[i][0];}// 记录最大右边界位置right = Math.max(intervals[i][1],right);}// 这里还需要添加一次, 最后一次没有加入进去res.add(new int[]{left,right});int[][] ans = new int[res.size()][];for(int i = 0; i < res.size(); i++) {ans[i] = res.get(i);}return ans;}}
第三题: 剑指 Offer II 075. 数组相对排序
LeetCode: 剑指 Offer II 075. 数组相对排序
描述:
给定两个数组,arr1
和 arr2
,
arr2
中的元素各不相同arr2
中的每个元素都出现在arr1
中
对 arr1
中的元素进行排序,使 arr1
中项的相对顺序和 arr2
中的相对顺序相同。未在 arr2
中出现过的元素需要按照升序放在 arr1
的末尾。
解题思路:
- 首先使用一个数组
tmp
, 记录arr1
中每一个元素出现的次数.- 再遍历
arr2
数组, 查看tmp
中该元素出现的次数, 然后添加到结果数组中res
- 再去遍历
tmp
. 查看tmp
中剩余的元素, 加入到res
中, 由于是按坐标来添加的, 所以自动就是排序的.
代码实现:
class Solution {public int[] relativeSortArray(int[] arr1, int[] arr2) {// 这里使用tmp数组来记录每个元素出现次数int[] tmp = new int[1001];for (int val : arr1) {tmp[val]++;}int index = 0;int[] res = new int[arr1.length];// 按照arr2的顺序, 将元素加入到结果数组, 出现几次加入几个for(int val : arr2) {while(tmp[val]-- != 0) {res[index++] = val;}}// 剩余的元素, 就是需要继续加的.for(int i = 0; i < 1001; i++) {if(tmp[i] != 0) {while(tmp[i]-- > 0) {res[index++] = i;}}}return res;}}
第四题: 剑指 Offer II 076. 数组中的第 k 大的数字
LeetCode: 剑指 Offer II 076. 数组中的第 k 大的数字
描述:
给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。
请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。
解题思路:
- 这里使用优先级队列. 创建一个大小为k的小根堆.
- 当队列大小小于k的时候, 直接入堆
- 当队列大小大于等于k的时候, 比较元素和堆顶元素的大小.
- 当元素大于堆顶元素的时候, 出堆顶元素. 然后将该元素入堆
代码实现:
class Solution {public int findKthLargest(int[] nums, int k) {PriorityQueue<Integer> pq = new PriorityQueue<>(k);for(int i = 0; i < k; i++) {pq.offer(nums[i]);}for(int i = k; i < nums.length; i++) {if(nums[i] > pq.peek()) {pq.poll();pq.offer(nums[i]);}}return pq.peek();}}
第五题: 剑指 Offer II 035. 最小时间差
LeetCode: 剑指 Offer II 035. 最小时间差
描述:
给定一个 24 小时制(小时:分钟 “HH:MM”)的时间列表,找出列表中任意两个时间的最小时间差并以分钟数表示。
解题思路:
- 首先将时间字符串转化成分钟时间
- 然后进行排序,
- 这里注意, 00:01 和 23:59, 的时间差, 会被省略掉, 解决办法 就是让最小的时间加上24*60.
- 然后俩俩进行计算时间差, 记录最小时间差
代码实现:
class Solution {public int findMinDifference(List<String> timePoints) {List<Integer> list = new ArrayList<>();for(int i = 0; i < timePoints.size(); i++) {list.add(getMin(timePoints.get(i)));}Collections.sort(list);list.add(list.get(0) + 24*60);int res = Integer.MAX_VALUE;for(int i = 1; i < list.size(); i++) {res = Math.min(res,list.get(i)-list.get(i-1));}return res;}public int getMin(String str) {String[] time = str.split(":");return Integer.parseInt(time[0])*60 +Integer.parseInt(time[1]);}}
第六题: 剑指 Offer II 034. 外星语言是否排序
LeetCode: 剑指 Offer II 034. 外星语言是否排序
描述:
某种外星语也使用英文小写字母,但可能顺序 order 不同。字母表的顺序(order)是一些小写字母的排列。
给定一组用外星语书写的单词 words,以及其字母表的顺序 order,只有当给定的单词在这种外星语中按字典序排列时,返回 true;否则,返回 false。
解题思路:
- 根据order字符串出现的顺序, 用一个数组
arr
来记录.- 两两字符串进行比较, 首先比较每个位置元素的出现顺序
- 如果left<rigth, 表示符合条件, 继续进行下两个字符串的比较
- 如果left>right, 直接不符合条件返回false
- 如果前面字符串都相等, 例如
ww
和www
, 那么比较两个字符串的长度.
代码实现:
class Solution {public boolean isAlienSorted(String[] words, String order) {int[] arr = new int[26];for(int i = 0; i < order.length(); i++) {arr[order.charAt(i)-'a'] = i;}for(int i = 1; i < words.length; i++) {boolean flg = true;for(int j = 0; j < words[i-1].length() && j < words[i].length() ; j++) {int left = arr[words[i-1].charAt(j)-'a'];int right = arr[words[i].charAt(j)-'a'];if (left < right) {flg = false;break;}else if (left > right) {return false;}}if (flg) {if (words[i-1].length() > words[i].length()){return false;}}}return true;}}