@TOC

Offer-03 數(shù)組中重復的數(shù)字

問題描述：在一個長度為 n 的數(shù)組 nums 里的所有數(shù)字都在 0～n-1 的范圍內。數(shù)組中某些數(shù)字是重復的，但不知道有幾個數(shù)字重復了，也不知道每個數(shù)字重復了幾次。請找出數(shù)組中任意一個重復的數(shù)字。

public int findRepeatNumber(int[] nums) {
    if (nums == null || nums.length < 1) {
        return -1;
    }
    int len = nums.length;
    for (int i = 0; i < len; i++) {
        int index = nums[i] % len;// 通過取余,獲取數(shù)字原來的數(shù),但僅作為索引使用,并改變當前遍歷點i的值
        if (nums[index] >= len) {//是index不是i,要判斷index是否重復
            return nums[i] % len;
        }
        nums[index] += len;//加length方便,將數(shù)還原
    }
    return -1;
}

Offer-66 構建乘積數(shù)組

問題描述：給定一個數(shù)組 A[0,1,…,n-1]，請構建一個數(shù)組 B[0,1,…,n-1]，其中 B[i] 的值是數(shù)組 A 中除了下標 i 以外的元素的積, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]，不能使用除法，具體可參考Offer-66題。

public int[] constructArr(int[] a) {
    int[] b = new int[a.length];
    b[0] = 1;
    for (int i = 1; i < a.length; i++) {
        b[i] = b[i - 1] * a[i - 1];
    }
    int tmp = 1;
    for (int i = a.length - 2; i >= 0; i--) {
        tmp = tmp * a[i+1];
        b[i] = tmp * b[i];
    }
    return b;
}

Offer-45 把數(shù)組排成最小的數(shù)

問題描述 ：輸入一個非負整數(shù)數(shù)組，把數(shù)組里所有數(shù)字拼接起來排成一個數(shù)，打印能拼接出的所有數(shù)字中最小的一個。如果輸入: [10,2]，輸出: "102"，具體可參考Offer-45題。關于排序的規(guī)則理解，可以親自按插入排序試一下。

在這里插入圖片描述

public String minNumber(Integer[] nums) {
    if (nums == null || nums.length < 1) {
        return "";
    }

    Arrays.sort(nums, new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            String x = o1.toString() + o2.toString();
            String y = o2.toString() + o1.toString();
            return x.compareTo(y);
        }
    });

    StringBuilder sb = new StringBuilder();
    for (Integer num : nums) {
        sb.append(num);
    }
    return sb.toString();
}

Offer-49 判斷丑數(shù)

問題描述：我們把只包含質因子 2、3 和 5 的數(shù)稱作丑數(shù)（Ugly Number），求按從小到大的順序的第 n 個丑數(shù)。蠻力法：根據(jù)丑數(shù)定義，若一個數(shù)能被2整除，則連續(xù)除以2；若還能被3整除，則連續(xù)除以3；若還能被5整除，則連續(xù)除以5；如果最后結果是1則是丑數(shù)，否則不是；動態(tài)規(guī)劃：新丑數(shù)，是前面已經(jīng)生成的丑數(shù)的2倍或3倍或5倍。具體詳見Offer-49題。

在這里插入圖片描述

在這里插入圖片描述

Offer-29 順時針打印矩陣

問題描述：輸入一個矩陣，按照從外向里以順時針的順序依次打印出每一個數(shù)字。輸入：matrix = [[1,2,3],[4,5,6],[7,8,9]]，輸出：[1,2,3,6,9,8,7,4,5]。

在這里插入圖片描述

public int[] spiralOrder2(int[][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return new int[0];
    }

    int cols = matrix[0].length;
    int rows = matrix.length;
    int[] order = new int[cols * rows];
    int top = 0, bottom = rows - 1, left = 0, right = cols - 1;
    int index = 0;
    while (index < order.length) {
        for (int column = left; column <= right; column++) {
            order[index++] = matrix[top][column];
        }
        if (index == order.length) {
            break;
        }

        for (int row = top + 1; row <= bottom; row++) {
            order[index++] = matrix[row][right];
        }
        if (index == order.length) {
            break;
        }

        for (int column = right - 1; column > left; column--) {
            order[index++] = matrix[bottom][column];
        }
        if (index == order.length) {
            break;
        }

        for (int row = bottom; row > top; row--) {
            order[index++] = matrix[row][left];
        }

        top++; bottom--; left++; right--;
    }
    return order;
}

offer-61 撲克牌中的順子

從撲克牌中隨機抽5張牌，判斷是不是一個順子，即這5張牌是不是連續(xù)的。2～10為數(shù)字本身，A為1，J為11，Q為12，K為13，而大、小王為 0 ，可以看成任意數(shù)字。A 不能視為 14。輸入: [1,2,3,4,5]，輸出: True；輸入: [0,0,1,2,5]，輸出: True；

在這里插入圖片描述

public boolean isStraight(int[] nums) {
    Set<Integer> set = new HashSet<>();
    int min = 15, max = -1;
    for (int num : nums) {
        if (set.contains(num)) {
            return false;
        }
        if (num == 0) {
            continue;
        }

        set.add(num);
        min = Math.min(min, num);
        max = Math.max(max, num);
    }
    return (max - min) < 5;
}

Offer-57 和為s的兩個數(shù)字

