#yyds干货盘点# LeetCode刷题集161 - 170

2021年11月24日 阅读数:4
这篇文章主要向大家介绍#yyds干货盘点# LeetCode刷题集161 - 170,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

博主私藏的LeetCode刷题集合
有些较难的问题都有思路和注释数组

162. 寻找峰值

峰值元素是指其值大于左右相邻值的元素。markdown

给定一个输入数组 nums,其中 nums[i] ≠ nums[i+1],找到峰值元素并返回其索引。app

数组可能包含多个峰值,在这种状况下,返回任何一个峰值所在位置便可。ide

你能够假设 nums[-1] = nums[n] = -∞。函数

示例 1:ui

输入: nums = [1,2,3,1]
输出: 2
解释: 3 是峰值元素,你的函数应该返回其索引 2。
示例 2:code

输入: nums = [1,2,1,3,5,6,4]
输出: 1 或 5
解释: 你的函数能够返回索引 1,其峰值元素为 2;
或者返回索引 5, 其峰值元素为 6。
说明:排序

你的解法应该是 O(logN) 时间复杂度的。索引

class Solution {
    // 找到峰值
    // 左右都是负无穷
    // 思路:二分
    public int findPeakElement(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        int mid = 0;
        while(left < right){
            mid = left + (right - left)/2;
            if(mid == 0 && nums[mid] > nums[mid+1] ||
                mid == nums.length - 1 && nums[mid] > nums[mid-1] || 
                nums[mid] > nums[mid+1] && nums[mid] > nums[mid-1]){
                return mid;
            }
            if(nums[mid] > nums[mid+1]){ // 左边确定有峰值
                right = mid;
            }else{
                left = mid + 1;
            }
        }
        return left;
    }
}

164. 最大间距

给定一个无序的数组,找出数组在排序以后,相邻元素之间最大的差值。ci

若是数组元素个数小于 2,则返回 0。

示例 1:

输入: [3,6,9,1]
输出: 3
解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。
示例 2:

输入: [10]
输出: 0
解释: 数组元素个数小于 2,所以返回 0。
说明:

你能够假设数组中全部元素都是非负整数,且数值在 32 位有符号整数范围内。
请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。

class Solution {
  public int maximumGap(int[] nums) {
        if(nums==null||nums.length<2)
            return 0;
        double min=nums[0];
        double max=nums[0];
        for(int i=0;i<nums.length;i++){       //遍历全部元素,找到最大值和最小值
            min = nums[i]<min ? nums[i]:min;
            max = nums[i]>max ? nums[i]:max;
        }
        if(min==max)
            return 0;
        Bucket[] buckets=new Bucket[nums.length];
        int gap=(int)Math.ceil((max-min)/(nums.length-1));      //计算桶的容量
        for(int i=0;i<nums.length;i++){                         //遍历每一个元素,计算该元素应该放置的桶的位置,将元素放入桶中,更新桶的最大值和最小值
            int index=getBucketIndex((int)min,nums[i],gap);
            putInBucket(buckets,nums[i],index);
        }
        int maxGap=buckets[0].max-buckets[0].min;
        int pre=buckets[0].max;
        for(int i=1;i<buckets.length;i++){                   //遍历全部桶,计算最大间距(桶间间距)
            if(buckets[i]!=null){
                if((buckets[i].min-pre)>maxGap){
                    maxGap=buckets[i].min-pre;
                }
                pre=buckets[i].max;
            }
        }
        return maxGap;
    }
    //内部类 桶
    class Bucket{
        int max=0;
        int min=0;
        boolean hasNum=false;
    }
    //根据元素的数值计算该元素应该在哪一个桶中
    public int getBucketIndex(int min,int num,int gap){
        return (int)(num-min)/gap;
    }
    //将元素放入桶种,更新桶的最大值和最小值
    public void putInBucket(Bucket[] buckets,int num,int index){
        if(buckets[index]==null){
            buckets[index]=new Bucket();
            buckets[index].hasNum=true;
            buckets[index].max=num;
            buckets[index].min=num;
        }
        if(num>buckets[index].max)
            buckets[index].max=num;
        if(num<buckets[index].min)
            buckets[index].min=num;
    }
}

165. 比较版本号

比较两个版本号 version1 和 version2。
若是 version1 > version2 返回 1,若是 version1 < version2 返回 -1, 除此以外返回 0。

你能够假设版本字符串非空,而且只包含数字和 . 字符。

. 字符不表明小数点,而是用于分隔数字序列。

例如,2.5 不是“两个半”,也不是“差一半到三”,而是第二版中的第五个小版本。

你能够假设版本号的每一级的默认修订版号为 0。例如,版本号 3.4 的第一级(大版本)和第二级(小版本)修订号分别为 3 和 4。其第三级和第四级修订号均为 0。

