[数据结构与算法][LeetCode]-无特定算法的题目

前言

记录 LeetCode 刷题时遇到的部分不知道该归属于哪些算法的题目，很多都是根据规律，或者题目信息，或者一些比较巧妙的想法才能做出来

400. 第 N 位数字(找规律)

public int findNthDigit(int n) {
    // [1, 9]        共 9 * 1 位数字      9 * 1 * 1      9 * pow(10,0) * 1
    // [10, 99]      共 90 * 2 位数字     9 * 10 * 2     9 * pow(10,1) * 2
    // [100, 999]    共 900 * 3 位数字    9 * 100 * 3    9 * pow(10,2) * 3
    // [1000, 9999]  共 9000 * 4 位数字   9 * 1000 * 4   9 * pow(10,3) * 4
    // ......                                           9 * pow(10,n - 1) * n
    //由以上规律，根据n的值，可以算出它属于哪个区间 (一位数的区间还是二位数的区间还是...
    int len = 1;
    long tmp;
    while((tmp = 9 * (long)Math.pow(10,len - 1) * len) < (long)n){
        n -= tmp;
        len++;
    }
    //经过上面的计算后，len的值就表示第n位数是处于len位数区间中，那么这个区间中每个数都是len位，
    //通过剩下的n除以len向上取整就可以算出第n位数所在的是这个len位数区间中的第几个len位数
    //例如n=13，那么经过上面的计算后，len=2，n=4，4/2向上取整即为2，说明第n位数所在的是二位数区间中的
    //第2个数，即11
    int numCount = (int)Math.ceil((double)n / len);
    //begin为这个区间中的第一个数，len为2，那么begin为10，即Math.pow(10,len - 1)
    int begin = (int)Math.pow(10,len - 1);
    //根据begin跟numCount就可以算出具体第n位数所在的是哪个len位数，10 + 2 - 1 = 11
    begin += numCount - 1;
    //最后算出第n位数在其所在的len位数中属于第几位(从左往右数)。4-4/2*2刚好得到0，说明为len位数中的最低位，即第len位
    //如果不是0，就可以通过begin / (int)Math.pow(10,len - n) % 10取出第n位数
    n -= n / len * len;
    return n == 0 ? begin % 10 : begin / (int)Math.pow(10,len - n) % 10;
}

977.有序数组的平方(题目信息)

 /**
 *给你一个===按 非递减顺序 排序===的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
 * 有正有负，按非递减顺序，说明平方后赎罪内从左到右数值的大小应该是一个U形，两端数值大，中间数值小，所以可以从两端开始遍历，找到较大的就放入
 * 结果数组，要从右边开始放z
**/
public int[] sortedSquares(int[] nums) {
    int length = nums.length;
    if(length == 0){
        return null;
    }
    if(length == 1){
        return new int[]{nums[0] * nums[0]};
    }
    int left = 0,right = length - 1,temp = length - 1;
    int[] resultArray = new int[length];
    while (left < right){
        if(nums[left] * nums[left] >= nums[right] * nums[right]){
            resultArray[temp--] = nums[left] * nums[left];
            left++;
        }else{
            resultArray[temp--] = nums[right] * nums[right];
            right--;
        }
    }
    resultArray[temp] = nums[left] * nums[left];
    return resultArray;
}

189. 轮转数组(找规律)

首先，向后轮转的实际位数为 k % n。可以发现，轮转后的结果，一是原数组中的后 k % n 个数放到了前面；二是剩下的前面 n - (k % n) 个数按顺序向后移了 k % n 位
所以可以，先翻转整个数组，然后再分别将前 k % n 个数以及剩下的后面 n - ( k % n) 个数翻转

class Solution {
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }

    public void reverse(int[] nums, int start, int end) {
        while (start < end) {
        	//交换数字用三步异或进一步提高效率
            nums[start] ^= nums[end];
            nums[end] ^= nums[start];
            nums[start] ^= nums[end];
            start++;
            end--;
        }
    }
}

57. 插入区间

