头像

adnil8130

SJTU




在线 


活动打卡代码 AcWing 621. 任务调度器

adnil8130
1小时前

贪心构造 $time O(n)$
使用出现次数最多的任务去构造循环节,可以证明总是可以在循环间隙节中将非最频繁任务插完并且不违反规则。

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

        vector<int> c2cnt(26);
        for (int task: tasks)
            ++c2cnt[task - 'A'];

        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);
    }
};



adnil8130
2小时前

哈希表 $time O(n)$
这道题的follow up答案是什么呢?!

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;
    }
};


活动打卡代码 LeetCode 617. 合并二叉树

adnil8130
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;
    }
};



adnil8130
4小时前

二分查找 $time O(n^2logn)$

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;
    }
};

双指针 $time O(n^2)$

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;
    }
};



adnil8130
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();
 */



adnil8130
5小时前

BFS $time O(n)$
跟层相关的一般用BFS层序遍历,当然DFS也是完全可以的。

/**
 * 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;
    }
};



adnil8130
5小时前

不动脑子版本 $time O(nlogn)$

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);
    }
};


活动打卡代码 AcWing 1352. 虫洞

adnil8130
19小时前

图论 + 遍历找环 $time O(11 * 9 * 7 * 5 * 3 * 1 * 12)$

#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;
}


活动打卡代码 AcWing 1354. 等差数列

adnil8130
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;
}


活动打卡代码 AcWing 1355. 母亲的牛奶

adnil8130
22小时前

搜索 $time O(n^3)$

#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;
}