前言

记录 LeetCode 刷题时遇到的部分使用独特算法的题目的题目，第二篇

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];
        }
    }
}

1352. 最后 K 个数的乘积

使用变量 len 记录当前列表数字个数，数组 pre 中 pre[i] 表示列表前 i 个数的乘积，pre[0] 置为 1

在添加 0 进入列表时重置 len 以及 pre 数组。这样，在 getProduct 时，如果 k 大于 len，就说明列表最后 k 个数一定至少包含一个 0 ，那么得到的 k 个数乘积一定为 0，直接返回 0；否则最后 k 个数的乘积就等于后 len 个数的乘积除以 len 个数中位于 k 个数之前的 len - k 个数的乘积，即 pre[len] / pre[len - k]

class ProductOfNumbers {
    int len;
    int[] pre;
    public ProductOfNumbers() {
        pre = new int[40001];
        pre[0] = 1;
        len = 0;
    }
    public void add(int num) {
        if (num == 0) len = 0;
        else{
            pre[++len] = num * pre[len - 1];
        }
    }
    
    public int getProduct(int k) {
        if (len < k) return 0;
        return pre[len] / pre[len - k];
    }
}

31. 下一个排列

参考题解，个人总结见代码注释

public void nextPermutation(int[] nums) {
    int len = nums.length;
    if(len == 1) return;
    int index = len - 1;
    while(index > 0){
    	//1. 从后往前找第一对严格升序的元素对，即nums[index - 1] < nums[index]
        if(nums[index - 1] < nums[index]){
            int last = len - 1;
            //2. 在[index,len)中从后往前找第一个大于nums[index - 1]的元素
            while(last >= index){
            	//3. 交换这个元素跟nums[index - 1]
                if(nums[last] > nums[index - 1]){
                    nums[last] ^= nums[index - 1];
                    nums[index - 1] ^= nums[last];
                    nums[last] ^= nums[index - 1];
                    break;
                }
                last--;
            }
            //4. 把index开始往后的区间排序
            Arrays.sort(nums,index,len);
            return;
        }
        index--;
    }
    //5. 找不到符合要求的升序元素对，说明整个数组为降序排序，也就是对应最大的排列，
    //那么下一个排列就是最小的排列，也就是整个数组升序排序
    Arrays.sort(nums);
}

556. 下一个更大元素 III

可以发现该题的目的跟上一道题 31.下一个排列 是相同的，所以可以使用相同的做法完成这道题，但如果将数转化为一个数组的话需要 O(k) 的空间复杂度，k 为 n 的位数

官方题解 中用了另外一种 O(1) 空间复杂度的方法，思路跟 31.下一个排列 一样，但是直接在 n 上进行操作。自己消化后复现代码，整体思路跟 31 题还是一样，为了跟 31 题保持一致，n 从高位到低位对应下标从小到大：

1. 从后往前找第一个升序对，即找到下标 index 满足 index - 1 位上的数小于 index 上的数：tmp % 10 即为最低位，tmp / 10 % 10 即为倒数第二低位，每次对 tmp 除以 10 直到 tmp % 10 > tmp / 10 % 10，此时 tmp % 10 即为 index 上的数，tmp / 10 % 10 即为 index - 1 上的数，然后把 tmp 除以 10，最低位即为 index - 1 位
2. 在 index 后(包括 index)，从后往前找到第一个大于 index - 1 位上的数 (tmp % 10) 的数：令 tmp2 = n，每次判断 tmp2 % 10 是否大于 tmp % 10，是的话 tmp2 的最低位即为从后往前第一个大于 index - 1 位上的数的数。然后将 tmp2 的最低位跟 tmp 的最低位交换
3. 最后将 index 开始后续的数升序排序，由于 index - 1 跟 index 上的数是 n 从后往前找到的第一个升序对，所以 index 往后的数都是降序的，直接翻转即可升序排序

public int nextGreaterElement(int n) {
    int tmp = n,count = 1; //count表示index-1(不包括index-1)后的位数
    for(;tmp >= 10 && tmp % 10 <= tmp / 10 % 10;tmp /= 10){
        count++;
    }
    tmp /= 10; //此时tmp为n除去index(包括index)后的位剩余的部分，即最低位为index-1
    if(tmp == 0) return -1;
    //tmp%10即为index-1;count表示从后往前第一个大于index-1的数的右边有多少位数（不包括这个数本身）
    int tmp2 = n,indexMinusOne = tmp % 10,count2 = 0; 
    while(tmp2 > 0 && tmp2 % 10 <= indexMinusOne){
        tmp2 /= 10;
        count2++;
    }
    //此时tmp2%10即为从后往前第一个大于index-1的数，将其与index-1上的数交换
    tmp += tmp2 % 10 - indexMinusOne;
    tmp2 += indexMinusOne - tmp2 % 10;
    count -= count2;
    //要反转index后的数，共count个数
    //后count2个数在n中，所以这里先反转后count2个数
    while(count2 > 0){
        tmp = tmp * 10 + n % 10;
        n /= 10;
        count2--;
    }
    //再将剩下的count - count2个数反转，这几个数在tmp2中而不是n，
    //因为从后往前第一个大于index - 1上的数的数已经改变了，而n自始至终未改变过
    while(count-- > 0){
        int originTmp = tmp;
        tmp = tmp * 10 + tmp2 % 10;
        //记录运算前的tmp值，计算后根据结果是否一致判断是否溢出
        if(tmp / 10 != originTmp) return -1; 
        tmp2 /= 10;
    }
    return tmp;
}

