LeetCode 数组

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

public int[] twoSum(int[] numbers, int target) {
    if(numbers==null||numbers.length<=0){
        return null;
    }
    int left=0,right=numbers.length-1;
    while(right>left){
        int sum=numbers[right]+numbers[left];
        if(sum==target){
            return new int[]{left+1,right+1};
        }if(sum<target){
            left++;
        }else{
            right--;
        }
    }
    return null;
}

输入：[1,8,6,2,5,4,8,3,7]
输出：49

public int maxArea(int[] height) {
        int len=height.length;
        if(len==0){
            return 0;
        }
        int max=Integer.MIN_VALUE;
        for(int i=0;i<len-1;i++){
            for(int j=i+1;j<len;j++){
                int minHight=height[i]>height[j]?height[j]:height[i];
                max=max>(j-i)*minHight ? max:(j-i)*minHight;
            }
        }
        return max;
 }

public int maxArea(int[] height) {
        int len=height.length;
        if(len==0){
            return 0;
        }
        int head=0,tail=len-1;
        int max=Integer.MIN_VALUE;
        while(head<len){
            tail=len-1; //开始改的时候这一句忘了加
            while(head!=tail){
                int minHight=height[tail]>height[head]?height[head]:height[tail];
                max=max>(tail-head)*minHight ? max:(tail-head)*minHight;
                if(height[head]<=height[tail]){
                    break;
                }else{
                    tail--;
                }
            }
            head++;
        }
        return max;
}

//update: 2020.4.18
public int maxArea(int[] height) {
    if(height==null || height.length<=0) return 0;
    int left=0,right=height.length-1;
    int max=0;
    while(left<right){
        max=Math.max((right-left)*Math.min(height[left],height[right]),max);
        //if(left<right){ 隐约记得之前也这样写过。没想到这次又在这里 WA 了
        if(height[left]<height[right]){
            left++;
        }else{
            right--;
        }
    }
    return max;
}

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

public static int trap(int []height){
    if (height==null || height.length<=0) {
        return 0;
    }
    int len=height.length;
    int[] leftMax=new int[len];
    leftMax[0]=height[0];
    int[] rightMax=new int[len];
    rightMax[len-1]=height[len-1];
    int res=0;
    //左右最大柱子包含当前柱子
    for (int i=1;i<len;i++) {
        leftMax[i]=Math.max(leftMax[i-1],height[i]);
    }
    for (int i=len-2;i>=0;i--) {
        rightMax[i]=Math.max(rightMax[i+1],height[i]);
    }
    for (int i=0;i<len;i++) {
        res+=Math.min(rightMax[i],leftMax[i])-height[i];
    }
    return res;
}

public static int trap(int []height){
    if (height==null || height.length<=0) {
        return 0;
    }
    int len=height.length;
    int leftMax=0,rightMax=0;
    int left=0,right=len-1,res=0;
    while(left<=right){
        leftMax=Math.max(leftMax,height[left]);
        rightMax=Math.max(rightMax,height[right]);
        //leftMax 小于 rightMax, 那么靠近 leftMax 的柱子 left 可以接的雨水就可以确定了
        if (leftMax<rightMax) {
            res+=leftMax-height[left]; 
            left++;
        }else{ //反之 leftMax 大于 rightMax, 那么考近 rightMax 的柱子 right 可以接的最多的雨水就可以 i 确定了
            res+=rightMax-height[right];
            right--;
        }
    }
    return res;
}

public static int trap5(int []height){
    //
    int n=height.length,idx=0,lefth=0,righth=0,area=0;
    for (int i=0;i<n;i++) idx=height[idx]<=height[i]?i:idx;
    for (int i=0;i<idx;i++){
        if(height[i]<lefth) area+=lefth-height[i]; 
        else lefth=height[i]; //更新最大值
    }
    for (int i=n-1;i>idx;i--){
        if(height[i]<righth) area+=righth-height[i]; 
        else righth=height[i]; //更新最大值
    }
    return area;
}

public static int trap6(int[] height) {
    if (height == null || height.length == 0) return 0;
    Deque<Integer> stack = new ArrayDeque<>(); //栈里面维护一个递减序列
    int res = 0;
    for (int i = 0; i < height.length; i++){
        while ( ! stack.isEmpty() && height[stack.peek()] < height[i]) { //当遍历的元素大于栈顶元素
            int tmp = stack.pop(); //栈顶弹出来
            if (stack.isEmpty()) break;
            res += (Math.min(height[i],height[stack.peek()]) - height[tmp]) * (i - stack.peek() - 1);
        }
        //维护递减序列
        stack.push(i);
    }
    return res;
}

