目錄

?三、滑動窗口

30. 長度最小的子數(shù)組?②

31. 無重復字符的最長子串?②

32. 串聯(lián)所有單詞的子串?③

33. 最小覆蓋子串?③

四、矩陣

34. 有效的數(shù)獨?②

35. 螺旋矩陣?②

36. 旋轉圖像?②

37. 矩陣置零?②

38. 生命游戲?②

?三、滑動窗口

30. 長度最小的子數(shù)組?②

?給定一個含有?n?個正整數(shù)的數(shù)組和一個正整數(shù)?target?。

找出該數(shù)組中滿足其總和大于等于?target?的長度最小的?連續(xù)子數(shù)組?[numsl, numsl+1, ..., numsr-1, numsr]?，并返回其長度。如果不存在符合條件的子數(shù)組，返回?0?。

示例 1：

輸入：target = 7, nums = [2,3,1,2,4,3]
輸出：2
解釋：子數(shù)組?[4,3]
?是該條件下的長度最小的子數(shù)組。

示例 2：

輸入：target = 4, nums = [1,4,4]
輸出：1

示例 3：

輸入：target = 11, nums = [1,1,1,1,1,1,1,1]
輸出：0

提示：

• 1 <= target <= 109
• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105

力扣題解：. - 力扣（LeetCode）

方法1：時間超時（通過15/18）

    public int minSubArrayLen(int target, int[] nums) {
        int min = nums.length + 1;
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            int left = i;
            sum += nums[left];
            int right = i + 1;
            while (right < nums.length && sum < target){
                sum += nums[right];
                right++;
            }
            if (sum >= target && min > right - left){
                min = right - left;
            }
        }
        return min == nums.length + 1? 0 : min;
    }

方法2：(0ms)

    public int minSubArrayLen(int target, int[] nums) {
        int l = 0, r = 0;
        int n = nums.length;
        int sum = 0;

        while(r < n && sum < target)
            sum += nums[r++];

        if(r == n)
            if (sum < target)
                return 0;
            else{
                while(sum > target)
                    sum -= nums[l++];
            }

        while(r < n){
            if(sum < target) sum += nums[r++];
            sum -= nums[l++];
        }
        if(sum < target) return r-l+1;
        return r -l;
    }

