【数据结构】03.手撕算法题目总结1-58
【嵌入式八股】一、语言篇（https://www.nowcoder.com/creation/manager/columnDetail/mwQPeM
【嵌入式八股】二、计算机基础篇（本专栏）https://www.nowcoder.com/creation/manager/columnDetail/Mg5Lym
【嵌入式八股】三、硬件篇https://www.nowcoder.com/creation/manager/columnDetail/MRVDlM
【嵌入式八股】四、嵌入式Linux篇https://www.nowcoder.com/creation/manager/columnDetail/MQ2bb0
手撕算法整理
手撕算法整理
数组
01.二分查找
[704. 二分查找 - 力扣（Leetcode）]
二分法
目标值存在返回下标，否则返回 -1
class Solution {
public:
int search(vector<int>& nums, int target) {
int low=0;
int high=nums.size()-1;
int middle;
while(low<=high)
{
middle=(low+high)/2;
//middle=low+(high-low)/2; 防溢出写法
if(nums[middle]==target)return middle;
else if(nums[middle]<target) low=middle+1;
else high=middle-1;
}
return -1;
}
};
02.搜索插入位置
[35. 搜索插入位置 - 力扣（Leetcode）]
二分法
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
「在一个有序数组中找第一个大于等于 target 的下标」
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left=0;
int right=nums.size()-1;
int middle=0;
int ans=nums.size(); //防空和插入位置在最后的情况
while(left<=right)
{
middle=(left+right)/2;
if(target<=nums[middle]) //<----条件合并一下就行了
{
ans=middle;
right=middle-1;
}
else left=middle+1;
}
return ans;
}
};
03.移除元素
[27. 移除元素 - 力扣（Leetcode）]
双指针-快慢指针
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slow=0;
for(int fast=0;fast<nums.size();fast++)
{
if(nums[fast]!=val)nums[slow++]=nums[fast];
}
return slow;
}
};
04.删除有序数组中的重复项
[26. 删除有序数组中的重复项 - 力扣（Leetcode）]
有序数组
双指针-快慢指针
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int slow=0;
for(int fast=0;fast<nums.size();fast++)
{
if(nums[fast]!=nums[slow])
{
slow++;
nums[slow]=nums[fast];
}
}
return slow+1;
}
};
05.长度最小的子数组
[209. 长度最小的子数组 - 力扣（Leetcode）]
滑动窗口（快慢指针）
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int slow=0;
int sum=0;
int sub; //记录窗口大小
int result=INT_MAX;
for(int fast=0;fast<nums.size();fast++)
{
sum+=nums[fast];
while(sum>=target)
{
sub=(fast-slow+1); //滑动窗口
if(sub<result) result=sub;
sum-=nums[slow++];
}
}
return result==INT_MAX?0:result;
}
};
06.寻找数组的中心下标
[724. 寻找数组的中心下标 - 力扣（Leetcode）]
前缀和
记数组的全部元素之和为 total，当遍历到第 i 个元素时，设其左侧元素之和为 sum，则其右侧元素之和为 total−nums[i]−sum
。左右侧元素相等即为 sum=total−nums[i]−sum即 2×sum+nums[i]=total。
class Solution {
public:
int pivotIndex(vector<int>& nums) {
int total=0;
int sum=0;
for(int i=0;i<nums.size();i++)
{
total+=nums[i];
}
for(int i=0;i<nums.size();i++)
{
if(2*sum+nums[i]==total) return i;
sum+=nums[i];
}
return -1;
}
};
链表
07.设计链表
[707. 设计链表 - 力扣（Leetcode）]
C++版
class MyLinkedList {
public:
struct ListNode{
int val;
ListNode* next;
};
MyLinkedList() {
dummyhead=new ListNode();
size=0;
}
void addAtHead(int val) {
ListNode* newnode=new ListNode();
newnode->val=val;
newnode->next=dummyhead->next;
dummyhead->next=newnode;
size++;
}
void addAtTail(int val) {
ListNode* cur=dummyhead; //不是dummyhead->next
ListNode* newnode=new ListNode();
newnode->val=val;
newnode->next=NULL;
while(cur->next)
{
cur=cur->next;
}
cur->next=newnode;
size++;
}
void addAtIndex(int index, int val) {
if(index>size) return ; //index>size 等于的话也能放
if(index < 0) index = 0;
ListNode* cur=dummyhead; //不是dummyhead->next 要找要插入节点的前一个节点
ListNode* newnode=new ListNode();
newnode->val=val;
while(index)
{
cur=cur->next;
index--;
}
newnode->next=cur->next;
cur->next=newnode;
size++;
}
int get(int index) {
if(index>(size-1) || index<0) return -1; //index>(size-1)
ListNode* cur=dummyhead->next; //【dummyhead->next可以保证和index一致
while(index)
{
cur=cur->next;
index--;
}
return cur->val;
}
void deleteAtIndex(int index) {
if(index>(size-1) || index<0) return;
ListNode* cur=dummyhead; //不是dummyhead->next，要找要删除节点的前一个节点
ListNode* del=new ListNode();
while(index)
{
cur=cur->next;
index--;
}
del=cur->next;
cur->next=cur->next->next;
delete del;
size--;
}
private:
ListNode* dummyhead;
int size;
};
C语言版
typedef struct MyLinkedList_t{
int val;
struct MyLinkedList_t *next;
} MyLinkedList;
/** Initialize your data structure here. */
MyLinkedList* myLinkedListCreate() {
MyLinkedList *obj = (MyLinkedList *)malloc(sizeof(MyLinkedList));
obj->val = 0;
obj->next = NULL;
return obj;
}
/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
int myLinkedListGet(MyLinkedList* obj, int index) {
if (index < 0 || obj->next == NULL) {
return -1;
}
int now = 0;
MyLinkedList *listNow = obj->next;
while (now < index) {
if (listNow == NULL) {
return -1;
}
listNow = listNow->next;
now++;
}
if (listNow != NULL) {
return listNow->val;
}
return -1;
}
/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
void myLinkedListAddAtHead(MyLinkedList* obj, int val) {
MyLinkedList *Node = (MyLinkedList *)malloc(sizeof(MyLinkedList));
Node->val = val;
Node->next = NULL;
if (obj->next == NULL) {
obj->next = Node;
return;
} else {
Node->next = obj->next;
obj->next = Node;
}
}
/** Append a node of value val to the last element of the linked list. */
void myLinkedListAddAtTail(MyLinkedList* obj, int val) {
MyLinkedList *Node = (MyLinkedList *)malloc(sizeof(MyLinkedList));
Node->val = val;
Node->next = NULL;
MyLinkedList *nowList = obj;
while (nowList->next != NULL) {
nowList = nowList->next;
}
nowList->next = Node;
}
/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) {
if (index <= 0) {
myLinkedListAddAtHead(obj, val);
}
int now = 0;
MyLinkedList *nowList = obj->next;
while (nowList->next != NULL) {
if (now == index - 1) {
break;
}
nowList = nowList->next;
now++;
}
if (index - 1 != now) {
return;
}
MyLinkedList *Node = (MyLinkedList *)malloc(sizeof(MyLinkedList));
Node->val = val;
Node->next = nowList->next;
nowList->next = Node;
}
/** Delete the index-th node in the linked list, if the index is valid. */
void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) {
if (index < 0 || obj->next == NULL) {
return;
}
if (index == 0) {
obj->next = obj->next->next;
return;
}
MyLinkedList *nowList = obj->next;
int now = 0;
while (nowList->next != NULL) {
if (now == index - 1) {
break;
}
nowList = nowList->next;
now++;
}
if (now == index - 1 && nowList->next != NULL) {
nowList->next = nowList->next->next;
}
}
void myNodeFree(MyLinkedList* Node) {
if (Node->next != NULL) {
myNodeFree(Node->next);
Node->next = NULL;
}
free(Node);
}
void myLinkedListFree(MyLinkedList* obj) {
myNodeFree(obj);
}
/**
* Your MyLinkedList struct will be instantiated and called as such:
* MyLinkedList* obj = myLinkedListCreate();
* int param_1 = myLinkedListGet(obj, index);
* myLinkedListAddAtHead(obj, val);
* myLinkedListAddAtTail(obj, val);
* myLinkedListAddAtIndex(obj, index, val);
* myLinkedListDeleteAtIndex(obj, index);
* myLinkedListFree(obj);
*/
08.移除链表元素
[203. 移除链表元素 - 力扣（Leetcode）]
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode* dummyhead=new(ListNode);
dummyhead->next=head;
ListNode* cur=dummyhead;
while(cur->next!=NULL) //cur最后指到最后一个元素就行了，不需要指向空
{
if(cur->next->val!=val) //里面用if，外面用while判断空
{
cur=cur->next;
}
else
{
ListNode* del=cur->next;
cur->next=cur->next->next;
delete del;
}
}
head=dummyhead->next;
delete dummyhead; //记得释放它
return head;
}
};
09.删除链表的倒数第 N 个结点
[19. 删除链表的倒数第 N 个结点 - 力扣（Leetcode）]
同[剑指 Offer 22. 链表中倒数第k个节点 - 力扣（Leetcode）]
同删除链表的倒数第n个节点_牛客题霸_牛客网 (nowcoder.com)
快慢指针
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummyhead=new ListNode();
dummyhead->next=head;
ListNode* fast=dummyhead;
ListNode* slow=dummyhead;
n++;
while(n--&&fast!=NULL) //fast!=NULL那么fast最后就可以指向NULL
{ //fast->next!=NULL那么fast最后指向最后一个节点
fast=fast->next;
}
while(fast!=NULL)
{
fast=fast->next;
slow=slow->next;
}
ListNode* del=slow->next;
slow->next=slow->next->next;
delete del;
return dummyhead->next;
}
};
10.删除有序链表中重复的元素
删除有序链表中重复的元素-II_牛客题霸_牛客网 (nowcoder.com)
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
// write code here
if(head==nullptr) return nullptr;
ListNode* dummy=new ListNode(0);
dummy->next=head;
ListNode* cur=dummy;
while(cur->next!=nullptr && cur->next->next!=nullptr)
{
//遇到相邻两个节点值相同
if(cur->next->val == cur->next->next->val){
int temp = cur->next->val;
//将所有相同的都跳过
while (cur->next != NULL && cur->next->val == temp)
cur->next = cur->next->next;
}
else
cur = cur->next;
}
return dummy->next;
}
};
11.反转链表
[剑指 Offer 24. 反转链表 LCOF - 力扣（Leetcode）]
同[206. 反转链表 - 力扣（Leetcode）]
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* cur=head;
ListNode* pre=NULL;
ListNode* temp=NULL;
while(cur) //cur最后要指向空
{
temp=cur->next;
cur->next=pre;
pre=cur;
cur=temp;
}
return pre;
}
};
12.K 个一组翻转链表
[25. K 个一组翻转链表 - 力扣（Leetcode）]
链表中的节点每k个一组翻转_牛客题霸_牛客网 (nowcoder.com)
class Solution {
public:
ListNode* reverse(ListNode* head)
{
ListNode* cur=head;
ListNode* pre=NULL;
while(cur)
{
ListNode* temp=cur->next;
cur->next=pre;
pre=cur;
cur=temp;
}
return pre;
}
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode* dummyhead=new ListNode(0);
dummyhead->next=head;
ListNode* pre=dummyhead;
ListNode* end=dummyhead;
while(end->next!=NULL) //end最后指向最后一个结点
{
for (int i = 0; i < k && end != NULL; i++) end = end->next;
if (end == NULL) break; //最后不满的一组不反转
ListNode* start=pre->next; //待反转的起点
ListNode* next=end->next; //未反转的起点
end->next=NULL; //断开
pre->next = reverse(start);
start->next = next; //连上，start已经变成K个的结尾了
pre = start;
end = pre;
}
return dummyhead->next;
}
};
13.链表内指定区间反转
链表内指定区间反转_牛客题霸_牛客网 (nowcoder.com)
class Solution {
public:
/**
*
* @param head ListNode类
* @param m int整型
* @param n int整型
* @return ListNode类
*/
ListNode* Reverse(ListNode* head)
{
ListNode* pre=nullptr;
ListNode* cur=head;
while(cur!=nullptr)
{
ListNode* temp=cur->next;
cur->next=pre;
pre=cur;
cur=temp;
}
return pre;
}
ListNode* reverseBetween(ListNode* head, int m, int n) {
// write code here
ListNode* dummy=new ListNode(0);
dummy->next=head;
ListNode* pre=dummy;
ListNode* end=dummy;
m--;
while(m--&&pre->next!=nullptr)
{
pre=pre->next;
}
while(n--&&end->next!=nullptr)
{
end=end->next;
}
ListNode* start=pre->next;
ListNode* next=end->next;
end->next=nullptr;
pre->next=Reverse(start);
start->next=next;
return dummy->next;
}
};
14.链表的中间结点
[876. 链表的中间结点 - 力扣（Leetcode）]
快慢指针
class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode* slow=head;
ListNode* fast=head;
while(slow->next!=NULL && fast->next!=NULL&&fast->next->next!=NULL) //既然是找中间节点，那么fast应该指向
{ //最后一个节点，所以判断fast->next!=NULL，但是一次走两步，所以判断fast->next->next!=NULL
slow=slow->next;
fast=fast->next->next;
}
if(fast->next!=NULL&&fast->next->next==NULL) slow=slow->next; //判断最后是否指向了倒数第二个节点
return slow;
}
};
15.链表相交
[面试题 02.07. 链表相交 - 力扣（Leetcode）]
[160. 相交链表 - 力扣（Leetcode）]
两个链表的第一个公共结点_牛客题霸_牛客网 (nowcoder.com)
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* curA=headA;
ListNode* curB=headB;
int lengthA=0;
int lengthB=0;
while(curA)
{
lengthA++;
curA=curA->next;
}
while(curB)
{
lengthB++;
curB=curB->next;
}
curA=headA;
curB=headB;
if(lengthB>lengthA)
{
swap(curA,curB);
swap(lengthA,lengthB);
}
int gap=lengthA-lengthB;
while(gap--)curA=curA->next;
while(curA!=NULL)
{
if(curA==curB)return curA;
curA=curA->next;
curB=curB->next;
}
return NULL;
}
};
【LeetCode 每日一题】160. 相交链表 | 手写图解版思路 + 代码讲解_哔哩哔哩_bilibili
//双指针法
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(headA==NULL||headB==NULL) return NULL;
ListNode * pA=headA;
ListNode * pB=headB;
while(pA!=pB)
{
pA=pA==NULL? headB:pA->next;
pB=pB==NULL? headA:pB->next;
}
return pA;
}
};
16.环形链表
[141. 环形链表 - 力扣（Leetcode）]
同[142. 环形链表 II - 力扣（Leetcode）]
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* fast=head;
ListNode* slow=head;
while(fast!=NULL&&fast->next!=NULL)
{
fast=fast->next->next;
slow=slow->next;
if(fast==slow)
{
ListNode* index1=fast;
ListNode* index2=head;
while(index1!=index2)
{
index1=index1->next;
index2=index2->next;
}
return index1;
}
}
return NULL;
}
};
17.合并两个有序链表
[21. 合并两个有序链表 - 力扣（Leetcode）]
合并两个排序的链表_牛客题霸_牛客网 (nowcoder.com)
迭代写法
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode* dummyhead=new ListNode;
ListNode* cur=dummyhead;
ListNode* cur1=list1;
ListNode* cur2=list2;
while(cur1!=NULL && cur2!=NULL)
{
if(cur1->val<=cur2->val)
{
cur->next=cur1;
cur1=cur1->next;
}
else
{
cur->next=cur2;
cur2=cur2->next;
}
cur=cur->next; //别忘了
}
if(cur1!=NULL) cur->next=cur1;
else cur->next=cur2;
return dummyhead->next;
}
};
递归写法
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1 == NULL) {
return l2;
}
if (l2 == NULL) {
return l1;
}
if (l1->val <= l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
}
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
};
18.合并k个已排序的链表
合并k个已排序的链表_牛客题霸_牛客网 (nowcoder.com)
class Solution {
public:
ListNode* MergeTwo(ListNode* pHead1, ListNode* pHead2) {
ListNode* dummy=new ListNode(0);
ListNode* cur=dummy;
ListNode* cur1=pHead1;
ListNode* cur2=pHead2;
while(cur1!=nullptr&&cur2!=nullptr)
{
if(cur1->val<=cur2->val)
{
cur->next=cur1;
cur1=cur1->next;
}
else
{
cur->next=cur2;
cur2=cur2->next;
}
cur=cur->next;
}
if(cur1!=nullptr) cur->next=cur1;
else cur->next=cur2;
return dummy->next;
}
//分治
ListNode* merge(vector<ListNode* > &lists, int left, int right) {
if (left >= right) return lists[left];
int mid = (left + right) / 2;
ListNode* l1 = merge(lists, left, mid);
ListNode* l2 = merge(lists, mid+1, right);
return MergeTwo(l1, l2);
}
ListNode* mergeKLists(vector<ListNode *> &lists) {
int len=lists.size();
if(len==0) return nullptr;
if(len==1) return lists[0];
return merge(lists, 0, lists.size()-1);
}
};
19.排序链表
[148. 排序链表 - 力扣（LeetCode）]
链表自顶向下归并排序+合并两个有序链表
class Solution {
public:
ListNode* sortList(ListNode* head) {
return sortList(head, nullptr);
}
ListNode* sortList(ListNode* head, ListNode* tail) {
if (head == nullptr) {
return head;
}
if (head->next == tail) {
head->next = nullptr;
return head;
}
ListNode* slow = head, *fast = head;
while (fast != tail) {
slow = slow->next;
fast = fast->next;
if (fast != tail) {
fast = fast->next;
}
}
ListNode* mid = slow;
return merge(sortList(head, mid), sortList(mid, tail));
}
ListNode* merge(ListNode* head1, ListNode* head2) {
ListNode* dummyHead = new ListNode(0);
ListNode* temp = dummyHead, *temp1 = head1, *temp2 = head2;
while (temp1 != nullptr && temp2 != nullptr) {
if (temp1->val <= temp2->val) {
temp->next = temp1;
temp1 = temp1->next;
} else {
temp->next = temp2;
temp2 = temp2->next;
}
temp = temp->next;
}
if (temp1 != nullptr) {
temp->next = temp1;
} else if (temp2 != nullptr) {
temp->next = temp2;
}
return dummyHead->next;
}
};
20.重排链表
[143. 重排链表 - 力扣（Leetcode）]
方法一：线性表
class Solution {
public:
void reorderList(ListNode* h剩余60%内容，订阅专栏后可继续查看/也可单篇购买
【嵌入式八股】二、计算机基础篇 文章被收录于专栏
查阅整理上千份嵌入式面经，将相关资料汇集于此，主要包括： 0.简历面试 1.语言篇 2.计算机基础【本专栏】 3.硬件篇 4.嵌入式Linux （建议PC端查看）
