leetcode刷题记录——2023年10月-能不能吃完饭再说

2、两数相加

注意的点：

同位相加大于10的情况注意进位
可能是极大的数字，转成整数直接相加不可行

class Solution
{
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
    {
        ListNode *ret = new ListNode();
        ListNode *head = ret;
        int jinwei = 0;
        ret->val = l1->val + l2->val;
        // 第一位如果有进位需要单独处理
        if (ret->val >= 10)
        {
            jinwei = ret->val / 10;
            ret->val = ret->val % 10;
        }
        // 遍历链表，还原整数
        while (l1->next != nullptr || l2->next != nullptr)
        {
            ListNode *tmp = new ListNode();
            if (l1->next != nullptr && l2->next != nullptr)
            {
                tmp->val = l1->next->val + l2->next->val;
                // 处理进位
                if (jinwei > 0)
                {
                    tmp->val += jinwei;
                    jinwei = 0;
                }
                if (tmp->val >= 10)
                {
                    jinwei = tmp->val / 10;
                    tmp->val = tmp->val % 10;
                }
                l1 = l1->next;
                l2 = l2->next;
            }
            else if (l1->next != nullptr)
            {
                tmp->val = l1->next->val;
                // 处理进位
                if (jinwei > 0)
                {
                    tmp->val += jinwei;
                    jinwei = 0;
                }
                if (tmp->val >= 10)
                {
                    jinwei = tmp->val / 10;
                    tmp->val = tmp->val % 10;
                }
                l1 = l1->next;
            }
            else
            {
                tmp->val = l2->next->val;
                // 处理进位
                if (jinwei > 0)
                {
                    tmp->val += jinwei;
                    jinwei = 0;
                }
                if (tmp->val >= 10)
                {
                    jinwei = tmp->val / 10;
                    tmp->val = tmp->val % 10;
                }
                l2 = l2->next;
            }
            ret->next = tmp;
            ret = ret->next;
        }
        // 最后一位如果有进位需要单独处理
        if (jinwei > 0)
        {
            ListNode *tmp = new ListNode();
            tmp->val += jinwei;
            jinwei = 0;
            ret->next = tmp;
        }

        return head;
    }
};

优化

首先创建一个新的链表节点cur，并将其赋值给head，head用于记录结果链表的头部。
初始化进位变量carry为0。
使用循环遍历两个输入链表l1和l2，直到两个链表都遍历完。
在每一次循环中，创建一个新的链表节点cur->next，用于存储当前位的和，并将cur指向cur->next。
如果l1和l2都不为空，将当前位的值设为(l1->val + l2->val + carry) % 10，并更新进位为(l1->val + l2->val + carry) / 10。
如果只有l1不为空，将当前位的值设为(l1->val + carry) % 10，并更新进位为(l1->val + carry) / 10。
如果只有l2不为空，将当前位的值设为(l2->val + carry) % 10，并更新进位为(l2->val + carry) / 10。
更新l1和l2为它们的下一个节点。
重复步骤4-8直到两个链表都遍历完。
如果最后的进位carry不为0，创建一个新的链表节点存储进位的值，并将其连接到cur的后面。

class Solution
{
public:
    ListNode *addTwoNumbers(ListNode *l1,
                            ListNode *l2)
    {
        ListNode *cur = new ListNode();
        ListNode *head = cur;
        int carry = 0;
        while (l1 || l2)
        {
            cur->next = new ListNode();
            if (l1 && l2)
            {
                cur->next->val = (l1->val + l2->val + carry) % 10;
                carry = (l1->val + l2->val + carry) / 10;
                l1 = l1->next;
                l2 = l2->next;
            }
            else if (l1)
            {
                cur->next->val = (l1->val + carry) % 10;
                carry = (l1->val + carry) / 10;
                l1 = l1->next;
            }
            else
            {
                cur->next->val = (l2->val + carry) % 10;
                carry = (l2->val + carry) / 10;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        if (carry)
        {
            cur->next = new ListNode(carry);
            cur->next->next = nullptr;
        }
        return head->next;
    }
};

1、两数之和

暴力枚举

该方法简单但是时间复杂度为O(n^2)。空间复杂度为O(1)。运行速度慢且内存空间消耗大。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ret;
        vector<int>::iterator it1;
        vector<int>::iterator it2;
        int num1, num2;
        for(it1 = nums.begin();it1!=nums.end();it1++){
            num1 = *it1;
            for(it2 = it1+1;it2!=nums.end();it2++){
                num2 = *it2;
                if((num1+num2) == target){
                    ptrdiff_t index1 = distance(nums.begin(), it1);
                    ptrdiff_t index2 = distance(nums.begin(), it2);
                    ret.push_back(static_cast<int>(index1));
                    ret.push_back(static_cast<int>(index2));
                }
            }
        }
        return ret;
    }
};

哈希-两次遍历

