1.1. 基本结构

数组占据一块连续的内存并按照顺序存储数据。创建时,需要指定数组的容量大小,然后根据大小分配内存。


1.2. 剑指Offer 面试题

1.2.1. 3.数组中重复数字。

  1. 使用排序的方法,将数组进行排序,然后根据判断是否有重复的两个连续的数。

    • 时间:o(n*log(n)),空间:o(1)
  2. 使用HashMap记录,遍历数组,每次记录一下。

    • 时间:o(n),空间:o(n)
  3. 使用重新排序的方法,因为是(0 >> N-1)个数排列在N位,因此如果没有重复的数据,则会数据与索引会一一对应。我们只要遍历数组,并将数据一一对应上,然后找到对应不上的数据即可。

    • 时间:o(n*log(n)),空间:o(1)

public class Solution {
    //方法一,使用排序的方法
    //时间:o(n*log(n)),空间o(1)
    public boolean duplicate(int numbers[], int length, int[] duplication) {
        //1.边界判断
        if(length==0){
            return false;
        }
        //2.排序
        Arrays.sort(numbers);
        //3.判重
        for (int i = 0; i < length - 1; i++) {
            if(numbers[i] == numbers[i+1]){
                duplication[0] = numbers[i];
                return true;
            }
        }
        return false;
    }
    //方法二,使用HashMap的方法
    //时间:o(n),空间o(n)
    public boolean duplicate1(int numbers[], int length, int[] duplication) {
        //1.边界判断
        if(length==0){
            return false;
        }
        //2.建立hashmap
        HashMap<Integer, Boolean> numberHash = new HashMap<>();
        for(int number:numbers){
            if(!(numberHash.get(number)==null)){
                numberHash.put(number,true);
            }
            else{
                duplication[0] = number;
                return true;
            }
        }
        return false;
    }
    //方法三,重排数字的方法
    //时间:o(n),空间o(1)
    public boolean duplicate2(int numbers[], int length, int[] duplication) {
        //1.边界判断
        if(length==0){
            return false;
        }
        //2.重排数据
        for (int i = 0; i < length; i++) {
            while (numbers[i] != i){
                if(numbers[i] == numbers[numbers[i]]){
                    duplication[0] = numbers[i];
                    return true;
                }
                //交换
                int tmp = numbers[i];
                numbers[i] = numbers[tmp];
                numbers[tmp] = tmp;
            }
        }
        return false;
    }
}

//测试类
public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] arr = {2,3,1,0,2,5,3};
        int[] num = {0};
        System.out.println(s.duplicate1(arr,arr.length,num));
    }
}

1.2.2. 4.二维数组中的查找

  1. 用遍历的方式,遍历所有元素。

    • 时间:o(n^2),空间:o(1)
  2. 使用先列后行的查找方式,每次判断最右上方的数(A)与 target 的关系。

    因为从左到右,数字不断增加,因此,如果 target < A ,矩阵将缩小,直到 target > A时;

    因为从上到下,数字不断增加,因此,如果 target > A ,矩阵将缩小,直到 target = A,或者矩阵为空。

public class Solution {
    public boolean Find(int target, int [][] array) {
        boolean flag = false;
        int cols = array.length;
        int rows = array[0].length;
        if( rows > 0 && cols > 0 ){
            int row = 0;
            int col = cols - 1;
            //1. 遍历整个数组
            while(row < rows && col >= 0){ //直到矩阵为空(行大于最大行,或者列小于0) 
                //2.发现相等直接反回
                if(array[row][col] == target){
                    flag =true;
                    break;
                }
                //如果A > target,则减列
                else if(array[row][col] > target){
                    -- col;
                }
                //如果 A < target,则加行
                else {
                    ++ row;
                }
            }

        }
        return flag;
    }
}

1.2.3. 21.调整数组顺序使奇数位于偶数前面

1.2.4. 39.数组中出现次数超过一半的数字

1.2.5. 42.连续子数组的最大和

1.2.6. 45.把数组排成最小的数

1.2.7. 49.丑数

1.2.8. 50.第一个只出现一次的字符

1.2.9. 51.数组中的逆序对

1.2.10. 56.数组中数字出现的个数

1.2.11. 57.和为s的数字

1.2.12. 59.队列的最大值

1.2.13. 61.扑克牌中的顺子

1.2.14. 63.股票的最大利润

1.3. LeetCode 面试题

1.3.1. 1. 两数之和(简单)

遍历数据O(n)

