头像

我要出去乱说

凯里学院 => 贵州大学




离线:1小时前


最近来访(137)
用户头像
诺亚方舟.
用户头像
初静
用户头像
acwing_陌路
用户头像
不会刷算法
用户头像
有何不可
用户头像
Misaka_9982
用户头像
米兰
用户头像
饮者
用户头像
TStark
用户头像
微笑意面
用户头像
Limited
用户头像
Minuet
用户头像
dys
用户头像
eyes_4
用户头像
Noyce765103
用户头像
神秘人3hd
用户头像
thezhu
用户头像
llsong98
用户头像
杨杰_1
用户头像
LH


用两次二分,第一次找目标元素的第一个位置,第二次找最后一个位置,反过来也行。时间复杂度为$O(logN)$。

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.empty()) return {-1, -1};

        int l = 0, r = nums.size() - 1, res_l;
        while (l < r)
        {
            int mid = (l + r) >> 1;             //当序列为奇数个时取不到最右边的元素
            if (nums[mid] >= target) r = mid;   //故先让右边界往左移动
            else l = mid + 1;
        }

        if (nums[l] != target) return {-1, -1};

        res_l = l;                              //记录第一个位置的坐标
        l = 0, r = nums.size() - 1;             //重置边界,开始第二次二分
        while (l < r)
        {
            int mid = (l + r + 1) >> 1;         //当序列为奇数个时取不到最左边的元素
            if (nums[mid] <= target) l = mid;   //故先让左边界往右移动
            else r = mid - 1;
        }

        return {res_l, r};
    }
};



class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.empty()) return {-1, -1};

        int l = 0, r = nums.size() - 1, res_l;
        while (l < r)
        {
            int mid = (l + r) >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }

        if (nums[l] != target) return {-1, -1};

        res_l = l, l = 0, r = nums.size() - 1;
        while (l < r)
        {
            int mid = (l + r + 1) >> 1;
            if (nums[mid] <= target) l = mid;
            else r = mid - 1;
        }

        return {res_l, r};
    }
};



class LRUCache {
public:
    struct Node     //定义双链表结构体
    {
        int key, val;
        Node *left, *right;
        Node(int _key, int _val):key(_key), val(_val), left(nullptr), right(nullptr){}
    }*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->right->left = p->left;   //当前节点右侧的左指针指向该节点的左侧
        p->left->right = p->right;  //节点左侧的右指针指向该节点的右侧
    }

    void insert(Node* p)            //将一个新节点插入到L节点和第一个节点之间
    {
        p->right = L->right;
        p->left = L;
        L->right->left = p;
        L->right = p;
    }

    int get(int key) {
        if (hash.find(key) == hash.end()) return -1;    //所查节点不存在的情况
        auto p = hash[key];                             //若存在,取出该节点并添加到链表首部
        remove(p);
        insert(p);
        return p->val;
    }

    void put(int key, int value) {
        if (hash.find(key) != hash.end())   //如果插入的值已经存在,则更新
        {
            auto p = hash[key];
            p->val = value;
            remove(p);
            insert(p);
        }
        else                            //爆容量只会发生在插入时
        {
            if (hash.size() == n)
            {
                auto p = R->left;       //要删除的节点位于R节点的左侧
                remove(p);              //从链表中删除节点
                hash.erase(p->key);     //从哈希表中删除节点
                delete p;               //从内存中删除节点
            }
            auto p = new Node(key, value);
            hash[key] = p;
            insert(p);
        }
    }
};


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

哈希表+双链表实现。

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->right->left = p->left;   //当前节点右侧的左指针指向该节点的左侧
        p->left->right = p->right;  //节点左侧的右指针指向该节点的右侧
    }

    void insert(Node* p)            //将一个新节点插入到L节点和第一个节点之间
    {
        p->right = L->right;
        p->left = L;
        L->right->left = p;
        L->right = p;
    }

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

    void put(int key, int value) {
        if (hash.find(key) != hash.end())   //如果插入的值已经存在,则更新
        {
            auto p = hash[key];
            p->val = value;
            remove(p);
            insert(p);
        }
        else        //爆容量只会发生在插入时
        {
            if (hash.size() == n)
            {
                auto p = R->left;       //要删除的节点位于R节点的左侧
                remove(p);              //从链表中删除节点
                hash.erase(p->key);     //从哈希表中删除节点
                delete p;               //从内存中删除节点
            }
            auto p = new Node(key, value);
            hash[key] = p;
            insert(p);
        }
    }
};


