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(包括后一个)；跳过这部分即可；
