140

heydayue

22小时前
class Solution {
public:
int maxEqualFreq(vector<int>& nums) {
//count统计每个数字出现的次数(频率),freq统计次数相同的个数(有多少个频率相同的个数)
unordered_map<int, int> count, freq;

int maxFreq = 0, res = 0;

for(int i = 0; i < nums.size(); i ++ ){
//统计次数曾经出现过,说明是旧数,频率即将+1,所以要更新freq
if(count[nums[i]] > 0){
freq[count[nums[i]]] --;
}
//频率+1
count[nums[i]] ++;
//更新最大频率
maxFreq = max(maxFreq, count[nums[i]]);
//频率的个数+1
freq[count[nums[i]]] ++;
//判断是否符合结果
bool ok = maxFreq == 1 || freq[maxFreq] * maxFreq + freq[maxFreq - 1] * (maxFreq - 1) == i + 1 && freq[maxFreq] == 1 || freq[maxFreq] * maxFreq + 1 == i + 1 && freq[1] == 1;
if(ok) {
res = max(res, i + 1);
}
}
return res;
}
};


1天前
/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
private:
int maxL = -1, sum = 0;
public:
int deepestLeavesSum(TreeNode* root) {
dfs(root, 0);
return sum;
}

void dfs(TreeNode* node, int level){
if(node == nullptr) return ;

if(level > maxL){
maxL = level;
sum = node -> val;
}
else if(level == maxL) sum += node -> val;

dfs(node -> left, level + 1);
dfs(node -> right, level + 1);
}
};


2天前
class OrderedStream {
private:
vector<string> os;
int ptr;
public:
OrderedStream(int n) {
os = vector<string> (n + 1);
ptr = 1;
}

vector<string> insert(int idKey, string value) {
os[idKey] = value;
vector<string> res;
while(ptr < os.size() && ! os[ptr].empty()){
res.push_back(os[ptr]);
ptr ++;
}
return res;
}
};

/**
* Your OrderedStream object will be instantiated and called as such:
* OrderedStream* obj = new OrderedStream(n);
* vector<string> param_1 = obj->insert(idKey,value);
*/


3天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010;
int h[N], e[N], ne[N], idx;
int q[N], d[N];
int n, m;

