头像

NFYD




离线:13小时前


最近来访(333)
用户头像
Hxxj
用户头像
辣鸡号航母
用户头像
只会一点点
用户头像
cuola
用户头像
我要出去乱说
用户头像
ctOS
用户头像
psychopath_6
用户头像
LittleLily
用户头像
Present.
用户头像
昕丶羽
用户头像
Wiselnn
用户头像
伊蕾娜我的伊蕾娜
用户头像
aa123
用户头像
无名小子
用户头像
月亮供电不足
用户头像
呓念
用户头像
ZXG_DXX
用户头像
笙笙笙笙
用户头像
novice_7
用户头像
一朵奔涌的浪花


NFYD
13小时前

快速选择排序

class Solution {
public:
    int quick_sort(vector<int>& q, int l, int r, int k)
    {
        if(l == r) return q[k];
        int i = l - 1, j = r + 1, x = q[l + r >> 1];
        while(i < j)
        {
            while(q[++ i] > x); //求第k大元素,这里要写大于号,与快排相反
            while(q[-- j] < x); //写小于号,与快排相反
            if(i < j) swap(q[i], q[j]);
        }
        if(k <= j) return quick_sort(q, l, j, k);
        return quick_sort(q, j + 1, r, k);
    }
    int findKthLargest(vector<int>& nums, int k) {
        return quick_sort(nums, 0, nums.size() - 1, k - 1);
    }
};


活动打卡代码 LeetCode 200. 岛屿数量

NFYD
18小时前

BFS写法

typedef pair<int, int> PII;
class Solution {
public:
    vector<vector<char>> g;
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; 

    void bfs(int x, int y)
    {
        g[x][y] = '0';
        queue<PII> q;
        q.push({x, y});

        while(q.size())
        {
            PII t = q.front();
            q.pop();

            for(int i = 0; i < 4; i ++ )
            {
                int a = t.first + dx[i], b = t.second + dy[i];
                if(a >= 0 && a < g.size() && b >= 0 && b < g[a].size() && g[a][b] == '1')
                {
                    q.push({a, b});
                    g[a][b] = '0';
                }
            }
        }
    }

    int numIslands(vector<vector<char>>& grid) {
        g = grid;
        int res = 0;
        for(int i = 0; i < g.size(); i ++ )
            for(int j = 0; j < g[0].size(); j ++ )
                if(g[i][j] == '1')
                {
                    bfs(i, j);
                    res ++ ;
                }
        return res;
    }
};

DFS写法

class Solution {
public:
    vector<vector<char>> g;
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; 

    void dfs(int x, int y)
    {
        g[x][y] = '0';
        for(int i = 0; i < 4; i ++ )
        {
            int a = x + dx[i], b = y + dy[i];
            if(a >= 0 && a < g.size() && b >= 0 && b < g[a].size() && g[a][b] == '1')
                dfs(a, b);
        }
    }

    int numIslands(vector<vector<char>>& grid) {
        g = grid;
        int res = 0;
        for(int i = 0; i < g.size(); i ++ )
            for(int j = 0; j < g[0].size(); j ++ )
                if(g[i][j] == '1')
                {
                    dfs(i, j);
                    res ++ ;
                }
        return res;
    }
};


活动打卡代码 LeetCode 198. 打家劫舍

NFYD
21小时前

Snipaste_2022-08-15_14-15-39.png

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n + 1), g(n + 1);
        for(int i = 1; i <= n; i ++ )
        {
            f[i] = g[i - 1] + nums[i - 1];
            g[i] = max(f[i - 1], g[i - 1]);
        }
        return max(f[n], g[n]);
    }
};


活动打卡代码 LeetCode 160. 相交链表

NFYD
22小时前
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        auto p = headA, q = headB;
        while(p != q)
        {
            p = p ? p->next : headB;
            q = q ? q->next : headA;
        }
        return p;
    }
};



NFYD
2天前

