SJTU

3.3万

1小时前

class Solution {
public:
int leastInterval(vector<char>& tasks, int n) {
int total = tasks.size();
if (n == 0)

vector<int> c2cnt(26);

sort(c2cnt.begin(), c2cnt.end());
int mxTimes = c2cnt.back(), i = 24, mxCnt = 1;

while (i >= 0 && c2cnt[i] == mxTimes)
--i, ++mxCnt;

return max(total, (mxTimes - 1) * (n + 1) + mxCnt);
}
};


2小时前

class Solution {
public:
vector<vector<string>> findDuplicate(vector<string>& paths) {
unordered_map<string, vector<string>> content2loc;
for (string &path: paths){
istringstream ssm(path);
string loc;
ssm >> loc;
string file;
while(ssm >> file){
int i = 0, len = file.size();
string name;
while (i < len && file[i] != '(')
name += file[i++];
++i;
string content;
while (i < len - 1)
content += file[i++];

content2loc[content].push_back(loc + '/' + name);
}
}

vector<vector<string>> res;
for (auto [content, loc]: content2loc)
if (loc.size() > 1)
res.push_back(loc);
return res;
}
};


3小时前

DFS 后序遍历 $time O(m + n)$

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
if (!t1 && !t2)
return nullptr;
if (!t1)
return t2;
if (!t2)
return t1;

TreeNode *left = mergeTrees(t1->left, t2->left);
TreeNode *right = mergeTrees(t1->right, t2->right);
TreeNode *root = new TreeNode(t1->val + t2->val);
root->left = left;
root->right = right;

return root;
}
};


4小时前

class Solution {
public:
int triangleNumber(vector<int>& nums) {
if (nums.size() < 3)
return 0;
int n = nums.size(), res = 0;
sort(nums.begin(), nums.end());

for (int i = 0 ; i < n - 2; ++i){
for (int j = i + 1; j < n - 1; ++j){
int a = nums[i], b = nums[j];
int lower = b - a, upper = a + b; // 只有小于upper,大于lower才能构成三角形
int start = upper_bound(nums.begin() + j + 1, nums.end(), lower) - nums.begin();
int end = upper_bound(nums.begin() + j + 1, nums.end(), upper - 1) - nums.begin();
// cout << start << " " << end << endl;
res += max(0, end - start);
}
}

return res;
}
};


class Solution {
public:
int triangleNumber(vector<int>& nums) {
if (nums.size() < 3)
return 0;
int n = nums.size(), res = 0;
sort(nums.begin(), nums.end());

for (int i = 0 ; i < n - 2; ++i){
for (int j = i + 1, k = j + 1; j < n - 1; ++j){
if (k == j)
k = j + 1;
while (k < n && nums[k] < nums[i] + nums[j])
++k;
res += k - j - 1;
}
}

return res;
}
};


5小时前

class MyCircularQueue {
private:
vector<int> MCQ;
int hh, tt;
int len;
public:
/** Initialize your data structure here. Set the size of the queue to be k. */
MyCircularQueue(int k) {
MCQ.resize(k);
hh = 0, tt = -1;
len = k;
}

/** Insert an element into the circular queue. Return true if the operation is successful. */
bool enQueue(int value) {
if (isFull())
return false;
++tt;
MCQ[tt % len] = value;
return true;
}

/** Delete an element from the circular queue. Return true if the operation is successful. */
bool deQueue() {
if (isEmpty())
return false;
++hh;
return true;
}

/** Get the front item from the queue. */
int Front() {
if (isEmpty())
return -1;
return MCQ[hh % len];
}

/** Get the last item from the queue. */
int Rear() {
if (isEmpty())
return -1;
return MCQ[tt % len];
}

/** Checks whether the circular queue is empty or not. */
bool isEmpty() {
return tt < hh;
}

/** Checks whether the circular queue is full or not. */
bool isFull() {
return tt - hh + 1 == len;
}
};

/**
* Your MyCircularQueue object will be instantiated and called as such:
* MyCircularQueue* obj = new MyCircularQueue(k);
* bool param_1 = obj->enQueue(value);
* bool param_2 = obj->deQueue();
* int param_3 = obj->Front();
* int param_4 = obj->Rear();
* bool param_5 = obj->isEmpty();
* bool param_6 = obj->isFull();
*/


5小时前

BFS $time O(n)$

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* addOneRow(TreeNode* root, int v, int d) {
if (!root)
return root;

TreeNode *dummy = new TreeNode(-1);
dummy->left = root;

queue<TreeNode *> Q; Q.push(dummy);
int lvl = 1;
while (Q.size()){
if (lvl == d)
break;
int size = Q.size();
for (int i = 0; i < size; ++i){
TreeNode *cur = Q.front(); Q.pop();
if (cur->left)
Q.push(cur->left);
if (cur->right)
Q.push(cur->right);
}
++lvl;
}

while (Q.size()){
TreeNode *node = Q.front(); Q.pop();
TreeNode *n_node_l = new TreeNode(v);
n_node_l->left = node->left;
TreeNode *n_node_r = new TreeNode(v);
n_node_r->right = node->right;

node->left = n_node_l;
node->right = n_node_r;
}

root = dummy->left;
delete dummy; dummy = nullptr;
return root;
}
};


5小时前

class Solution {
public:
int maximumProduct(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
int neg = 0, pos = 0, zero = 0;
for (int num: nums){
if (num > 0) ++pos;
else if (num < 0) ++neg;
else ++zero;
}

int res = INT_MIN;
if (neg >= 2)
res = max(res, nums[0] * nums[1] * nums[n - 1]);

for (int i = 0; i + 2 < n; ++i)
res = max(res, nums[i] * nums[i + 1] * nums[i + 2]);

return res;
}
};