public int[] twoSum(int[] nums, int target) {
    HashMap<Integer, Integer> hashMap = new HashMap<>();
    int[] result = new int[2];
    // 1. 使用hashMap存储数据
    for (int i = 0; i < nums.length; i++) {
        hashMap.put(nums[i], i);
    }
    // 2. 遍历数据,利用hashMap查找
    for (int i = 0; i < nums.length; i++) {
        int other = target - nums[i];
        if (hashMap.get(other) != null && hashMap.get(other) != i) {
            result[0] = i;
            result[1] = hashMap.get(other);
            return result;
        }
    }
    return result;
}

1.3.2. 11.盛最多水的容器(中等)

  1. 使用双指针 O(n)
public static int maxArea(int[] height) {
    int lo = 0, hi = height.length - 1; // 初始化指针
    int max = 0; // 初始化结果
    while (lo < hi) {
        int len = hi - lo; // 计算长度
        int wid = Math.min(height[lo], height[hi]); // 计算高度
        max = Math.max(max, wid * len); // 更新最大值
        // 更新导致高度小的那个数
        if (height[lo] < height[hi]) {
            lo++;
        } else {
            hi--;
        }

    }
    return max;
}
  1. 暴力O(n^2)

1.3.3. 15. 三数之和(中等)

  1. 使用排序+双指针,时间复杂度O(n^2)
public static List<List<Integer>> threeSum(int[] nums) {
        // 0. 建立一个返回集合用于存储数据
        List<List<Integer>> result = new LinkedList<>();
        // 1. 将数组进行排序
        Arrays.sort(nums);
        // 2. 去除一些特殊情况,如长度小于3的
        if (nums.length < 3) {
            return null;
        }
        // 3. 进行循环检测,
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                break; // 当遇到开始值(左侧值)大于0的跳出,因为右>左,所以不会为0.
            } else if (i > 0 && nums[i] == nums[i - 1]) {
                break;// 当遇到相同数据的跳出,因为不允许重复
            } else {
                int lo = i + 1, hi = nums.length - 1; // 初始化指针
                while (lo < hi) {
                    int sum = nums[i] + nums[lo] + nums[hi]; // 计算结果
                    if (sum == 0) { // 如果等于0
                        result.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
                        while (lo < hi && nums[lo] == nums[lo + 1]) {
                            lo++; // 去重
                        }
                        while (lo < hi && nums[hi] == nums[hi - 1]) {
                            hi--; // 去重
                        }
                        //lo++;//也可不要,a+b+c=0,如果c减小,b必须增大
                        hi--;
                    } else if (sum < 0) {
                        lo++; //左侧的向右移动 
                    } else {
                        hi--;//右侧的向左移动
                    }

                }

            }
        }
        return result;
    }
  1. 使用hashmap(暂时还有问题,答案不对。)
public static List<List<Integer>> threeSum(int[] nums) {
    // 0. 建立一个返回集合用于存储数据
    List<List<Integer>> result = new LinkedList<>();
    // 1. 排序
    Arrays.sort(nums);
    System.out.println(Arrays.toString(nums));
    // 2. 将数据存入hashMap
    HashMap<Integer, Integer> numHashMap = new HashMap<>();
    for (Integer num : nums) {
        numHashMap.put(num, num);
    }
    for (int i = 0; i < nums.length; i++) {
        numHashMap.put(nums[i],i);
    }
    for (int i = 0; i < nums.length; i++) {
        if (nums[i]>0){break;}
        for (int j = i + 1; j < nums.length; j++) {
            int c = nums[i] + nums[j];
            if (numHashMap.containsKey(-c)) {
                result.add(Arrays.asList(nums[i], nums[j], -c));
                //                    while (j < nums.length - 2 && nums[j] == nums[j++]) {
                //                        j++;
                //                    }
                //                    while (i < nums.length - 2 && nums[i] == nums[i++]) {
                //                        i++;
                //                    }
                j++;
            }
        }
    }
    return result;
}

1.3.4. 26. 删除排序数组中的重复项(简单)

使用双指针,O(n)

public int removeDuplicates(int[] nums) {
    if (nums.length == 0) {
        return 0;
    }
    //i为慢指针,用于记录每一次不同数据的首个;
    //j为快指针,用于遍历整个数据。
    int i = 0;
    for (int j = 1; j < nums.length; j++) {
        if (nums[j] != nums[i]) {//当发现不同的。
            i++;//向后移动一位
            nums[i] = nums[j]; // 将不同的复制过去。
        }
    }
    return i + 1;
}

1.3.5. 66. 加一(简单)

模拟计算实现,O(n)