示例 1:

输入: version1 = "0.1", version2 = "1.1"
输出: -1
示例 2:

输入: version1 = "1.0.1", version2 = "1"
输出: 1
示例 3:

输入: version1 = "7.5.2.4", version2 = "7.5.3"
输出: -1
示例 4:

输入:version1 = "1.01", version2 = "1.001"
输出:0
解释:忽略前导零,“01” 和 “001” 表示相同的数字 “1”。
示例 5:

输入:version1 = "1.0", version2 = "1.0.0"
输出:0
解释:version1 没有第三级修订号,这意味着它的第三级修订号默认为 “0”。

提示:

版本字符串由以点 (.) 分隔的数字字符串组成。这个数字字符串可能有前导零。
版本字符串不以点开始或结束,而且其中不会有两个连续的点。

class Solution {
    public int compareVersion(String version1, String version2) {
        String[] a1 = version1.split("\\.");
        String[] a2 = version2.split("\\.");

        for(int n = 0; n < Math.max(a1.length, a2.length); n++){
            int i = (n < a1.length ? Integer.valueOf(a1[n]) : 0);
            int j = (n < a2.length ? Integer.valueOf(a2[n]) : 0);
            if(i < j) return -1;
            else if(i > j) return 1;
        }
        return 0;  
    }
}

166. 分数到小数

给定两个整数,分别表示分数的分子 numerator 和分母 denominator,以字符串形式返回小数。

若是小数部分为循环小数,则将循环的部分括在括号内。

示例 1:

输入: numerator = 1, denominator = 2
输出: "0.5"
示例 2:

输入: numerator = 2, denominator = 1
输出: "2"
示例 3:

输入: numerator = 2, denominator = 3
输出: "0.(6)"

class Solution {
       public String fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0 || denominator == 0) return "0";
        int sign = 1;
        if (numerator > 0 && denominator < 0) sign = -1;
        long big = (long) numerator / (long) denominator;
        long small = numerator % denominator;
        StringBuilder result = new StringBuilder(String.valueOf(big));
        if (sign == -1) result.insert(0, "-");
        if (small != 0) {
            result.append(".");
            StringBuilder smallStr = new StringBuilder();
            Map<String, Integer> smallIndexs = new HashMap<String, Integer>();
            while (small != 0) {
                small *= 10;
                big = small / denominator;
                small = small % denominator;
                String str = small + "_" + big;
                if (smallIndexs.containsKey(str)) {
                    smallStr.append(")");
                    smallStr.insert(smallIndexs.get(str), "(");
                    break;
                } else {
                    smallIndexs.put(str, smallStr.length());
                    smallStr.append(Math.abs(big));
                }
            }
            result.append(smallStr);
        }
        return result.toString();
    }
}

167. 两数之和 II - 输入有序数组

给定一个已按照升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1 和 index2,其中 index1 必须小于 index2。

说明:

返回的下标值(index1 和 index2)不是从零开始的。
你能够假设每一个输入只对应惟一的答案,并且你不能够重复使用相同的元素。
示例:

输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。所以 index1 = 1, index2 = 2 。

class Solution {
     public int[] twoSum(int[] numbers, int target) {
        int[] res = new int[2];
        int low = 0;
        int high = numbers.length - 1;
        while (low < high) {
            if (numbers[low] + numbers[high] > target) {
                high--;
            }
            else if (numbers[low] + numbers[high] < target) {
                low++;
            }
            else {
                res[0] = low + 1;
                res[1] = high + 1;
                break;
            }
        }
        return res;
    }
}

168. Excel表列名称

给定一个正整数,返回它在 Excel 表中相对应的列名称。

例如,

1 -> A
2 -> B
3 -> C
...
26 -> Z
27 -> AA
28 -> AB 
...

示例 1:

输入: 1
输出: "A"
示例 2:

输入: 28
输出: "AB"
示例 3:

输入: 701
输出: "ZY"

class Solution {
    public String convertToTitle(int n) {
if (n <= 0) {
            return "";
        }
        StringBuilder sb = new StringBuilder();
        while (n > 0) {
            n--;
            sb.append((char) (n % 26 + 'A'));

            n =n / 26;
        }
        return sb.reverse().toString();
    }
}

169. 多数元素

给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你能够假设数组是非空的,而且给定的数组老是存在多数元素。

示例 1:

输入: [3,2,3]
输出: 3
示例 2:

输入: [2,2,1,1,1,2,2]
输出: 2

class Solution {
      public int majorityElement(int[] nums) {
        int count = 1;
        int maj = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (maj == nums[i])
                count++;
            else {
                count--;
                if (count == 0) {
                    maj = nums[i + 1];
                }
            }
        }
        return maj;
    }
}