?
lcp56. memo優化tle
或者改用bfs
class Solution {
? ? int m, n;
? ? int dx[4] = {0, 0, 1, -1};
? ? int dy[4] = {1, -1, 0, 0};
? ??
public:
? ? int conveyorBelt(vector<string>& matrix, vector<int>& start, vector<int>& end)?
? ? {
? ? ? ? int ret = INT_MAX;
? ? ? ? m = matrix.size();
? ? ? ? n = matrix[0].size();
? ? ? ? vector<vector<bool>> vis(m, vector<bool>(n, false));
? ? ? ? vis[start[0]][start[1]] = true;?
? ? ? ??
? ? ? ? function<void(int, int, int)> dfs = [&](int a, int b, int cnt)
? ? ? ? {
? ? ? ? ? ? if(cnt>=ret) return;
? ? ? ? ? ? if (a == end[0] && b == end[1])
? ? ? ? ? ? {
? ? ? ? ? ? ? ? ret = min(ret, cnt);
? ? ? ? ? ? ? ? return;
? ? ? ? ? ? }
? ? ? ? ? ??
? ? ? ? ? ? for (int k = 0; k < 4; k++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? int x = a + dx[k], y = b + dy[k];
? ? ? ? ? ? ? ? if (x >= 0 && y >= 0 && x < m && y < n && !vis[x][y])
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? int op = cnt;
? ? ? ? ? ? ? ? ? ? if (check(k) != matrix[a][b])?
? ? ? ? ? ? ? ? ? ? ? ? op++;
? ? ? ? ? ? ? ? ? ? vis[x][y] = true;
? ? ? ? ? ? ? ? ? ? dfs(x, y, op);
? ? ? ? ? ? ? ? ? ? vis[x][y] = false;?
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? };
? ? ? ??
? ? ? ? dfs(start[0], start[1], 0);?
? ? ? ??
? ? ? ? return ret;
? ? }
? ??
? ? char check(int k)
? ? {
? ? ? ? if (k == 0) return '>';
? ? ? ? if (k == 1) return '<';
? ? ? ? if (k == 2) return 'v';
? ? ? ? return '^';?
? ? }
};
?
lc3015.
法1：暴力bfs，數據范圍only 100，可以過
?
法2：加入了x,y，可以思考加入的x,y影響了什么呢? 通過數學找規律
class Solution {
public:
vector<int> countOfPairs(int n, int x, int y) {
vector<int> 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;
}
};
?
assign
assign? 是容器（比如 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)%6=0，余數相同的兩個數，做差可被整除。
class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k)?
{
int n=nums.size();
vector<int> f(n+1,0);
for(int i=0;i<n;i++)
{
f[i+1]=f[i]+nums[i];
}
unordered_map<int,int> hash;
hash[0]=0;
for(int i=0;i<=n;i++)
{
int mod=f[i]%k;
if(hash.count(mod))
{
if(i-hash[mod]>=2)
return true;
}
else
hash[mod]=i;
}
return false;
}
};
?
lc1423.
滑動窗口?正難則反(用滑動窗口，就要轉化為連續部分才能滑～)
?
取兩邊最大->轉化為中間最小
喜提tle....
class Solution {
vector<int> card;
int n=0,k=0,ret=0;
public:
int maxScore(vector<int>& cardPoints, int k)?
{
card=cardPoints;
this->k=k;
n=cardPoints.size();
dfs(0,n-1,0,0);
return ret;
}
void dfs(int b,int e,int sum,int cnt)
{
if(cnt==k)?
{?
ret=max(ret,sum);
return;
}
dfs(b,e-1,sum+card[e],cnt+1);
dfs(b+1,e,sum+card[b],cnt+1);
}
};
滑動窗口，正難則反
class Solution {
public:
? ? int maxScore(vector<int>& cardPoints, int k) {
? ? ? ? int ret=INT_MAX,sum=0;
? ? ? ? int l=0,r=0;
? ? ? ? int n=cardPoints.size();
? ? ? ? int w=n-k;
? ? ? ? int tt=0;
? ? ? ??
? ? ? ? for(auto& c:cardPoints)
? ? ? ? ? ? tt+=c;
? ? ? ??
? ? ? ? while(r<n)
? ? ? ? {
? ? ? ? ? ? sum+=cardPoints[r];
? ? ? ? ? ? r++;
? ? ? ? ? ??
? ? ? ? ? ? if(r-l==w)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? ret=min(ret,sum);
? ? ? ? ? ? ? ? sum-=cardPoints[l];
? ? ? ? ? ? ? ? l++;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? int ans=tt-ret;
? ? ? ? if(ret==INT_MAX) ans=tt;
? ? ? ? return ans;
? ? }
};
?
)