例如，给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

public static List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> list = new ArrayList();
    Arrays.sort(nums);
    // 先排序  o(nlogn)
    int len = nums.length;
    if(nums == null || len < 3) return list;
    // 完备性
    for (int i = 0; i < len-2; i++) {
        if(nums[i]>0){
            //大于 0 了，后面的和加起来肯定>0 了
            break;
        }
        //遍历数组，相同的元素只需要遍历一遍，不然会重复
        if(i > 0 && nums[i] == nums[i-1]) continue;
        // 一次去重优化
        //当前元素的下一个元素。
        int L = i+1;
        //尾元素
        int R = len-1;
        while(L<R){
            int sum = nums[i] + nums[L] + nums[R];
            if(sum == 0){
                list.add(Arrays.asList(nums[i],nums[L],nums[R]));
                //-4 -1 -1 0 1 2
                while (L<R && nums[L] == nums[L+1]) L++;
                //二次去重优化
                while (L<R && nums[R] == nums[R-1]) R--;
                L++;
                R--;
            } else if (sum < 0){ //小于 0 所以要增大 L, 逼近 0 else R--;
                 L++;   
            } else R--; //大于 0 就减小 R
        }
    }
    return list;
}

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

public int threeSumClosest(int[] nums, int target) {
    int len=nums.length;
    if(nums==null||len<3) return 0;
    Arrays.sort(nums);
    int closest=nums[0]+nums[1]+nums[2];
    for (int i=0;i<len-2;i++) {
        if(i!=0&&nums[i]==nums[i-1])continue;
        //跳过重复元素提高效率
        int L=i+1;
        int R=len-1;
        while(L<R){
            int sum=nums[L]+nums[R]+nums[i];
            closest=Math.abs(closest-target)>Math.abs(sum-target)?sum:closest;
            if(sum==target){
                return target;
            } else if(sum>target){
                while(L<R && nums[R]==nums[R-1])R--;
                R--;
            } else{
                while(L<R && nums[L]==nums[L+1])L++;
                L++;
            }
        }
    }
    return closest;
}

给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

满足要求的四元组集合为：
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

public static List<List<Integer>> fourSum(int[] nums, int target) {
    List<List<Integer>> res=new ArrayList<>();
    Arrays.sort(nums);
    int n=nums.length;
    //0 0 -1 1
    for (int i=0;i<n-3;i++) {
        //这里我开始写的是和后一个比较，0，0，0，0 这种过不了
        if(i>0 && nums[i]==nums[i-1])continue;
        if (nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target) break;
        if (nums[i]+nums[n-1]+nums[n-2]+nums[n-3]<target) continue;
        for (int j=i+1;j<n-2;j++) {
            //同上
            if(j>i+1&&nums[j]==nums[j-1])continue;
            if (nums[i]+nums[j]+nums[j+2]+nums[j+1]>target) break;
            if (nums[i]+nums[j]+nums[n-2]+nums[n-1]<target) continue;
            int two=nums[i]+nums[j];
            //左右边界
            int left=j+1,right=n-1;
            while(left<right){
                if (target-two==nums[left]+nums[right]) {
                    res.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
                    //想清楚什么时候跳，放外面就错了
                    while(left<right && nums[left]==nums[left+1]){left++;};
                    while(left<right && nums[right]==nums[right-1]){right--;};
                    left++;
                    right--;
                }else if (target-two>nums[left]+nums[right]) {
                    left++;
                }else{
                    right--;
                }
            }
        }
    }
    return res;
}

给定数组 nums = [1,1,2], 

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 

你不需要考虑数组中超出新长度后面的元素。

给定 nums = [0,0,1,1,1,2,2,3,3,4],

函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

你不需要考虑数组中超出新长度后面的元素。

public int removeDuplicates(int[] nums) {
    if (nums.length == 0) return 0;
    int i = 0;
    for (int j = 1; j < nums.length; j++) {
        if (nums[j] != nums[i]) {
            nums[i++] = nums[j];
        }
    }
    return i + 1;
}