方法3：

    public int minSubArrayLen(int target, int[] nums) {
        int lo = 0, hi = 0, sum = 0, min = Integer.MAX_VALUE;
        while (hi < nums.length) {
            sum += nums[hi++];
            while (sum >= target) {
                min = Math.min(min, hi - lo);
                sum -= nums[lo++];
            }
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }

?方法4：（2ms）

    public int minSubArrayLen(int target, int[] nums) {
         int left = 0;
        int res = Integer.MAX_VALUE;
        int add = 0;
         for (int right = 0; right < nums.length; right++) {
            add += nums[right];
            while (add >= target) {
                res = Math.min(res, right - left + 1);
                add -= nums[left];
                ++left;
            }
        }
        return res > nums.length ? 0 : res;
    }

31. 無重復字符的最長子串?②

?給定一個字符串?s?，請你找出其中不含有重復字符的?最長子串?的長度。

示例?1:

輸入: s = "abcabcbb"
輸出: 3 
解釋: 因為無重復字符的最長子串是 "abc"，所以其長度為 3。

示例 2:

輸入: s = "bbbbb"
輸出: 1
解釋: 因為無重復字符的最長子串是 "b"，所以其長度為 1。

示例 3:

輸入: s = "pwwkew"
輸出: 3
解釋: 因為無重復字符的最長子串是?"wke"，所以其長度為 3。
?    請注意，你的答案必須是 子串 的長度，"pwke"?是一個子序列，不是子串。

提示：

• 0 <= s.length <= 5 * 104
• s?由英文字母、數(shù)字、符號和空格組成

方法1：（7ms）

    public static int lengthOfLongestSubstring(String s) {
        TreeSet<Integer> set = new TreeSet<>();
        if (s.length() == 0){
            return 0;
        }else if (s.length() == 1){
            return 1;
        }else {
            int left = 0;
            int right = 1;
            while (right < s.length()){
                String substring = s.substring(left, right);
                if (substring.contains(s.charAt(right) + "")){
                    set.add(right - left);
                    left = s.indexOf(s.charAt(right), left) + 1;
                }else {
                    if (right == s.length() - 1) {
                        set.add(right - left + 1);
                        break;
                    }
                }
                right++;
            }
            return set.last();
        }
    }

方法2：（滑動窗口? 5ms）

    public int lengthOfLongestSubstring(String s) {
        if (s.length()==0) return 0;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int max = 0;
        int left = 0;
        for(int i = 0; i < s.length(); i ++){
            if(map.containsKey(s.charAt(i))){
                left = Math.max(left,map.get(s.charAt(i)) + 1);
            }
            map.put(s.charAt(i),i);
            max = Math.max(max,i-left+1);
        }
        return max;
        
    }

作者：powcai
鏈接：https://leetcode.cn/problems/longest-substring-without-repeating-characters/solutions/3982/hua-dong-chuang-kou-by-powcai/

32. 串聯(lián)所有單詞的子串?③

33. 最小覆蓋子串?③

四、矩陣

34. 有效的數(shù)獨?②

?請你判斷一個?9 x 9?的數(shù)獨是否有效。只需要?根據(jù)以下規(guī)則?，驗證已經(jīng)填入的數(shù)字是否有效即可。

1. 數(shù)字?1-9?在每一行只能出現(xiàn)一次。
2. 數(shù)字?1-9?在每一列只能出現(xiàn)一次。
3. 數(shù)字?1-9?在每一個以粗實線分隔的?3x3?宮內(nèi)只能出現(xiàn)一次。（請參考示例圖）

注意：

• 一個有效的數(shù)獨（部分已被填充）不一定是可解的。
• 只需要根據(jù)以上規(guī)則，驗證已經(jīng)填入的數(shù)字是否有效即可。
• 空白格用?'.'?表示。

示例 1：

輸入：board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
輸出：true

示例 2：

輸入：board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
輸出：false
解釋：除了第一行的第一個數(shù)字從 5 改為 8 以外，空格內(nèi)其他數(shù)字均與 示例1 相同。 但由于位于左上角的 3x3 宮內(nèi)有兩個 8 存在, 因此這個數(shù)獨是無效的。

提示：

• board.length == 9
• board[i].length == 9
• board[i][j]?是一位數(shù)字（1-9）或者?'.'

方法1：

    public static boolean isValidSudoku(char[][] board) {
        String[] rows = new String[9];
        String[] columns = new String[9];
        String[] areas = new String[9];
        for (int i = 0; i < 9; i++) {
            if (rows[i] == null){
                rows[i] = "a";
            }

            for (int j = 0; j < 9; j++) {
                if (columns[j] == null){
                    columns[j] = "a";
                }
                if (rows[i].contains(board[i][j] + "")){
                    return false;
                }else if (board[i][j] != '.' && !rows[i].contains(board[i][j] + "")){
                    rows[i] += board[i][j];
                }
                if (columns[j].contains(board[i][j] + "")){
                    return false;
                }else if (board[i][j] != '.' && !columns[j].contains(board[i][j] + "")){
                    columns[j] += board[i][j];
                }
                int row = i / 3; // 0 1 2
                int column = j / 3; //0 1 2
                int area = row * 3 + column;
                if (areas[area] == null){
                    areas[area] = "a";
                }
                if (areas[area].contains(board[i][j] + "")){
                    return false;
                }else  if (board[i][j] != '.' && !areas[area].contains(board[i][j] + "")){
                    areas[area] += board[i][j];
                }
            }
        }
        return true;
    }

方法2：（0ms）

    public boolean isValidSudoku(char[][] board) {
        short[] rows = new short[9];
        short[] cols = new short[9];
        short[] squares = new short[9];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    short value = (short)(1 << (board[i][j] - '0'));
                    int boxNum = i / 3 * 3 + j / 3;
                    if ((rows[i] & value) != 0 || (cols[j] & value) != 0 || (squares[boxNum] & value) != 0) {
                        return false;
                    }
                    rows[i] |= value;
                    cols[j] |= value;
                    squares[boxNum] |= value;
                }
            }
        }
        return true;
    }

方法3：（1ms）

    public boolean isValidSudoku(char[][] board) {
        int[] rows = new int[9];
        int[] cols = new int[9];
        int[] subboxes = new int[9];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                if (c != '.') {
                    int x = (1 << (c - '1'));
                    if ((rows[i] & x) != 0) {
                        return false;
                    } else {
                        rows[i] |= x;
                    }
                    if ((cols[j] & x) != 0) {
                        return false;
                    } else {
                        cols[j] |= x;
                    }
                    if ((subboxes[i / 3 * 3 + j / 3] & x) != 0) {
                        return false;
                    } else {
                        subboxes[i / 3 * 3 + j / 3] |= x;
                    }
                }
            }
        }
        return true;
    }

