给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。

示例 1：

输入：[3,2,3]
输出：[3]

示例 2：

输入：nums = [1]
输出：[1]

示例 3：

输入：[1,1,1,3,3,2,2,2]
输出：[1,2]

提示：

• 1 <= nums.length <= 5 * 104
• -109 <= nums[i] <= 109

进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。

简要思路就是：

1. 留3个位置记录数字和次数，
2. 挨个从头开始读，记录到步骤1的值里，如果数字相同累加，如果不同找个位子记下来
3. 当凑满3个不同的数字的时候，所有数字统计数都减一
4. 最后加进来的那个数字只有一个，所以最后那个数字个数变成了0，但是前面也是有可能有其他数字之前也只有一个，现在剩下0个的
5. 把0个的数字占的位子清空，继续添加下一个数字，重复上面的操作，直到最后
6. 剩下的两个数字中一定是有超过1/3的个数的
7. 回去再遍历一遍，统计下数量，（为了省下其他数字数量统计的空间也是煞费苦心了），最后超过1/3的留下

不好理解的话，我们换个角度。假如你有一根火腿肠，但是吃火腿肠的话有一个奇怪的习惯，需要把火腿肠分成N段，然后凑齐其中的3段，并排在一起，然后一起咬一块。

大概就。。这样？一根长度为9的火腿肠（毕竟比较好除以3）

此时你切成的N段火腿肠中，确保有一段是长度大于1/3的，那么思考一下，在每次都要拿着3段一起吃的情况下，即使你一直拿着那个大于1/3的那段，到最后这段也会生下来，毕竟到最后凑不出3段一起吃了。

或者换个思路，除去最长的大于1/3的那段，剩下的总和是小于2/3的，那么这个2/3再分成两段的，最极限情况下，要保持3段的情况，这边分出来的也都是小于1/3的。

最后剩余的情况
剩下的数字并不一定的大于1/3的，还是上面的长度9的举例子，比如分成了4，3，2这样的长度组合的，3个一起进行消除，最后剩下的长度的2，1，所以还得回去再统计一遍，不过再统计的时候只需要统计剩下的两个数字的，如果是剩下1个，必然是大于1/3的。

先决条件：需要保证给出的数组中一定存在数量超过1/3的数字

那么在理解了思想的情况下这个之后，如果是类似的题目就基本都是这个套路能解决了

代码

class Solution {


    /**
     * 初始化了边界外的数值，表示一个空位子
     */
    int[] nums = {1000000001,1000000001,1000000001};

    int[] countArr = {0,0,0};

    public List<Integer> majorityElement(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            processNum(nums[i]);
        }

        //数量重新归零
        countArr[0] = 0;
        countArr[1] = 0;
        countArr[2] = 0;

        for (int i = 0; i < nums.length; i++) {
            //统计剩下的数字出现的次数
            countArr[0] += this.nums[0] == nums[i]?1:0;
            countArr[1] += this.nums[1] == nums[i]?1:0;
            countArr[2] += this.nums[2] == nums[i]?1:0;
        }
        
        
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < this.nums.length; i++) {
            //留下大于1/3的
            if (this.nums[i] < 1000000001 && countArr[i] > nums.length/3){
                list.add(this.nums[i]);
            }
        }

        return list;
    }

    public void processNum(int num){
        //是否是新插入的
        boolean insertFlag = false;
        for (int i = 0; i < 3; i++) {
            //原有有这个数字
            if (nums[i] == num){
                //数量加1
                countArr[i]++;
                insertFlag = true;
            }
        }
        //是原来不存在的数字，
        if (!insertFlag){
            for (int i = 0; i < 3; i++) {
                //找个空位子给安排下，并计数为1
                if (nums[i] == 1000000001){
                    nums[i] = num;
                    countArr[i] = 1;
                    break;
                }
            }
        }
        //如果没凑到3个数字，就继续往里一个新数字来处理
        if (countArr[0]==0 || countArr[1] == 0 || countArr[2]==0){
            return;
        }
        //如果是3个不同的数字，每个数字减一，
        // 并把剩余0的那个数字占的位子空出来
        for (int i = 0; i < 3; i++) {
            countArr[i]--;
            if (countArr[i]==0){
                nums[i] = 1000000001;
            }
        }
    }



}

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