問題描述：輸入一個遞增排序的數(shù)組和一個數(shù)字s，在數(shù)組中查找兩個數(shù)，使得它們的和正好是s。如果有多對數(shù)字的和等于s，則輸出任意一對即可。

在這里插入圖片描述

public int[] twoSum(int[] nums, int target) {
    if (nums == null || nums.length < 3) {
        return nums;
    }

    int i = 0, j = nums.length - 1;
    while (i < j) {
        int s = nums[i] + nums[j];
        if (s == target) {
            return new int[]{nums[i], nums[j]};
        }
        if (s < target) {
            i++;
            continue;
        }
        j--;
    }
    return new int[0];
}

Offer-57-II 和為s的連續(xù)正數(shù)序列

輸入一個正整數(shù) target ，輸出所有和為 target 的連續(xù)正整數(shù)序列（至少含有兩個數(shù)）。序列內的數(shù)字由小到大排列，不同序列按照首個數(shù)字從小到大排列。輸入：target = 9，輸出：[[2,3,4],[4,5]]

在這里插入圖片描述

public int[][] findContinuousSequence(int target) {
    int i = 1; // 滑動窗口的左邊界
    int j = 1; // 滑動窗口的右邊界
    int sum = 0; // 滑動窗口中數(shù)字的和
    List<int[]> list = new ArrayList<>();
    while (i <= target / 2) {
        if (sum < target) {
            sum += j;
            j++;
            continue;
        }

        if (sum > target) {
            sum -=i;
            i++;
            continue;
        }

        int[] arr = new int[j-i]; // 記錄結果
        for (int k = i; k < j; k++) {
            arr[k-i] = k;
        }
        list.add(arr);
        sum -= i;// 左邊界向右移動
        i++;
    }
    return list.toArray(new int[list.size()][]);
}

Offer-59-1 滑動窗口的最大值

問題描述：給定一個數(shù)組 nums 和滑動窗口的大小 k，請找出所有滑動窗口里的最大值。

在這里插入圖片描述

public Integer[] maxSlidingWindow(Integer[] nums, int k) {
    if (nums == null || nums.length < 1) {
        return new Integer[0];
    }
    Integer[] result = new Integer[nums.length - k + 1];
    Deque<Integer> queue = new LinkedList<>();
    for (int i = 0; i < k; i++) {
        while (!queue.isEmpty() && queue.peekLast() < nums[i]) { // 查找插入位置
            queue.removeLast();
        }
        queue.offer(nums[i]);
    }
    Integer index = 0;
    result[index++] = queue.peekFirst();
    for (int j = k; j < nums.length; j++) {
        if (nums[j - k] == queue.peekFirst()) {
            queue.removeFirst();
        }
        while (!queue.isEmpty() && queue.peekLast() < nums[j]) { // 查找插入位置
            queue.removeLast();
        }
        queue.offer(nums[j]);
        result[index++] = queue.peekFirst();
    }
    return result;
}

Offer-44 數(shù)字序列中某一位的數(shù)字

數(shù)字以0123456789101112131415…的格式序列化到一個字符序列中。在這個序列中，第5位（從下標0開始計數(shù)）是5，第13位是1，第19位是4，等等。請寫一個函數(shù)，求任意第n位對應的數(shù)字。

在這里插入圖片描述

public int findNthDigit(int n) {
    int digit = 1;
    long start = 1, count = 9;
    while (n > count) { // 求所在的數(shù)字的位數(shù)
        n -= count;
        digit++;
        start *= 10;
        count = 9 * start * digit;
    }
    long num = start + (n-1)/digit; // 求坐在數(shù)字
    return Long.toString(num).charAt(((n - 1) % digit)) -'0';
}

Offer-39 數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字

數(shù)組中有一個數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半，請找出這個數(shù)字。你可以假設數(shù)組是非空的，并且給定的數(shù)組總是存在多數(shù)元素。

在這里插入圖片描述

public int majorityElement(int[] nums) {
    if (nums == null || nums.length < 1) {
        return -1;
    }

    int vote = 0, x = -1;
    for (int num : nums) {
        if (vote == 0) {
            x = num;
        }
        vote += num == x ? 1 : -1;
    }
    return x;
}

面試題-01-08 零矩陣

問題描述：編寫一種算法，若M × N矩陣中某個元素為0，則將其所在的行與列清零，具體詳見 金典01-08題。

public void setZeroes(int[][] matrix) {
    if (matrix == null || matrix.length < 1) {
        return;
    }
    boolean[] rows = new boolean[matrix.length];
    boolean[] cols = new boolean[matrix[0].length];

    for (int i = 0; i < rows.length; i++) {
        for (int j = 0; j < cols.length; j++) {
            if (matrix[i][j] == 0) {
                rows[i] = true;
                cols[j] = true;
            }
        }
    }

    for (int i = 0; i < rows.length; i++) {
        for (int j = 0; j < cols.length; j++) {
            if (rows[i] || cols[j]) {
                matrix[i][j] = 0;
            }
        }
    }
}

面試題-01-07 旋轉矩陣

問題描述：給你一幅由 N × N 矩陣表示的圖像，其中每個像素的大小為 4 字節(jié)。請你設計一種算法，將圖像旋轉 90 度。不占用額外內存空間能否做到。

在這里插入圖片描述

本文由mdnice多平臺發(fā)布