遍历一次将nums中的数据存储为<num[i], i>的键-值形式在哈希表中。再遍历一次，计算target-nums[i]这个键的出现次数，如果出现次数大于0则存在另一个数与当前nums[i]相加等于target，然后获取i与hash[target-nums[i]]即可。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> hash;
        // 初始化一个大小为2，值为-1的容器b
        vector<int> ret(2, -1);
        for(int i = 0;i < nums.size();i++){
            hash.insert(map<int,int>::value_type(nums[i],i));
        }
        for(int i = 0;i < nums.size();i++){
            // 计算键target-nums[i]出现次数
            if(hash.count(target - nums[i])>0 && (hash[target-nums[i]]!=i)){
                ret[0] = i;
                ret[1] = hash[target-nums[i]];
                break;
            }
        }
        return ret;
    }
};

哈希-一次遍历

遍历一次nums，计算hash中键target-nums[i]出现次数，如果大于0则找到了一个结果。如果未找到，则将<nums[i], i>放入hash中，继续遍历。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> hash;
        vector<int> ret(2, -1);
        for(int i = 0;i < nums.size();i++){
            // 计算键target-nums[i]出现次数
            if(hash.count(target - nums[i])>0){
                ret[0] = hash[target-nums[i]];
                ret[1] = i;
                break;
            }
            hash[nums[i]] = i;
        }
        return ret;
    }
};

198、打家劫舍

动态规划。将问题划分成若干小问题。对于前k间房间，有两种偷窃情况，偷窃前k-1家和偷窃前k-2家与第k家，因此比较f(k-1)与f(k-2)+v(k)的大小，然后更新到f(k)。需要确定f(0)=0和f(1)=v(0)的初始状态，然后进行迭代。

优化：每次迭代只用到f(k-1)与f(k-2)，因此可以只记录这两个状态。

class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size()==0){
            return 0;
        }
        int len = nums.size();
        vector<int> dp(3, 0);
        dp[0] = 0;
        dp[1] = nums[0];
        for(int k = 2;k<=len;k++){
            dp[2] = max(dp[1], nums[k-1] + dp[0]);
            dp[0] = dp[1];
            dp[1] = dp[2];
        }
        return dp[1];
    }
};

1583、统计不开心的朋友

用两个数组模拟，order[i][j]数组表示j在i中的排位，match[i]表示与i配对的对象序号。

有了这两个数组，就可以开始遍历所有人：首先找到与之配对的人y的下标index，然后遍历0-index寻找在x心中排位比y高的人u，找到后再通过match数组寻找与u配对的x。如果满足条件：

x与u的亲近程度胜过x与y，且
u与x的亲近程度胜过u与v

则不开心的人数加一

class Solution {
public:
    int unhappyFriends(int n, vector<vector<int>>& preferences, vector<vector<int>>& pairs) {
        int ret = 0;
        int order[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n-1;j++){
                // preferences[i][j]在i心中的排位
                order[i][preferences[i][j]] = j; 
            }
        }
        int match[n];
        for(int i=0;i<pairs.size();i++){
            match[pairs[i][0]] = pairs[i][1];
            match[pairs[i][1]] = pairs[i][0];
        }
        for(int x=0;x<n;x++){
            // 找到与之配对的
            int y = match[x];
            int index = order[x][y];
            // 寻找是否存在好感度更高的
            for(int j=0;j<index;j++){
                int u = preferences[x][j];
                int v = match[u];
                // 如果u也更想和x组队
                if(order[u][x] < order[u][v]){
                    ret++;
                    break;
                }
            }
        }
        return ret;
    }
};

213、打家劫舍Ⅱ

与第198题的不同之处是，其中房屋是首尾相连的，因此第一间房屋和最后一间房屋不能在同一晚上偷窃。所以可以分成两种情况，偷窃1到n-1间房子和偷窃2到n间房子，然后对于分解出来的这两个范围再对其使用上述198题的方法即可。

class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size()==0){
            return 0;
        }
        int len = nums.size();
        vector<int> dp(3, 0);
        dp[0] = 0;
        dp[1] = nums[0];
        for(int k = 2;k<=len-1;k++){
            dp[2] = max(dp[1], nums[k-1] + dp[0]);
            dp[0] = dp[1];
            dp[1] = dp[2];
        }
        vector<int> dp1(3, 0);
        dp1[0] = 0;
        if(len > 1){
            dp1[1] = nums[1];
        }
        for(int k = 3;k<=len;k++){
            dp1[2] = max(dp1[1], nums[k-1] + dp1[0]);
            dp1[0] = dp1[1];
            dp1[1] = dp1[2];
        }
        return max(dp[1], dp1[1]);
    }
};

337、打家劫舍Ⅲ

对于一个节点，有两种偷窃情况：1、偷窃该节点，不能偷窃子节点，保存状态f[node]为该节点权重+子树上不选中node的子节点的最大权重；2、不偷窃该节点，保存状态g[node]为node的子节点被选中或者不被选中两种情况下的最大值。

这样思路就清晰了，定义两个哈希表f、g，对该二叉树进行深度优先搜索，并更新f[node]与g[node]，前者为node->val+g[node->left]+g[node+right]（该节点权重+子树上不选中node的子节点的最大权重），后者为max(f[node->left], g[node.left])+max(f[node->right], g[node.right])（node的子节点被选中或者不被选中两种情况下的最大值），最后的结果就是根节点root在f与g哈希表中的最大权值了。