原有的每个区间都无重叠。插入区间插入后，原有区间跟他的关系为：在插入区间的左侧，在插入区间的右侧，跟插入区间有重叠部分。对于跟插入区间有重叠部分的区间，我们不用对其情况进行细分，因为不管区间是以怎样的形式与插入区间重叠，这些区间最终都应跟插入区间一起合并为一个大交集。而这个大交集的左边界就是这些包括插入区间在内的所有重叠区间的左边界的最小值，而大交集的右边界就是这些所有重叠区间的右边界的最大值
引入大交集后，所有的区间又可以分为这样的三类：在原来的插入区间的左侧的区间，在原来的插入区间右侧的区间，以及大交集
所以解题思路就是遍历 intervals 数组，找出所有在原来的插入区间的左侧的区间直接放到结果 list 中，一边维护更新大交集的左右边界，在找到第一个在原来的插入区间的右侧的区间时，就可以将大交集放入 list，再把剩下的在原来的插入区间右侧的区间全部加入 list 即可
还要注意的 case 是，插入区间就在原有所有区间的左侧或者就在原有所有区间的右侧

public int[][] insert(int[][] intervals, int[] newInterval) {
    int left = newInterval[0];
    int right = newInterval[1];
    boolean flag = false; //标记大交集是否已放入 list
    List<int[]> list = new ArrayList<>();
    for (int[] interval : intervals) {
        if (interval[0] > right) { //区间在大交集的右侧
            //此时 大交集如果还未放入，就要先把大交集放入，即遍历到第一个在大交集右侧的区间。以后再遍历到大交集右侧的区间时直接放入即可
            if (!flag) { 
                list.add(new int[]{left, right});
                flag = true;                    
            }
            list.add(interval);
        } else if (interval[1] < left) {//在大交集的左侧
            list.add(interval);
        } else {
            // 与插入区间有交集，计算它们的并集
            left = Math.min(left, interval[0]);
            right = Math.max(right, interval[1]);
        }
    }
    if (!flag) { //如果从头到尾大交集都没有被放入，说明插入区间在所有原来区间的右侧，此时的大交集只有插入区间本身。直接放入即可
        list.add(new int[]{left, right});
    }
    return list.toArray(new int[0][]);
}

164. 最大间距

参考该题解的解法二，自己整理如下：
首先，将整个数组排序，然后遍历一遍数组，就能找出最大间距。至于排序算法，平常用的都是O(nlogn)的算法，这里可以选用基数排序 (可以看这篇文章) 以实现O(n)的复杂度
接下来考虑另一种做法：
将数组按照区间分为多个部分 (每个区间称为一个桶或一个箱子) ，例如将[2,3,6,7,22,29,30,38]，按照每十个值为一个区间，得到如下四个桶：

然后得到每个桶内的最大最小值，可以计算出每两个桶之间的“间距”，即当前桶中最小值减去左边桶 (如果左边的桶中没有任何元素就忽略) 的最大值 (当前桶的最小值跟左边桶的最大值一定在原数组排序后数组中是连续的) ，然后比较得到这些“间距”中的最大间距。可惜这个最大间距并不是最终答案，因为我们到现在为止只考虑了两个桶之间的间距，还没有考虑每个桶中连续 (连续指的是在排序后数组中连续) 元素之间的差值
但如果可以保证每个桶中任意两个连续元素之间的差值一定不会大于两个桶的间距，不就可以不用再考虑每个桶中的元素而只考虑桶之间的间距即可，那怎么做到呢？
我们用变量interval来表示每个桶中最多可能有几个元素，(即每个区间的长度，区间中有多少个正整数) ，如上图中interval的值就为10，那么可以发现，每个桶中可能出现的最大间距是 interval - 1 ，如上图第一个桶中，如果只存放了0跟9，那么就会得到这个间距为9，那么要做到 “保证每个桶中任意两个连续元素之间的差值一定不会大于两个桶的间距” ，反过来就是做到至少有两个连续的桶，它们之间的间距一定要大于等于interval - 1，这样，所有这些桶的间距中最大的一个间距，一定会大于等于这个间距，也就是一定大于等于interval - 1
从上图可以看到，当至少有一个桶为空的时候，就能满足这一点，第二个桶为空，那么第三个桶跟第一个桶之间的间距至少都为20 - 9 = 11 ，即interval + 1
那么怎样保证至少有一个桶为空呢：鸽巢原理，当有n个元素要放入一些箱子中，如果箱子数大于n，那么就一定有箱子是空的。对于这道题，为了尽量减少桶的数量，可以把数组中的最小值跟最大值单独拿出来处理，所以一共有n - 2个元素，那么就设置n - 1个桶
最后一个问题就是每个桶中区间的选择，即每个桶的范围，先求出数组的最大最小值max以及min，那么每个桶的范围就是(max - min) / n - 1，算出来的可能不是整数，向上取整就可以
大致总结一下：