给定 nums = [1,1,1,2,2,3],

函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。

你不需要考虑数组中超出新长度后面的元素。

给定 nums = [0,0,1,1,1,1,2,3,3],

函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。

你不需要考虑数组中超出新长度后面的元素。

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度，它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

public int removeDuplicates(int[] nums) {
    int index=2;
    for (int i=2;i<nums.length;i++){
        if(nums[i]!=nums[i-1] || (nums[i]==nums[i-1] && nums[index-2]!=nums[index-1])){
            nums[index++]=nums[i];
        }
    }
    return index;
}

给定 nums = [3,2,2,3], val = 3,

函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。

你不需要考虑数组中超出新长度后面的元素。

给定 nums = [0,1,2,2,3,0,4,2], val = 2,

函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

注意这五个元素可为任意顺序。

你不需要考虑数组中超出新长度后面的元素。

public int removeElement(int[] nums, int val) {
    int i = 0;
    for (int j = 0; j < nums.length; j++) {
        if (nums[j] != val) {
            nums[i++] = nums[j];
        }
    }
    return i;
}

public int removeElement2(int[] nums, int val) {
    int i = 0;
    int n = nums.length;
    while (i < n) {
        if (nums[i] == val) {
            nums[i] = nums[--n];
        } else {
            i++;
        }
    }
    return n;
}

输入：[0,1,0,3,12]
输出：[1,3,12,0,0]

public void moveZeroes(int[] nums) {
    if(nums==null||nums.length<=1){
        return;
    }
    int index=0;
    for(int i=0;i<nums.length;i++){
        if(nums[i]!=0){
            nums[index++]=nums[i];
        }
    }
    for(int i=index;i<nums.length;i++){
        nums[i]=0;
    }
}

public void moveZeroes(int[] nums) {
    int m=0; //[0,m) 为非 0 元素
    for(int i=0;i<nums.length;i++){
        if(nums[i]!=0){
            if(i!=m){
                int temp=nums[i];
                nums[i]=nums[m];
                nums[m]=temp;   
            }
            m++;
        }
    }
}

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

public void nextPermutation(int[] nums) {
    int len=nums.length;
    if(nums==null||len<=1){
        return;
    }
    for (int i=len-2;i>=0;i--) {
        while(i>=0 &&nums[i]>=nums[i+1]){
            //找到第一个峰值左相邻的元素（从左到右）
            i--;
        }
        //逆序的，没有最大值
        if(i==-1){
            reverse(nums,0);
            return;
        }
        //找到峰值右边 [i+1 , len-1] 最后一个比 i 大的元素
        for (int j=len-1;j>i;j--) {
            if(nums[j]>nums[i]){
                swap(nums,j,i);
                reverse(nums,i+1);
                return;
            }
        }
    }
}

//翻转数组
private void reverse(int[] nums, int start) {
    for (int i=start,j=nums.length-1;i<j;i++,j--) {
        swap(nums,i,j);
    }
}

private  static void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

输入：12
输出：21

输入：21
输出：-1

public int nextGreaterElement(int n) {
    StringBuilder sb=new StringBuilder();
    while(n/10>0){
        sb.append(n%10);
        n/=10;
    }
    sb.append(n);
    System.out.println(sb);
    char[] nums=sb.reverse().toString().toCharArray();
    int len=nums.length;
    for (int i=len-1;i>0;i--) {
        if (nums[i]>nums[i-1]) { //逆序的峰值 i
            if (i==0) return -1; 
            for (int j=len-1;j>=i;j--) {
                if (nums[j]>nums[i-1]) {
                    swap(nums,j,i-1);
                    reverse(nums,i,len-1);
                    return Long.valueOf(new String(nums))>Integer.MAX_VALUE?-1:Integer.valueOf(new String(nums));
                }
            }
        }
    }
    return -1;
}

public void reverse(char[] nums,int begin,int end){
    for (int i=begin,j=end;i<j;i++,j--) {
        swap(nums,i,j);
    }
}

public void swap(char[] nums,int a,int b){
    char temp=nums[a];
    nums[a]=nums[b];
    nums[b]=temp;
}

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

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

public int majorityElement(int[] nums) {
    return majorityElement(nums,0,nums.length-1);
}