/**
 * 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 {
public:
    map <TreeNode*, int> f, g;
    void dfs(TreeNode *node){
        if(node == nullptr){
            return;
        }
        dfs(node->left);
        dfs(node->right);
        f[node] = g[node->left]+g[node->right]+node->val;
        g[node] = max(f[node->left], g[node->left])+max(f[node->right], g[node->right]);
    }
    int rob(TreeNode* root) {
        dfs(root);
        return max(f[root], g[root]);
    }
};

2560、打家劫舍Ⅳ

典型的最小化最大值问题。将小偷窃取的房屋中最大值upper初始化为nums中最大值，最小值lower设置为nums中最小值。使用二分查找，遍历nums，当该栋房子金额小于等于mid且前一栋房子未被偷窃则cnt+1，遍历结束后的cnt表示当最大偷窃能力为mid的情况下，可以偷窃的最大房屋数量。如果cnt比给出的k值大，说明此时的mid可能略大故让upper=mid向左收拢，否则使lower=mid+1向右收拢。迭代直到lower大于upper的情况，返回upper或者lower（最后lower==upper），即为至少偷窃k间房子的最小窃取能力。

class Solution {
public:
    int minCapability(vector<int>& nums, int k) {
        int lower = *min_element(nums.begin(), nums.end());
        int upper = *max_element(nums.begin(), nums.end());
        while(lower < upper){
            int mid = (upper+lower)/2;
            int cnt = 0;
            int visited = 0;
            for(int x : nums){
                if(x<=mid&&!visited){
                    cnt++;
                    visited = 1;
                }else{
                    visited = 0;
                }
            }
            if(cnt >= k){
                upper = mid;
            }else{
                lower = mid+1;
            }
        }
        return upper;
    }
};

1993、树上的操作

上锁和解锁的过程都十分简单，重点在于upgrade的过程。在canbeup函数中，首先判断是否为未上锁；然后判断是否存在至少一个上锁的后代节点，通过深度优先搜索遍历，将返回值的初始值设为false，当存在任一一个上锁的后代节点，则返回true，并且在递归调用时使用或操作，保证一个true的返回值可以在调用栈一直传递；最后判断是否存在上锁的父节点，利用parent数组迭代即可。如果可以升级，则直接利用深度优先搜索解锁所有后代节点并将当前节点上锁。

class LockingTree {
public:
    LockingTree(vector<int>& parent) {
        int len = parent.size();
        this->parent = parent;
        this->lockNodeUser = vector<int>(len, -1);
        this->children = vector<vector<int>>(len);
        for(int i = 0;i < len;i++){
            int p = parent[i];
            if(p != -1){
                children[p].push_back(i);
            }
        }
    }
    
    bool lock(int num, int user) {
        if(this->lockNodeUser[num] == -1){
            this->lockNodeUser[num] = user;
            return true;
        }
        return false;
    }
    
    bool unlock(int num, int user) {
        if(this->lockNodeUser[num] == user){
            this->lockNodeUser[num] = -1;
            return true;
        }
        return false;
    }
    
    bool upgrade(int num, int user) {
        if(!canbeup(num)){
            return false;
        }
        // 将所有子孙节点解锁
        unlockchildren(num);
        // 给指定节点上锁
        lock(num, user);
        return true;
    }

    bool canbeup(int num){
        // 当前节点未上锁
        if(lockNodeUser[num] != -1){
            return false;
        }
        // 至少有个上锁的子孙节点
        if(!anyloackchild(num)){
            return false;
        }
        if(anylockparent(num)){
            return false;
        }
        return true;
    }
    // 深度优先
    // 至少一个上锁的子孙节点
    bool anyloackchild(int num){
        int ret = false;
        for(int i = 0;i < children[num].size();i++){
            // 求或
            ret = ret || anyloackchild(children[num][i]);
        }
        if(lockNodeUser[num] != -1){
            return true;
        }else{
            return ret;
        }
    }

    // 判断是否有上锁的祖先节点
    bool anylockparent(int num){
        num = parent[num];
        while (num != -1) {
            if (lockNodeUser[num] != -1) {
                return true;
            }
            num = parent[num];
        }
        return false;
    }

    // 深度优先
    // 解锁子孙节点
    void unlockchildren(int num){
        for(int i = 0;i < children[num].size();i++){
            unlockchildren(children[num][i]);
        }
        this->lockNodeUser[num] = -1;
    }
private:
    vector<int> parent;
    vector<int> lockNodeUser;
    vector<vector<int>> children;
};

/**
 * Your LockingTree object will be instantiated and called as such:
 * LockingTree* obj = new LockingTree(parent);
 * bool param_1 = obj->lock(num,user);
 * bool param_2 = obj->unlock(num,user);
 * bool param_3 = obj->upgrade(num,user);
 */

146、LRU缓存

双向链表、哈希表、LRU（最近最少使用）算法。用哈希表模拟内存中的key-value对，用双向链表模拟内存中的key的使用情况，哈希表的value指向双向链表中对应的节点。当放入新页时，直接加到双向链表头部如果超过内存空间最大容量则移除链表尾部节点，当访问或者更新页时将节点放置在链表头部并更新value。