public int[] plusOne(int[] digits) {
    // 从最末尾开始遍历数据
    for (int i = digits.length - 1; i >= 0; i--) {
        //首先,最后一位加一;其次,如果出现进位,则加一
        digits[i] = digits[i] + 1;
        if (digits[i] % 10 != 0) {
            // 如果不进位直接返回
            return digits;
        } else {
            digits[i] = 0;
        }
    }
    // 如果出来,肯定还要进位,例如99+1=100
    digits = new int[digits.length + 1];
    digits[0] = 1;
    return digits;
}

1.3.6. 70.爬楼梯(简单)

  1. 动态规划
public int climbStairs(int n) {
    if (n <= 3) {
        return n;
    } else {
        List<Integer> list = new ArrayList<>(Arrays.asList(0, 1, 2));
        for (int i = 3; i < n+1 ; i++) {
            list.add(list.get(i - 1) + list.get(i - 2));
        }
        return list.get(list.size()-1);
    }
}

1.3.7. 88. 合并两个有序数组(简单)

public void merge(int[] nums1, int m, int[] nums2, int n) {
    // 去除nums2为空数组的情况
    if (n != 0) {
        // 1. 首先讲nums1 中的所有数据,向后移动。
        if (m >= 0) {
            System.arraycopy(nums1, 0, nums1, nums1.length - m, m);
        }
        // 2. 建立a,b,i三个指针
        int a = nums1.length - m;//移动nums1取数据
        int b = 0;//移动nums2取数据
        int i = 0;//移动nums1放数据
        while (a < nums1.length && b < n) {
            // 放入较小的数据,并移动相应的指针
            if (nums1[a] < nums2[b]) {
                nums1[i] = nums1[a];
                a++;
            } else {
                nums1[i] = nums2[b];
                b++;
            }
            i++;
        }
        // 如果nums2中还有剩余的数据,直接放入nums1中。
        if (n - b >= 0) {
            System.arraycopy(nums2, b, nums1, nums1.length - n + b, n - b);
        }
    }
    // System.out.println(Arrays.toString(nums1));
}

1.3.8. 189. 旋转数组(简单)

暴力O(n)

public void rotate(int[] nums, int k) {
    int temp, previous;
    //移动K次
    for (int i = 0; i < k; i++) {
        previous = nums[nums.length - 1];
        // 每个数据移动一位
        for (int j = 0; j < nums.length; j++) {
            //调换当前位置数据与前一位置数据
            temp = nums[j];
            nums[j] = previous;
            previous = temp;
        }

    }
    System.out.println(Arrays.toString(nums));
}

使用环状替换

public void rotate(int[] nums, int k) {
        k = k % nums.length;
        int count = 0;
        for (int start = 0; count < nums.length; start++) {
            int current = start;
            int prev = nums[start];
            do {
                int next = (current + k) % nums.length;
                int temp = nums[next];
                nums[next] = prev;
                prev = temp;
                current = next;
                count++;
            } while (start != current);
        }
    }

1.3.9. 240. 搜索二维矩阵 II(中等)

  1. 遍历数组查找O(n^2)
public boolean searchMatrix(int[][] matrix, int target) {
    for (int[] nums : matrix) {
        for (int num : nums) {
            if (target < num) {//终止条件
                break;
            } else if (target == num) {
                return true;
            }
        }
    }
    return false;
}
  1. 从最右上角的元素开始找,如果这个元素比target大,则说明找更小的,往左走;如果这个元素比target小,则说明应该找更大的,往下走。复杂度O(n+m)
public boolean searchMatrix(int[][] matrix, int target) {
    if (matrix == null || matrix.length < 1 || matrix[0].length < 1) {
        return false;
    }
    // 从右上角的元素开始
    int row = 0, col = matrix[0].length - 1;
    // 判断当前数组元素和target,如果当前大于target,往左走;小与target,往下走
    while (row < matrix.length && col >= 0) { // 门限
        if (matrix[row][col] < target) {
            row++; // 向下走
        } else if (matrix[row][col] > target) {
            col--; // 向左走
        } else {
            return true;
        }
    }
    return false;
}

1.3.10. 283.移动零(简单)

  1. 对数组进行一次遍历,得到结果。时间O(n)
public void moveZeroes(int[] nums) {
    int index = 0;
    // 1. 遍历数组,去除0
    for (int num : nums) {
        if (num != 0) {
            nums[index] = num;
            index++;
        }
    }
    // 2. 根据数组的长度,将缺少的0插入。
    for (int i = index; i < nums.length; i++) {
        nums[i] = 0;
    }
    System.out.println(Arrays.toString(nums));
}

1.3.11. 287. 寻找重复数(中等)

  1. 遍历,并使用双指针进行查找
