公网站建设,云南云南省建设厅网站,龙华区网站建设,网站开发资金投入lc3015.法1#xff1a;暴力bfs#xff0c;数据范围only 100#xff0c;可以过法2#xff1a;加入了x,y#xff0c;可以思考加入的x,y影响了什么呢? 通过数学找规律class Solution {
public:vectorint countOfPairs(int n, int x, int y) {vectorint ret(…
lc3015.法1暴力bfs数据范围only 100可以过 法2加入了x,y可以思考加入的x,y影响了什么呢? 通过数学找规律
class Solution {
public:vectorint countOfPairs(int n, int x, int y) {vectorint ret(n, 0);for (int i 1; i n; i) {for (int j i 1; j n; j) {// 计算三种可能路径的最短距离int direct j - i; int viaX abs(i - x) 1 abs(j - y); int viaY abs(i - y) 1 abs(j - x); int minDist min({direct, viaX, viaY});ret[minDist - 1] 2;}}return ret;}
}; assignassign 是容器比如 vector的一个接口作用清空容器原来的内容然后放入新的元素。打个比方就像你有一个盒子 assign(n, false) 就相当于- 先把盒子里原来的东西全倒掉- 再往盒子里放 n 个 false 这样能确保容器里的内容是全新的不会有之前残留的数据避免出错。
lc523.同余定理两个注意点同余定理余数相同的两个数做差可被整除。--前缀和hash存mod不可以用set因为要保证len大于等于2所以要存idx映射还有对于全选和全不选的两个边界下标初始化处理
同余定理就是说两个整数 a 和 b如果除以同一个正整数 m 后余数相同就称 a 和 b 对 m 同余简单记成 a ≡ b (mod m) 大白话就是“除以 m 剩得一样” 。比如 17 和 5 除以 6 都余 5就说 17 和 5 对 6 同余 。则(17-5)%60余数相同的两个数做差可被整除。class Solution {
public:bool checkSubarraySum(vectorint nums, int k) {int nnums.size();vectorint f(n1,0);for(int i0;in;i){f[i1]f[i]nums[i];}unordered_mapint,int hash;hash[0]0;for(int i0;in;i){int modf[i]%k;if(hash.count(mod)){if(i-hash[mod]2)return true;}elsehash[mod]i;}return false;}
};
lc1423.滑动窗口➕正难则反(用滑动窗口就要转化为连续部分才能滑) 取两边最大-转化为中间最小
喜提tle....class Solution {vectorint card;int n0,k0,ret0;
public:int maxScore(vectorint cardPoints, int k) {cardcardPoints;this-kk;ncardPoints.size();dfs(0,n-1,0,0);return ret;}void dfs(int b,int e,int sum,int cnt){if(cntk) { retmax(ret,sum);return;}dfs(b,e-1,sumcard[e],cnt1);dfs(b1,e,sumcard[b],cnt1);}
};滑动窗口正难则反class Solution {public: int maxScore(vectorint cardPoints, int k) { int retINT_MAX,sum0; int l0,r0; int ncardPoints.size(); int wn-k; int tt0; for(auto c:cardPoints) ttc; while(rn) { sumcardPoints[r]; r; if(r-lw) { retmin(ret,sum); sum-cardPoints[l]; l; } } int anstt-ret; if(retINT_MAX) anstt; return ans; }};
