- hash相关：
(1). 两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
例如：
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
class Solution
{
public:
vector<int> twoSum(vector<int>& nums, int target)
{
unordered_map<int, int> m;
for (int i = 0; i < nums.size(); i++)
{
//每次向hash表中放入数据前先看之前放入的数据中和这次要放的数据是否存在相加等于target的结果
if (m.find(target - nums[i]) != m.end()) //m.find(key)是通过传入键返回迭代器
return { m[target - nums[i]],i };
m[nums[i]] = i; //没找到时将本元素的值作为hash表中的键，本元素在nums中的下标作为hash表中的值插入hash表
}
return {};
}
};
//当可以确定哈希表中存在键为key的元素时，使用map[key]找到值，否则用map.find(key) == map.end()来判断是否存在键为key的元素
2. 链表操作
(1). 链表原地逆序
ListNode* reverse(ListNode* head)
{
ListNode* pre = NULL;
ListNode* next = NULL;
while (head)
{
next = head->next;
head->next = pre;
pre = head;
head = next;
}
return pre;
}
(2)对逆序排列的两个存在链表中的数相加并逆序输出结果
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
class Solution
{
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
{
ListNode* res = new ListNode(0);
ListNode* rec = res;
bool flag = 0;
while (l1 && l2)
{
res->next = new ListNode(0);
res = res->next;
res->val = l1->val + l2->val;
if (flag)
res->val += 1;
if (res->val >= 10)
{
res->val %= 10;
flag = 1;
}
else
flag = 0;
l1 = l1->next;
l2 = l2->next;
}
ListNode* temp = NULL;
if (l1)
temp = l1;
else if(l2)
temp = l2;
while (temp)
{
res->next = new ListNode(temp->val);
res = res->next;
if (flag)
{
res->val += 1;
if (res->val >= 10)
{
res->val %= 10;
flag = 1;
}
else
flag = 0;
}
temp = temp->next;
}
if (flag)
res->next = new ListNode(1);
return rec->next;
}
};
a. 初始化两个链表指针res和rec，res用来构建每一个链表元素，rec->next用来作链表头指针
b. res指向的第一个结点需要舍弃，因为下面while循环每次都会在循环开始构建一个新结点用来存放本次相加的结果
（循环1）
c. 当l1与l2均不为空时执行while循环
d. 循环中先为res->next分配空间并后移res，再将相加的值放入val中，最后看是否需要加前一位的进位
e. 判断val是否大于等于10，大于等于10进位并取10的模，设置进位标志位，否则清空进位标志位
f. l1与l2后移，开始下一次while循环
g. 循环结束后判断l1与l2哪个不为空，用一个新的指针temp指向不为空的部分链表
（循环2）
h. 当temp不为空时，为res->next分配空间并后移，再将temp->val的值放入res->val中
i. 判断是否有前一位的进位，有则加一，再判断是否大于等于10，大于等于10时进位并取10的模，否则清空进位标志位
j. temp指针后移
k. 最后看是否存在进位，存在时新建一个结点并存入1
(3). 删除链表倒数第n个元素
class Solution
{
public:
ListNode* removeNthFromEnd(ListNode* head, int n)
{
ListNode* res = head;
int count = 0;
while (head)
{
count++;
head = head->next;
}
head = res;
int loop = count - n - 1;
if (loop < 0)
return res->next;
for (int i = 0; i < loop; i++)
head = head->next;
head->next = head->next->next;
return res;
}
};
双循环
第一次循环计算出链表长度，为下次循环找到倒数第n-1个元素做准备
若链表长度是5，n=5，这时倒数第n-1个元素不存在，直接返回head->next
第二次循环找到倒数第n-1个元素
将其next设为next->next
(4). 旋转链表
输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL
class Solution
{
public:
ListNode* rotateRight(ListNode* head, int k)
{
if (!head || !head->next || k == 0)
return head;
int length = 0;
ListNode* first = head;
while (head->next)
{
length++;
head = head->next;
}
length++;
head->next = first;
head = first;
for (int i = 0; i < length - (k % length) - 1;i++)
head = head->next;
ListNode* res = head->next;
head->next = NULL;
return res;
}
};
a. 将链表连成循环链表并记录原链表的长度
b. 将head指针重新指向原链表的头结点
c. head循环后移length - (k % length) - 1次后找到的结点即为所求链表的尾结点
d. 断开尾结点的next，即为结果
(5). 复制带随机指针的链表
class Solution
{
public:
Node* copyRandomList(Node* head)
{
if (!head)
return NULL;
unordered_map<Node*, Node*> map;
Node* rec = head;
//对应生成新结点并放入map中
while (head)
{
map[head] = new Node(head->val);
head = head->next;
}
head = rec;
//将新结点连接起来
while (head->next)
{
map[head]->next = map[head->next];
head = head->next;
}
head = rec;
//对每个新结点的random赋值
while (head)
{
if (head->random)
map[head]->random = map[head->random];
else
map[head]->random = NULL;
head = head->next;
}
return map[rec];
}
};
a. 使用unordered_map，键和值分别存放原链表结点和对应深拷贝生成链表的结点的地址
（循环1）
b. 依次生成原链表和深拷贝链表的每个结点，并对应存入哈希表中
（循环2）
c. 将深拷贝生成的每个结点按原结点顺序链接起来
（循环3）
d. 依次根据原链表每个结点的random中的地址找到哈希表中对应生成的深拷贝结点地址，并对深拷贝结点的random赋值
e. 哈希表中键为原链表头结点地址的元素的值即为所求链表头结点地址