1. 求出最大最小值
2. 设置n - 1个桶，然后计算出每个桶的范围interval
3. 遍历数组，将元素放入桶然后计算更新当前桶中最大最小值 (当然不用真的放入)
4. 遍历桶，计算每两个连续桶的间距然后维护最大间距

public int maximumGap(int[] nums) {
   int n = nums.length;
    //根据题意，数组元素个数小于2返回0
    if (n <= 1) {
        return 0;
    }
    int min = nums[0];
    int max = nums[0];
    for (int i = 1; i < n; i++) {
    	//求最大最小值
        min = Math.min(nums[i], min);
        max = Math.max(nums[i], max);
    }
    //最大值最小值相等，说明数组中的元素都是相等的，自然最大间距为0
    if(max - min == 0) {
        return 0;
    }
    //箱子的个数为n - 1
    int bucketCount = n - 1;
    //算出每个箱子的范围，向上取整
    int interval = (int) Math.ceil((double)(max - min) / (bucketCount));
    //记录每个箱子里数字的最小值和最大值
    int[] bucketMin = new int[bucketCount];
    int[] bucketMax = new int[bucketCount];
    //最小值初始为Integer.MAX_VALUE
    Arrays.fill(bucketMin, Integer.MAX_VALUE);
    //最大值初始化为 -1
    Arrays.fill(bucketMax, -1);
    for (int i = 0; i < nums.length; i++) {
        //当前数字要放入的目标箱子的下标
        int index = (nums[i] - min) / interval;
        //最大数和最小数不需要考虑
        if(nums[i] == min || nums[i] == max) {
            continue;
        }
        //更新当前数字所在箱子的最小值和最大值
        bucketMin[index] = Math.min(nums[i], bucketMin[index]);
        bucketMax[index] = Math.max(nums[i], bucketMax[index]);
    }
    int maxGap = 0;
    //min 看做第-1个箱子的最大值
    int previousMax = min;
    //从第0个箱子开始计算，计算当前箱子的最小值与前一个箱子的最大值的差值
    for (int i = 0; i < bucketCount; i++) {
        //最大值是-1说明箱子中没有数字，直接跳过
        if (bucketMax[i] == -1) {
            continue;
        }
        //计算当前箱子的最小值减去前一个箱子的最大值的差值，然后与前面得到的最大差值比较，得到较大差值
        maxGap = Math.max(bucketMin[i] - previousMax, maxGap);
        previousMax = bucketMax[i];
    }
    //一开始数组的最大值没有放入箱子，所以额外计算它与最后一个桶的最大值的差值
    maxGap = Math.max(max - previousMax, maxGap);
    return maxGap;
}

1013. 将数组分成和相等的三个部分

假设数组的元素总和为 sum。根据题意，如果能将数组分成和相等的三个部分，说明每一部分的和都为 sum / 3

public boolean canThreePartsEqualSum(int[] arr) {
    int sum = 0;
    for(int i : arr){
        sum += i;
    }
    //如果 sum 不能被3整除就肯定不能满足题意
    if(sum % 3 != 0) return false;
    int oneThird = sum / 3;
    int len = arr.length,i = 0;
    int tmp = 0; //记录计算得到的数组部分和
    while(i < len){
        tmp += arr[i++];
        //计算得到第一个等于 sum / 3 的部分就作为第一部分
        if(tmp == oneThird) break;
    }
    //由于上面的循环中是i++，所以此时i指向的应该是第二部分的第一个元素，
    //为了数组能拆分成三部分，i此时至少应该指向数组中倒数第二个元素
    if(tmp != oneThird || i >= len - 1) return false;
    tmp = 0;
    while(i < len){
        tmp += arr[i];
        if(tmp == oneThird) break;
        i++;
    }
    //上面的循环把取值arr[i]跟i+1拆开，所以当循环跳出的时候i指向的应该是
    //第二部分的最后一个元素，那么为了能拆成三部分，i此时一样至少应该指向数组中倒数第二个元素
    if(tmp != oneThird || i >= len - 1) return false;
    return true;
}

