LeetCode刷题笔记
目录
LeetCode1.两数之和
思路：
暴力：
最容易想到的方法是枚举数组中的每一个数 x，寻找数组中是否存在 target - x。
当我们使用遍历整个数组的方式寻找 target - x 时，需要注意到每一个位于 x 之前的元素都已经和 x 匹配过，因此不需要再进行匹配。而每一个元素不能被使用两次，所以我们只需要在 x 后面的元素中寻找 target - x。两数之和，梦开始的地方。
哈希表：
注意到方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。
使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N) 降低到 O(1)。这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。
代码：
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};
}
};class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> hashtable;
for (int i = 0; i < nums.size(); ++i) {
auto it = hashtable.find(target - nums[i]);
if (it != hashtable.end()) {
return {it->second, i};
}
hashtable[nums[i]] = i;
}
return {};
}
};
LeetCode2.两数相加
思路：
由于输入的两个链表都是逆序存储数字的位数的，因此两个链表中同一位置的数字可以直接相加。我们同时遍历两个链表，逐位计算它们的和，并与当前位置的进位值相加。具体而言，如果当前两个链表处相应位置的数字为 n1,n2，进位值为 carry，则它们的和为 n1+n2+carry；其中，答案链表处相应位置的数字为 (n1+n2+carry)mod10，如果两个链表的长度不同，则可以认为长度短的链表的后面有若干个 0 。此外，如果链表遍历结束后，有 arry>0，还需要在答案链表的后面附加一个节点，节点的值为 carry。
代码：
/**
* 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;
}
};整体思路：
将长度较短的链表在末尾补零使得两个连表长度相等，再一个一个元素对其相加（考虑进位）
- 获取两个链表所对应的长度
- 在较短的链表末尾补零
- 对齐相加考虑进位
LeetCode1171.链表删除和为0的连续节点
思路：
给你一个链表的头节点 head，反复删去链表中总和值为 0 的连续节点组成的序列。建立一个 new_head 节点，指向 head，节点值为 0。遍历一遍链表，同时记录前缀和，以当前前缀和为 key，当前节点为，存入哈希表中。如果相同前缀和已经存在，就可以直接覆盖掉原有节点。
第二遍重新遍历链表，同时记录前缀和 sum，哈希表中对应 sum 的节点是最后一次出现相同前缀和的节点，我们将这个节点的下一个节点，赋值给当前节点的下一个节点，中间跳过的部分总和即为 0。最后我们返回 new_head 节点的下一节点作为新的头节点。注意满足题目要求的答案不唯一，可以返回任何满足题目要求的答案。
简单来说就是，在原来链表基础上，头部添加0，利用前缀和的性质，前轴和相同时，两者之间的和为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;
}
};
- 点赞
- 收藏
- 关注作者
评论（0）