一、基本排序算法
1.1、冒泡排序
//1、冒泡排序//时间复杂度为O(n^2),额外空间复杂度为O(1)void BubbleSort(int a[], int n) {if (n < 2) {return;}for (int i = n - 1; i > 0; i--) {for (int j = 0; j < i; j++) {if (a[j] > a[j + 1]) {swap(a[j], a[j + 1]);}}}}
1.2、选择排序
//2、选择排序//时间复杂度为O(n^2),额外空间复杂度为O(1)void SelectSort(int a[], int n) {if (n < 2) {return;}for (int i = 0; i < n - 1; i++) {int minIndex = i;for (int j = i + 1; j < n; j++) {minIndex = a[j] < a[minIndex] ? j : minIndex;}swap(a[i], a[minIndex]);}}
1.3、插入排序
//3、插入排序//时间复杂度为O(n^2),额外空间复杂度为O(1)void InsertSort(int a[], int n) {if (n < 2) {return;}for (int i = 1; i < n; i++) {for (int j = i - 1; j >= 0 && a[j] > a[j + 1]; j--) {swap(a[j], a[j + 1]);}}}
1.4、归并排序
//4、归并排序//时间复杂度为O(n*logn),额外空间复杂度为O(n)void merge(int a[], int temp[], int l, int m, int r);void msort(int a[], int temp[], int l, int r);void MergeSort(int a[], int n) {int *temp = new int[n];if (temp != nullptr) {msort(a, temp, 0, n - 1);delete[] temp;}}void msort(int a[], int temp[], int l, int r) {if (l >= r) {return;}//int mid = (l + r) / 2; //存在越界的可能int mid = l + ((r - l) >> 1); //不会越界且位运算比算术运算速度快msort(a, temp, l, mid); //对[l,middle]递归做归并排序msort(a, temp, mid + 1, r); //对[middle+1，r]递归做归并排序merge(a, temp, l, mid, r); //组合}void merge(int a[], int temp[], int l, int m, int r) {//l->左边起始点 m->左边结束点 m+1->右边起始点 r->右边结束点int p1 = l;int p2 = m + 1;int i = 0;int length = r - l + 1;//数组长度while (p1 <= m && p2 <= r) {temp[i++] = a[p1] < a[p2] ? a[p1++] : a[p2++];}//左右两端可能还存在剩余元素while (p1 <= m) {temp[i++] = a[p1++];}while (p2 <= r) {temp[i++] = a[p2++];}for (i = 0; i < length; i++) {a[l + i] = temp[i];}}
1.5、随机快速排序
//5、随机快速排序//时间复杂度为O(n*logn),额外空间复杂度为O(logn)vector<int> partition(vector<int> &a, int l, int r) {int less = l - 1;int more = r;int cur = l;while (cur < more) {if (a[cur] < a[r]) {swap(a[++less], a[cur++]);}else if (a[cur] > a[r]) {swap(a[--more], a[cur]);}else {cur++;}}swap(a[more], a[r]);vector<int> pos(2);pos[0] = less + 1;pos[1] = more;return pos;}void Quick_Sort(vector<int> &a, int l, int r) {if (l < r) {swap(a[l + rand() % (r - l)], a[r]);vector<int> pos = partition(a, l, r);Quick_Sort(a, l, pos[0] - 1);Quick_Sort(a, pos[1] + 1, r);}}void QuickSort(vector<int> &a) {if (a.size() < 2) {return;}Quick_Sort(a, 0, a.size() - 1);}
1.6、堆排序
堆排序是用数组模拟堆（完全二叉树），堆结构分为大根堆和小根堆。
大根堆：在完全二叉树中，任意一个子树的最大值都是其头部。
小根堆：在完全二叉树中，任意一个子树的最小值都是其头部。
对于堆结构中，第 i 个位置的父节点为：(i - 1) / 2 ，左孩子为2 * i + 1：，右孩子为：2 * i + 2。
//6、堆排序//时间复杂度为O(n*logn),额外空间复杂度为O(1)//从下往上插入void heapInsert(int a[], int index) {while (a[index] > a[(index - 1) / 2]) {swap(a[index], a[(index - 1) / 2]);index = (index - 1) / 2;}}//从上往下调整void heapify(int a[], int index, int size) {int left = 2 * index + 1;while (left < size) {//左右孩子比较取最大值int largest = left + 1 < size && a[left + 1] > a[left] ? left + 1 : left;//左右孩子比较后得到的最大值与父节点比较得出最大值largest = a[largest] > a[index] ? largest : index;//如果上述操作取得的最大值和index相同则表示原来的父节点就是最大值，不比交换，直接breakif (largest == index) {break;}//此时，largest!=indexswap(a[largest], a[index]);index = largest;left = 2 * index + 1;}}void HeapSort(int a[], int n) {if (n < 2) {return;}//构建大根堆for (int i = 0; i < n; i++) {heapInsert(a, i);}int size = n;swap(a[0], a[--size]);while (size > 0) {heapify(a, 0, size);swap(a[0], a[--size]);}}
1.7、基数排序
非比较排序，与被排序样本的数据状况很有关系。
//7、基数排序
//时间复杂度为O(n),额外空间复杂度为O(n)
int maxbits(int a[], int n);
int getDigit(int x, int d);
void radix_sort(int a[], int l, int r, int digit);
void RadixSort(int a[], int n) {
if (n < 2) return;
//求出需要排序的次数
int times = maxbits(a, n);
return radix_sort(a, 0, n - 1, times);
}
int maxbits(int a[], int n) {
int largest = INT_MIN;
for (int i = 0; i < n; i++) {
largest = max(largest, a[i]);
}
int res = 0;
while (largest != 0) {
res++;
largest /= 10;
}
return res;
}
int getDigit(int x, int d) {
return ((x / (static_cast<int>(pow(10, d - 1)))) % 10);
}
void radix_sort(int a[], int l, int r, int digit) {
int radix = 10;
int i = 0;
int j = 0;
vector<int> count(radix);
vector<int> bucket(r - l + 1);
for (int d = 1; d <= digit; d++) {
for (i = 0; i < radix; i++) {
count[i] = 0;
}
for (i = l; i <= r; i++) {
j = getDigit(a[i], d);
count[j]++;
}
for (i = 1; i < radix; i++) {
count[i] = count[i] + count[i - 1];
}
for (i = r; i >= l; i--) {
j = getDigit(a[i], d);
bucket[count[j] - 1] = a[i];
count[j]--;
}
for (i = l, j = 0; i <= r; i++, j++) {
a[i] = bucket[j];
}
}
}
1.8、计数排序
非比较排序，与被排序样本的数据状况很有关系。
//8、计数排序
//时间复杂度为O(n),额外空间复杂度为O(n)
void CountSort(int a[], int n) {
if (n < 2) return;
//取出这个数组中的最大值
int max = a[0];
for (int i = 0; i < n; i++) {
if (a[i] > max) {
max = a[i];
}
}
//此时max已经是数组a中的最大元素
//申请max+1大小的数组，初始化为0
vector<int> count(max + 1, 0);
for (int i = 0; i < n; i++) {
count[a[i]]++;
}
//用pos来辅助数据填充
int pos = 0;
for (int i = 0; i <= max; i++) {
while ((count[i]--) > 0) {
a[pos++] = i;
}
}
}
二、链表
2.1、单链表节点的插入、删除操作
struct Node {
Node(int data) :val(data) { };
int val;
Node* next;
};
//创建
Node* creat() {
Node* head = nullptr;
Node* p1 = new Node(1);
Node* p2 = new Node(2);
Node* p3 = new Node(3);
Node* p4 = new Node(4);
Node* p5 = new Node(5);
Node* p6 = new Node(6);
head = p1;
p1->next = p2;
p2->next = p3;
p3->next = p4;
p4->next = p5;
p5->next = p6;
p6->next = nullptr;
return head;
}
//打印
void printList(Node* head) {
Node* cur = head;
while (cur != nullptr) {
cout << cur->val;
if (cur->next != nullptr) {
cout << " -> ";
}
cur = cur->next;
}
}
//在（不带头节点）链表的第i个位置(前面)插入元素data
//节点从 1 开始计数
Node* insertList(Node* head, int pos, int data) {
Node* newNode = new Node(data);
//插入在第 1 个节点前需要单独考虑
if (pos == 1) {
//修改头指针
newNode->next = head;
head = newNode;
return head;
}
else {
int p = 1;
Node* cur = head;//通过cur指针的不断移动找到第 pos-1 个节点
while (cur != nullptr && p < pos - 1) {
cur = cur->next;
p++;
}
if (cur == nullptr || pos < 1) {
cout << "越界！" << endl;
}
else {
newNode->next = cur->next;
cur->next = newNode;
}
}
return head;
}
//删除（不带头节点）链表的第 i 个节点
Node* deleteList(Node* head, int pos) {
if (head == nullptr) {
cout << "链表为空！" << endl;
return nullptr;
}
//删除第一个节点，需要改变头指针
if (pos == 1) {
Node* temp = head;
head = temp->next;
delete temp;
return head;
}
else {
int p = 1;
Node* cur = head;//通过cur指针的不断移动找到第 pos-1 个节点
while (cur != nullptr && p < pos - 1) {
cur = cur->next;
p++;
}
if (cur->next == nullptr || pos < 1) {
cout << "越界！" << endl;
}
else {
Node* temp = cur->next;
cur->next = temp->next;
delete temp;
}
}
return head;
}
int main() {
Node* head = creat();
printList(head); //1 -> 2 -> 3 -> 4 -> 5 -> 6
cout << endl;
head = insertList(head, 1, 10);
printList(head); //10 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6
cout << endl;
head = deleteList(head, 3);
printList(head); //10 -> 1 -> 3 -> 4 -> 5 -> 6
return 0;
}
2.2、反转链表
//反转链表（三指针）
Node* reverseList(Node* head) {
Node* cur = head;//当前节点
Node* pre = nullptr;//前驱节点
while (cur != nullptr) {
Node* temp = cur->next;
cur->next = pre;
//移动cur和pre
pre = cur;
cur = temp;
}
return pre;
}
//反转链表（递归版本）（随便看看，忘记了！）
Node* reverseList(Node* head) {
//递归出口
if (head == nullptr || head->next == nullptr) {
return head;
}
//递归
Node *ret = reverseList(head->next);
//拼接
head->next->next = head;//当前递归的head->next的next指向head
head->next = nullptr; //而head指向null
return ret;
}
2.3、回文链表
//回文链表（辅助栈）
bool isPalindrome(Node *head) {
stack<int> help;
Node* cur = head;
//遍历链表，放入栈中
while (cur != nullptr) {
help.push(cur->val);
cur = cur->next;
}
cur = head;
//出栈，判断是否为回文
while (cur != nullptr) {
if (help.top() != cur->val) {
return false;
}
help.pop();
cur = cur->next;
}
return true;
}
//回文链表（快慢指针）
bool isPalindrome(Node *head) {
//如果链表为空或者链表节点数为1，则返回true
if (head == nullptr || head->next == nullptr) {
return true;
}
Node* fast = head;
Node* slow = head;
//找到中点
while (fast->next != nullptr && fast->next->next != nullptr) {
fast = fast->next->next;
slow = slow->next;
}
//找到右侧开始点
fast = slow->next;
slow->next = nullptr;
//反转右半部分
Node* cur = fast;
Node* pre = nullptr;
while (cur != nullptr) {
Node* temp = cur->next;
cur->next = pre;
pre = cur;
cur = temp;
}
//左边的头为head，反转后的头为pre
Node* p1 = head;
Node* p2 = pre;
while (p1 != nullptr && p2 != nullptr) {
if (p1->val != p2->val) {
return false;
}
p1 = p1->next;
p2 = p2->next;
}
return true;
}
2.3、
删除链表中重复的节点
多看几遍!!
【题目描述】
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5，处理后为 1->2->5。
Node* deleteDuplicates(Node* head) {
//设置一个虚拟头节点，以解决第一个、第二个节点就重复的情况
Node* dummyHead = new Node(-1);
dummyHead->next = head;
//三指针，pre为已经确定不重复的节点，left，right则为找重复区间
Node* pre = dummyHead;
//pre一直移动，只要它的下一个节点为空则结束循环
while (pre->next != nullptr) {
Node* left = pre->next;
Node* right = pre->next;
//只要right的下一个节点不为空，且right的下一个节点的值与left的值相同，就一直往下走
while (right->next != nullptr && left->val == right->next->val) {
right = right->next;
}
//说明不重复
if (left == right) {
pre = pre->next;
}
else {
pre->next = right->next;
//删除指针，并内存回收
while (left != right) {
Node* temp = left;
left = left->next;
delete temp;
}
delete left;
}
}
//回收设置虚拟头节点的内存
Node* res = dummyHead->next;
delete dummyHead;
return res;
}
2.4、判断链表是否有环
对上一个问题，请证明 slow 指针一次走1步，fast 指针一次走 2 步，为什么一定能追上而不会错过。那么 slow 走 1 步，fast 走 3 步呢？那么 slow 走 1 步，fast 走 4 步呢？
快指针一定比慢指针先入环，假设当慢指针入环了以后，快指针与慢指针之间的距离为 n ，然后两个指针每走一次，距离缩小 1（n，n - 1，n - 2，n - 3，… ，n - n）当他们之间距离为 0 的时候，一定就追上了。
并且，慢指针进环后，在慢指针走一圈之内，快指针就一定已经追上慢指针。（因为，慢指针快走一圈了，说明快指针已经块走两圈了，所以一定相遇）
slow 走 1 步，fast 走 3 步呢？那么 slow 走 1 步，fast 走 4 步呢？==不行！！==因为有可能会错过（环的大小为2，low 走 1 步，fast 走 3 步永远不会相遇）。
//判断一个单链表是否有环并找出入环点（快慢指针）
Node* getLoopNode(Node* head) {
//如果链表为空，或者链表只有一或两个节点，都必无环
if (head == nullptr || head->next == nullptr || head->next->next == nullptr) {
return nullptr;
}
Node* fast = head->next->next;
Node* slow = head->next;
//通过快慢指针判断是否有环，若快指针和慢指针有一个遇到 nullptr ，则必无环
//如果有环，快慢指针必会相遇
while (fast != slow) {
if (fast->next == nullptr || fast->next->next == nullptr) {
return nullptr;
}
slow = slow->next;
fast = fast->next->next;
}
//跳出while循环，则说明fast == slow，则必有环
//下面开始找入环点
//将快指针移动到开头，并设置为一次走一步，继续与慢指针相遇
fast = head;
while (fast != slow) {
fast = fast->next;
slow = slow->next;
}
return fast;
}
2.5、两个链表相交问题
//两个链表相交问题，分三种情况：两个都无环，一个有环一个无环和两个都有环
Node* noLoop(Node* head1, Node* head2);
Node* bothLoop(Node* head1, Node* head2, Node* loop1, Node* loop2);
Node* getIntersectNode(Node* head1, Node* head2) {
if (head1 == nullptr || head2 == nullptr) {
return nullptr;
}
//得到第一个链表的入环点
Node* loop1 = getLoopNode(head1);
//得到第二个链表的入环点
Node* loop2 = getLoopNode(head2);
//两个无环链表相交问题
if (loop1 == nullptr && loop2 == nullptr) {
return noLoop(head1, head2);
}
//两个有环链表相交问题
else if (loop1 != nullptr && loop2 != nullptr) {
return bothLoop(head1, head2, loop1, loop2);
}
//一个有环，一个无环必不可能相交
return nullptr;
}
Node* noLoop(Node* head1, Node* head2) {
if (head1 == nullptr || head2 == nullptr) {
return nullptr;
}
Node* cur1 = head1;
Node* cur2 = head2;
int n = 0;
while (cur1 != nullptr) {
n++;
cur1 = cur1->next;
}
while (cur2 != nullptr) {
n--;
cur2 = cur2->next;
}
//经过上述操作，如果n > 0，则说明链表1长，链表2短，反之则反
//此处的cur1和cur2为变量复用，因为长度可能不一致，所以让长的先走，知道两条链表长度一致
//cur1代表先走，cur2代表后走
cur1 = n > 0 ? head1 : head2;
cur2 = cur1 == head1 ? head2 : head1;
n = abs(n);
while (n--) {
cur1 = cur1->next;
}
while (cur1 != cur2) {
cur1 = cur1->next;
cur2 = cur2->next;
}
return cur1;
}
Node* bothLoop(Node* head1, Node* head2, Node* loop1, Node* loop2) {
//两个链表都有环，只有三种情况：1、独自成环，此时无交点。2、两个链表的入环点相同。3、两个链表的入环点不同。
//两个链表入环点相同的话，可以转换成无环链表相交解决
Node* cur1 = nullptr;
Node* cur2 = nullptr;
if (loop1 == loop2) {//情况2
cur1 = head1;
cur2 = head2;
int n = 0;
while (cur1 != loop1) {
n++;
cur1 = cur1->next;
}
while (cur2 != loop2) {
n--;
cur2 = cur2->next;
}
cur1 = n > 0 ? head1 : head2;
cur2 = cur1 == head1 ? head2 : head1;
n = abs(n);
while (n--) {
cur1 = cur1->next;
}
while (cur1 != cur2) {
cur1 = cur1->next;
cur2 = cur2->next;
}
return cur1;
}
else {
//从一个入环点开始，转一圈，如果遇到另一个入环点，则说明有交点，交点为两个入环点的任意一个
//如果没有遇到另一个入环点，则说明两个链表独自成环，无交点
cur1 = loop1->next;
while (cur1 != loop1) {
if (cur1 == loop2) {
return loop1;
}
cur1 = cur1->next;
}
return nullptr;
}
}
2.6、链表中倒数第K个节点
到时候自己在纸上画画就知道先走几步了，知道有单指针和双指针两种方法。
//倒数第k个节点（单个指针，需要遍历两次）
Node* getKthFromEnd(Node* head, int k) {
if (head == nullptr) {
return nullptr;
}
//1、需要遍历两次：第一次先遍历完链表，求出链表的长度n，第二次则走 n-k 步就会找到
int n = 0;
Node* cur = head;
while (cur != nullptr) {
n++;
cur = cur->next;
}
cur = head;
int step = n - k;
while (step--) {
cur = cur->next;
}
return cur;
}
//倒数第k个节点（双指针，仅需遍历一次）
Node* getKthFromEnd(Node* head, int k) {
if (head == nullptr) {
return nullptr;
}
//2、双指针，仅遍历一次：先让快指针移动 k 步，然后快慢指针一起移动，
// 当快指针到达 nullptr 时，此时慢指针就位于倒数第 k 个节点。
Node* fast = head;
Node* slow = head;
while (k--) {
fast = fast->next;
}
while (fast != nullptr) {
fast = fast->next;
slow = slow->next;
}
return slow;
}
2.7、链表的中间元素
Node* middleNode(Node* head) {
//快慢指针：快指针一次走两步，慢指针一次走一步，当快指针无法向后走两步的时停止
// 若链表为奇数，慢指针所指为中心元素
// 若链表为偶数，可以设置 结束条件 来使其指向中间两个节点的前、后任意一个
if (head == nullptr) {
return nullptr;
}
Node* fast = head;
Node* slow = head;
/*
while (fast->next->next != nullptr) {//此时偶数节点，中间节点为前一个
fast = fast->next->next;
slow = slow->next;
}
*/
while (fast != nullptr && fast->next != nullptr) {//此时偶数节点，中间节点为后一个
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
2.8、合并两个排序的链表
输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
【示例】
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
Node* Merge(Node* head1, Node* head2) {
if (head1 == nullptr) {
return head2;
}
else if (head2 == nullptr) {
return head1;
}
//设置虚拟头节点
Node* dummyHead = new Node(-1);
Node* tail = dummyHead;
//整个思路就是取出小的尾插在tail后
//因为这里是整合两个链表成新的链表，则原来的会消失
//所以这里直接用head1、head2进行遍历
while (head1 != nullptr && head2 != nullptr) {
if (head1->val <= head2->val) {
tail->next = head1;
head1 = head1->next;
}
else {
tail->next = head2;
head2 = head2->next;
}
//因为tail的含义为新链表的尾节点，不要忘记将其后移
tail = tail->next;
}
//上述循环结束，肯定还有一个链表还有剩余部分，将其串进新链表
tail->next = head1 != nullptr ? head1 : head2;
//!!!!!!!!!!!!!!!
//回收，防止内存泄露
//!!!!!!!!!!!!!!!
Node* res = dummyHead->next;
delete dummyHead;
return res;
}
2.9、 复杂链表的复制
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
【思路】
1、拷贝链表的每一个节点，拷贝的节点先连接到原链表被拷贝节点的后面
2、处理拷贝节点的random指针：拷贝节点的random指针指向被拷贝节点随机指针的下一个位置
3、拆解链表，把拷贝的链表从原链表中拆解出来，再连接出拷贝链表
Node* copyRandomList(Node* head) {
//1、拷贝链表的每一个节点，拷贝的节点先连接到原链表被拷贝节点的后面
Node* cur = head;
while (cur != nullptr) {
//拷贝一个和cur相同的节点
Node* copy = new Node(cur->val);
//链接到cur的后面
Node* next = cur->next;
cur->next = copy;
copy->next = next;
//cur链接完毕，继续往后走
cur = next;
}
//2、处理拷贝节点的random指针：拷贝节点的random指针指向被拷贝节点随机指针的下一个位置
cur = head;
while (cur != nullptr) {
Node* copy = cur->next;
if (cur->random == nullptr) {
copy->random = nullptr;
}
else {
//关键点！拷贝节点的random指针指向被拷贝节点随机指针的下一个位置
copy->random = cur->random->next;
}
//往后移动
cur = cur->next->next;
if (copy->next != nullptr) {
copy = copy->next->next;
}
}
//3、拆解链表，把拷贝的链表从原链表中拆解出来，再连接出拷贝链表
cur = head;
//设置虚拟头节点
Node* dummyHead = new Node(-1);
Node* tail = dummyHead;
while (cur != nullptr) {
Node* copy = cur->next;
//定义一个next，防止找不到下一个节点
Node* next = copy->next;
cur->next = next;
//尾插
tail->next = copy;
tail = copy;
//往后移动
cur = next;
}
Node* res = dummyHead->next;
delete dummyHead;
return res;
}
2.10、 约瑟夫环
【圆圈中最后剩下的数字】
0,1, … ,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。
例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
【示例 1】
输入: n = 5, m = 3 输出: 3
【示例 2】
输入: n = 10, m = 17 输出: 2
//循环链表
int lastRemaining(int n, int m) {
Node* head = new Node(0);
Node* cur = head;
for (int i = 1; i < n; i++) {
cur->next = new Node(i);
cur = cur->next;
if (i == n - 1) {
cur->next = head;
}
}
//cur 当前节点
//pre 当前节点的前一个节点
cur = head;
Node* pre = nullptr;
while (cur->next != cur) {
for (int i = 1; i < m; i++) {
pre = cur;
cur = cur->next;
}
//删除第 m 个
pre->next = cur->next;
//内存回收
Node* temp = cur;
cur = cur->next;
delete temp;
}
return cur->val;
}
三、字符串
3.1、二进制字符串相加问题
string addBinary(string a, string b)
{
string res;
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
//找出a和b哪个比较长
int n = max(a.size(), b.size());
int carry = 0;
for (size_t i = 0; i < n; i++){
carry += i < a.size() ? (a[i] == '1') : 0;
carry += i < b.size() ? (b[i] == '1') : 0;
res.push_back((carry % 2) ? '1' : '0');
carry /= 2;
}
//计算到最后，如果最高位不为0，则加上
if (carry){
res.push_back('1');
}
reverse(res.begin(), res.end());
return res;
}
3.2、十进制字符串相加问题
string addLongInteger(string a, string b)
{
string res;
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
size_t n = max(a.size(), b.size());
int carry = 0;
for (size_t i = 0; i < n; i++){
int ai = i < a.size() ? a[i] - '0' : 0;
int bi = i < b.size() ? b[i] - '0' : 0;
int val = (ai + bi + carry) % 10;
carry = (ai + bi + carry) / 10;
res.push_back(val + '0');
}
if(carry){
res.push_back('1');
}
reverse(res.begin(), res.end());
return res;
}
3.3、最长回文串（leetcode409）
给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。在构造过程中，请注意区分大小写。比如 “Aa” 不能当做一个回文字符串。
注意:假设字符串的长度不会超过 1010。
示例 1:
输入:”abccccdd”
输出:7
解释:我们可以构造的最长的回文串是”dccaccd”, 它的长度是 7。
class Solution
{
public:
int longestPalindrome(string s)
{
unordered_map<char, int> help;
for (auto elem : s){
help[elem]++;
}
int res = 0;
for (auto elem : help){
//判断奇偶
if (elem.second % 2 == 1){
elem.second -= 1;
}
res += elem.second;
}
res = res == s.size() ? res : res + 1;
return res;
}
};
3.4、单词规律（leetcode290）
给定一种规律 pattern 和一个字符串 str ，判断 str 是否遵循相同的规律。
这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律。
示例1:
输入: pattern = “abba”, str = “dog cat cat dog”
输出: true
示例 2:
输入:pattern = “abba”, str = “dog cat cat fish”
输出: false
示例 3:
输入: pattern = “aaaa”, str = “dog cat cat dog”
输出: false
示例 4:
输入: pattern = “abba”, str = “dog dog dog dog”
输出: false
class Solution
{
public:
bool wordPattern(string pattern, string str)
{
//先把str分割
stringstream istr(str);
vector<string> v;
string temp;
while (getline(istr, temp, ' ')){
v.push_back(temp);
}
if(pattern.size() != v.size()){
return false;
}
//需要两个哈希表来分清楚 abba 和 dog dog dog dog
unordered_map<char, string> map;
unordered_map<string, char> rmap;
//find():找key指向的value的迭代器，若找不到，则返回end()
for (int i = 0; i < pattern.size(); i++){
char key = pattern[i];
//判断key是否在哈希表中
//如果两个哈希表已存在key，但是存在的key对应的value不等于v[i]
if (map.count(key) == 1 && map[key] != v[i] || rmap.count(v[i]) == 1 && rmap[v[i]] != key){
return false;
}
map[key] = v[i];
rmap[v[i]] = key;
}
return true;
}
};
3.5、字符串分割函数
//C++ 字符串分割
vector<string> split(const string &s, char delim)
{
stringstream str(s);
vector<string> res;
string temp;
while (getline(str, temp, delim)) {
res.push_back(temp);
}
return res;
}
//示例
string s = "aa bb cc dd";
vector<string> v;
v = split(s, ' ');// "aa" "bb" "cc" "dd"
3.6、字母异位词分组（leetcode49）
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例:
输入: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出:
[
[“ate”,”eat”,”tea”],
[“nat”,”tan”],
[“bat”]
]
说明：
所有输入均为小写字母。
不考虑答案输出的顺序
class Solution
{
public:
vector<vector<string>> groupAnagrams(vector<string>& strs)
{
vector<vector<string>> res;
unordered_map<string, vector<string>> mp;
for (auto elem : strs){
string key = elem;
sort(key.begin(), key.end());
mp[key].push_back(elem);
}
for (auto elem : mp){
res.push_back(elem.second);
}
return res;
}
};
3.7、无重复字符的最长子串（leetcode3）
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:
输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:
输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。
class Solution
{
public:
int lengthOfLongestSubstring(string s)
{
if (s.length() == 0)
return 0;
unordered_map<char, int> hashTable;
int Max = 0;//最大长度
int cur = 0;//当前长度
int start = 0;
for (int i = 0; i < s.length(); i++){
char key = s[i];
if (hashTable.find(key) == hashTable.end()){//表示当前字符不重复
cur++;
hashTable[key] = i;
}
else{//表示当前字符重复
Max = cur > Max ? cur : Max;
//出现重复的只可能已经不在当前滑动窗口
start = max(hashTable[key], start);
cur = i - start;
hashTable[key] = i;
}
}
Max = cur > Max ? cur : Max;
return Max;
}
};
3.8、重复的DNA序列（leetcode187）
所有 DNA 都由一系列缩写为 A，C，G 和 T 的核苷酸组成，例如：“ACGAATTCCG”。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。
编写一个函数来查找目标子串，目标子串的长度为 10，且在 DNA 字符串 s 中出现次数超过一次。
示例：
输入：s = “AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT”
输出：[“AAAAACCCCC”, “CCCCCAAAAA”]
class Solution
{
public:
vector<string> findRepeatedDnaSequences(string s)
{
//找出所有长度为10的子串，再找出所以出现次数超过1的
vector<string> res;
unordered_map<string, int> mp;
for (int i = 0; i < s.size(); i++){
string key;
key = s.substr(i, 10);
mp[key]++;
}
for (auto elem : mp){
if (elem.second > 1){
res.push_back(elem.first);
}
}
return res;
}
};
四、队列和栈
4.1、用固定大小数组实现栈
class ArrayStack {
public:
//构造函数
ArrayStack(int MaxSize) :size(MaxSize),index(0) {
if (MaxSize < 0) {
cout << "The Maxsize is less than Zero!" << endl;
}
arr = new int[size];
}
//析构函数
~ArrayStack() {
delete[] arr;
}
//push()
void push(int data) {
if (index == size - 1) {
cout << "The stack is full!" << endl;
}
arr[index++] = data;
}
//pop()
void pop() {
if (index == 0) {
cout << "No element in the stack!" << endl;
}
arr[--index];
}
//top()
int top() {
if (index == 0) {
cout << "No element in the stack!" << endl;
}
return arr[index - 1];
}
private:
int size;
int index;
int* arr;
};
4.2、用固定大小数组实现队列
class ArrayQueue {
public:
//构造函数
ArrayQueue(int MaxSize) :size(MaxSize), num(0), last(0), first(0) {
if (MaxSize < 0) {
cout << "The Maxsize is less than Zero!" << endl;
}
arr = new int[size];
}
//析构函数
~ArrayQueue() {
delete[] arr;
}
//push()
void push(int data) {
if (num == size) {
cout << "The stack is full!" << endl;
}
num++;
arr[last] = data;
//last的运动轨迹是循环的
last = last == size - 1 ? 0 : last + 1;
}
//top()
int top() {
if (num == 0) {
cout << "No element in the queue!" << endl;
}
return arr[first];
}
//pop()
void pop() {
if (num == 0) {
cout << "The queue is empty!" << endl;
}
num--;
//first的运动轨迹是循环的
first = first == size - 1 ? 0 : first + 1;
}
private:
int size;
int last;//尾
int first;//头
int num;//记录当前的大小
int *arr;
};
4.3、队列实现栈
class queue_to_stack
{
public:
void push(int val)
{
//先搬空data，搬到help暂存
while (!data.empty()){
help.push(data.front());
data.pop();
}
//data空了，新插入的元素在最开始
data.push(val);
//把help中元素全部搬回data
while (!help.empty()){
data.push(help.front());
help.pop();
}
}
int pop()
{
int temp = data.front();
data.pop();
return temp;
}
int top()
{
return data.front();
}
bool empty()
{
return data.empty();
}
private:
queue<int> data;
queue<int> help;
};
4.4、栈实现队列
class stack_to_queue {
public:
//push()
void push(int val) {
data.push(val);
}
//top()
int top() {
//如果help为空，才需要把data倒入help。否则不可以
if (help.empty()) {
while (!data.empty()) {
help.push(data.top());
data.pop();
}
}
return help.top();
}
//pop()
void pop() {
//如果help为空，才需要把data倒入help。否则不可以
if (help.empty()) {
while (!data.empty()) {
help.push(data.top());
data.pop();
}
}
help.pop();
}
private:
stack<int> data;
stack<int> help;
};
4.5、包含min函数的栈
class MinStack{
public:
//push
void push(int val){
//需要加上 min.empty() 的条件，不然一开始插入不了元素
if (min.empty() || val <= this->getMin()){
min.push(val);
}
data.push(val);
}
//pop
void pop(){
if (data.top() == this->getMin()) {
min.pop();
}
data.pop();
}
//getMin
int getMin(){
return min.top();
}
private:
stack<int> data;
stack<int> min;
}
4.6、栈的压入、弹出序列
bool IsPopOrder(vector<int> pushV,vector<int> popV){
stack<int> help;
int pos = 0;//记录popV的位置
for (auto elem : pushV){
help.push(elem);
while (!help.empty() || elem == popV[pos]){
help.pop();
pos++;
}
}
return help.empty();
}
4.7、队列的最大值
4.8、滑动窗口的最大值
五、二分查找
5.1、有效的完全平方数
给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 True，否则返回 False。
class Solution {
public:
bool isPerfectSquare(int num) {
if(num < 1) return false;
long long left = 1;
long long right = num;
long long mid = left + ((right - left) > 2);
while(left <= right){
if(mid * mid < num){
left = mid + 1;
mid = left + ((right - left) > 2);
}
else if(mid * mid > num){
right = mid-1;
mid = left + ((right - left) > 2);
}
else{
return true;
}
}
return false;
}
};
六、矩阵
6.1、顺时针打印矩阵c
class Solution
{
public:
//打印一条边
void printEdge(const vector<vector<int>> &matrix, vector<int> &res,
int row1, int col1, int row2, int col2)
{
if (row1 == row2)
{ //一条横条
for (int i = col1; i <= col2; i++)
{
res.push_back(matrix[row1][i]);
}
}
else if (col1 == col2)
{ //一条竖条
for (int i = row1; i <= row2; i++)
{
res.push_back(matrix[i][col1]);
}
}
else
{
int cur_row = row1;
int cur_col = col1;
while (cur_col != col2)
{
res.push_back(matrix[row1][cur_col++]);
}
while (cur_row != row2)
{
res.push_back(matrix[cur_row++][col2]);
}
while (cur_col != col1)
{
res.push_back(matrix[row2][cur_col--]);
}
while (cur_row != row1)
{
res.push_back(matrix[cur_row--][col1]);
}
}
}
vector<int> spiralOrder(vector<vector<int>> &matrix)
{
if (matrix.size() == 0 || matrix[0].size() == 0)
return {};
int row1 = 0;
int col1 = 0;
int row2 = matrix.size() - 1;
int col2 = matrix[0].size() - 1;
vector<int> res;
while (row1 <= row2 && col1 <= col2)
{
printEdge(matrix, res, row1++, col1++, row2--, col2--);
}
return res;
}
};
6.2、旋转正方形矩阵
给定一个整型正方形矩阵matrix，请把该矩阵调整成顺时针旋转90度的样子。
6.3、“之”字形打印矩阵
#include <iostream>
#include <vector>
using namespace std;
//打印一条斜边
void PrintLevel(const vector<vector<int>> &arr, int a_row, int a_col, int b_row, int b_col, bool flag){
//flag为真，表示从右上往左下打印
if (flag){
while (a_row != b_row + 1){
cout << arr[a_row++][a_col--] << " ";
}
}
//flag为假，表示从左下往右上打印
else{
while (b_row != a_row - 1){
cout << arr[b_row--][b_col++] << " ";
}
}
}
//之字形打印矩阵
void ZigZagPrintMatrix(vector<vector<int>> &arr){
int a_row = 0;
int a_col = 0;
int b_row = 0;
int b_col = 0;
int end_row = arr.size() - 1;
int end_col = arr[0].size() - 1;
bool flag = false;
while (a_row != end_row + 1){
PrintLevel(arr, a_row, a_col, b_row, b_col, flag);
a_row = a_col == end_col ? a_row + 1 : a_row;
a_col = a_col == end_col ? a_col : a_col + 1;
b_row = b_row == end_row ? b_row : b_row + 1;
b_col = b_row == end_row ? b_col + 1 : b_col;
flag = !flag;
}
}
int main()
{
vector<vector<int>> b = {
{0 , 1 , 2 , 3 , 4 , 5 , 6 }, // 0
{10 , 12 , 13 , 15 , 16 , 17 , 18 }, // 1
{23 , 24 , 25 , 26 , 27 , 28 , 29 }, // 2
{44 , 45 , 46 , 47 , 48 , 49 , 50 }, // 3
{65 , 66 , 67 , 68 , 69 , 70 , 71 }, // 4
{96 , 97 , 98 , 99 , 100, 111, 122}, // 5
{166, 176, 186, 187, 190, 195, 200}, // 6
{233, 243, 321, 341, 356, 370, 380} // 7
};
ZigZagPrintMatrix(b);
return 0;
}
七、二叉树
7.1、二叉树的前序遍历
//递归（0 offer写法）
void preOrder(TreeNode *head) {
if (head == nullptr) {
return;
}
cout << head->val << " ";
preOrder(head->left);
preOrder(head->right);
}
//非递归
///使用辅助栈
void preOrder(TreeNode *head) {
if (head != nullptr) {
stack<TreeNode*> help;
help.push(head);
while (!help.empty()) {
//弹出栈顶元素
TreeNode* temp = help.top();
//弹出就打印
cout << temp->val << " ";
help.pop();
//因为先序遍历是，根->左->右
//所以先把右节点先压入，则栈的性质会让它后弹出
if (temp->right != nullptr) {
help.push(temp->right);
}
if (temp->left != nullptr) {
help.push(temp->left);
}
}
}
}
7.2、 二叉树的中序遍历
//递归（0 offer写法）
void inOrder(TreeNode *head) {
if (head == nullptr) {
return;
}
preOrder(head->left);
cout << head->val << " ";
preOrder(head->right);
}
//非递归
void inOrder(TreeNode* head) {
if (head != nullptr) {
stack<TreeNode*> help;
TreeNode* cur = head;
while (!help.empty() || cur != nullptr) {
//只要当前节点不为空，就把左孩子压入栈中
if (cur != nullptr) {
help.push(cur);
cur = cur->left;
}
//当前节点到达左边界，已经为空，但是此时栈不为空，依然能进入while循环
//然后不满足cur != nullptr 条件，进入 else 部分代码
else {
//cur已经到达左边界，然后从栈中拿一个，打印。
//cur来到栈顶元素位置，往右跑
cur = help.top();
cout << cur->val << " ";
help.pop();
cur = cur->right;
}
}
}
}
7.3、二叉树的后序遍历
//递归（0 offer写法）
void posOrder(TreeNode *head) {
if (head == nullptr) {
return;
}
preOrder(head->left);
preOrder(head->right);
cout << head->val << " ";
}
//非递归
//后续遍历是左->右->中
//利用前序遍历相似方法变成：中->右->左
//然后在out栈中弹出，变成：左->右->中
void posOrder(TreeNode* head) {
if (head == nullptr) {
stack<TreeNode*> help;
stack<TreeNode*> out;
help.push(head);
while (!help.empty()) {
TreeNode* temp = help.top();
out.push(temp);
help.pop();
if (temp->left != nullptr) {
help.push(temp->left);
}
if (temp->right != nullptr) {
help.push(temp->right);
}
}
while (!out.empty()) {
cout << out.top()->val << " ";
out.pop();
}
}
}
7.4、二叉树的层序遍历
//利用队列完成
void levelOrder(TreeNode* head) {
if (head != nullptr) {
queue<TreeNode*> help;
help.push(head);
while (!help.empty()) {
TreeNode* temp = help.front();
cout << temp->val << " ";
help.pop();
if (temp->left != nullptr) {
help.push(temp->left);
}
if (temp->right != nullptr) {
help.push(temp->right);
}
}
}
}
7.5、二叉树的后继节点
7.6、重建二叉树
7.7、树的子结构
7.8、二叉树的镜像
7.9、对称的二叉树
class Solution
{
public:
bool isSymmetric(TreeNode *root)
{
if (root == nullptr)
return true;
return dfs(root->left, root->right);
}
bool dfs(TreeNode *left, TreeNode *right) {
if (left == nullptr && right == nullptr)
return true;
if (left == nullptr || right == nullptr)
return false;
if (left->val != right->val)
return false;
return dfs(left->left, right->right) && dfs(left->right, right->left);
}
};
7.10、二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
class Solution{
public:
int minDepth(TreeNode *root)
{
if(root==nullptr)
return 0;
queue<TreeNode *> help;
int Min = 1;
help.push(root);
while(!help.empty())
{
int sz = help.size();
for (int i = 0; i < sz; i++)
{
auto temp = help.front();
help.pop();
if (temp->left == nullptr && temp->right == nullptr)
return Min;
if (temp->left != nullptr)
help.push(temp->left);
if (temp->right != nullptr)
help.push(temp->right);
}
Min++;
}
return Min;
}
};
7.11、机器人的运动范围
地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
示例 1：
输入：m = 2, n = 3, k = 1
输出：3
示例 2：
输入：m = 3, n = 1, k = 0
输出：1
//===================
//DFS
//===================
class Solution
{
public:
int movingCount(int m, int n, int k)
{
vector<vector<bool>> visited(m, vector<bool>(n, false));
return dfs(0, 0, m, n, k, visited);
}
int dfs(int x, int y, int m, int n, int k, vector<vector<bool>> &visited){
if (x < 0 || x >= m || y < 0 || y >= n || get(x) + get(y) > k || visited[x][y]){
return 0;
}
visited[x][y] = true;
int res = 1 + dfs(x + 1, y, m, n, k, visited) + dfs(x - 1, y, m, n, k, visited)
+ dfs(x, y + 1, m, n, k, visited) + dfs(x, y - 1, m, n, k, visited);
return res;
}
int get(int x){
int sum = 0;
while(x){
sum += x % 10;
x /= 10;
}
return sum;
}
};
//===================
//BFS
//===================
class Solution
{
public:
int movingCount(int m, int n, int k)
{
queue<pair<int, int>> q;
vector<vector<bool>> visited(m, vector<bool>(n, false));
q.push(make_pair(0, 0));
int res = 0;
while (!q.empty()){
pair<int,int> temp = q.front();
q.pop();
int x = temp.first;
int y = temp.second;
if (x >= m || y >= n || get(x) + get(y) > k || visited[x][y])
continue;
visited[x][y] = true;
res++;
q.push(make_pair(x + 1, y));
q.push(make_pair(x, y + 1));
}
return res;
}
int get(int x){
int sum = 0;
while (x != 0){
sum += x % 10;
x /= 10;
}
return sum;
}
};
八、动态规划
8.1、斐波那契数列
8.2、跳台阶
8.3、矩阵中最小路径和（LeetCode 64）
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
8.4、剪绳子（整数拆分）
8.5、不同路径（LeetCode 62）
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。问总共有多少条不同的路径？
8.6、打家劫舍（LeetCode 198）
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
8.7、完全平方数（LeetCode 279）
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
8.8、背包问题
8.9、股票的最大值
九、设计模式
#include <iostream>
using namespace std;
//单例设计模式
class Singleton {
private:
Singleton() {}
static Singleton* instance;
public:
static Singleton* getInstance() {
if (instance == nullptr) {
static CGarhuishou huishou;
instance = new Singleton();
}
return instance;
}
//用于回收内存
class CGarhuishou {
public:
~CGarhuishou() {
delete Singleton::instance;
Singleton::instance = nullptr;
}
};
//测试
void test() {
cout << "测试" << endl;
}
};
Singleton* Singleton::instance = nullptr;
int main() {
Singleton* p1 = Singleton::getInstance();//创建一个对象
//Singleton* p2 = Singleton::getInstance();
p1->test();
//p2->test();
return 0;
}
- 懒汉模式：不到万不得已就不会去实例化类，也就是说在第一次用到类实例的时候才会去实例化，懒汉模式本身是线程不安全的。
- 饿汉模式：在单例类定义的时候就进行实例化，饿汉模式就是线程安全的。
如何选择懒汉和饿汉模式？
- 懒汉：在访问量较小时，采用懒汉实现。这是以时间换空间。
- 饿汉：由于要进行线程同步，所以在访问量比较大，或者可能访问的线程比较多时，采用饿汉实现，可以实现更好的性能。这是以空间换时间。
若有收获，就点个赞吧
0 人点赞