struct DLinkedNode {
    int key, value;
    DLinkedNode* prev;
    DLinkedNode* next;
    DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {}
    DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}
};


class LRUCache {
public:
    LRUCache(int capacity) {
        this->mem = 0;
        this->capacity = capacity;
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head->next = tail;
        tail->prev = head;
    }
    
    int get(int key) {
        if (cache.count(key) > 0) {
            DLinkedNode* node = cache[key];
            movetohd(node);
            return node->value;
        } else {
            return -1;
        }
    }
    
    void put(int key, int value) {
        if (cache.count(key) > 0) {
            DLinkedNode* node = cache[key];
            node->value = value;
            movetohd(node);
        }else{
            DLinkedNode* node = new DLinkedNode(key, value);
            cache[key] = node;
            addtohd(node);
            mem++;
            if(mem > capacity){
                DLinkedNode* node = removetail();
                cache.erase(node->key);
                delete node;
                mem--;
            }
        }
    }
    // 添加到头部
    void addtohd(DLinkedNode* node) {
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }
    // 移动到头部
    void movetohd(DLinkedNode* node){
        node->prev->next = node->next;
        node->next->prev = node->prev;
        addtohd(node);
    }
    // 删除尾部
    DLinkedNode* removetail(){
        DLinkedNode* node = tail->prev;
        node->prev->next = node->next;
        node->next->prev = node->prev;
        return node;
    }
private:
    map<int, DLinkedNode*> cache;
    DLinkedNode* head;
    DLinkedNode* tail;
    int mem;
    int capacity;
};

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

1333、餐厅过滤器

定义一个包含两个属性id和rating的结构体，并对该结构重定义运算符 > ，即rating更大的结构更大，rating相等的id更多的结构更大。在过滤函数中，首先遍历餐厅从中取出符合条件的餐厅赋值给新的结构体rest并存入ret当中。然后调用sort(ret.begin(), ret.end(), greater<rest>())函数进行排序，第三个参数表示自定义的比较函数也就是在结构体中重定义的运算符 > 。排序后将id数组返回即可。

class Solution {
public:   
    struct rest{
        int id;
        int rating;
        bool operator> (const rest& a) const {
            if (this->rating != a.rating) {
                return this->rating > a.rating;
            } else {
                return this->id > a.id;
            }
        }
    };
    vector<int> filterRestaurants(vector<vector<int>>& restaurants, int veganFriendly, int maxPrice, int maxDistance) {
        vector<rest> ret;
        int cnt;
        for(int i=0;i<restaurants.size();i++){
            if(veganFriendly == 1 && restaurants[i][2]!=1){
                continue;
            }
            if(restaurants[i][3] > maxPrice){
                continue;
            }
            if(restaurants[i][4] > maxDistance){
                continue;
            }
            struct rest r;
            r.id = restaurants[i][0];
            r.rating = restaurants[i][1];
            ret.push_back(r);
        }
        sort(ret.begin(), ret.end(), greater<rest>());
        vector<int> list;
        for(int i = 0;i< ret.size();i++){
            list.push_back(ret[i].id);
        }
        return list;
    }
};

2251、花期内花的数目

当第i个人到达时，时间为time，假设在time之前（包括time）开花的花数量为bloom，在time之前（不time）枯萎的花数量为fall，则time时刻第i个人能看到的花的数量为bloom-fall。将二维数组flowers中的花期开始与结束两个属性分别放在begin和end两个数组中，然后将这两个数组从小到大排序。

接下来遍历people数组，使用二分查找找到begin数组中小于等于time的元素数量（即在此刻即此刻之前开放的花），end数组中小于time的元素数量（即在此刻之前枯萎的花），第i个人能够观察到的花的数量为bloom-fall。

std::upper_bound函数返回在有序序列中大于给定值的第一个元素的迭代器。
std::lower_bound函数返回在有序序列中大于等于给定值的第一个元素的迭代器。
std::binary_search：该函数检查有序序列中是否存在与给定值匹配的元素，返回一个布尔值。

class Solution {
public:
    vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& people) {
        int NumofFlower = flowers.size();
        int NumofPerson = people.size();
        vector<int> ans(NumofPerson);
        vector<int> begin(NumofFlower), end(NumofFlower);
        for(int i = 0;i<NumofFlower;i++){
            begin[i] = flowers[i][0];
            end[i] = flowers[i][1];
        }
        sort(begin.begin(), begin.end());
        sort(end.begin(), end.end());
        for(int i =0;i<NumofPerson;i++){
            int time = people[i];
            int bloom, fall;
            bloom = upper_bound(begin.begin(), begin.end(), time)-begin.begin();
            fall = lower_bound(end.begin(), end.end(), time)-end.begin();
            ans[i] = bloom-fall;
        }
        return ans;
    }
};

309、买卖股票的最佳时机含冷冻期

