天天看點
傳回

LeetCode Weekly Contest 1675283. 二進制連結清單轉整數 顯示英文描述5124. 順次數 顯示英文描述5285. 元素和小于等于門檻值的正方形的最大邊長 顯示英文描述5286. 網格中的最短路徑 顯示英文描述

5283. 二進制連結清單轉整數 顯示英文描述

給你一個單連結清單的引用結點 head。連結清單中每個結點的值不是 0 就是 1。已知此連結清單是一個整數數字的二進制表示形式。

請你傳回該連結清單所表示數字的 十進制值 。

示例 1：

輸入：head = [1,0,1]

輸出：5

解釋：二進制數 (101) 轉化為十進制數 (5)

示例 2：

輸入：head = [0]

輸出：0

示例 3：

輸入：head = [1]

輸出：1

示例 4：

輸入：head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0]

輸出：18880

示例 5：

輸入：head = [0,0]

輸出：0

提示：

連結清單不為空。

連結清單的結點總數不超過 30。

每個結點的值不是 0 就是 1。

思路

由于C++中有無符号類型而Java中沒有，是以在C++中移位不用考慮補碼問題，故此題采用C++實作。

代碼 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    int getDecimalValue(ListNode* head) {
        unsigned int ans = 0;
        while (head) {
            ans = (ans << 1) + (unsigned int)(head->val);
            head = head->next;
        }
        return (int) ans;
    }
};

5124. 順次數 顯示英文描述

我們定義「順次數」為：每一位上的數字都比前一位上的數字大 1 的整數。

請你傳回由 [low, high] 範圍内所有順次數組成的 有序 清單（從小到大排序）。

示例 1：

輸出：low = 100, high = 300

輸出：[123,234]

示例 2：

輸出：low = 1000, high = 13000

輸出：[1234,2345,3456,4567,5678,6789,12345]

提示：

10 <= low <= high <= 10^9

思路

簡單的模拟題。下面的代碼裡周遊的時候根據

low

和

high

計算了下界和上界，實際上完全不必要計算上下界。因為在題目所給的範圍内符合各位數字單調上升的整數個數總共隻有

(1+8)*8/2=36

個，直接周遊判斷是否在

[low, high]

之間即可。

代碼 

class Solution {
    private int getHead(int val) {
        while (val >= 10) {
            val /= 10;
        }
        return val;
    }
    
    private int getDigits(int val) {
        int digits = 0;
        while (val > 0) {
            val /= 10;
            ++digits;
        }
        return digits;
    }
    
    private int genUp(int head, int digits) {
        int val = head;
        --digits;
        while (digits > 0) {
            val *= 10;
            ++head;
            val += head;
            --digits;
        }
        return val;
    }
    
    public List<Integer> sequentialDigits(int low, int high) {
        int lowHead = getHead(low), lowDigits = getDigits(low), highHead = getHead(high), highDigits = getDigits(high), head = lowHead, digits = lowDigits, tmp = -1;
        List<Integer> ans = new ArrayList<>();
        while (true) {
            if (head + digits <= 10) {
                tmp = genUp(head, digits);
            } else {
                tmp = -1;
            }
            if ((digits > highDigits) || (digits == highDigits && head > highHead)) {
                break;
            } else if (head == highHead && digits == highDigits) {
                if (tmp != -1 && tmp <= high && tmp >= low) {
                    ans.add(tmp);
                }
                break;
            } else {
                if (tmp != -1) {
                    if (tmp >= low && tmp <= high) {
                        ans.add(tmp);
                    }
                }
                if (tmp == -1) {
                    head = 1;
                    ++digits;
                } else {
                    ++head;
                }
            }
        }
        return ans;
    }
}

5285. 元素和小于等于門檻值的正方形的最大邊長 顯示英文描述

給你一個大小為 m x n 的矩陣 mat 和一個整數門檻值 threshold。

請你傳回元素總和小于或等于門檻值的正方形區域的最大邊長；如果沒有這樣的正方形區域，則傳回 0 。

示例 1：

輸入：mat = [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]], threshold = 4

輸出：2

解釋：總和小于 4 的正方形的最大邊長為 2，如圖所示。

示例 2：

輸入：mat = [[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2]], threshold = 1

輸出：0

示例 3：

輸入：mat = [[1,1,1,1],[1,0,0,0],[1,0,0,0],[1,0,0,0]], threshold = 6

輸出：3

示例 4：

輸入：mat = [[18,70],[61,1],[25,85],[14,40],[11,96],[97,96],[63,45]], threshold = 40184

輸出：2

提示：

1 <= m, n <= 300

m == mat.length

n == mat[i].length

0 <= mat[i][j] <= 10000

0 <= threshold <= 10^5

思路

對正方形的邊長二分搜尋，對于每個邊長，周遊所有可能的正方形求面積。“周遊所有正方形求面積”采用字首和實作，預先計算好

m*n

各以(0,0)為左頂點的矩形面積，這樣一來，求字首和的複雜度為

O(m*n)

，在每個邊長下周遊所有正方形求面積的複雜度也是

O(m*n)

，後者重複計算

