LeetCode Hot100 21~30
矩阵
21. 搜索二维矩阵
很简单 只需要找到一个角落 这个角落往两边移动能得到不同的结果即可
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int n = matrix.size() - 1;
int m = matrix[0].size() - 1;
int i = 0;
int j = m ;
bool ans = false;
while (i <= n && j >= 0) {
if (matrix[i][j] > target) {
j--;
}else if (matrix[i][j] < target) {
i++;
}else {
ans = true;
break;
}
}
return ans;
}
};
链表
22. 相交链表
使用两个指针遍历完一个链表之后遍历另外一个 保证遍历的次数相同 就能相遇
需要注意的是 转移指针也算是一次移动
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* curA = headA;
ListNode* curB = headB;
while (curA != curB) {
if (curA == NULL) {
curA = headB;
}else {
curA = curA -> next;
}
if (curB == NULL) {
curB = headA;
}else {
curB = curB -> next;
}
}
return curA;
}
};
23. 翻转链表
很简单 三个指针转一下就行 如果不会的话试试画图
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}
ListNode* NodePre = head;
ListNode* NodeCur = head->next;
ListNode* NodeNext = head->next->next;
head->next = nullptr;
while (NodeCur) {
NodeCur->next = NodePre;
NodePre = NodeCur;
NodeCur = NodeNext;
if (NodeNext) {
NodeNext = NodeNext->next;
}
}
return NodePre;
}
};
24. 回文链表
用个数组存储数据即可
class Solution {
public:
bool isPalindrome(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return true;
}
vector<int> vNode;
while (head) {
vNode.push_back(head->val);
head = head->next;
}
int n = vNode.size();
int left = 0;
int right = n - 1;
while(left < right) {
if (vNode[left] != vNode[right]) {
return false;
}
left++;
right--;
}
return true;
}
};
25. 环形链表
很简单的快慢指针就能解决
class Solution {
public:
bool hasCycle(ListNode *head) {
if (head == NULL || head->next == NULL) {
return false;
}
ListNode* slow = head;
ListNode* fast = head;
while (slow && fast) {
slow = slow->next;
if (fast->next) {
fast = fast->next->next;
}else {
return false;
}
if (fast == slow) {
return true;
}
}
return false;
}
};
26. 环形链表2
代码简单 要理解推导公式 假设距离分别为abc 根据二倍公式推导
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if (head == NULL || head->next == NULL) {
return NULL;
}
ListNode* slow = head;
ListNode* fast = head;
while (slow && fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
fast = head;
while (slow ) {
if (slow == fast) {
return slow;
}else {
slow = slow->next;
fast = fast->next;
}
}
}
}
return NULL;
}
};
27. 合并链表
简单的归并排序 需要注意while的终止条件 不能想当然
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if (list1 == nullptr) {
return list2;
}
if (list2 == nullptr) {
return list1;
}
ListNode* Head = nullptr;
if (list1->val < list2->val) {
Head = list1;
list1 = list1->next;
}else {
Head = list2;
list2 = list2->next;
}
ListNode* ans = Head;
while (list1 && list2) {
ListNode* tmp = nullptr;
if (list1->val < list2->val) {
tmp = list1;
list1 = list1->next;
}else {
tmp = list2;
list2 = list2->next;
}
Head->next = tmp;
Head = Head->next;
}
while(list1) {
Head->next = list1;
break;
}
while(list2) {
Head->next = list2;
break;
}
return ans;
}
};
28. 两数相加
短的链表补0 只有如果有进位则加上 最后返回结果即可
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
int len1=1;//记录l1的长度
int len2=1;//记录l2的长度
ListNode* p=l1;
ListNode* q=l2;
while(p->next!=NULL)//获取l1的长度
{
len1++;
p=p->next;
}
while(q->next!=NULL)//获取l2的长度
{
len2++;
q=q->next;
}
if(len1>len2)//l1较长，在l2末尾补零
{
for(int i=1;i<=len1-len2;i++)
{
q->next=new ListNode(0);
q=q->next;
}
}
else//l2较长，在l1末尾补零
{
for(int i=1;i<=len2-len1;i++)
{
p->next=new ListNode(0);
p=p->next;
}
}
p=l1;
q=l2;
bool count=false;//记录进位
ListNode* l3=new ListNode(-1);//存放结果的链表
ListNode* w=l3;//l3的移动指针
int i=0;//记录相加结果
while(p!=NULL&&q!=NULL)
{
i=count+p->val+q->val;
w->next=new ListNode(i%10);
count=i>=10?true:false;
w=w->next;
p=p->next;
q=q->next;
}
if(count)//若最后还有进位
{
w->next=new ListNode(1);
w=w->next;
}
return l3->next;
}
};
29. 删除链表的倒数第N个节点
很简单 找出第N - 1个就行 如果删除的是第0个 特殊处理一下
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
if (head == nullptr || head->next == nullptr) {
return nullptr;
}
int count = 0;
ListNode* cur = head;
while (cur) {
cur = cur->next;
count++;
}
if (n == count) {
return head->next;
}
int step = count - n - 1;
cur = head;
while (step) {
step--;
cur = cur->next;
}
cur->next = cur->next->next;
return head;
}
};
30. 两两交换链表中的节点
首先观察至少需要多少个节点 之后添加一个虚拟头节点 再观察下终止条件即可
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummyList = new ListNode();
dummyList->next = head;
ListNode* Node0 = dummyList;
while (Node0->next && Node0->next->next) {
ListNode* Node1 = Node0->next;
ListNode* Node2 = Node1->next;
ListNode* Node3 = Node2->next;
Node0->next =Node2;
Node2->next = Node1;
Node1->next = Node3;
Node0 = Node1;
}
return dummyList->next;
}
};