方法4：（2ms）

    public boolean isValidSudoku(char[][] board) {            
        int[][] row = new int[9][9]; // 行
        int[][] columns = new int[9][9]; // 列
        int[][][] a = new int[3][3][9];
        for (int i = 0; i < 9; i++) {
            Set<Character> set = new HashSet<>();
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                if (c != '.') {
                    row[i][c - 49]++;
                    columns[j][c - 49]++;
                    a[i / 3][j / 3][c - 49]++;
                    if (row[i][c - 49] > 1 || columns[j][c - 49] > 1 || a[i / 3][j / 3][c - 49] > 1) {
                        return false;
                    }
                }

            }
        }
        return true;
    }

35. 螺旋矩陣?②

?給你一個?m?行?n?列的矩陣?matrix?，請按照?順時針螺旋順序?，返回矩陣中的所有元素。

示例 1：

輸入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
輸出：[1,2,3,6,9,8,7,4,5]

示例 2：

輸入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
輸出：[1,2,3,4,8,12,11,10,9,5,6,7]

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 10
• -100 <= matrix[i][j] <= 100

方法1：（0ms）

    public static List<Integer> spiralOrder(int[][] matrix) {
        int[][] path = new int[matrix.length][matrix[0].length];
        int step = 0;
        ArrayList<Integer> list = new ArrayList<>();
        int row = 0;
        int col = 0;
        int direct = 0;
        while (step < matrix.length * matrix[0].length){
            list.add(matrix[row][col]);
            path[row][col] = 1;
            if (direct == 0){
                col++;
                if (col == matrix[0].length || path[row][col] == 1){
                    direct = 1;
                    col--;
                    row++;
                }
            }else if (direct == 1){
                row++;
                if (row == matrix.length || path[row][col] == 1){
                    direct = 2;
                    row--;
                    col--;
                }
            }else if (direct == 2){
                col--;
                if (col == -1 || path[row][col] == 1){
                    direct = 3;
                    col++;
                    row--;
                }
            }else {
                row--;
                if (row == 0 || path[row][col] == 1){
                    direct = 0;
                    row++;
                    col++;
                }
            }
            step++;
        }
        return list;
    }

方法2：（0ms）

   public List<Integer> spiralOrder(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        List<Integer> res = new ArrayList<>();
        int u = 0, d = m - 1, l = 0, r = n - 1;
        while (true) {
            for (int i = l; i <= r; i ++) res.add(matrix[u][i]);
            if (++u > d) break;
            for (int i = u; i <= d; i ++) res.add(matrix[i][r]);
            if (--r < l) break;
            for (int i = r; i >= l; i --) res.add(matrix[d][i]);
            if (--d < u) break;
            for (int i = d; i  >= u; i --) res.add(matrix[i][l]);
            if (++l > r) break;
        }
        return res; 
    }

36. 旋轉圖像?②

?給定一個?n?×?n?的二維矩陣?matrix?表示一個圖像。請你將圖像順時針旋轉 90 度。

你必須在?原地?旋轉圖像，這意味著你需要直接修改輸入的二維矩陣。請不要?使用另一個矩陣來旋轉圖像。

示例 1：

輸入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
輸出：[[7,4,1],[8,5,2],[9,6,3]]

示例 2：

輸入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
輸出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

提示：

• n == matrix.length == matrix[i].length
• 1 <= n <= 20
• -1000 <= matrix[i][j] <= 1000

方法1：（0ms）

    public static void rotate(int[][] matrix) {
        int n = matrix.length;
        int row = 0;
        int col = n - 1;
        int index = 0;
        while (row < col){
            while (row + index < col) {
                int leftUp = matrix[row][row + index];
                int rightUp = matrix[row + index][col];
                int rightDown = matrix[col][col - index];
                int leftDown = matrix[col - index][row];
                matrix[row][row + index] = leftDown;
                matrix[row + index][col] = leftUp;
                matrix[col][col - index] = rightUp;
                matrix[col - index][row] = rightDown;
                index++;
            }
            index = 0;
            row++;
            col--;
        }

    }

37. 矩陣置零?②

?給定一個?m x n?的矩陣，如果一個元素為?0?，則將其所在行和列的所有元素都設為?0?。請使用?原地?算法。

示例 1：

輸入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
輸出：[[1,0,1],[0,0,0],[1,0,1]]

示例 2：

輸入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
輸出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

提示：

• m == matrix.length
• n == matrix[0].length
• 1 <= m, n <= 200
• -231 <= matrix[i][j] <= 231 - 1