169. 多数元素

做法来自官方题解。算法名叫 Boyer-Moore 投票算法

假设我们正在进行一场投票，数组中的每个元素都是参选人。在投票过程中会去枚举每个元素让他们投票。当前所得票数最多的人视为候选人，记为 candidate，初始我们可以随便设置一个数，这并不影响最终结果；其当前所得票数记为 vote

那么，当轮到某个元素投票时，它的投票策略为：在正式投票之前，如果当前候选人的所得票数已为 0，那么该元素可以选择自己作为新的候选人。接下来正式投票，如果候选人就是自己，那么就让票数加一；否则让票数减一
最后得到的候选人就是数组中的众数，自然也就是本题所要的多数元素

可以这么理解：根据投票规则，每个人都会倾向于投正票给自己 (+1)，投负票给别人 (-1)，那么由于多数元素占的比例较多，那么它得到的票数自然应该会是最多的；同理，对于其它非众数来说，由于与他不同的元素较多，投给自己负票的人也更多，那么自己得到的票数应该会趋于负数

public int majorityElement(int[] nums) {
    int len = nums.length;
    int candidate = -1,vote = 0;
    for(int i : nums){
        if(vote == 0){
            candidate = i;
        }
        vote += i == candidate ? 1 : -1;
    }
    return candidate;
}

剑指 Offer 45. 把数组排成最小的数

定义如下的 排序规则：对于 nums[i] 和 nums[i + 1]，比较 nums[i] append nums[i + 1] 组成的字符串所代表的数字跟 nums[i + 1] append nums[i] 得到的字符串所代表的数字哪个更大，如果前者更大，那么 nums[i] 优先于 nums[i + 1]，反之 nums[i + 1] 优先于 nums[i]

按照这个排序对数组进行升序排序，再按顺序将每个元素 append 起来，得到的结果就是最小的数

class Solution {
    public String minNumber(int[] nums) {
        if(nums == null || nums.length == 0) return "";
        //先转化为字符串数组。如果还是使用整形数组的话，后续在排序比较的时候还是需要将整形数据转化为字符串进行append
        //尝试之后发现先转化为字符串的话耗时会更少
        String[] s = new String[nums.length];
        for(int i = 0;i < nums.length;i++){
            s[i] = String.valueOf(nums[i]);
        }
        //使用快排进行排序。也可以直接使用 Arrays.sort() 进行排序
        quickSort(s,0,s.length - 1);
        //使用 StringBuilder 把排序后的所有字符串append起来得到答案
        StringBuilder res = new StringBuilder();
        for(String str : s){
            res.append(str);
        }
        return res.toString();
    }
    public void quickSort(String[] s,int l,int r){
        if(l >= r){
            return;
        }
        /* 枢轴随机化的操作
        int pivotIndex = new Random().nextInt(r - l + 1) + l;
        if(pivotIndex != l && s[pivotIndex] != s[l]){
            swap(s,l,pivotIndex);
        }*/
        String pivot = s[l];
        int left = l,right = r;
        while(left < right){
        	//(pivot + s[right]).compareTo(s[right] + pivot) < 0，则pivot优先级低于right
            while(left < right && (pivot + s[right]).compareTo(s[right] + pivot) < 0) right--;
            while(left < right && (pivot + s[left]).compareTo(s[left] + pivot) >= 0) left++; 
            if(left < right){
                swap(s,left,right);
            }
        }
        s[l] = s[left];
        s[left] = pivot;
        quickSort(s,l,left - 1);
        quickSort(s,left + 1,r);
    }
    public void swap(String[] s,int l,int r){
        String tmp = s[l];
        s[l] = s[r];
        s[r] = tmp;
    }
}

179. 最大数

这道题跟上一道题 剑指 Offer 45. 把数组排成最小的数 刚好相反，思路一样，排序的时候改为优先级降序排序即可

public String largestNumber(int[] nums) {
    String[] str = new String[nums.length];
    for(int i = 0;i < nums.length;i++){
        str[i] = String.valueOf(nums[i]);
    }
    Arrays.sort(str,(a,b)->{
    	//条件成立说明a优先于b，那么按照降序排序应该返回-1否则返回1
        return (a + b).compareTo(b + a) > 0 ? -1 : 1;
    });
    StringBuilder sb = new StringBuilder();
    for(String s : str){
        sb.append(s);
    }
    int len = sb.length();
    int i = 0;
    //去除前导0
    while(i < len && sb.charAt(i) == '0'){
        i++;
    }
    String res = sb.substring(i);
    //res为去除前导0后的字符串，有可能原字符串都为0，那么去完之后就都剩空串了，此时应该返回0而不能直接返回空串
    return "".equals(res) ? "0" : res;
}