将每天的状态分为三类——持股、不持股且处于冷冻期、不持股且不处于冷冻期。今日持股状态下的最大收益=max(前日持股状态下的最大收益，前日不持股且处于非冷冻期最大收益-今日股价)，不持股且处于冷冻期状态下的最大收益=max(前日持股最大收益+今日股价，前日不持股且处于冷冻期状态下最大收益)，不持股且不处于冷冻期状态下的最大收益=max(前一日不持股且不处于冷冻期的最大收益，前一日不持股且处于冷冻期)。

因为最后一日之前肯定会将股票抛售，所以最后最大收益为max(最后一日不持股且不处于冷冻期的最大收益，最后一日不持股且处于冷冻期的最大收益)。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len = prices.size();
        if(len == 1 || len == 0){
            return 0;
        }
        vector<vector<int>> money(len, vector<int>(3));
        money[0][0] = -prices[0];
        money[0][1] = 0;
        money[0][2] = 0;
        for(int i = 1;i<len;i++){
            // 当前状态为持有，则最大值为 前一日持有股票 和 前一日非冷冻期且不持股-今日股价 中的最大
            money[i][0] = max(money[i-1][0], money[i-1][2]-prices[i]);
            // 当前状态为无股票且处于冷冻期，则最大值为 前一日持有股票+今日出售 和 前一日冷冻期且不持股 中的最大
            money[i][1] = max(money[i-1][1], money[i-1][0]+prices[i]);
            // 当前状态为无股票且不处于冷冻期，则最大值为 前一日无股 和 前一日冷冻期且不持股 中的最大
            money[i][2] = max(money[i-1][1], money[i-1][2]);
        }
        return max(money[len-1][1], money[len-1][2]);
    }
};

714、买卖股票的最佳时机含手续费

将每天的状态分为三类——持股、不持股。今日持股的最大收益=max(前一日持股的最大收益，前一日不持股的最大收益-今日股价)，今日不持股的最大收益=max(前一日不持股的最大收益，前一日持股的最大收益+今日股价-手续费)。

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int len = prices.size();
        if(len == 1 || len == 0){
            return 0;
        }
        vector<vector<int>> money(len, vector<int>(2));
        money[0][0] = -prices[0];
        money[0][1] = 0;
        for(int i = 1;i<len;i++){
            money[i][0] = max(money[i-1][0], money[i-1][1]-prices[i]);
            money[i][1] = max(money[i-1][1], money[i-1][0]+prices[i]-fee);
        }
        return money[len-1][1];
    }
};

11、盛最多水的容器

贪心+双指针。第一个指针指向数组开头，第二个指针指向数组末尾。面积大小只与两个指针距离和最低高度有关，所以对指针进行迭代同时记录最大面积（当两个指针相等时结束），每次迭代将高度较低的那个指针向前迭代。

class Solution {
public:
    int maxArea(vector<int>& height) {
        int begin=0, end=height.size()-1;
        int size = 0;
        int tmp = 0;
        int lower = 0;
        while(begin != end){
            lower =  min(height[begin], height[end]);
            tmp =lower*(end-begin);
            size = max(size, tmp);
            if(height[begin] > height[end]){
                end--;
            }else{
                begin++;
            }
        }
        return size;
    }
};

12、整数转罗马数字

从高位转到低位就行，只需要考虑与4和9有关的特殊情况就行。

class Solution {
public:
    string intToRoman(int num) {
        map<int, string> map;
        vector<int> nums = {1,5,10,50,100,500,1000};
        map[1] = "I";
        map[5] = "V";
        map[10] = "X";
        map[50] = "L";
        map[100] = "C";
        map[500] = "D";
        map[1000] = "M";
        string ret;
        int lv;
        int cnt;
        for(int i=6;i>=0;i--){
            lv = nums[i];
            cnt = num/lv;
            if(i%2==0 && i!=6 && cnt==4){
                ret.append(map[lv]);
                ret.append(map[nums[i+1]]);
                num = num%lv;
            }
            else if(i%2==1 && num/nums[i-1]==9){
                ret.append(map[nums[i-1]]);
                ret.append(map[nums[i+1]]);
                num = num%nums[i-1];
                i--;
            }
            else{
                for(int j=0;j<cnt;j++){
                    ret.append(map[lv]);
                }
                num = num%lv;
            }
        }
        return ret;
    }
};

136、只出现一次的数字

异或

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret=0;
        for(int i=0;i<nums.size();i++){
            ret = ret^nums[i];
        }
        return ret;
    }
};

137、只出现一次的数字Ⅱ

计算数组里面所有数字的二进制第 i 位（0<=i<32）的和cnt，将其模3，得到的结果0或1就是只出现一次的数字的二进制的第 i 位（0<=i<32）。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        for(int i=0;i<32;i++){
            int cnt=0;
            for(int num : nums){
                cnt += (num >> i)&1;

            }
            if(cnt%3 == 1){
                ret |= (1 << i);
            }
        }
        return ret;
    }
};

260、只出现一次的数字Ⅲ