class Solution {
public:
int maximumProduct(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());

int res = INT_MIN;
res = max(res, nums[0] * nums[1] * nums[n - 1]);
res = max(res, nums[n - 1] * nums[n - 2] * nums[n - 3]);

return res;
}
};


class Solution {
public:
int maximumProduct(vector<int>& nums) {
int n = nums.size();
int max1 = INT_MIN, max2 = INT_MIN, max3 = INT_MIN, min1 = INT_MAX, min2 = INT_MAX;

for (int num: nums){
if (num >= max1){
max3 = max2;
max2 = max1;
max1 = num;
} else if (num >= max2){
max3 = max2;
max2 = num;
} else if (num > max3){
max3 = num;
}

if (num <= min1){
min2 = min1;
min1 = num;
} else if (num <= min2){
min2 = num;
}
}

return max(max1 * max2 * max3, min1 * min2 * max1);
}
};


19小时前

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 14;
int res, n;
int to_right[N], to_wormhole[N], visited[N][2];
bool st[N];

struct Coord{
int x, y;
bool operator < (Coord &c){
if (y != c.y)
return y < c.y;
return x < c.x;
}
} coords[N];

bool cyclic(int x, int y){
// cout << x << " " << y << endl;
if (visited[x][y] == -1)
return true;
if (visited[x][y] == 1)
return false;

visited[x][y] = -1;
if (y == 0){
if (cyclic(to_wormhole[x], 1))
return true;
} else {
if (to_right[x] != -1){
if (cyclic(to_right[x], 0))
return true;
}
}

visited[x][y] = 1;
return false;
}

// 检查图是否有环
bool check(){
memset(visited, 0, sizeof visited);
for (int i = 0; i < n; ++i){
for (int j = 0; j < 2; ++j){
if (cyclic(i, j))
return true;
}
}

return false;
}

// 枚举配对
void dfs(int cur){
if (cur == n / 2){

if (check())
++res;
return;
}

for (int i = 0; i < n; ++i){
if (!st[i]){
for (int j = i + 1; j < n; ++j){
if (!st[j]){
to_wormhole[i] = j, to_wormhole[j] = i;
st[i] = st[j] = true;
dfs(cur + 1);
st[i] = st[j] = false;
to_wormhole[i] = -1, to_wormhole[j] = -1;
}
}
break;
}
}
}

int main(){
// 读取数据
scanf("%d\n", &n);
for (int i = 0; i < n; ++i)
scanf("%d %d\n", &coords[i].x, &coords[i].y);

sort(coords, coords + n);
// 建图
memset(to_right, -1, sizeof to_right);
memset(to_wormhole, -1, sizeof to_wormhole);
for (int i = 1; i < n; ++i){
if (coords[i].y == coords[i - 1].y)
to_right[i - 1] = i;
}

// 枚举遍历所有配对情况
dfs(0);

printf("%d\n", res);
return 0;
}


21小时前

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
int n, m;
const int N = 3125010;

bool st[125010];
struct Seq{
int f, d;
bool operator < (Seq &s){
if (d != s.d)
return d < s.d;
return f < s.f;
}
} res[N];
int cnt;

int main(){
scanf("%d %d\n", &n, &m);
for (int i = 0; i <= m; ++i){
for (int j = i; j <= m; ++j){
st[i * i + j * j] = true;
}
}

for (int i = 0; i <= m * m * 2; ++i){
if (st[i]){
for (int j = i + 1; j <= m * m * 2; ++j){
int first = i, d = j - i;
if (first + d * (n - 1) > m * m * 2)
break;
bool flag = true;
for (int k = 0; k < n; ++k){
if (!st[i + k * d]){
flag = false;
break;
}
}

if (flag)
res[cnt++] = {first, d};
}
}
}

sort(res, res + cnt);

if (cnt == 0)
puts("NONE");
else{
for (int i = 0; i < cnt; ++i)
printf("%d %d\n", res[i].f, res[i].d);
}

return 0;
}


22小时前

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <set>

using namespace std;
const int N = 22;
bool visited[N][N][N];
int A, B, C;
set<int> res;

struct State{
int a, b, c;
bool operator < (State &s){
if (a != s.a)
return a < s.a;
if (b != s.b)
return b < s.b;
return c < s.c;
}
};

void add(queue<State> &Q, int can_a, int can_b, int can_c){
if (visited[can_a][can_b][can_c])
return;
visited[can_a][can_b][can_c] = true;
if (can_a == 0)
res.insert(can_c);
Q.push({can_a, can_b, can_c});

}

int main(){
scanf("%d %d %d\n", &A, &B, &C);
State initial_state = {0, 0, C};
queue<State> Q; Q.push(initial_state);
visited[0][0][C] = true;
res.insert(C);

while (Q.size()){
State cur_state = Q.front(); Q.pop();
int cur_a = cur_state.a, cur_b = cur_state.b, cur_c = cur_state.c;
add(Q, cur_a - min(cur_a, B - cur_b), cur_b + min(cur_a, B - cur_b), cur_c); // A->B
add(Q, cur_a - min(cur_a, C - cur_c), cur_b, cur_c + min(cur_a, C - cur_c)); // A->C
add(Q, cur_a + min(cur_b, A - cur_a), cur_b - min(cur_b, A - cur_a), cur_c); // B->A
add(Q, cur_a, cur_b - min(cur_b, C - cur_c), cur_c + min(cur_b, C - cur_c)); // B->C
add(Q, cur_a + min(cur_c, A - cur_a), cur_b, cur_c - min(cur_c, A - cur_a)); // C->A
add(Q, cur_a, cur_b + min(cur_c, B - cur_b), cur_c - min(cur_c, B - cur_b)); // C->B
}

for (int h: res)
printf("%d ", h);

return 0;
}