示例 1:

输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:

输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

提示:

• 2 <= n <= 58

一般分析

数字n的时候，我们把它分成两份

1. 小于n的k
2. n-k
   这两部分

以k部分固定，想要乘积最大的话，那么 n-k部分内部的乘积需要最大
那么我们就可以得到这样的分析

整数n的最大分段乘积为 k 乘以 [n-k]部分的最大分段乘积，从k从 2 取到 n-1,所有的情况都遍历一遍之后取最大值。

特殊情况

在执行用例过程中，发现一点特殊情况

1. 如果被分割出的一部分为2的话，应当直接取2， 显然 2比 1*1 更大，不是么
2. 当n=6的时候，按照之前的逻辑，因为dp[4] = 4,所以 2 * dp[4] = 8，这是得到的最大值，但是显然最大值应该是 3 * 3 = 9, 那么就存在一种情况下 n/2的平方才是最大值。

class Solution {
    public int integerBreak(int n) {
        if (n<=2){
            return 1;
        }
        int[] dp = new int[n+1];
        dp[1] = 1;
        dp[2] = 2;
        int i = 2;
        while (++i <= n){
            int j = 1;
            dp[i] = i * i / 4;
            while (++j <= i-1){
                dp[i] = Math.max(dp[i],j*dp[i-j]);
            }
        }
        return dp[n];
    }
}

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1：

输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。

示例 2：

输入：digits = [4,3,2,1]
输出：[4,3,2,2]
解释：输入数组表示数字 4321。

示例 3：

输入：digits = [0]
输出：[1]

提示：

• 1 <= digits.length <= 100
• 0 <= digits[i] <= 9

简单打卡收工

class Solution {
    public int[] plusOne(int[] digits) {
        //进位标识
        boolean flag = false;
        //从末位开始往前
        int idx = digits.length;
        while (--idx>=0){
            //原数字只可能是0-9所以加1的话小于等于10
            if (digits[idx]+1==10){
                digits[idx] = 0;
                //表示要进位
                flag = true;
            }else{
                //表示不用进位
                flag = false;
                digits[idx] +=1;
            }
            //如果不用进位的话就可以直接结束了
            if (!flag){
                return digits;
            }
        }
        //到第一个数字如果仍需要进位的话，那么情况只可能是9+1,99+1,999+1,9999+1这种的情况
        int[] res = new int[digits.length+1];
        res[0] = 1;
        return res;
    }
}

给你一个长度为 n 的整数数组，每次操作将会使 n - 1 个元素增加 1 。返回让数组所有元素相等的最小操作次数。

示例 1：

输入：nums = [1,2,3]
输出：3
解释：
只需要3次操作（注意每次操作会增加两个元素的值）：
[1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]

示例 2：

输入：nums = [1,1,1]
输出：0

提示：

• n == nums.length
• 1 <= nums.length <= 105
• -109 <= nums[i] <= 109
• 答案保证符合 32-bit 整数

凑合公式分析

分析一下，比如

假定最小值1，即使是有相同值的情况下，也认为第一个1是最小值
1 1 3 2
2 2 3 3
3 3 4 3
4 4 4 4

或者
1 2 2 2
2 3 3 2
3 4 3 3
4 4 4 4

可以看到最小值每次都要移动

1. 假定最终停下来的位置为target,最小值为min,移动次数为steps
2. 可以知道min + steps = target
3. 另外还有一个条件，每次移动n - 1，也就是nums.length - 1个
4. 最终状态下SUM( target - nums[i] ) = ( nums.length - 1 ) * steps 左边是每个数字移动的次数之和，右边也是总和
5. 愉快的求解方程时间，二元一次方程，带入消除，基本数学操作
6. 开始求解方程nums.length * target - SUM(nums) = (nums.length - 1) * steps，左边等价于现在这样，类似求面积那种
7. 继续换算，把之前的target带入得到
   nums.length * ( min + steps ) - SUM( nums ) = ( nums.length - 1 ) * steps
