class Solution {
public:
int maxSubArray(vector<int>& nums) {
int dp[nums.size()];
dp[0] = nums[0];
int res = dp[0];
for(int i = 1; i < nums.size(); i++)
{
if(dp[i-1] < 0) dp[i] = nums[i];
else dp[i] = dp[i-1] + nums[i];
res = max(res, dp[i]);
}
return res;
}
};
活动打卡代码
LeetCode 554. Brick Wall
class Solution {
public:
int leastBricks(vector<vector<int>>& wall) {
int ans = 0;
unordered_map<int, int> mp;
int n = wall.size();
for(int i = 0; i < n; ++i)
{
int pre = 0;
for(int j = 0; j < wall[i].size() - 1; ++j)
{
pre += wall[i][j];
// cout << pre << endl;
if(mp.find(pre) != mp.end()) mp[pre]++;
else mp[pre] = 1;
ans = max(ans, mp[pre]);
}
}
return n - ans;
}
};
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
class Solution {
public:
int calculate(string s) {
//
stack<char> ops;
stack<long long> nums;
int i = 0;
// for(auto &c : s)
// cout << "zhang" << endl;
while(i < s.length())
{
// i++;
char c = s[i];
cout << c << endl;
if(c == ' ')
{
i++;
continue;
}
if(c >= '0' && c <= '9')
{
long long t = 0;
while(c >= '0' && c <= '9')
{
t = t*10 + c - '0';
i++;
c = s[i];
}
nums.push(t);
}
else
{
if(ops.empty()) ops.push(c);
else if((c == '*' || c == '/'))
{
while(!ops.empty() && (ops.top() == '*' || ops.top() == '/'))
{
if(ops.top() == '*')
{
long long t2 = nums.top(); nums.pop();
long long t1 = nums.top(); nums.pop();
nums.push(t1 * t2);
}
else if(ops.top() == '/')
{
long long t2 = nums.top(); nums.pop();
long long t1 = nums.top(); nums.pop();
nums.push(t1 / t2);
}
ops.pop();
}
ops.push(c);
}
else // + -
{
while(!ops.empty())
{
if(ops.top() == '*')
{
long long t2 = nums.top(); nums.pop();
long long t1 = nums.top(); nums.pop();
nums.push(t1 * t2);
}
else if(ops.top() == '/')
{
long long t2 = nums.top(); nums.pop();
long long t1 = nums.top(); nums.pop();
nums.push(t1 / t2);
}
else if(ops.top() == '+')
{
long long t2 = nums.top(); nums.pop();
long long t1 = nums.top(); nums.pop();
nums.push(t1 + t2);
}
else if(ops.top() == '-')
{
long long t2 = nums.top(); nums.pop();
long long t1 = nums.top(); nums.pop();
nums.push(t1 - t2);
}
ops.pop();
}
ops.push(c); //
}
i++;
}
}
while(!ops.empty())
{
if(ops.top() == '+')
{
long long t2 = nums.top(); nums.pop();
long long t1 = nums.top(); nums.pop();
nums.push(t1 + t2);
}
else if(ops.top() == '-')
{
long long t2 = nums.top(); nums.pop();
long long t1 = nums.top(); nums.pop();
nums.push(t1 - t2);
}
else if(ops.top() == '*')
{
long long t2 = nums.top(); nums.pop();
long long t1 = nums.top(); nums.pop();
nums.push(t1 * t2);
}
else
{
long long t2 = nums.top(); nums.pop();
long long t1 = nums.top(); nums.pop();
nums.push(t1 / t2);
}
ops.pop();
}
return (int)nums.top();
}
};
C++ 代码
class Solution {
private:
bool visited[55][55];
int dx[5] = {-1, 1, 0, 0};
int dy[5] = {0, 0, -1, 1};
int res = 0;
int n, m;
int area = 0;
public:
void dfs(int x, int y, vector<vector<int>>& grid)
{
for(int i = 0; i < 4; ++i)
{
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == 1 && !visited[nx][ny])
{
visited[nx][ny] = true;
area += 1;
dfs(nx, ny, grid);
}
}
}
int maxAreaOfIsland(vector<vector<int>>& grid) {
n = grid.size();
m = grid[0].size();
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < m; ++j)
{
if(!visited[i][j] && grid[i][j] == 1)
{
area = 1;
visited[i][j] = true;
dfs(i, j, grid);
res = max(area, res);
}
}
}
return res;
}
};
控制台
C++ 代码
class Solution {
private:
int n;
vector<vector<int>> res;
vector<int> flag = vector<int> (8, 0);
vector<int> index = vector<int> (8, 0);
public:
void dfs(int step, vector<int>& nums)
{
if(step == n)
{
vector<int> tmp;
for(int i = 0; i < n; i++) tmp.push_back(nums[index[i]]);
res.push_back(tmp);
return;
}
for(int i = 0; i < n; i++)
{
if(!flag[i])
{
flag[i] = 1;
index[step] = i;
dfs(step + 1, nums);
flag[i] = 0;
}
}
}
vector<vector<int>> permute(vector<int>& nums) {
n = nums.size(); // index 1 - n的全排列
dfs(0, nums);
return res;
}
};
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int N = 1010, M = 20010; // 因为是有向边！所以边都开2倍
int h[N], e[M], ne[M], idx = 0;
int d[N];
int s[N];
int dt[N];
int n, m;
void init()
{
memset(h, -1, sizeof h);
}
void add(int a, int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
bool topo()
{
for(int i = 1; i <= n; i++)
{
int t = s[i];
if(dt[t]) return false; // 入度不为0返回false
else
{
for(int k = h[t]; k != -1; k = ne[k])
{
int j = e[k];
dt[j]--;
}
}
}
return true;
}
int main()
{
init();
scanf("%d%d", &n, &m);
while(m --)
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
d[b]++; // 入度++
}
int q;
vector<int> res;
scanf("%d", &q);
for(int i = 0; i < q; i++)
{
for(int j = 1; j <= n; j++)
scanf("%d", &s[j]), dt[j] = d[j];
if(!topo()) res.push_back(i);
}
for(auto t : res)
{
printf("%d ", t);
}
return 0;
}
活动打卡代码
AcWing 873. 欧拉函数
[toc]
题目描述
给定 n 个正整数 ai，请你求出每个数的欧拉函数。
欧拉函数的定义
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个正整数 aiai。
输出格式
输出共 n 行，每行输出一个正整数 aiai 的欧拉函数。
数据范围
1≤n≤100,
1≤ai≤2×10^9输入样例：
3 3 6 8输出样例：
2 2 4
欧拉函数
分析
根据公式求每个数的质因子即可
代码
#include<iostream>
using namespace std;
int phi(int x)
{
int res = x;
for(int i = 2; i <= x/i; i++)
{
// 找到一个质因子
if(x % i == 0)
{
res = res / i * (i-1); // 即 res*(1 - 1/i);
while(x % i == 0) x /= i;
}
}
if(x > 1) res = res / x * (x - 1);
return res;
}
int main()
{
int n;
cin >> n;
while (n -- )
{
int x;
cin >> x;
cout << phi(x) << endl;
}
return 0;
}
时间复杂度
参考文章
活动打卡代码
AcWing 125. 耍杂技的牛
底下的牛的强壮程度S越大越好(越强壮的越放下面)
上面牛的重量和W越小越好(越重的放越下面)
=>
直觉是S[i]+W[i]越大的放越下面
#include<iostream>
#include<cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 50010;
struct Cow
{
LL w, s, ws;
}cows[N];
bool cmp(Cow a, Cow b)
{
return a.ws < b.ws; //按照w+s从小到大排序才是重点！！！
}
int n;
int main()
{
cin >> n;
for(int i = 0; i < n; i++)
{
int s, w;
cin >> s >> w;
cows[i] = {s, w, s+w};
}
sort(cows, cows + n, cmp);
int res = -0x3f3f3f3f;
LL tot = 0;
for(int i = 0; i < n; i++)
{
int t = tot - cows[i].s;
res = max(res, t);
tot += cows[i].w;
}
cout << res << endl;
return 0;
}
活动打卡代码
AcWing 104. 货仓选址
acwing 104. 货仓选址（排序不等式）
[toc]
题目描述
在一条数轴上有 N 家商店，它们的坐标分别为 A1∼AN。
现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。
为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。
输入格式
第一行输入整数 N。
第二行 N 个整数 A1∼AN。
输出格式
输出一个整数，表示距离之和的最小值。
数据范围
1≤N≤100000
0≤Ai≤40000输入样例：
4 6 2 9 1输出样例：
12
排序不等式
分析
假设选一个点$x$
现在有点$x_1, x_2, x_3, … , x_{n-1}, x_n$，首先将其排序
那么就是求$|x_1 - x| + |x_2 - x| + |x_3 - x| + … |x_{n-1} - x| + |x_n - x| $ 的最小值
我们将它分组：$(|x_1 - x| + |x_n - x|)+ (|x_2 - x|+ |x_{n-1} - x|) + … $
对于$|a-x| + |b-x| \ge b - a$ 易知，当x位于a,b之间的时候，该和最小，为|a - b|
所以对于上面的分组， $(|x_1 - x| + |x_n - x|)+ (|x_2 - x|+ |x_{n-1} - x|) + … \ge (x_n - x_1) + (x_{n-1} - x_2) + …$
只需要取x作为$x_1, x_2, x_3, … , x_{n-1}, x_n$的中位数， $x = x_{n/2}$
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 100010;
int a[N];
int n;
int main()
{
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i];
sort(a, a + n); // 从小到大排序
int x = a[n/2]; // 选取中位数
int res = 0;
for(int i = 0; i < n; i++) res += abs(a[i] - x);
cout << res ;
return 0;
}
