独一无二的哈密瓜

独一无二的哈密瓜

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

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

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

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

如果平方根不是整数,输出只保留整数的部分,小数部分将被舍去。
每日刷题记录 (十)-LMLPHP

解题思路:

代码实现:

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] 。请你合并所有重叠的区间,并返回一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间。
每日刷题记录 (十)-LMLPHP

解题思路:

代码实现:

class Solution {
    public int[][] merge(int[][] intervals) {
    	// 先排序
        Arrays.sort(intervals,(o1,o2)->o1[0]-o2[0]);
        List<int[]> res = new ArrayList<>();
        // 先记录left和right
        int 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. 数组相对排序
描述:
给定两个数组,arr1arr2

  • arr2 中的元素各不相同
  • arr2 中的每个元素都出现在 arr1

arr1 中的元素进行排序,使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。

每日刷题记录 (十)-LMLPHP

解题思路:

代码实现:

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 个不同的元素。
每日刷题记录 (十)-LMLPHP

解题思路:

代码实现:

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”)的时间列表,找出列表中任意两个时间的最小时间差并以分钟数表示。
每日刷题记录 (十)-LMLPHP

解题思路:

代码实现:

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。
每日刷题记录 (十)-LMLPHP

解题思路:

代码实现:

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;
    }
}
07-01 19:28