新鲜事 原文

来北京两个月了,从上一个单位离职,告别了曾一起实习一起奋斗的同事,独自搬到西二旗附近,马上要去新公司实习了。3000一月的房租,小小的一个单间,刚好能住下我。下午点了份黄焖鸡外卖,一个人一边吃一边看电影,突然觉得非常难过,又哭不出来。下楼把垃圾扔了,顺便去附近超市买了一些日用品,晚上坐在电脑前听着歌,不知道要做什么。初来北京时的满心壮志,到现在只剩空虚孤独, 但又能怎么样呢,只能继续朝这条路走下去。希望明天会更好吧



时间复杂度为$O(log(N+M))$。

class Solution {
public:
    //k表示要找第k个数
    int find(vector<int>& nums1, int i, vector<int>& nums2, int j, int k)
    {
        //保持第一个数组为较小的那个数组
        if (nums1.size() - i > nums2.size() - j) return find(nums2, j, nums1, i, k);
        if (k == 1)
        {
            if (nums1.size() == i) return nums2[j]; //第一个数组为空就返回第二个数组的第一个元素
            else return min(nums1[i], nums2[j]);
        }

        //若第一个数组已经为空,则直接返回第二个数组的中位数
        if (nums1.size() == i) return nums2[j + k - 1];
        int si = min((int)nums1.size(), i + k / 2), sj = j + k - k / 2;
        if (nums1[si - 1] > nums2[sj - 1])
            return find(nums1, i, nums2, sj, k - (sj - j));
        else   
            return find(nums1, si, nums2, j, k - (si - i));
    }

    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int total = nums1.size() + nums2.size();
        if (total % 2 == 0)     //中位数有两个的情况
        {
            int left = find(nums1, 0, nums2, 0, total / 2);
            int right = find(nums1, 0, nums2, 0, total / 2 + 1);
            return (left + right) / 2.0;
        }
        else 
            return find(nums1, 0, nums2, 0, total / 2 + 1);
    }
};


活动打卡代码 LeetCode 54. 螺旋矩阵

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> res;
        if (matrix.empty()) return res;

        int left = 0, right = matrix[0].size() - 1, top = 0, down = matrix.size() - 1;
        while (true)
        {
            for (int i = left; i <= right; ++ i) res.push_back(matrix[top][i]);
            if ( ++ top > down) break;
            for (int i = top; i <= down; ++ i) res.push_back(matrix[i][right]);
            if ( -- right < left) break;
            for (int i = right; i >= left; -- i) res.push_back(matrix[down][i]);
            if ( -- down < top) break;
            for (int i = down; i >= top; -- i) res.push_back(matrix[i][left]);
            if ( ++ left > right) break;
        }

        return res;
    }
};



class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int p = n + m - 1;
        int p1 = m - 1, p2 = n - 1;

        while (~p1 && ~p2)
        {
            if (nums1[p1] > nums2[p2])
                nums1[p -- ] = nums1[p1 -- ];
            else
                nums1[p -- ] = nums2[p2 -- ];
        }

        while (~p1) nums1[p -- ] = nums1[p1 -- ];
        while (~p2) nums1[p -- ] = nums2[p2 -- ];
    }
};


活动打卡代码 AcWing 171. Excel表列序号

class Solution {
public:
    int titleToNumber(string columnTitle) {
        if (columnTitle.empty()) return 0;

        int res = 0;
        for (int i = 0; i < columnTitle.size(); ++ i)
        {
            int num = columnTitle[i] - 'A' + 1;     //没有写一起是为了防止爆int
            res = res * 26 + num;
        }

        return res;
    }
};



class Solution {
public:
    string addStrings(string num1, string num2) {
        int i = num1.size() - 1, j = num2.size() - 1;   //从后往前开始累加
        int t = 0;
        string res = "";

        while (~i || ~j || t != 0)              //i或j大于零,或t不为0
        {
            if (i >= 0) t += num1[i -- ] - '0';
            if (j >= 0) t += num2[j -- ] - '0';

            res.push_back(t % 10 + '0');
            t /= 10;
        }                                       //不需要额外判断进位,因为循环中已经做了

        reverse(res.begin(), res.end());        //res需要一次反转
        return res;
    }
};