​LeetCode刷题实战303：区域和检索数组不可变

算法的重要性&＃xff0c;我就不多说了吧&＃xff0c;想去大厂&＃xff0c;就必须要经过基础知识和业务逻辑面试&＃43;算法面试。所以&＃xff0c;为了提高大家的算法能力&＃xff0c;这个公众号后续每天带大家做一道算法题&＃xff0c;题目就从LeetCode上面选 &＃xff01;

今天和大家聊的问题叫做 区域和检索 - 数组不可变&＃xff0c;我们先来看题面&＃xff1a;

https://leetcode-cn.com/problems/range-sum-query-immutable/

给定一个整数数组  nums&＃xff0c;求出数组从索引 i 到 j&＃xff08;i ≤ j&＃xff09;范围内元素的总和&＃xff0c;包含 i、j 两点。

实现 NumArray 类&＃xff1a;

NumArray(int[] nums) 使用数组 nums 初始化对象

int sumRange(int i, int j) 返回数组 nums 从索引 i 到 j&＃xff08;i ≤ j&＃xff09;范围内元素的总和&＃xff0c;包含 i、j 两点&＃xff08;也就是 sum(nums[i], nums[i &＃43; 1], ... , nums[j])&＃xff09;

示例

示例:
输入:
["0010","0110","0100"
]
和 x &＃61; 0, y &＃61; 2输出: 6


解题

找最小矩形的面积&＃xff0c;可以转化为找所有黑色像素的X, Y坐标极值&＃xff0c;这个面积应该等于:(x2-x1&＃43;1)*(y2-y1&＃43;1)

所以一趟DFS可以找到所有黑色的点&＃xff0c;找到每个点的时候刷新一下极值即可。

class Solution {int x1 &＃61; INT_MAX, x2 &＃61; -1;int y1 &＃61; INT_MAX, y2 &＃61; -1;
public:int minArea(vector>& image, int x, int y) {int m &＃61; image.size(), n &＃61; image[0].size(), i, j, nx, ny, k;vector> dir &＃61; {{1,0},{0,1},{0,-1},{-1,0}};queue> q;q.push({x,y});image[x][y] &＃61; &＃39;0&＃39;;//访问过了while(!q.empty()){i &＃61; q.front()[0];j &＃61; q.front()[1];q.pop();x1 &＃61; min(x1, i);x2 &＃61; max(x2, i);y1 &＃61; min(y1, j);y2 &＃61; max(y2, j);for(k &＃61; 0; k <4; &＃43;&＃43;k){nx &＃61; i &＃43; dir[k][0];ny &＃61; j &＃43; dir[k][1];if(nx>&＃61;0 && nx&＃61;0 && ny};


好了&＃xff0c;今天的文章就到这里&＃xff0c;如果觉得有所收获&＃xff0c;请顺手点个在看或者转发吧&＃xff0c;你们的支持是我最大的动力 。

上期推文&＃xff1a;

LeetCode1-280题汇总&＃xff0c;希望对你有点帮助&＃xff01;

LeetCode刷题实战301&＃xff1a;删除无效的括号

LeetCode刷题实战302&＃xff1a;包含全部黑色像素的最小矩阵