- 下降路徑最小和 II
給你一個(gè) n x n 整數(shù)矩陣 grid ，請(qǐng)你返回 非零偏移下降路徑 數(shù)字和的最小值。非零偏移下降路徑 定義為：從 grid 數(shù)組中的每一行選擇一個(gè)數(shù)字，且按順序選出來(lái)的數(shù)字中，相鄰數(shù)字不在原數(shù)組的同一列。
f[i][j] 表示從數(shù)組的前i行中的每一行選擇一個(gè)數(shù)字，并且第 i 行選擇的數(shù)字為 grid[i][j]時(shí)，可以得到的路徑和最小值
class Solution {
public:
int minFallingPathSum(vector<vector<int>>& grid) {
int n = grid.size();
vector<vector<int>> d(n, vector<int>(n, INT_MAX));
for (int i = 0; i < n; i++) {
d[0][i] = grid[0][i];
}
for (int i = 1; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
if (j == k) {
continue;
}
d[i][j] = min(d[i][j], d[i - 1][k] + grid[i][j]);
}
}
}
int res = INT_MAX;
for (int j = 0; j < n; j++) {
res = min(res, d[n - 1][j]);
}
return res;
}
};
- 二進(jìn)制鏈表轉(zhuǎn)整數(shù)
給你一個(gè)單鏈表的引用結(jié)點(diǎn) head。鏈表中每個(gè)結(jié)點(diǎn)的值不是 0 就是 1。已知此鏈表是一個(gè)整數(shù)數(shù)字的二進(jìn)制表示形式。請(qǐng)你返回該鏈表所表示數(shù)字的 十進(jìn)制值 。
按位操作即可。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
int getDecimalValue(ListNode* head) {
int n = 0;
while (head)
{
n = n << 1 | head->val;
head = head->next;
}
return n;
}
};
- 順次數(shù)
我們定義「順次數(shù)」為：每一位上的數(shù)字都比前一位上的數(shù)字大 1 的整數(shù)。請(qǐng)你返回由 [low, high] 范圍內(nèi)所有順次數(shù)組成的 有序 列表（從小到大排序）。
外層循環(huán)定第一位數(shù)字，內(nèi)層循環(huán)遍歷所有可能性，枚舉就完事。
class Solution {
public:
vector<int> sequentialDigits(int low, int high) {
vector<int> ans;
for (int i = 1; i <= 9; ++i) {
int num = i;
for (int j = i + 1; j <= 9; ++j) {
num = num * 10 + j;
if (num >= low && num <= high) {
ans.push_back(num);
}
}
}
sort(ans.begin(), ans.end());
return ans;
}
};
- 元素和小于等于閾值的正方形的最大邊長(zhǎng)
給你一個(gè)大小為 m x n 的矩陣 mat 和一個(gè)整數(shù)閾值 threshold。請(qǐng)你返回元素總和小于或等于閾值的正方形區(qū)域的最大邊長(zhǎng)；如果沒(méi)有這樣的正方形區(qū)域，則返回 0 。
要點(diǎn)主要有：1.二位前綴和；2.三種循環(huán)遍歷查找；3. 三種循環(huán)的兩個(gè)優(yōu)化：找到了大小為n的，后面直接n+1找起/如果c都不行，后面就不用看了直接跳過(guò)當(dāng)前循環(huán)。
class Solution {
public:
int getRect(const vector<vector<int>>& P, int x1, int y1, int x2, int y2) {
return P[x2][y2] - P[x1 - 1][y2] - P[x2][y1 - 1] + P[x1 - 1][y1 - 1];
}
int maxSideLength(vector<vector<int>>& mat, int threshold) {
int m = mat.size(), n = mat[0].size();
vector<vector<int>> P(m + 1, vector<int>(n + 1));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
P[i][j] = P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] + mat[i - 1][j - 1];
}
}
int r = min(m, n), ans = 0;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
for (int c = ans + 1; c <= r; ++c) {
if (i + c - 1 <= m && j + c - 1 <= n && getRect(P, i, j, i + c - 1, j + c - 1) <= threshold) {
++ans;
}
else {
break;
}
}
}
}
return ans;
}
};
- 網(wǎng)格中的最短路徑
給你一個(gè) m * n 的網(wǎng)格，其中每個(gè)單元格不是 0（空）就是 1（障礙物）。每一步，您都可以在空白單元格中上、下、左、右移動(dòng)。如果您 最多 可以消除 k 個(gè)障礙物，請(qǐng)找出從左上角 (0, 0) 到右下角 (m-1, n-1) 的最短路徑，并返回通過(guò)該路徑所需的步數(shù)。如果找不到這樣的路徑，則返回 -1 。
廣度優(yōu)先搜索 + 隊(duì)列
struct Nagato {
int x, y;
int rest;
Nagato(int _x, int _y, int _r): x(_x), y(_y), rest(_r) {}
};
class Solution {
private:
static constexpr int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public:
int shortestPath(vector<vector<int>>& grid, int k) {
int m = grid.size(), n = grid[0].size();
if (m == 1 && n == 1) {
return 0;
}
k = min(k, m + n - 3);
bool visited[m][n][k + 1];
memset(visited, false, sizeof(visited));
queue<Nagato> q;
q.emplace(0, 0, k);
visited[0][0][k] = true;
for (int step = 1; q.size() > 0; ++step) {
int cnt = q.size();
for (int _ = 0; _ < cnt; ++_) {
Nagato cur = q.front();
q.pop();
for (int i = 0; i < 4; ++i) {
int nx = cur.x + dirs[i][0];
int ny = cur.y + dirs[i][1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
if (grid[nx][ny] == 0 && !visited[nx][ny][cur.rest]) {
if (nx == m - 1 && ny == n - 1) {
return step;
}
q.emplace(nx, ny, cur.rest);
visited[nx][ny][cur.rest] = true;
}
else if (grid[nx][ny] == 1 && cur.rest > 0 && !visited[nx][ny][cur.rest - 1]) {
q.emplace(nx, ny, cur.rest - 1);
visited[nx][ny][cur.rest - 1] = true;
}
}
}
}
}
return -1;
}
};
- 統(tǒng)計(jì)位數(shù)為偶數(shù)的數(shù)字
給你一個(gè)整數(shù)數(shù)組 nums，請(qǐng)你返回其中位數(shù)為 偶數(shù) 的數(shù)字的個(gè)數(shù)。
轉(zhuǎn)化成string取長(zhǎng)度，或者直接對(duì)數(shù)看奇偶。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-705850.html
class Solution {
public:
int findNumbers(vector<int>& nums) {
int ans = 0;
for (int num: nums) {
if ((int)(log10(num) + 1) % 2 == 0) {
++ans;
}
}
return ans;
}
};
- 劃分?jǐn)?shù)組為連續(xù)數(shù)字的集合
給你一個(gè)整數(shù)數(shù)組 nums 和一個(gè)正整數(shù) k，請(qǐng)你判斷是否可以把這個(gè)數(shù)組劃分成一些由 k 個(gè)連續(xù)數(shù)字組成的集合。
如果可以，請(qǐng)返回 true；否則，返回 false。
貪心算法：排序后依次遍歷。用一個(gè)哈希表存儲(chǔ)元素及其次數(shù)，每次用到了就–。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-705850.html
class Solution {
public:
bool isPossibleDivide(vector<int>& nums, int k) {
int n = nums.size();
if (n % k != 0) {
return false;
}
sort(nums.begin(), nums.end());
unordered_map<int, int> cnt;
for (auto & num : nums) {
cnt[num]++;
}
for (auto & x : nums) {
if (!cnt.count(x)) {
continue;
}
for (int j = 0; j < k; j++) {
int num = x + j;
if (!cnt.count(num)) {
return false;
}
cnt[num]--;
if (cnt[num] == 0) {
cnt.erase(num);
}
}
}
return true;
}
};
到了這里，關(guān)于leetcode解題思路分析（一百四十八）1289 - 1296 題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