把所有数字异或得到结果x，为最终的两个数字x1、x2的异或。计算x & -x，得到第 i 位为1，x1、x2在这一位上必不同。因此将所有数字分为两类，第 i 位位0和第 i 位位1的，再一次遍历nums，然后计算两类数字的异或能够得到x1和x2.

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int x = 0;
        vector<int> ret(2, 0);
        for(int num : nums){
            x ^= num;
        }
        int bit = 0;
        if(x == INT_MIN){
            bit = x;
        }else{
            bit = x & -x;
        }
        for(int num : nums){
            if(num & bit){
                ret[0] ^= num;
            }else{
                ret[1] ^= num;
            }
        }
        return ret;

    }
};

80、删除有序数组中的重复项

双指针。

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int curr=0, next=1;
        int cnt = 0;
        while(curr < nums.size()-1){
            // 如果相等cnt+1
            if(nums[curr] == nums[next]){
                cnt++;
                // 超过两个元素，则删除next指向的元素
                if(cnt == 2){
                    auto iter= nums.begin()+next;
                    nums.erase(iter);
                    // 减少一个
                    cnt--;
                    continue;
                }
            }else{
                cnt = 0;
            }
            // 指针后移
            curr++;
            next++;
        }
        return nums.size();
    }
};

169、多数元素

对于多数元素，其二进制的每一位都是所有数据中最多的。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int ret = 0;
        for(int i = 0;i<32;i++){
            int zero = 0;
            int one = 0;
            for(int num:nums){
                if(num & (1 << i)){
                    one++;
                }else{
                    zero++;
                }
            }
            if(one > zero){
                ret |= (1 << i);
            }
        }
        return ret;
    }
};

189、轮转数组

从it=0开始迭代，完成 it、it+k mod len、it+2k mod len … 这条链上的轮转，每放置好一个元素则 cnt++。这样会有一个问题，并非所有元素都一定在这条链上，因此当轮转到 it==n*k mod len 也就是回到起点时，退出这一条链的轮转，判断cnt是否等于len，如果相等则说明所有元素都轮转了，退出迭代，否则让 it++，完成新的一条链的轮转。

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int len = nums.size();
        int ptr1 = 0, ptr2 = k%len;
        if(len == 1){
            return;
        }
        int it = 0;
        int cnt = 0;
        while(1){
            int ptr1 = it;
            int num1 = nums[ptr1]; 
            int num2 = num1;
            do{
                ptr2 = (ptr1+k)%len;
                // 元素移位
                num1 = num2;
                num2 = nums[ptr2];
                cnt++;
                nums[ptr2] = num1;
                ptr1 = ptr2%len;
                // 当回到起点，接下来会进入循环
            }while(it != ptr1);
            // 当所有元素全部迭代完成
            if(cnt == len){
                break;
            }
            it++;
        }
    }
};

2530、执行K此操作后的最大分数

使用make_heap(): 用于构建堆。它接受两个迭代器范围 [first, last)，将该范围内的元素重新排列为最大堆。默认情况下，它使用 operator< 来确定堆的顺序。然后迭代k次，每次取出堆顶元素，然后存储在tmp中，再计算大于或等于 tmp/3 的最小整数，将该整数重新放入堆。

class Solution {
public:
    long long maxKelements(vector<int>& nums, int k) {
        make_heap(nums.begin(), nums.end());
        long long ret = 0;
        long long tmp = 0;
        for(int i=0;i<k;i++){
            ret += nums[0];
            tmp = nums[0];
            pop_heap(nums.begin(), nums.end());
            nums.pop_back();
            nums.push_back((tmp+2)/3);
            push_heap(nums.begin(), nums.end());
        }
        return ret;
    }
};

1726、同积元组

嵌套迭代nums，获取所有不同两个元素的积并使用哈希表统计数量。最后遍历哈希表，当该积数量大于1时，计算C阶乘然后乘8即为以该乘积为积的同积元组的数量。

class Solution {
public:
    int c(int num){
        int fact = 1;
        for(int i = num;i>num-2;i--){
            fact *= i;
        }
        return fact/2;
    }

    int tupleSameProduct(vector<int>& nums) {
        int ret = 0;
        unordered_map<int, int> map;
        for(int i = 0;i<nums.size();i++){
            for(int j = i+1;j< nums.size();j++){
                if (map.find(nums[i]*nums[j]) != map.end()){
                    map[nums[i]*nums[j]]++;
                }else{
                    map[nums[i]*nums[j]] = 1;
                }
            }
        }
        for (const auto& pair : map) {
            if(pair.second > 1){
                ret += c(pair.second)*8;
            }
        }
        return ret;
    }
};

392、判断子序列

双指针

class Solution {
public:
    bool isSubsequence(string s, string t) {
        if(s.size()==0){
            return true;
        }
        int par = 0, sub = 0;
        int cnt = 0;
        for(;sub<s.size();sub++){
            for(int i=par;i<t.size();i++){
                if(s[sub]==t[i]){
                    cnt++;
                    if(cnt == s.size()){
                        return true;
                    }
                    par = ++i;
                    break;
                }
            }
        }
        return false;
    }
};

45、跳跃游戏Ⅱ

动态规划，dp数组存放到达终点的最少步数。从倒数第二个开始向前遍历，当可以直接到达终点时，dp[i] = 1，否则从i+1向后遍历到i可达的位置，计算到达终点的最少步数。遍历完成后，dp[0]即使到达终点的最少步数。