public int findDuplicate(int[] nums) {
    int lo, hi;
    for (int i = 0; i < nums.length - 1; i++) {
        lo = 0;//左指针
        hi = nums.length - 1;//右指针
        while (lo <= hi) {
            if (i != lo && nums[i] == nums[lo]) {
                return nums[i];
            } else if (i != hi && nums[i] == nums[hi]) {
                return nums[i];
            }
            lo++;
            hi--;
        }
    }
    return 0;
}
  1. 使用快慢指针,O(n),不太理解。
public int findDuplicate(int[] nums) {
    // 发现重复换的位置
    int slow = nums[0], fast = nums[0];
    do {
        System.out.println(slow);
        slow = nums[slow];
        System.out.println(nums[fast]);
        fast = nums[nums[fast]];
    } while (slow != fast);
    // 找到重复数据
    int ptr1 = nums[0];
    int ptr2 = slow;
    while (ptr1 != ptr2) {
        ptr1 = nums[ptr1];
        ptr2 = nums[ptr2];
    }
    return ptr1;
}

1.3.12. 378. 有序矩阵中第K小的元素(中等)

  1. 使用最大队列,O(n^2)
public int kthSmallest(int[][] matrix, int k) {
    PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2-o1);
    for (int [] nums : matrix) {
        for (int num : nums){
            queue.offer(num);
            if(queue.size()>k){//超出的部分
                queue.poll();
            }
        }
    }
    return queue.peek();
}
  1. 使用二分法(我还没懂)

    思路非常简单: 1.找出二维矩阵中最小的数left,最大的数right,那么第k小的数必定在left~right之间 2.mid=(left+right) / 2;在二维矩阵中寻找小于等于mid的元素个数count 3.若这个count小于k,表明第k小的数在右半部分且不包含mid,即left=mid+1, right=right,又保证了第k小的数在left~right之间 4.若这个count大于k,表明第k小的数在左半部分且可能包含mid,即left=left, right=mid,又保证了第k小的数在left~right之间 5.因为每次循环中都保证了第k小的数在left~right之间,当left==right时,第k小的数即被找出,等于right

    注意:这里的left mid right是数值,不是索引位置。

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 = row - 1;
    int j = 0;
    int count = 0;
    while (i >= 0 && j < col) {
        if (matrix[i][j] <= mid) {
            // 第j列有i+1个元素<=mid
            count += i + 1;
            j++;
        } else {
            // 第j列目前的数大于mid,需要继续在当前列往上找
            i--;
        }
    }
    return count;
}

1.3.13. 485. 最大连续1的个数(简单)

遍历数组,O(n)

public int findMaxConsecutiveOnes(int[] nums) {
    int counts = 0, result = 0;
    for (int num : nums) {
        if (num == 1) {// 是1 的时候,增加。
            counts++;
        } else {
            result = Math.max(counts, result);// 当为其它值的时候,取大的值。
            counts = 0;
        }
    }
    result = Math.max(counts, result); //当结束循环的时候仍未1,判断最大值。
    return result;
}

1.3.14. 565. 数组嵌套(中等)

  1. 暴力O(n^2)
public int arrayNesting(int[] nums) {
    int res = 0;
    for (int num : nums) {
        int start = num, count = 0;
        do {
            start = nums[start];
            count++;
        }
        while (start != num);
        res = Math.max(res, count);

    }
    return res;
}
  1. 将一些重复数据记录下来,不走这些路。O(n)
// 例如 [5,4,0,3,1,6,2] 
// 第一次时候 5>6>2>0>5, 重复:6>2>0>5>6, 2>0>5>6>2.因此将走过的记录下来,减少走的次数。
public int arrayNesting(int[] nums) {
    boolean[] visited = new boolean[nums.length];
    int res = 0;
    for (int i = 0; i < nums.length; i++) {
        if (!visited[i]) {
            int start = nums[i], count = 0;
            do {
                start = nums[start];
                count++;
                visited[start] = true;
            }
            while (start != nums[i]);
            res = Math.max(res, count);
        }
    }
    return res;
}

1.3.15. 566.重塑矩阵(简单)

遍历整个二维数组,一个个添加。O(n^2)

public int[][] matrixReshape(int[][] nums, int r, int c) {
    // 1. 去除特殊情况
    if (nums.length == 0 || nums.length * nums[0].length != r * c) {
        return nums;
    }
    // 2.初始化数组,存储
    int[][] result = new int[r][c];
    int nr = 0, nc = 0;
    // int counts = 0;
    for (int[] num : nums) {
        for (int i : num) {
            // 方法一:使用门限
            result[nr][nc] = i;
            nc++;
            if (nc == c) { //当到达门限时,换行。
                nr++;
                nc = 0;
            }
            // 方法二:使用余数
            // result [counts/c] [counts%c] = i;
            // counts++;
        }
    }
    return result;
}