O(log(min(m,n))

次，總的時間複雜度為

O(log(min(m,n)) * m * n)

代碼 

class Solution {
    private void getSuffix(int[][] mat, int[][] suffix) {
        int m = mat.length, n = mat[0].length, i = 0, j = 0;
        suffix[0][0] = mat[0][0];
        for (j=1; j<n; ++j) {
            suffix[0][j] = suffix[0][j-1] + mat[0][j];
        }
        for (i=1; i<m; ++i) {
            suffix[i][0] = suffix[i-1][0] + mat[i][0];
        }
        for (i=1; i<m; ++i) {
            for (j=1; j<n; ++j) {
                suffix[i][j] = suffix[i-1][j] + suffix[i][j-1] - suffix[i-1][j-1] + mat[i][j];
            }
        }
    }
    
    private boolean checkSquare(int[][] suffix, int s, int threshold) {
        int m = suffix.length, n = suffix[0].length, i = 0, j = 0, tmp = 0;
        for (i=0; i<=m-s; ++i) {
            for (j=0; j<=n-s; ++j) {
                if (i == 0 && j == 0) {
                    tmp = suffix[s-1][s-1];
                } else if (i == 0) {
                    tmp = suffix[s-1][j+s-1] - suffix[s-1][j-1];
                } else if (j == 0) {
                    tmp = suffix[i+s-1][s-1] - suffix[i-1][s-1];
                } else {
                    tmp = suffix[i+s-1][j+s-1] - suffix[i+s-1][j-1] - suffix[i-1][j+s-1] + suffix[i-1][j-1];
                }
                if (tmp <= threshold) {
                    return true;
                }
            }
        }
        return false;
    }
    
    //for debug
    private void printMat(int[][] mat) {
        for (int[] row: mat) {
            for (int item: row) {
                System.out.print(item + " ");
            }
            System.out.print('\n');
        }
        System.out.println();
    }
    
    public int maxSideLength(int[][] mat, int threshold) {
        int m = mat.length, n = mat[0].length, left = 1, right = Math.min(m, n), mid = 0;
        int[][] suffix = new int[m][n];
        getSuffix(mat, suffix);
        while (left <= right) {
            mid = (left + right) / 2;
            if (checkSquare(suffix, mid, threshold)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return right;
    }
}

5286. 網格中的最短路徑 顯示英文描述

給你一個 m * n 的網格，其中每個單元格不是 0（空）就是 1（障礙物）。每一步，您都可以在空白單元格中上、下、左、右移動。

如果您 最多 可以消除 k 個障礙物，請找出從左上角 (0, 0) 到右下角 (m-1, n-1) 的最短路徑，并傳回通過該路徑所需的步數。如果找不到這樣的路徑，則傳回 -1。

示例 1：

輸入：

grid =

[[0,0,0],

[1,1,0],

[0,0,0],

[0,1,1],

[0,0,0]],

k = 1

輸出：6

解釋：

不消除任何障礙的最短路徑是 10。

消除位置 (3,2) 處的障礙後，最短路徑是 6 。該路徑是 (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2).

示例 2：

輸入：

grid =

[[0,1,1],

[1,1,1],

[1,0,0]],

k = 1

輸出：-1

解釋：

我們至少需要消除兩個障礙才能找到這樣的路徑。

提示：

grid.length == m

grid[0].length == n

1 <= m, n <= 40

1 <= k <= m*n

grid[i][j] == 0 or 1

grid[0][0] == grid[m-1][n-1] == 0

思路

在傳統的bfs求無權圖最短路的基礎上，增加一個搜尋狀态次元k，進而變成一個在三維空間(x, y, k)的bfs搜尋。其中x, y表示矩陣中的橫縱坐标索引，k表示走到矩陣中這個位置時，還剩下幾次“穿牆”可以使用。k < 0的狀态是無效狀态。

代碼 

class Solution {
    class Position {
        int x, y, k, dis;
        
        public Position(int x, int y, int k, int dis) {
            this.x = x;
            this.y = y;
            this.k = k;
            this.dis = dis;
        }
    }
    
    int[] MOV_X = {1, -1, 0, 0}, MOV_Y = {0, 0, 1, -1};
    
    private int shortestK(int[][] grid, int k) {
        int m = grid.length, n = grid[0].length, i = 0, nx = 0, ny = 0, nk = 0;
        LinkedList<Position> q = new LinkedList<Position>();
        boolean[][][] vis = new boolean[m][n][k+1];
        vis[0][0][k] = true;
        q.add(new Position(0, 0, k, 0));
        while (!q.isEmpty()) {
            Position p = q.removeFirst();
            if (p.x == m-1 && p.y == n-1) {
                return p.dis;
            }
            for (i=0; i<4; ++i) {
                nx = p.x + MOV_X[i];
                ny = p.y + MOV_Y[i];
                if (nx < 0 || ny < 0 || nx >= m || ny >= n) {
                    continue;
                }
                if (grid[nx][ny] == 1) {
                    nk = p.k - 1;
                } else {
                    nk = p.k;
                }
                if (nk < 0) {
                    continue;
                }
                if (vis[nx][ny][nk]) {
                    continue;
                }
                q.add(new Position(nx, ny, nk, p.dis + 1));
                vis[nx][ny][nk] = true;
            }
        }
        return -1;
    }
    
    public int shortestPath(int[][] grid, int k) {
        return shortestK(grid, k);
    }
}
leetcode 周賽 java
上一篇: ThreadLocal簡單的學習和了解過程
下一篇: 49-C++使用for循環通路字元串

繼續閱讀