class Solution {
public:
    int jump(vector<int>& nums) {
        int len = nums.size();
        vector<int> dp(len, 10000);
        dp[len-1] = 0;
        for(int i = len-2;i>=0;i--){
            if(i+nums[i] >= len-1){
                dp[i] = 1;
                continue;
            }
            for(int j = 1;j<=nums[i];j++){
                dp[i] = min(dp[i], 1+dp[i+j]);
            }
        }
        return dp[0];
    }
};

380、O(1)时间插入、删除和获取随机元素

用哈希表记录每个值得下标，当插入元素时，通过哈希表判断该元素是否存在，存在则返回false。

当删除元素时，要O(1)时间内完成操作，通过哈希表判断该元素是否存在。当该元素存在时从哈希表中获取该元素下标，然后将数组的该下标位置设置为数组的最后一个元素，同时更新哈希表中该值的下标。然后将数组最后一个元素删除，哈希表该元素删除即可。

class RandomizedSet {
public:
    RandomizedSet() {
        srand((unsigned)time(NULL));
    }
    
    bool insert(int val) {
        if(map.count(val)){
            return false;
        }
        nums.emplace_back(val);
        map[val] = size;
        size++;
        return true;
    }
    
    bool remove(int val) {
        if(!map.count(val)){
            return false;
        }
        nums[map[val]] = nums.back();
        map[nums[map[val]]] = map[val];
        nums.pop_back();
        map.erase(val);
        size--;
        return true;
    }
    
    int getRandom() {
        int random = rand()%size;
        return nums[random];
    }
private:
    vector<int> nums;
    unordered_map<int, int> map;
    int size = 0;
};

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet* obj = new RandomizedSet();
 * bool param_1 = obj->insert(val);
 * bool param_2 = obj->remove(val);
 * int param_3 = obj->getRandom();
 */

2316、统计无向图中无法互相到达点对数

无向图中无法到达点的对数怎么计算？将无向图分为m个连通分量，无法到达的点的对数即其中n个连通分量的两两相乘的结果。知道这个思路就很明确了，首先构造临接表矩阵，然后初始化访问状态。无向图最多有n个连通分量，因此开始遍历，然后使用深度优先搜索获取连通分量中的节点个数（每次搜索后不将访问状态回复），然后将此次获取的连通分量中的节点个数与之前获取的所有连通分量的节点的个数相乘，重复此过程，直到遍历完所有连通分量。

class Solution {
public:
    long long countPairs(int n, vector<vector<int>>& edges) {
        long long ret = 0;
        vector<vector<int>> map(n);
        for(int i=0;i<edges.size();i++){
            map[edges[i][0]].push_back(edges[i][1]);
            map[edges[i][1]].push_back(edges[i][0]);
        }
        bool vis[n];
        memset(vis, 0, sizeof(vis));
        function<int(int)> dfs = [&](int node){
            if(vis[node]){
                return 0;
            }
            vis[node] = true;
            int cnt = 1;
            for(int i=0;i<map[node].size();i++){
                cnt+=dfs(map[node][i]);    
            }
            return cnt;
        };
        long tmp = 0;
        for(int i=0;i<n;i++){
            int vec = dfs(i);
            ret += tmp*vec;
            tmp += vec;
        }
        return ret;
    }
};

1402、做菜顺序——动态规划

动态规划。对于第i道菜，在此之前做的菜数量为j（范围在0~i之间），因此对于i可能做了0~i+1道菜，以此建立dp数组。首先对菜的好感度进行排序，然后遍历1~i道菜，计算制作j道菜的最大like-time系数。最后返回其中的最大like-time系数。

class Solution {
public:
    int maxSatisfaction(vector<int>& satisfaction) {
        sort(satisfaction.begin(), satisfaction.end());
        int len = satisfaction.size();
        int ret = 0;
        vector<vector<int>> dp(len, vector<int>(len+1, 0));
        dp[0][0] = 0;
        dp[0][1] = satisfaction[0];
        for(int i=1;i<len;i++){
            dp[i][0] = 0;
            for(int j=1;j<=i;j++){
                dp[i][j] = max(dp[i-1][j-1]+satisfaction[i]*j, dp[i-1][j]);
                ret = max(ret, dp[i][j]);
            }
            dp[i][i+1] = dp[i-1][i]+satisfaction[i]*(i+1);
            ret = max(ret, dp[i][i+1]);
        }
        return ret; 
    }
};

206、反转链表

递归。每次递归反转一根指针，tmp保存尾节点即反转后的头节点。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == nullptr || head->next == nullptr){
            return head;
        }
        ListNode* tmp = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return tmp;
    }
};

1155、掷骰子等于目标和的方法数

用数组dp[i][j]保存i个骰子，目标和为j的方法数量。初始状态为dp[0][0] = 1。然后进行迭代，dp[i][j]的值为dp[i][0]+dp[i][1]+……dp[i][j-1]。最终的结果为dp[n][target]。