void add(int a, int b){
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

bool topsort(){
int hh = 0, tt = -1;

//所有入度为0的点入队
for(int i = 1; i <= n; i ++ ){
if(! d[i]){
q[++ tt] = i;
}
}

while(hh <= tt){
int t = q[hh ++];

for(int i = h[t]; i != -1; i = ne[i]){
int j = e[i];
d[j] --;
if(! d[j]) q[++ tt ] = j;
}
}
//队列长度为n(等于所有点的个数),则说明存在拓扑序列
return tt == n - 1;
}

int main(){
cin >> n >> m;

memset(h, -1, sizeof h);
for(int i = 0; i < m; i ++ ){
int a, b;
cin >> a >> b;
d[b] ++;
}

if(topsort()){
for(int i = 0; i < n; i ++ ) cout << q[i] << " ";
puts("");
}
else
cout << -1 << endl;

return 0;
}


3天前
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;
const int N = 100010;
int h[N], e[N], ne[N], d[N], idx;
int n, m;

//h[a]表示a指向的第一条邻边的地址
void insert(int a, int b){
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int bfs(){
queue<int> q;
q.push(1);
memset(d, -1, sizeof d);
d[1] = 0;

while(! q.empty()){
int t = q.front();
q.pop();

//遍历t的所有邻边
for(int i = h[t]; i != -1; i = ne[i]){
int j = e[i];
//如果j没有被遍历过
if(d[j] == -1){
d[j] = d[t] + 1;
q.push(j);
}
}
}
return d[n];
}

int main(){
cin >> n >> m;

memset(h, - 1, sizeof h);

//记录邻接表
for(int i = 0; i < m; i ++ ){
int a, b;
cin >> a >> b;
insert(a, b);
}

cout << bfs() << endl;

return 0;
}


3天前
class MyCircularDeque {
public:
vector<int> q;
int front, rear;
int capacity;
public:
MyCircularDeque(int k) {
q = vector<int> (k + 1);
front = 0;
rear = 0;
capacity = k + 1;
}

bool insertFront(int value) {
if(isFull()) return false;
front = (front - 1 + capacity) % capacity;
q[front] = value;
return true;
}

bool insertLast(int value) {
if(isFull()) return false;
q[rear] = value;
rear = (rear + 1) % capacity;
return true;
}

bool deleteFront() {
if(isEmpty()) return false;
front = (front + 1) % capacity;
return true;
}

bool deleteLast() {
if(isEmpty()) return false;
rear = (rear - 1 + capacity) % capacity;
return true;
}

int getFront() {
if(isEmpty()) return -1;
return q[front];
}

int getRear() {
if(isEmpty()) return -1;
return q[(rear - 1 + capacity) % capacity];
}

bool isEmpty() {
return (rear - front + capacity) % capacity == 0;
}

bool isFull() {
return (rear + 1) % capacity == front;
}
};

/**
* Your MyCircularDeque object will be instantiated and called as such:
* MyCircularDeque* obj = new MyCircularDeque(k);
* bool param_1 = obj->insertFront(value);
* bool param_2 = obj->insertLast(value);
* bool param_3 = obj->deleteFront();
* bool param_4 = obj->deleteLast();
* int param_5 = obj->getFront();
* int param_6 = obj->getRear();
* bool param_7 = obj->isEmpty();
* bool param_8 = obj->isFull();
*/


4天前
#include <iostream>
#include <cstring>
#include <vector>
#include <unordered_map>

using namespace std;

//最大单词个数
const int N = 310;
//存储所有单词
string a[N];
//记录字母到字母图形的映射
unordered_map<char, vector<string>> mp;
//字母图形的每一行
string s;

int main(){
//用于得到每个单词字符串
string x = "";
int res = 0;

//读入字母图形
for(int i = 0; i < 26; i ++ ){
char c = char('A' + i);
for(int j = 0; j < 7; j ++ ){
cin >> s;
mp[c].push_back(s);
}
}

//吞掉空格
getchar();
getline(cin, s);

//划分所有单词
for(int i = 0; i < s.size(); i ++ ){
if(s[i] >= 'A' && s[i] <= 'Z') x += string(1, s[i]);
else{
if(x != "") a[res ++ ] = x;
x = "";
}
}

if(x != "") a[res ++] = x;

//遍历每个单词
for(int i = 0; i < res; i ++ ){
//得到每个单词的长度
int len = a[i].size();
//按行输入单词中每个字母的第j行
for(int j = 0; j < 7; j ++ ){
//遍历每个字母
for(int k = 0; k < len; k ++ ){
cout << mp[a[i][k]][j];
if(k != len - 1) cout << " ";
}
if(j != 6) cout << endl;
}
if(i != res - 1) cout << endl << endl;
}
return 0;
}


5天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
//N代表点数,M代表边数
const int N = 100020, M = 2 * N;
//h存储以u为根结点的第一条邻边的地址
int h[N], e[M], ne[M], idx;
//状态数组,点是否被遍历过
int st[N];
int n;
int ans = N;

void add(int a, int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}

//返回以u为根结点的子树大小
int dfs(int u){
//记录u已经被遍历过
st[u] = true;

//sum初始表示自己本身就算一个点 res记录当前最大连通块个数
int sum = 1, res = 0;
//遍历u的邻边,并不断深搜dfs
for(int i = h[u]; i != -1; i = ne[i]){
int j = e[i];
if(! st[j]){
//返回子树大小
int t = dfs(j);
res = max(res, t);
sum += t;
}
}
res = max(res, n - sum);
ans = min(ans, res);

return sum;
}

int main(){
scanf("%d", &n);

memset(h, -1, sizeof h);

for(int i = 0; i < n - 1; i ++ ){
int a, b;
scanf("%d%d", &a, &b);
}

//1最保险
dfs(1);

printf("%d\n", ans);

return 0;
}


5天前
//4507.子数组异或和 运用前缀和

#include <iostream>
#include <algorithm>

using namespace std;
typedef long long ll;

const int N = 300010;
int a, s[N], odd[N], even[N], oddcnt, evencnt;
int n;
ll res;

int main(){
scanf("%d", &n);

//处理前缀和
for(int i = 1; i <= n; i ++ ){
scanf("%d", &a);
s[i] = s[i - 1] ^ a;
}

// !!! i从0开始,表示可以有从开头开始的数组符合条件
for(int i = 0; i <= n; i ++ ){
if(i & 1) odd[oddcnt ++ ] = s[i];
else even[evencnt ++ ] = s[i];
}

//排序方便处理
sort(odd, odd + oddcnt);
sort(even, even + evencnt);

// !!! 防止快指针j跑到odd[oddcnt] 使得odd[j]=odd[i]
for(ll i = 0, j = 0; i < oddcnt; i = j){
while(odd[i] == odd[j]) j ++;
res += (j - i ) * (j - i - 1ll) >> 1;
}

for(ll i = 0, j = 0; i < evencnt; i = j){
while(even[i] == even[j]) j ++;
res += (j - i) * (j - 1ll - i) >> 1;
}

printf("%lld\n", res);

return 0;
}



5天前
class Solution {
public:
int maxChunksToSorted(vector<int>& arr) {
int len = arr.size();
long long s1[len + 1], s2[len + 1];
s1[0] = arr[0];
for(int i = 1; i < len; i ++) s1[i] = s1[i - 1] + arr[i];
sort(arr.begin(), arr.end());
s2[0] = arr[0];
for(int i = 1; i < len; i ++ ) s2[i] = s2[i - 1] + arr[i];

int res = 0;
for(int i = 0; i < len; i ++ ){
if(s1[i] == s2[i]) res++;
}
return res;
}
};