DP

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int res = nums[0];
        int f = nums[0], g = nums[0];
        for (int i = 1; i < nums.size(); i ++ ) 
        {
            int a = nums[i], fa = f * a, ga = g * a;
            f = max(a, max(fa, ga));
            g = min(a, min(fa, ga));
            res = max(res, f);
        }
        return res;
    }
};


活动打卡代码 LeetCode 155. 最小栈

NFYD
3天前
class MinStack {
public:
    stack<int> stk;
    stack<int> stk_min;
    MinStack() {

    }

    void push(int val) {
        stk.push(val);
        if (stk_min.size()) {
            int x = stk_min.top();
            stk_min.push(min(x, val));
        } else {
            stk_min.push(val);
        }
    }

    void pop() {
        stk.pop();
        stk_min.pop();
    }

    int top() {
        return stk.top();
    }

    int getMin() {
        return stk_min.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */


活动打卡代码 LeetCode 146. LRU缓存机制

NFYD
5天前

双链表 + 哈希表

class LRUCache {
public:
    struct Node
    {
        int key, val;
        Node *left, *right;
        Node(int _key, int _val): key(_key), val(_val), left(NULL), right(NULL) {}
    }*L, *R;
    unordered_map<int, Node*> hash;
    int n;

    LRUCache(int capacity) {
        n = capacity;
        L = new Node(-1, -1), R = new Node(-1, -1);
        L->right = R;
        R->left = L;
    }

    void remove(Node* p)
    {
        p->left->right = p->right;
        p->right->left = p->left;
    }

    void insert(Node* p) 
    {
        p->right = L->right;
        p->left = L;
        L->right->left = p;
        L->right = p;
    }

    int get(int key) {
        if(hash.count(key) == 0) return -1;
        auto p = hash[key];
        remove(p);
        insert(p);
        return p->val;
    }

    void put(int key, int value) {
        if(hash.count(key))
        {
            auto p = hash[key];
            p->val = value;
            remove(p);
            insert(p);
        }
        else
        {
            if(hash.size() == n)
            {
                auto p = R->left;
                remove(p);
                hash.erase(p->key);
                delete p;
            }
            auto p = new Node(key, value);
            hash[key] = p;
            insert(p);
        }
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */


活动打卡代码 LeetCode 169. 多数元素

NFYD
5天前

摩尔投票法

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int val, cnt = 0;
        for(auto c : nums)
        {
            if(cnt == 0) val = c, cnt ++ ;
            else if(c == val) cnt ++ ;
            else cnt -- ;
        }
        return val;
    }
};


活动打卡代码 LeetCode 647. 回文子串

NFYD
5天前
class Solution {
public:
    int countSubstrings(string s) {
        int res = 0;
        for(int i = 0; i < s.size(); i ++ )
        {
            //枚举回文串长度为奇数的情况
            for(int j = i, k = i; j >= 0 && k < s.size(); j --, k ++ )
            {
                if(s[j] != s[k]) break;
                res ++ ;
            }

            //枚举回文串长度为偶数的情况
            for(int j = i, k = i + 1; j >= 0 && k < s.size(); j --, k ++ )
            {
                if(s[j] != s[k]) break;
                res ++ ;
            }
        }
        return res;
    }
};



NFYD
6天前
class Solution {
public:
    stack<int> num;
    void eval(string c)
    {
        auto b = num.top(); num.pop();
        auto a = num.top(); num.pop();
        int x;
        if(c == "+") x = a + b;
        else if(c == "-") x = a - b;
        else if(c == "*") x = a * b;
        else if(c == "/") x = a / b;
        num.push(x);
    }
    int evalRPN(vector<string>& tokens) {
        unordered_set<string> S{"+", "-", "*", "/"};
        for(auto& c: tokens)
        {
            if(S.count(c)) eval(c);
            else num.push(stoi(c));
        }
        return num.top();
    }
};