public int majorityElement(int[] nums,int lo,int hi) {
    if (lo==hi) {
        return nums[lo];
    }
    int mid=lo+(hi-lo)/2;
    int leftMode=majorityElement(nums,lo,mid);
    int rightMode=majorityElement(nums,mid+1,hi);
    if (leftMode==rightMode) {
        return rightMode;
    }
    return countMode(nums,lo,mid,leftMode)>countMode(nums,mid+1,hi,rightMode)?leftMode:rightMode;
}

public int countMode(int[] nums,int left,int right,int mode){
    int count=0;
    for (int i=left;i<=right;i++) {
        if (mode==nums[i]) {
            count++;
        }
    }
    return count;
}

public int majorityElement(int[] nums) {
    int sum=1;
    int res=nums[0]; 
    for (int i=1;i<nums.length;i++) {
        if (sum==0) {
            res=nums[i];
        }
        //将众数看做 1, 其他的看作-1, 最后和一定是大于 0 的
        if (res!=nums[i]) {
            sum--;
        }else{
            sum++;
        }
    }
    return res;
}

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

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

//update：2020.4.23 用 go 在 web 上随手写了一个，感觉比之前 java 写的哪个好理解
func majorityElement(nums []int) []int {
    var res []int
    //超过 n/3 的元素最多 2 个
    cand1:=-1 //设置成 nums 中不存在的值比较好，比如-1
    count1:=0
    cand2:=-1
    count2:=0
    for _,num:=range nums{
        if num==cand1{ //投 1
            count1++
        }else if num==cand2{ //投 2
            count2++
        }else { //都不投
            if count1==0 {
                cand1=num
                count1=1
            }else if count2==0{
                cand2=num
                count2=1
            }else{
                count1--
                count2--
            }
        }
    }
    temp1:=0
    temp2:=0
    for _,num:= range nums{
        if num==cand1{
            temp1++
        }
        if num==cand2{
            temp2++
        }
    }

    if temp1>len(nums)/3 {
        res=append(res,cand1)
    }
    if temp2>len(nums)/3 {
        res=append(res,cand2)
    }
    return res
}

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

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

输入：[7,8,9,11,12]
输出：1

public int firstMissingPositive(int[] nums) {
    if(nums==null||nums.length<=0){
        return 1;
    }
    for (int i=0;i<nums.length;++i){
        //将每个元素归位，我开始只有一层循环，那样会漏掉很多元素（可能被交换的元素后面也需要交换），这样的就是一次直接到位。
        while(nums[i]>=1&&nums[i]<=nums.length&&nums[nums[i]-1]!=nums[i])
        {
            int temp=nums[nums[i]-1];
            nums[nums[i]-1]=nums[i];
            nums[i]=temp;
        }
    }
    for (int i=0;i<nums.length;++i){
        if(nums[i]!=i+1)
            return i+1;
    }
    return nums.length+1;
}

func firstMissingPositive(nums []int) int {
    for i:=0;i<len(nums);i++{
        for nums[i]>0 && nums[i]<len(nums) && nums[i]!=i+1 && nums[nums[i]-1]!=nums[i]{
            nums[nums[i]-1],nums[i]=nums[i],nums[nums[i]-1]
        }
    }
    for i,n := range nums{
        if n!=i+1{
            return i+1
        }
    }
    return len(nums)+1
}

public int firstMissingPositive2(int[] nums) {
        if(nums==null||nums.length<=0){
            return 1;
        }
        int [] bucket=new int[nums.length];
        for(int i=0;i<nums.length;++i){
            if(nums[i]>0 && nums[i]<=nums.length){
                bucket[nums[i]-1]=1; //代表这个桶有元素了
            }
        }
        for(int i=0;i<bucket.length;++i){
            if(bucket[i]==0)
                return i+1;
        }
        return nums.length+1;
}

输入：
[4,3,2,7,8,2,3,1]

输出：
[2,3]

public List<Integer> findDuplicates(int[] nums) {
    for (int i=0;i<nums.length;i++) {
        while(nums[i]!=i+1 && nums[i]!=nums[nums[i]-1]){
            int temp=nums[nums[i]-1];
            nums[nums[i]-1]=nums[i];
            nums[i]=temp;
        }
    }
    List<Integer> res=new LinkedList<>();
    for (int i=0;i<nums.length;i++) {
        if (nums[i]!=i+1) {
            res.add(nums[i]);
        }
    }
    return res;
}