1.3.16. 645. 错误的集合(简单)

  1. 使用计数的方法,时间O(n),空间O(n)
public int[] findErrorNums(int[] nums) {
    // 记录数据
    int[] counter = new int[nums.length + 1];
    // 错误数据
    int[] errors = new int[2];
    // 遍历数组,将出现的数据数字++
    for (int i : nums) {
        counter[i]++;
    }
    // 找到错误数据
    for (int i = 0; i < counter.length; i++) {
        if (counter[i] == 2) {
            errors[0] = i;
        } else if (counter[i] == 0) {
            errors[1] = i;
        }
    }
    return errors;
}
  1. 排序后做差O(nlogn)
public int[] findErrorNums(int[] nums) {
    Arrays.sort(nums);// 排序
    int dup = -1, missing = 1;// 初始化数据
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] == nums[i - 1]) {
            dup = nums[i];
        } else if (nums[i] > nums[i - 1] + 1) { 
            missing = nums[i - 1] + 1;
        }
    }
    // 当{2,2} 时,数据无法处理。因此,在返回处判断最后一位数据是否为数据长度。
    return new int[] {dup, nums[nums.length - 1] != nums.length ? nums.length : missing};
}

1.3.17. 667. 优美的排列 II(中等)

实在看不懂,以后再看,解题链接

public int[] constructArray(int n, int k) {
    int[] res = new int[n];
    for (int i = 0, l = 1, r = n; l <= r; i++) {
        res[i] = k > 1 ? (k-- % 2 != 0 ? l++ : r--) : l++;
    }
    return res;
}

1.3.18. 697. 数组的度(简单)

使用数学方法,连续字串的长度=右侧位置-左侧位置+1,时间O(n),空间O(n)

public int findShortestSubArray(int[] nums) {
    // 1.建立数据,counts 记录数据,left记录左边的位置,right记录右边位置
    HashMap<Integer, Integer> counts = new HashMap<>();
    HashMap<Integer, Integer> left = new HashMap<>();
    HashMap<Integer, Integer> right = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int num = nums[i];
        // 1.1 记录数量
        if (counts.containsKey(num)) {
            counts.put(num, counts.get(num) + 1);
        } else {
            counts.put(num, 1);
        }
        // 1.2 记录左侧
        if (!left.containsKey(num)) {
            left.put(num, i);
        }
        // 1.3 记录右侧,不断更新自己
        right.put(num, i);
    }
    // 2. 找到最大值
    int degree = Collections.max(counts.values());
    // 3. 结果,长度 = 右侧位置-左侧位置+1
    int result = nums.length;
    for (int num : counts.keySet()) {
        if (counts.get(num) == degree) {
            result = Math.min(result, right.get(num) - left.get(num) + 1);
        }
    }
    return result;
}

1.3.19. 766. 托普利茨矩阵(简单)

发现,如果是托普利茨矩阵的话,所有数字都是由第一行和第一列决定的。时间O(n)

public boolean isToeplitzMatrix(int[][] matrix) {
    int width = matrix.length;
    int length = matrix[0].length;
    // 处理第一行,遍历所有斜线上数字(新数字=旧数字(行+1,列+1))
    for (int i = 0; i < length - 1; i++) {
        int y = 0;
        int x = i;
        while (x < length && y < width) {
            if (matrix[0][i] != matrix[y++][x++]) {
                return false;
            }
        }
    }
    // 处理列
    for (int i = 0; i < width - 1; i++) {
        int y = i;
        int x = 0;
        while (x < length && y < width) {
            if (matrix[i][0] != matrix[y++][x++]) {
                return false;
            }
        }
    }
    return true;
}

1.3.20. 769. 最多能完成排序的块(中等)

由于该数组的特殊性,要看到某个点 i 能不能切分,就看它和左边区间 [ :i] 里的最大值是不是和 i 本身相同。如果是就可以切分,如果不是说明肯定还有更大的值在其中,需要换到更后面的位置,就不能在该处切分。

时间O(n)

public int maxChunksToSorted(int[] arr) {
    int ans = 0, max = 0;
    for (int i = 0; i < arr.length; ++i) {
        max = Math.max(max, arr[i]);
        if (max == i) {
            ans++;
        }
    }
    return ans;
}

results matching ""

    No results matching ""