每日刷题记录 (十)

文章目录

第一题: 剑指 Offer II 072. 求平方根

LeetCode: 剑指 Offer II 072. 求平方根

描述:
给定一个非负整数 x ，计算并返回 x 的平方根，即实现 int sqrt(int x) 函数。

正数的平方根有两个，只输出其中的正数平方根。

如果平方根不是整数，输出只保留整数的部分，小数部分将被舍去。

解题思路:

1. 这里使用二分法
2. 每次比较 mid * mid 是否小于等于 x - 如果当前小于等于x, 让left = mid+1;- 如果当前大于x, 让right = mid -1;
3. 最终返回left-1;

代码实现:

classSolution{publicintmySqrt(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] 

。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

解题思路:

1. 首先根据左边界进行排序.
2. 如果下一个范围的左边界, 大于当前范围的右边界, 就把当前记录的left和right加入到结果集中. 并标记当前left 为下一个范围的左边界
3. 让right标记, 当前右边界, 和下一个范围的右边界的最大值,
4. 遍历结束返回结果集

代码实现:

classSolution{publicint[][]merge(int[][] intervals){// 先排序Arrays.sort(intervals,(o1,o2)->o1[0]-o2[0]);List<int[]> res =newArrayList<>();// 先记录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(newint[]{left,right});
                left = intervals[i][0];}// 记录最大右边界位置
            right =Math.max(intervals[i][1],right);}// 这里还需要添加一次, 最后一次没有加入进去
        res.add(newint[]{left,right});int[][] ans =newint[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中, 由于是按坐标来添加的, 所以自动就是排序的.

代码实现:

classSolution{publicint[]relativeSortArray(int[] arr1,int[] arr2){// 这里使用tmp数组来记录每个元素出现次数int[] tmp =newint[1001];for(int val : arr1){
            tmp[val]++;}int index =0;int[] res =newint[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 个不同的元素。

解题思路:

1. 这里使用优先级队列. 创建一个大小为k的小根堆.
2. 当队列大小小于k的时候, 直接入堆
3. 当队列大小大于等于k的时候, 比较元素和堆顶元素的大小. - 当元素大于堆顶元素的时候, 出堆顶元素. 然后将该元素入堆

代码实现:

classSolution{publicintfindKthLargest(int[] nums,int k){PriorityQueue<Integer> pq =newPriorityQueue<>(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”）的时间列表，找出列表中任意两个时间的最小时间差并以分钟数表示。

解题思路:

1. 首先将时间字符串转化成分钟时间
2. 然后进行排序,
3. 这里注意, 00:01 和 23:59, 的时间差, 会被省略掉, 解决办法 就是让最小的时间加上24*60.
4. 然后俩俩进行计算时间差, 记录最小时间差

代码实现:

classSolution{publicintfindMinDifference(List<String> timePoints){List<Integer> list =newArrayList<>();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;}publicintgetMin(String str){String[] time = str.split(":");returnInteger.parseInt(time[0])*60+Integer.parseInt(time[1]);}}

第六题: 剑指 Offer II 034. 外星语言是否排序

LeetCode: 剑指 Offer II 034. 外星语言是否排序

描述:
某种外星语也使用英文小写字母，但可能顺序 order 不同。字母表的顺序（order）是一些小写字母的排列。

给定一组用外星语书写的单词 words，以及其字母表的顺序 order，只有当给定的单词在这种外星语中按字典序排列时，返回 true；否则，返回 false。

解题思路:

1. 根据order字符串出现的顺序, 用一个数组arr来记录.
2. 两两字符串进行比较, 首先比较每个位置元素的出现顺序 - 如果left<rigth, 表示符合条件, 继续进行下两个字符串的比较- 如果left>right, 直接不符合条件返回false- 如果前面字符串都相等, 例如 ww 和 www, 那么比较两个字符串的长度.

代码实现:

classSolution{publicbooleanisAlienSorted(String[] words,String order){int[] arr =newint[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;}elseif(left > right){returnfalse;}}if(flg){if(words[i-1].length()> words[i].length()){returnfalse;}}}returntrue;}}