Java?C++題解leetcode764最大加號標志示例
更新時間：2023年01月16日 11:37:03 作者：AnjaVon
這篇文章主要為大家介紹了Java?C++題解leetcode764最大加號標志示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪
題目
思路：前綴和
Java
class Solution {
public int orderOfLargestPlusSign(int n, int[][] mines) {
// 構建網格與雷
int[][] grid = new int[n + 1][n + 1];
for (int i = 1; i <= n; i++)
Arrays.fill(grid[i], 1);
for (var m : mines)
grid[m[0] + 1][m[1] + 1] = 0;
// 上下左右前綴和
int[][] up = new int[n + 10][n + 10], down = new int[n + 10][n + 10], left = new int[n + 10][n + 10], right = new int[n + 10][n + 10];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (grid[i][j] == 1){
right[i][j] = right[i - 1][j] + 1;
down[i][j] = down[i][j - 1] + 1;
}
if (grid[n + 1 - i][n + 1 - j] == 1) {
left[n + 1 - i][n + 1 - j] = left[n + 2 - i][n + 1 - j] + 1;
up[n + 1 - i][n + 1 - j] = up[n + 1 - i][n + 2 - j] + 1;
}
}
}
// 找答案，四方向上的最小值即為當前點的十字大小
int res = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
res = Math.max(res, Math.min(Math.min(right[i][j], down[i][j]), Math.min(left[i][j], up[i][j])));
}
}
return res;
}
}
- 時間復雜度：O(n^2)
- 空間復雜度：O(n^2)
C++
class Solution {
public:
int orderOfLargestPlusSign(int n, vector<vector<int>>& mines) {
// 構建網格與雷
int grid[n + 1][n + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
grid[i][j] = 1;
}
}
for (auto m : mines)
grid[m[0] + 1][m[1] + 1] = 0;
// 上下左右前綴和
int up[n + 10][n + 10], down[n + 10][n + 10], left[n + 10][n + 10], right[n + 10][n + 10];
memset(up, 0, sizeof(up));
memset(down, 0, sizeof(down));
memset(left, 0, sizeof(left));
memset(right, 0, sizeof(right));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (grid[i][j] == 1){
right[i][j] = right[i - 1][j] + 1;
down[i][j] = down[i][j - 1] + 1;
}
if (grid[n + 1 - i][n + 1 - j] == 1) {
left[n + 1 - i][n + 1 - j] = left[n + 2 - i][n + 1 - j] + 1;
up[n + 1 - i][n + 1 - j] = up[n + 1 - i][n + 2 - j] + 1;
}
}
}
// 找答案，四方向上的最小值即為當前點的十字大小
int res = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
res = max(res, min(min(right[i][j], down[i][j]), min(left[i][j], up[i][j])));
}
}
return res;
}
};
- 時間復雜度：O(n^2)
- 空間復雜度：O(n^2)
Rust
impl Solution {
pub fn order_of_largest_plus_sign(n: i32, mines: Vec<Vec<i32>>) -> i32 {
// 構建網格與雷
let n = n as usize;
let mut grid = vec![vec![1; n + 1]; n + 1];
mines.iter().for_each(|m| grid[m[0] as usize + 1][m[1] as usize + 1] = 0);
// 上下左右前綴和
let (mut up, mut down, mut left, mut right) = (vec![vec![0; n + 10]; n + 10], vec![vec![0; n + 10]; n + 10], vec![vec![0; n + 10]; n + 10], vec![vec![0; n + 10]; n + 10]);
for i in 1..=n {
for j in 1..=n {
if (grid[i][j] == 1){
right[i][j] = right[i - 1][j] + 1;
down[i][j] = down[i][j - 1] + 1;
}
if (grid[n + 1 - i][n + 1 - j] == 1) {
left[n + 1 - i][n + 1 - j] = left[n + 2 - i][n + 1 - j] + 1;
up[n + 1 - i][n + 1 - j] = up[n + 1 - i][n + 2 - j] + 1;
}
}
}
// 找答案，四方向上的最小值即為當前點的十字大小
let mut res = 0;
for i in 1..=n {
for j in 1..=n {
res = res.max(right[i][j].min(left[i][j]).min(down[i][j].min(up[i][j])));
}
}
res
}
}
- 時間復雜度：O(n^2)
- 空間復雜度：O(n^2)
總結
意外的前綴和，本來想用DFS的；
還是蠻快樂的模擬題~
以上就是Java C++題解leetcode764最大加號標志示例的詳細內容，更多關于Java C++題解最大加號標志的資料請關注腳本之家其它相關文章！
相關文章
單例模式（Singleton Pattern）是 Java 中最簡單的設計模式之一。這種類型的設計模式屬于創(chuàng)建型模式，它提供了一種創(chuàng)建對象的最佳方式，這種模式涉及到一個單一的類，該類負責創(chuàng)建自己的對象，同時確保只有單個對象被創(chuàng)建2021-10-10
這篇文章主要介紹了IntelliJ IDEA的build path設置方法，本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2021-04-04
這篇文章主要為大家詳細介紹了JavaFX實現簡單日歷效果，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-11-11
測試是開發(fā)的一個非常重要的方面，可以在很大程度上決定一個應用程序的命運。良好的測試可以在早期捕獲導致應用程序崩潰的問題，但較差的測試往往總是導致故障和停機。本文主要介紹java程序員編寫更好的單元測試的7個技巧。下面跟著小編一起來看下吧2017-03-03
什么是正則表達式，正則表達式的作用是什么？這篇文章主要為大家詳細介紹了Java正則表達式的相關資料，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-05-05
通過實例了解java checked和unchecked異常
這篇文章主要介紹了通過實例了解checked和unchecked異常，Java異常分為兩種類型，checked異常和unchecked異常，另一種叫法是異常和錯誤。下面小編就帶大家來一起學習一下吧2019-06-06
fastjson轉換對象實體@JsonProperty不生效問題及解決
這篇文章主要介紹了fastjson轉換對象實體@JsonProperty不生效問題及解決，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-08-08
spring Mvc配置xml使ResponseBody返回Json的方法示例
這篇文章主要給大家介紹了關于spring Mvc配置xml使ResponseBody返回Json的相關資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧。2018-04-04
這篇文章主要為大家介紹了Spring?IOC容器的Bean管理基于注解屬性注入方式，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-05-05
這篇文章主要介紹了ssm 使用token校驗登錄的實現，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-04-04