Leetcode连载 | 数组

class Solution {
    public void moveZeroes(int[] nums) {
        if (nums == null) {
            return;
        }
        //使用双指针i,j，用指针i遍历数组，用指针j记录非0元素的下标
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[j++] = nums[i];
            }
        }
        
        for (int i = j; i < nums.length; i++) {
            nums[i] = 0;
        }
    }
}

public int[][] matrixReshape(int[][] nums, int r, int c) {
        if (nums.length == 0 || (nums.length * nums[0].length) != (r * c)) {
            return nums;
        }

        int row = 0;
        int col = 0;
        int[][] res = new int[r][c];
        //当col==c-1时，矩阵换行
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums[0].length; j++) {
                res[row][col] = nums[i][j];
                if (col == c - 1) {
                    row++;
                    col = 0;
                }else {
                    col++;
                }
            }
        }
        return res;
    }

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int count = 0;
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 1) {
                count++;
            }else {
                max = Math.max(count, max);
                count = 0;
            }
        }
        return Math.max(count, max);
    }
}

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) {
            return false;
        }

        int row = 0;
        int col = matrix[0].length - 1;

        while(row < matrix.length && col >=0) {
            if (matrix[row][col] > target) {
                col -= 1;
            }else if (matrix[row][col] < target){
                row += 1;
            }else {
                return true;
            }
        }
        return false; 
    }
}

class Solution {
    //二分查找
    public int kthSmallest(int[][] matrix, int k) {
        int row = matrix.length;
        int col = matrix[0].length;
        int left = matrix[0][0];
        int right = matrix[row-1][col-1];
        while (left < right) {
            // 每次循环都保证第K小的数在start~end之间，当start==end，第k小的数就是start
            int mid = (left + right) / 2;
            // 找二维矩阵中<=mid的元素总个数
            int count = findNotBiggerThanMid(matrix, mid, row, col);
            if (count < k) {
                // 第k小的数在右半部分，且不包含mid
                left = mid + 1;
            }else {
                // 第k小的数在左半部分，可能包含mid
                right = mid;
            }
        }
        return right;
    }

    private int findNotBiggerThanMid(int[][] matrix, int mid, int row, int col) {
        // 以列为单位找，找到每一列最后一个<=mid的数即知道每一列有多少个数<=mid
        int i = 0;
        int j = col-1;
        int count = 0;
        while (i < row && j >=0) {
            if (matrix[i][j] <= mid) {
                count += j+1;
                i += 1;
            }else {
                j -= 1;
            }
        }
        return count;
    }
}

class Solution {
    //哈希表方法
    public int[] findErrorNums(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        int dup = -1;
        int miss = 1;
        for (int n : nums) {
            map.put(n, map.getOrDefault(n, 0) + 1);
        }
        for (int i = 1; i <= nums.length; i++) {
            if (map.containsKey(i)) {
                if (map.get(i) == 2) {
                    dup = i;
                }
            }else {
                miss = i;
            }
        }
        return new int[] {dup, miss};
    }
}

class Solution {
    /*
    * 遍历nums数组，在1-n数字中，如果整数i对应的nums[|i|-1]改为相反数
    * 即原本为正改为负数，原本为复数改为正数。只出现一次的元素恒为负数，因此
    * 重复的数字是该正数，而缺失的数字则是该索引+1
    */
    public int[] findErrorNums(int[] nums) {
        int dup = -1;
        int miss = 1;
        for(int n : nums) {
            if (nums[Math.abs(n) - 1] < 0) {
                dup = Math.abs(n);
            }else {
                nums[Math.abs(n) - 1] *= -1;
            }
            sum += n;
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                miss = i +1;
            }
        }
        return new int[] {dup, miss};
    }
}

