LeetCode刷题笔记-阿里云开发者社区

LeetCode刷题笔记

2023-06-21 27

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： LeetCode刷题笔记

LeetCode1.两数之和

两数之和梦开始的地方，让我们开始追逐自己的梦想吧！

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int i=0,j=0;
        int len=nums.size();
        for(int i=0;i<len;i++){
            for(int j=i+1;j<len;j++){
                if(nums[i]+nums[j]==target){
                    return {i,j};
                }
            }
        }
            return {i,j};
    }
};

LeetCode2.两数相加

/**
 * 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* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* head=new ListNode;   //建立头结点
        ListNode* head_list=head;      //往后移动的指针
        bool flage=false;              //标记是否进位
        while(l1 || l2 || flage){
            short int sum=0;
            sum+=(l1?l1->val:0);
            sum+=(l2?l2->val:0);
            if(flage) sum+=1;
            if(sum>=10) {
                sum-=10;
                flage=true;
            }else{
                flage=false;
            }
            ListNode* node=new ListNode(sum,nullptr); 
            head_list->next=node;
            head_list=node;
            if(l1)l1=l1->next;
            if(l2)l2=l2->next;
        }
        return head->next;
    }
};

首先节点范围是[1,100]，因此不能完全转化为数组类型。

思路：

1.两个链表对应位相加，短的在末尾补0

2.当相加大于10时，取个位数存到该节点，并且进位1

LeetCode1171.链表删除和为0的连续节点

/**
 * 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* removeZeroSumSublists(ListNode* head) {
        ListNode* new_head=new ListNode(0,head);  
        unordered_map<int, ListNode*>arr_sum;   //STL库
        int sum=0;
        for(ListNode* node=new_head;node;node=node->next){
            sum+=node->val;
            arr_sum[sum]=node;
            //sum从0开始
        }
        sum=0;
        for(ListNode* node=new_head;node;node=node->next){
            sum+=node->val;
            node->next=arr_sum[sum]->next;
        }
        return new_head->next;
    }
};

给你一个链表的头节点 head，反复删去链表中总和值为 0 的连续节点组成的序列。建立一个 new_head 节点，指向 head，节点值为 0。遍历一遍链表，同时记录前缀和，以当前前缀和为 key，当前节点为，存入哈希表中。如果相同前缀和已经存在，就可以直接覆盖掉原有节点。

第二遍重新遍历链表，同时记录前缀和 sum，哈希表中对应 sum 的节点是最后一次出现相同前缀和的节点，我们将这个节点的下一个节点，赋值给当前节点的下一个节点，中间跳过的部分总和即为 0。最后我们返回 new_head 节点的下一节点作为新的头节点。注意满足题目要求的答案不唯一，可以返回任何满足题目要求的答案。

简单来说就是，在原来链表基础上，头部添加0，利用前缀和的性质，前轴和相同时，两者之间的和为0(包括后一个)；跳过这部分即可；