招行科技笔试——合并区间，移动零

合并区间：

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

第一个点：比较器的重写：重写sort方法中的比较器

第二个点：这里是用 List去存储每个一维数组，最后去toArray转化回去

第三个点：合并区间的边界条件的判断：当前遍历的数组左区间和上一个数组的右区间的大小关系，如果大于，说明不需要合并，直接把当前遍历的数组add进去
否则，就需要比较当前数组和上一个数组的右区间，谁大取谁。
这里一个比较细的点就是：比较当前数组和上一个数组，不是当前数组和下一个数组（越界问题）

class Solution {
    public int[][] merge(int[][] intervals) {
        int n = intervals.length;
        if(n ==1 ) return intervals;
        Arrays.sort(intervals,new Comparator<int[]>(){
            public int compare(int[] o1 , int[] o2){
                // 升序
                return o1[0]-o2[0];
            } 
        });
        List<int[]> merged = new ArrayList<int[]>();
        for(int i = 0 ; i < n ; i ++){
            int L = intervals[i][0] , R = intervals[i][1];
            // 这里如果是比较后面一个数，即 intervals[i+1][1]，容易越界，数组嘛，所以和前面一个去比较
            // 同时，第一个数是判断过的，不用考虑前一个数不存在的情况（集合为空，直接放进去了）
            if(merged.size() == 0 || merged.get(merged.size()-1)[1]<L ){
                merged.add(new int[]{L,R});
            }else{
                merged.get(merged.size()-1)[1] =  Math.max(merged.get(merged.size()-1)[1],R);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }
}

移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

遍历一次：时间复杂度O(n)

public void moveZeroes(int[] nums) {
        int n = nums.length;
        if(n == 1) return ;
        int j = 0;
		for(int i=0;i<nums.length;i++) {
			//当前元素!=0，就把其交换到左边，等于0的交换到右边
			if(nums[i]!=0) {
				int tmp = nums[i];
				nums[i] = nums[j];
				nums[j] = tmp;
                j++;
			}
        }
    }

 遍历两次：时间复杂度O(n2)

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

（拓展）把零放最左边：

public void moveZeroes(int[] nums) {
        int n = nums.length;
        if(n==1) return;
        // i用来锁定第一个非0元素，j用来遍历数组
        int i = 0, j = 1;
        for(; j<n; j++){
            while(i==0){
                i++;
            }
            if(nums[j]==0){
                int temp = nums[j];
                nums[j] = nums[i];
                nums[i] = temp;
                
            }
        }
    }