48. 旋转图像

题解给了三种解法，不过我觉得下面这种深得我心：顺时针旋转图像其实就是将第 0 行变为第 n 列，第 1 行变为第 n - 1 列，…，第 n - 1行变为第 0 列。通过将整个图像水平翻转一次再沿着主对角线 (从左上角到右下角的对角线) 翻转一次就能得到相同的效果

public void rotate(int[][] matrix) {
    int n = matrix.length;
    //水平翻转
    for(int i = 0;i < n / 2;i++){
        for(int j = 0;j < n;j++){
            matrix[i][j] ^= matrix[n - 1 - i][j];
            matrix[n - 1 - i][j] ^= matrix[i][j];
            matrix[i][j] ^= matrix[n - 1 - i][j];
        }
    }
    //沿主对角线翻转
    for(int i = 0;i < n;i++){
        for(int j = i + 1;j < n;j++){
            matrix[i][j] ^= matrix[j][i];
            matrix[j][i] ^= matrix[i][j];
            matrix[i][j] ^= matrix[j][i];
        }
    }
}

856. 括号的分数

参考官方题解：只有 () 会对字符串 S 贡献实质的分数，其它的括号只会将分数乘二或者将分数累加。因此，我们可以找到每一个 () 对应的深度 x，它对应的得分即为 2^x，所以最终答案就是每一个 () 的得分之和

public int scoreOfParentheses(String S) {
        int ans = 0, dep = 0;
        int len = S.length();
        char[] c = S.toCharArray();
        for (int i = 0; i < len; ++i) {
            if (c[i] == '(') {
                dep++; //维护深度
            } else {
                dep--;
                if (c[i - 1] == '(') //遇到')'，判断前面是不是'('，即判断是否是 "()"，是则累加一份得分
                    ans += 1 << dep;
            }
        }
        return ans;
    }

134. 加油站

假设我们从下标 begin 的加油站出发，当前处于下标 i 的加油站的位置，每次要向下一个加油站出发时，先减掉 cost[i] 判断当前油量 oil 是否小于 0，如果小于 0 说明不能从 begin 开始；否则就可以继续往下一个加油站走。如果最后能走到 i 与 begin 相等，那就说明从 begin 开始可以走一周，返回 begin

如果在 i 的时候，oil = oil - cost[i] 发现此时 oil 小于 0，那么就不能从 begin 开始走，需要选下一个起点，那么下一个起点要选在哪呢？

选在 begin + 1？肯定是可以的，这就是两层循环的做法，枚举每一个下标 i，尝试从 i 开始是否能绕一周，不能就枚举 i + 1，直到枚举到一个有解的 i 返回 i，或者枚举完 n 个数都没有解就返回 -1

但是这并不是最好的做法。假设从 begin 开始，走到某个下标 tmp 的时候，想接着往下走，发现 oil = oil - cost[i] 小于 0，即走不到 tmp + 1 了，这时去更改 begin 为 begin + 1 是没有用的，因为既然能从 begin 走到 begin + 1，那么说明走到 begin + 1 时，要么油量有多余，要么油量刚好耗完，而如果直接从 begin + 1 开始走的话，就只是相当于是从 begin 走到 begin + 1 时油量刚好耗完，也就是说，从 begin 开始走对后续的贡献肯定是优于或等于从 begin + 1 开始走的

以此类推可以知道，如果从 begin 开始在 tmp 时走不到 tmp + 1 了，那应该从 tmp + 1 开始，即 begin = tmp + 1。所有 begin 跟 tmp 中间的位置都是可以直接不去考虑的，所以当已经走到了 n - 1 的位置或者已经走到了 begin 前面的位置时发现油量小于 0 了，就说明问题是没有解的，直接返回 -1

public int canCompleteCircuit(int[] gas, int[] cost) {
    int n = gas.length;
    int begin = 0;
    int i = 0;
    int oil = gas[begin];
    while(true){
        oil = oil - cost[i];
        if(oil < 0){
            if(i < begin || i == n - 1) return -1;
            begin = i == n - 1 ? 0 : i + 1;
            i = begin;
            oil = gas[begin];
        }else{
            i = i == n - 1 ? 0 : i + 1;
            if(i == begin) return begin;
            oil += gas[i];
        }
    }
}