class Solution {
    //二分查找
    public int findDuplicate(int[] nums) {
        int left = 1;
        int right = nums.length-1;
        int mid = (left + right) / 2;
        while (left < right) {
            int count = 0;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] <= mid) {
                    count++;
                }
            }
            if (count > mid) {
                right = mid;
                mid = (left + right) / 2; 
            }else {
                left  = mid + 1;
                mid = (left + right) / 2;
            }
        }
        return left;
    }
}

class Solution {
    //快慢指针
    public int findDuplicate(int[] nums) {
        int low = nums[0];
        int fast = nums[0];
        while (true) {
            low = nums[low];
            fast = nums[nums[fast]];
            if (low == fast){
                break;
            }
        }
        fast = nums[0];
        while (low != fast) {
            low = nums[low];
            fast = nums[fast];
        }
        return low;
    }
}

class Solution {
    /**
    * 拥有相同大小的度的最短连续子数组的首尾元素都应为拥有最大度的元素
    * 因此只需要找到第一个最大度元素和最后一个元素的位置，即可计算出该子数组的长度
    * 考虑使用HashMap计算元素出现次数，元素首次出现索引和最后一次出现索引
    */
    public int findShortestSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return 1;
        }
        
        Map<Integer, Integer> count = new HashMap<>();//存储元素在数组中出现次数
        Map<Integer, Integer> firstIndex = new HashMap<>();//元素在数组中首次出现的索引
        Map<Integer, Integer> lastIndex = new HashMap<>(); //元素在数组中最后出现的索引

        for(int i = 0; i < nums.length; i++) {
            int x = nums[i];
            count.put(x, count.getOrDefault(x, 0) + 1);//如果元素在hashmap中未出现过，则默认值为0+1
            lastIndex.put(x, i);
            if (!firstIndex.containsKey(x)) {//如果hashmap中不含元素x，则首次出现的索引为i，如果包含则不更新
                firstIndex.put(x, i);
            }
        }

        //统计最大度为多少
        int max = 0;
        for(int num : nums) {
            if (count.get(num) > max) {
                max = count.get(num);
            }
        }
        
        //拥有相同度数的元素可能有多个，因此要比较他们的连续子数组的大小
        int shortestLen = nums.length;
        for(int num : nums) {
            if (count.get(num) == max) {
                int len = lastIndex.get(num) - firstIndex.get(num) + 1;
                if (len < shortestLen) {
                    shortestLen = len; //相同最大度元素中连续子数组最短的长度
                }
            }
        }
        
        return shortestLen;

    }
}

class Solution {
    /**.
    * 检查相邻右上元素
    * 若矩阵从左上到右下的对角线元素相等，那么我们可以得出规律：
    * 矩阵中任意元素若上方和右方有相邻元素时，相邻元素相等，则为托普利茨矩阵 
    * 因此遍历时，除去第一行和最后一列进行遍历
    */
    public boolean isToeplitzMatrix(int[][] matrix) {
        for (int i = 0; i < matrix.length; i++) {
            for(int j = 0; j < matrix[0].length; j++) {
                if (i > 0 && j < matrix[0].length - 1 && matrix[i - 1][j] != matrix[i][j + 1]) {
                    return false;
                }else{
                    continue;
                }
            }
        }
        return true;
    }
}

class Solution {
    /**
    * n长度的数组中包含0-n-1的不重复数字，取出一个数字以当前数字作为下一个数字的下标，
    * 可以看出按此逻辑取出的数字最终会构成一个圆环，剩下的数字也如此能构成圆环，找最长的序列，就是找最大的圆环。
    * 因此，题目可以转换为，一个图中存在一个或多个圆环，求其中最大的圆环长度。从圆环中的任意元素出发所得的结果相同。
    * 
    * 操作：遍历数组，将数组值作为嵌套数组的下标，并将遍历过的值赋为-1
    */ 
    public int arrayNesting(int[] nums) {
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            int count = 0;
            int index = i;
            while (nums[index] != -1){
                count++;
                int tmp = nums[index];
                nums[index] = -1;
                index = tmp;
            }
            res = Math.max(count, res);
        }
        return res;
    }
}