進階：

• 一個直觀的解決方案是使用 ?O(mn)?的額外空間，但這并不是一個好的解決方案。
• 一個簡單的改進方案是使用?O(m?+?n)?的額外空間，但這仍然不是最好的解決方案。
• 你能想出一個僅使用常量空間的解決方案嗎？

方法1：

    public void setZeroes(int[][] matrix) {
        TreeSet<Integer> rowSet = new TreeSet<>();
        TreeSet<Integer> columnSet = new TreeSet<>();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0){
                    rowSet.add(i);
                    columnSet.add(j);
                }
            }
        }
        for (int i = 0; i < matrix.length; i++) {
            if (rowSet.contains(i)){
                Arrays.fill(matrix[i], 0);
            }
        }
        for (int i = 0; i < matrix[0].length; i++) {
            if (columnSet.contains(i)){
                for (int j = 0; j < matrix.length; j++) {
                    matrix[j][i] = 0;
                }
            }
        }
    }

方法2：

    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        // 統(tǒng)計行列是否需要置為0 空間復雜度 O(m+n)
        boolean[] zeroRow = new boolean[m];
        boolean[] zeroCol = new boolean[n];
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(matrix[i][j] == 0){
                    zeroRow[i] = true;
                    zeroCol[j] = true;
                }
            }
        }

        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(zeroRow[i] || zeroCol[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }

38. 生命游戲?②

?根據(jù)?百度百科?，?生命游戲?，簡稱為?生命?，是英國數(shù)學家約翰·何頓·康威在 1970 年發(fā)明的細胞自動機。

給定一個包含?m × n?個格子的面板，每一個格子都可以看成是一個細胞。每個細胞都具有一個初始狀態(tài)：?1?即為?活細胞?（live），或?0?即為?死細胞?（dead）。每個細胞與其八個相鄰位置（水平，垂直，對角線）的細胞都遵循以下四條生存定律：

1. 如果活細胞周圍八個位置的活細胞數(shù)少于兩個，則該位置活細胞死亡；
2. 如果活細胞周圍八個位置有兩個或三個活細胞，則該位置活細胞仍然存活；
3. 如果活細胞周圍八個位置有超過三個活細胞，則該位置活細胞死亡；
4. 如果死細胞周圍正好有三個活細胞，則該位置死細胞復活；

下一個狀態(tài)是通過將上述規(guī)則同時應用于當前狀態(tài)下的每個細胞所形成的，其中細胞的出生和死亡是同時發(fā)生的。給你?m x n?網(wǎng)格面板?board?的當前狀態(tài)，返回下一個狀態(tài)。

示例 1：

輸入：board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
輸出：[[0,0,0],[1,0,1],[0,1,1],[0,1,0]]

示例 2：

輸入：board = [[1,1],[1,0]]
輸出：[[1,1],[1,1]]

提示：

• m == board.length
• n == board[i].length
• 1 <= m, n <= 25
• board[i][j]?為?0?或?1

進階：

• 你可以使用原地算法解決本題嗎？請注意，面板上所有格子需要同時被更新：你不能先更新某些格子，然后使用它們的更新后的值再更新其他格子。
• 本題中，我們使用二維數(shù)組來表示面板。原則上，面板是無限的，但當活細胞侵占了面板邊界時會造成問題。你將如何解決這些問題？

方法1：（0ms）文章來源地址http://www.zghlxwxcb.cn/news/detail-851160.html

    public static void gameOfLife(int[][] board) {
        int[][] map = new int[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                int row = Math.max(i - 1, 0);
                int col = Math.max(j - 1, 0);
                int src = board[i][j];
                int count = 0;
                while (row < board.length && col < board[0].length){
                    count += board[row][col];
                    col++;
                    if (col == j + 2 || col == board[0].length){
                        row++;
                        col = Math.max(j - 1, 0);
                    }
                    if (row == i + 2 || row == board.length){
                        break;
                    }
                }
                count -= src;
                if (src == 1 && count == 1) {
                    map[i][j] = 0;
                }else if (src == 1 && (count == 2 || count == 3)){
                    map[i][j] = 1;
                }else if (src == 1 && count > 3){
                    map[i][j] = 0;
                }else if (src == 0 && count == 3){
                    map[i][j] = 1;
                }
            }
        }
//        board = map;
//        for (int[] ints : board) {
//            System.out.println(Arrays.toString(ints));
//        }
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                board[i][j] = map[i][j];
            }
        }
    }

到了這里，關于【滑動窗口、矩陣】算法例題的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！