再再再再再再再再次翻车了
第三个没仔细想+超时挂了3次
第四个最大值没搞好+瞎提交WA了3次。。。
思维又慢，码得又慢，没救了。
模拟一下， 旋转可以多次，但状态最多就4种：
不旋转，旋转90度，旋转180度，旋转270度。
这里循环一下， 每次旋转90度，在比较是否相等就好了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution {
public:
bool findRotation(vector<vector<int>>& mat, vector<vector<int>>& target) {
int n = mat.size();
vector<vector<int>> temp(n, vector<int>(n));
for(int k=0;k<4;k++) {
if(mat == target) return true;
for(int i=0;i<n/2;i++){
for(int j=i;j<n-1-i;j++) {
temp[i][j] = mat[n-1-j][i];
temp[j][n-1-i] = mat[i][j];
temp[n-1-i][n-1-j] = mat[j][n-1-i];
temp[n-1-j][i] = mat[n-1-i][n-1-j];
}
}
if(n&1) temp[n/2][n/2] = mat[n/2][n/2];
mat = temp;
}
return false;
}
};
|
如果存在两个数，a<b ， 则b一定会变到a的转态。所以统计会变成当前数字的数字个数就好。
处理的话，因为有重复值，所以放到一个桶里面。从小到大遍历上去统计就好。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
int sum[50005];
int reductionOperations(vector<int>& nums) {
int tot = nums.size();
int mx = nums[0];
memset(sum, 0, sizeof(sum));
for(auto a: nums) sum[a]++, mx = max(mx, a);
int ans = 0;
for(int i=1;i<=mx;i++) {
if(sum[i] != 0) {
ans += tot - sum[i] - sum[i-1];
}
sum[i]+=sum[i-1];
}
return ans;
}
};
|
这里写的有点丑，代码没法看，，
分情况讨论：
- 偶数长度的字符串：它要么变成
0101010这种，要么变成101010这种，第一个操作对他无影响。 - 奇数长度的字符串：第一个操作对他有影响，
10101是可以变成10110的。所以这种情况下，可以分成两段，前一段1开头，后一段0开头。或者前一段0开头，后一段1开头。
注意奇数的情况下处理时可以线性。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| class Solution {
public:
int f(string s, bool flag, bool flag2 = false) {
int l = s.size();
string s1, s2;
for(int i=0;i<l;i++) {
s1 += (i&1^flag)?"0":"1";
s2 += (i&1^flag)?"1":"0";
}
int sum = 0;
for(int i=0;i<l;i++) {
if(s[i] != s1[i]) ++sum;
}
if(flag2) return sum;
int ans = sum;
int cnt1 = 0, cnt2 = 0;
for(int i=0;i<l;i++){
if(s[i] != s1[i]) ++cnt1;
if(s[i] != s2[i]) ++cnt2;
ans = min(ans, sum - cnt1 + cnt2);
}
return ans;
}
int minFlips(string s) {
int l = s.size();
if(l&1) return min(f(s, true), f(s, false));
else {
return min(f(s, true, true), f(s, false, true));
}
}
};
|
考虑数据范围，只可以遍历所有商家的所有盒子。
针对不同商家统计每个盒子的空余空间就好。一个盒子，利用两个前缀和统计需要使用它的货物个数，以及需要使用它货物占用大小总数，最后减一下就好了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| class Solution {
public:
static const int MOD = 1e9+7;
static const int N = 1e5+7;
typedef long long int LL;
LL sum[N];
LL tot[N];
int minWastedSpace(vector<int>& a, vector<vector<int>>& b) {
memset(sum, 0, sizeof(sum));
memset(tot, 0, sizeof(tot));
int mx = 0;
for(auto x: a) sum[x]++, tot[x]+=x, mx = max(mx, x);
for(int i=1;i<=100000;i++) {
sum[i] += sum[i-1];
tot[i] += tot[i-1];
}
LL ans = 1000000000000LL;
bool flag = false;
for(auto t: b) {
sort(t.begin(), t.end());
if(t[t.size()-1] >= mx) flag = true;
else continue;
int p = 0;
LL tmp = 0;
for(auto bb: t){
tmp += (sum[bb]-sum[p]) * bb - (tot[bb] - tot[p]);
p = bb;
}
ans = min(ans, tmp);
}
if(!flag) return -1;
return ans%MOD;
}
};
|