8. 两边同时减去相同的部分num.length * steps得到这样的方程
   nums.length * min - SUM(nums) = - steps
9. 翻转一下steps = SUM(nums) - nums.length * min;

class Solution {
    public int minMoves(int[] nums) {
        //target 最终停下来的值
        //min 最小值
        //steps 移动次数
        //min + steps = target
        //SUM(target - nums[i]) = (nums.length - 1) * steps
        //num.length * target - SUM(nums) = (nums.length - 1) * steps
        //num.length * ( min + steps) - SUM(nums) = (nums.length - 1) * steps
        //nums.length * min - SUM(nums) = - steps
        //steps = SUM(nums) - nums.length * min;




        int min = Integer.MAX_VALUE;
        int sum = 0;
        for(int num : nums){
            min = Math.min(min,num);
            sum += num;
        }
        return sum - nums.length * min;
    }
}

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3 

限制：

2 <= n <= 100000

哈希排序之类的解法都很好理解，不做赘述了，主要就讲下原地交换的解法

照旧，看图，主要还是利用的数组本身下标作为哈希来实现的，用数组代替哈希表来实现哈希是中常用的哈希优化方法，必要的话还是需要掌握下

第一行对应下标索引，从第二行开始为数字，每行表示每次操作的事项

第一行对应下标索引，从第二行开始为数字，每行表示每次操作的事项

• 从下标0开始，下标0上的数字为2，把下标0和下标2上的数字交换
• 此时下标0上的数字已经变为1了，继续和下标1上的数字交换
• 此时下标0上的数字已经变为3了，继续和下标3上的数字交换
• 此时下标0上的数字已经变为1了
• 往后依次查找，下标和上面的值是否相等
• 直到遇到下标4的时候，下标4上的值为2，那么和下标2进行交换，但是下标2上的值已经为2了，此时冲突发生，直接返回结果2

class Solution {
    public int findRepeatNumber(int[] nums) {
        int i = -1;
        while ( ++i < nums.length ){
            if(nums[i]==i)continue;
            while (nums[i]!=i){
                if (nums[nums[i]] == nums[i]){
                    return nums[i];
                }
                swap(nums,i,nums[i]);
            }
        }
        return -1;
    }

    public void swap(int[] nums,int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a am I"。

示例 1：

输入: "the sky is blue"
输出: "blue is sky the"

示例 2：

输入: "  hello world!  "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：

输入: "a good   example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

说明：

• 无空格字符构成一个单词。
• 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
• 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

注意：本题与主站 151 题相同：https://leetcode-cn.com/problems/reverse-words-in-a-string/

注意：此题对比原题有改动

【String本质其实是char[]】

class Solution {
    public String reverseLeftWords(String s, int n) {
        char[] arr = s.toCharArray();
        char[] newArr = new char[s.length()];
        System.arraycopy(arr,n,newArr,0,s.length()-n);
        System.arraycopy(arr,0,newArr,s.length()-n,n);
        return new String(newArr);
    }
}

嗯 双指针，其实一样的。

class Solution {
    public String reverseLeftWords(String s, int n) {
        char[] arr = s.toCharArray();
        char[] newArr = new char[s.length()];
        int idxNew = -1;
        int idx = n;

        while (++idxNew < s.length()){
            newArr[idxNew] = arr[idx];
            idx = idx==s.length()-1?0:idx+1;
        }

        return new String(newArr);
    }
}

还有一个

class Solution {
    public String reverseLeftWords(String s, int n) {
        char[] arr = s.toCharArray();
        char[] doubleArr = new char[s.length()*2];
        System.arraycopy(arr,0,doubleArr,0,s.length());
        System.arraycopy(arr,0,doubleArr,s.length(),s.length());
        char[] newArr = new char[s.length()];
        System.arraycopy(doubleArr,n,newArr,0,s.length());
        return new String(newArr);
    }
}