class Solution {
public:
    int numRollsToTarget(int n, int k, int target) {
        vector<vector<int>> dp(n+1, vector<int>(target + 1, 0));
        dp[0][0] = 1;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=target;j++){
                for(int x=1;x<=k;x++){
                    if(j-x < 0){
                        break;
                    }
                    dp[i][j] = (dp[i][j]+dp[i-1][j-x])%1000000007;
                }
            }
        }
        return dp[n][target];
    }
};

1402、做菜顺序——后缀和

仔细观察一下，只要开始做菜，那么从这之后的所有菜都制作才能达到最大like-time系数。最后的like-time系数即所有菜的后缀和，因此要判断从哪道菜开始制作，只需要它的后缀和大于等于0即可，这样对整体like-time系数是有益的。所以首先找到后缀和不为负的最大下标，然后从这个下标开始计算后缀和即可得到最大的like-time系数。

class Solution {
public:
    int maxSatisfaction(vector<int>& satisfaction) {
        sort(satisfaction.begin(), satisfaction.end());
        int len = satisfaction.size();
        int ret = 0;
        int index = len;
        int sum = 0;
        for(int i=len-1;i>=0;i--){
            sum += satisfaction[i];
            if(sum < 0){
                break;
            }
            index--;
        }
        if(index == len){
            return ret;
        }
        int cnt = 1;
        for(;index<len;index++, cnt++){
            ret += cnt*satisfaction[index];
        }
        return ret; 
    }
};

2558、从数量最多的堆中取走礼物

优先队列，时间复杂度O(n+k)

class Solution {
public:
    long long pickGifts(vector<int>& gifts, int k) {
       make_heap(gifts.begin(), gifts.end());
       long long ret = 0;
       int tmp = 0;
       for(int i=0;i<k;i++){
            tmp = gifts[0];
            pop_heap(gifts.begin(), gifts.end());
            gifts.pop_back();
            gifts.push_back(floor(sqrt(tmp)));
            push_heap(gifts.begin(), gifts.end());
       }
       for(auto num:gifts){
           ret+=num;
       }
       return ret;
    }
};

274、H指数

先将H指数初始化可能的最大值，然后进行递减。每次迭代计算引用次数大于等于当前H指数的论文的数量，如果大于等于，该H指数即为最大H指数。

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int hindex = 0;
        sort(citations.begin(), citations.end());
        hindex = citations.size()>citations[citations.size()-1]?citations.size():citations[citations.size()-1];
        for(;hindex>=0;hindex--){
            int cnt = 0;
            for(int num : citations){
                if(num >= hindex){
                    cnt++;
                }
            }
            if(cnt>=hindex){
                break;
            }
        }
        return hindex;
    }
};

优化

首先对引用量进行排序，然后初始化H指数为0。从大到小遍历数组，如果当前引用值大于hindex，则增加hindex的值并向前移动指针，直到hindex与citations[l]汇合，说明hindex无法继续增大了。返回hindex。

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int hindex = 0, l = citations.size()-1;
        sort(citations.begin(), citations.end());
        while(l >= 0 && citations[l] > hindex){
            hindex++;
            l--;
        }
        return hindex;
    }
};

275、H指数 Ⅱ

要求对数时间复杂度，使用二分查找。当mid论文的引用次数等于len-mid即大于等于这个引用次数的论文个数时，说明找到了最大的H指数；当大于时，则说明有可能存在更大的H指数，保存当前的H指数，并继续二分查找；当小于时，则说明当前H指数需要更小，因此将查找范围往右缩短，移动left指针。

最后返回hindex，实现对数时间复杂度。

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int left=0, right = citations.size()-1;
        int len = citations.size();
        int mid;
        int hindex = 0;
        while(left <= right){
            mid = (left+right)/2;
            if(citations[mid] == len-mid){
                hindex =  citations[mid];
                break;
            }else if(citations[mid] > len-mid){
                right = mid-1;
                hindex =  len-mid;
            }else{
                left = mid+1;
            }
        }
        return hindex;
    }
};

117、填充每个节点的下一个右侧指针Ⅱ

层次遍历。

使用队列按层次遍历二叉树，while循环遍历的是层次，for循环遍历的一层中的节点。在for循环遍历一层节点时，每个节点的右节点就是队列的队首元素，但是当遍历到最后一个节点时，节点的右节点就是null了。然后再将节点的左右节点（如果有）放入队列。

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        if (root == nullptr) {
            return nullptr;
        }
        queue<Node*> q;
        q.push(root);

        while (!q.empty()) {
            int levelSize = q.size();

            for (int i = 0; i < levelSize; i++) {
                Node* current = q.front();
                q.pop();

                if (i < levelSize - 1) {
                    current->next = q.front();
                }else{
                    current->next = nullptr;
                }
                if (current->left != nullptr) {
                    q.push(current->left);
                }
                if (current->right != nullptr) {
                    q.push(current->right);
                }
            }
        }
        return root;
    }
};

------本页内容已结束，喜欢请分享------

文章作者

能不能吃完饭再说

隐私政策

PrivacyPolicy

用户协议

UseGenerator

许可协议

NC-SA 4.0

文章版权归作者所有，未经允许请勿转载。

THE END

leetcode刷题记录——2023年10月