数据结构和算法八股与手撕

数据结构和算法八股文

第一章 数据结构

1.1 常见结构

见http://t.csdnimg.cn/gmc3U

1.2 二叉树重点

1.2.1 各种树的定义

  • 满二叉树：只有度为0的结点和度为2的结点，并且度为0的结点在同一层上

  • 完全二叉树：除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。（优先级队列即堆是一棵完全二叉树）

    • 结点数为n的完全二叉树的叶子结点数量为n/2（n为偶数），(n+1)/2（n为奇数）
    • 通常使用数组存储完全二叉树，下标为i的结点的父结点下标为(i-1)/2，左孩子结点下标为2i+1，右孩子结点下标为2i+2

  • 二叉搜索树：有序树，若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉搜索树

  • 平衡二叉树：又称为AVL树，是一种特殊的二叉搜索树，它不仅满足了二叉搜索树的性质，而且左子树和右子树的高度之差的绝对值小于等于1；左子树和右子树也是平衡二叉树。其在插入和删除操作后，会通过自平衡的调整保持树的高度平衡，从而提高搜索、插入和删除等操作的效率。

    • C++中map、set、multiset、multimap底层都是红黑树（红黑树是平衡二叉树的一种特殊实现），增删查的时间复杂度为O(log n)。而unordered_set和unordered_map底层是哈希表，增删查的时间复杂度为O(1)；

  • 单支树：非叶子结点只有一个孩子节点，且方向一致

  • 哈夫曼树：压缩和解压缩用到的特殊二叉树是哈夫曼树，对应的方法是哈夫曼编码。（参考：https://blog.csdn.net/NOSaac/article/details/125901955）

    • 结点路径长度：两个节点中间隔线条数
    • 树的路径长度：除根结点外，其他结点到根结点路径长度之和
    • 结点带权路径长度：从该结点到根结点路径长度与结点上权的乘积
    • 树带权路径长度：树中所有叶子结点的带权路径长度之和
    • 构造方法：首先从权值列表中选择最小的两个结点，将其设置为左右（较小为左，较大为右）孩子结点，并设置其根节点的权值为两个权值之和，并将该结点加入到权值列表，删除权值列表中这两个最小结点。重复上述步骤，直至权值列表只有一个值后完成创建。
    • 哈夫曼树的带权路径长度最短。哈夫曼树没有度为1的结点，若有n个叶子结点则有n-1个非叶子结点，所有结点数目为2n-1。

1.2.2 使用ACM方式构建树

输入一行数据，第一个数字为结点总数，后面按层序遍历字符数组的方式输入结点，如果结点为空则输入#

#include <iostream>
#include <vector>
using namespace std;
struct TreeNode {char val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};int main() {int n;cin >> n;char c;vector<TreeNode*> vec(n);for (int i = 0; i < n; i++) {cin >> c;vec[i] = new TreeNode(c);}for (int i = 0; i < n; i++) {if (vec[i]->val == '#') continue;int leftIndex = 2 * i + 1, rightIndex = 2 * i + 2;if (leftIndex < n && vec[i]->val != '#') vec[i]->left = vec[leftIndex];else vec[i]->left = nullptr;if (rightIndex < n && vec[i]->val != '#') vec[i]->right = vec[rightIndex];else vec[i]->right = nullptr;}TreeNode* root = vec[0];  // root即为结果return 0;
}

1.2.3 二叉树遍历

  • 深度优先遍历：先往深走，遇到叶子结点再往回走。有前序遍历、中序遍历、后序遍历的递归法和迭代法实现（6个，其中中序遍历的迭代方法需要特殊记忆），中间结点的顺序即为遍历方式（前序遍历：中左右，中序遍历：左中右，后续遍历：左右中）
    在这里插入图片描述

  • 广度优先遍历：有层序遍历，通过迭代法实现（1个，需要特殊记忆）

1.2.3.1 前序遍历递归法实现

144. 二叉树的前序遍历

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector res;void traversal(TreeNode* root) {if (root == nullptr) return ;res.push_back(root->val);traversal(root->left);traversal(root->right);}vector preorderTraversal(TreeNode* root) {traversal(root);return res;}
};
1.2.3.2 前序遍历迭代法实现

144. 二叉树的前序遍历

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector preorderTraversal(TreeNode* root) {vector res;stack st;if (root != nullptr) st.push(root);while (!st.empty()) {TreeNode* node = st.top();st.pop();res.push_back(node->val);if (node->right != nullptr) st.push(node->right);if (node->left != nullptr) st.push(node->left);}return res;}
};
1.2.3.3 中序遍历递归法实现

94. 二叉树的中序遍历

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector res;void traversal(TreeNode* root) {if (root == nullptr) return ;traversal(root->left);res.push_back(root->val);traversal(root->right);}vector inorderTraversal(TreeNode* root) {traversal(root);return res;}
};
1.2.3.4 中序遍历迭代法实现（着重记忆）

94. 二叉树的中序遍历

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector inorderTraversal(TreeNode* root) {vector res;stack st;TreeNode* node = root;while (node != nullptr || !st.empty()) {if (node != nullptr) {st.push(node);node = node->left;} else {node = st.top();st.pop();res.push_back(node->val);node = node->right;}}return res;}
};
1.2.3.5 后序遍历递归法实现

145. 二叉树的后序遍历

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector res;void traversal(TreeNode* root) {if (root == nullptr) return ;traversal(root->left);traversal(root->right);res.push_back(root->val);}vector postorderTraversal(TreeNode* root) {traversal(root);return res;}
};
1.2.3.6 后序遍历迭代法实现

145. 二叉树的后序遍历

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector postorderTraversal(TreeNode* root) {vector res;stack st;if (root != nullptr) st.push(root);while (!st.empty()) {TreeNode* node = st.top();st.pop();res.push_back(node->val);if (node->left != nullptr) st.push(node->left);if (node->right != nullptr) st.push(node->right);}reverse(res.begin(), res.end());return res;}
};
1.2.3.7 层序遍历迭代法实现（着重记忆）

102. 二叉树的层序遍历

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector> levelOrder(TreeNode* root) {vector> res;queue que;if (root != nullptr) que.push(root);while (!que.empty()) {vector vec;int size = que.size();for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();vec.push_back(node->val);if (node->left != nullptr) que.push(node->left);if (node->right != nullptr) que.push(node->right);}res.push_back(vec);}return res;}
};

第二章 算法

2.1 时间复杂度

时间复杂度就是算法的时间度量，记为T(n)=O(f(n))，表示随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称为算法的渐进时间复杂度，简称时间复杂度。步骤：首先常数1取代加法常数，其次只保留最高阶项并把最高阶项的系数设为1。

2.2 排序算法（重点）

  1. 冒泡排序：平均时间复杂度O(n2)、空间复杂度O(1)、稳定排序（相等元素位置不变）
  2. 选择排序：平均时间复杂度O(n2)、空间复杂度O(1)、非稳定排序
  3. 插入排序：平均时间复杂度O(n2)、空间复杂度O(1)、稳定排序
  4. 快速排序：平均时间复杂度O(nlog2n)、空间复杂度O(1)、非稳定排序
  5. 希尔排序：插入排序的优化版本。平均时间复杂度通常被认为是介于O(n)和O(n2)之间与增量序列有关，Hibbard 增量序列和 Knuth 增量序列等都可以使希尔排序达到 O(nlog2n) 的平均时间复杂度、空间复杂度O(1)、非稳定排序
  6. 归并排序：分治法，平均时间复杂度O(nlog2n)、空间复杂度O(n)、稳定排序
  7. 堆排序：时间复杂度O(nlog2n)、空间复杂度O(1)、非稳定排序
    在这里插入图片描述

2.2.1 冒泡排序

原理：重复地遍历待排序数组，每次比较相邻的两个元素，如果它们的顺序错误，就交换它们的位置，直到整个数组排序完成。

void bubbleSort(vector<int>& nums) {int n = nums.size();for (int i = 0; i < n; i++) {for (int j = 0; j < n - i - 1; j++) {if (nums[j] > nums[j + 1]) swap(nums[j], nums[j + 1]);}}
}

2.2.2 选择排序

原理：将待排序的数组分成已排序和未排序两部分，每次从未排序部分选择最小的元素，然后与未排序部分的第一个元素交换，并将其放到已排序部分的末尾。重复这个过程直到整个数组排序完成。

void selectionSort(vector<int>& nums) {int n = nums.size();for (int i = 0; i < n; i++) {int minIndex = i;for (int j = i + 1; j < n; j++) {if (nums[j] < nums[minIndex]) minIndex = j;}swap(nums[i], nums[minIndex]);}
}

2.2.3 插入排序

原理：将待排序的数组分成已排序和未排序两部分，每次从未排序部分取出第一个元素，从后往前在已排序部分找到合适的位置插入该元素，直到所有元素都完成插入。

void insertSort(vector<int>& nums) {int n = nums.size();for (int i = 1; i < n; i++) {if (nums[i] < nums[i - 1]) {int temp = nums[i];int j = i - 1;while (j >= 0 && nums[j] > temp) {nums[j + 1] = nums[j];j--;}nums[j + 1] = temp;}}
}

2.3.4 快速排序

图解参考：https://blog.csdn.net/king13059595870/article/details/103421774

原理：分治法+双指针：选择第一个元素为基准，然后将数组分割为两个子数组，左边的子数组中的元素都比基准小，右边的子数组中的元素都比基准大。然后对两个子数组进行递归排序，直到整个数组完成排序。

void fastSort(vector<int>& nums, int low, int high) {if (low >= high) return;int first = low;int last = high;int key = nums[first];  // 选择首元素作为中轴元素（即基准）while (first < last) {// 从右往左，将比第一个小的移到前面while (first < last && nums[last] > key) last--;if (first < last) nums[first++] = nums[last];// 从左往右，将比第一个大的移到后面while (first < last && nums[first] < key) first++;if (first < last) nums[last--] = nums[first];}nums[first] = key;fastSort(nums, low, first - 1);fastSort(nums, first + 1, high);
}

2.3.5 希尔排序

代码参考：https://blog.csdn.net/weixin_44915226/article/details/119512633

原理：希尔排序是插入排序的一种，通过逐步缩小间隔来分组进行插入排序，从而提高排序的效率。

void shellSort(vector<int>& nums) {int n = nums.size();for (int gap = n / 2; gap > 0; gap /= 2) {for (int i = gap; i < n; i++) {if (nums[i] < nums[i - gap]) {int temp = nums[i];int j = i - gap;while (j >= 0 && nums[j] > temp) {nums[j + gap] = nums[j];j -= gap;}nums[j + gap] = temp;}}}
}

2.3.6 归并排序

图解参考：https://blog.csdn.net/qq_38307826/article/details/107445750

原理：分治法

  1. 先分解：将待排序的数组不断地二分，直到每个子数组都只包含一个元素，即认为它们已经排好序。
  2. 再合并：将两个有序的子数组合并为一个有序数组，在合并的过程中保持元素有序性。

归并排序使用了递归的方式来分解和合并，最终得到一个完全有序的数组。

void mergeSort(vector<int>& nums, vector<int>& numsTemp, int low, int high) {if (low >= high) return ;int mid = low + (high - low) / 2;int first1 = low, last1 = mid;int first2 = mid + 1, last2 = high;mergeSort(nums, numsTemp, start1, end1);mergeSort(nums, numsTemp, start2, end2);int index = low;while (first1 <= last1 && first2 <= last2) numsTemp[index++] = nums[first1] < nums[first2] ? nums[first1++] : nums[first2++];while (first1 <= last1) numsTemp[index++] = nums[first1++];while (first1 <= last1) numsTemp[index++] = nums[first2++];for (index = low; index <= high; index++) nums[index] = numsTemp[index];
}

2.3.7 堆排序

原理：堆排序是一种基于堆的排序算法，通过构建大顶堆并反复将堆顶元素与数组末尾交换，实现将最大值置于末尾，然后逐步递减堆的规模得到有序数组。

  • 堆是一棵完全二叉树，分为大顶堆和小顶堆，大顶堆指父节点数值大于等于左右孩子结点数值，小顶堆指父节点数值小于等于左右孩子结点数值。
  • 通常使用数组存储完全二叉树，下标为i的结点的父结点下标为(i-1)/2，左孩子结点下标为2*i+1，右孩子结点下标为2*i+2。
void heapify(vector<int>& nums, int n, int root) {int largest = root;int left = 2 * root + 1;int right = 2 * root + 2;if (left < n && nums[largest] < nums[left]) largest = left;if (right < n && nums[largest] < nums[right]) largest = right;if (largest != root) {swap(nums[root], nums[largest]);heapify(nums, n, largest);}
}
void heapSort(vector<int>& nums) {int n = nums.size();for (int i = n / 2 - 1; i >= 0; i--) heapify(nums, n, i);for (int i = n - 1; i >= 0; i++) {swap(nums[0], nums[i]);heapify(nums, i, 0);}
}

第三章 常见手撕

3.1 反转链表

206. 反转链表

class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* cur = head;ListNode* pre = nullptr;while (cur) {// 逻辑顺序：先保存cur->next（temp），再将cur->next指向pre，pre指向cur，cur指向tempListNode* temp = cur->next;cur->next = pre;pre = cur;cur = temp;}return pre;}
};

3.2 字母异位分组

49. 字母异位词分组

#include 
#include 
#include 
#include 
#include using namespace std;int main() {vector strs= {"eat", "aet", "tea", "ban"};vector> res;unordered_map> umap;for (auto s : strs) {string skey = s;sort(skey.begin(), skey.end());umap[skey].push_back(s);}for (auto i : umap) res.push_back(i.second);// 输出结果for (auto r : res) {cout << "[";for (int i = 0; i < group.size(); i++) {cout << r[i];if (i < r.size() - 1) {cout << ", ";}}cout << "]," << endl;}return 0;
}

3.3 验证二叉搜索树

中序遍历构造数组，之后判断数组是否升序

98. 验证二叉搜索树

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector vec;void traversal(TreeNode* root) {if (root == NULL) return;traversal(root->left);vec.push_back(root->val);traversal(root->right);}bool isValidBST(TreeNode* root) {traversal(root);for (int i = 0; i < vec.size() - 1; i++) {if (vec[i] >= vec[i + 1]) return false;}return true;}
};

3.4 粉刷房子II

力扣256

假如有一排 n 个房子，每个房子可以被粉刷成 k 种颜色中的一种，你需要粉刷所有的房子，使得相邻的房子不能够有相同的颜色。

费用函数 cost[i][j] 表示粉刷第 i 个房子使用颜色 j 的费用。

你需要找到所有房子粉刷完所需的最小费用。

注意：所有花费都是正整数。

#include 
#include 
#include   // climits包括INT_MAX，INT_MIN等宏
using namespace std;int minCostII(vector>& costs) {if (costs.empty() || costs[0].empty()) return 0;int n = costs.size();int k = costs[0].size();// 1. 明确dp数组的下标及含义：dp[i][j]表示粉刷前i个房子，且最后一个房子使用颜色j粉刷的最小成本vector> dp(n, vector(k, 0));// 2. dp数组初始化，第0个房子粉刷颜色j的最小成本（即为costs[0][j]）for (int j = 0; j < k; ++j) dp[0][j] = costs[0][j];// 3. 确定递推公式：对于每个颜色 j，找到上一个房子的最小成本，但不能是同颜色，因此需要遍历上一个房子的所有颜色，取除了 j 颜色之外的最小成本。// 4. 确定遍历顺序：由左到右for (int i = 1; i < n; i++) {for (int j = 0; j < k; j++) {int min_cost = INT_MAX;for (int m = 0; m < k; m++) {if (m != j) min_cost = min(min_cost, dp[i - 1][m]);}dp[i][j] = costs[i][j] + min_cost;}}// 最终，遍历最后一个房子的所有颜色 j，找出最小的成本作为结果。int result = INT_MAX;for (int j = 0; j < k; ++j) result = min(result, dp[n - 1][j]);return result;
}int main() {vector> costs = {{1, 5, 3}, {2, 9, 4}};int result = minCostII(costs);cout << "Minimum cost: " << result << endl;return 0;
}

3.5 16进制转为10进制

#include 
using namespace std;
int stoi(char* s) {int res = 0;while (*s != '\0') {if (*s >= '0' && *s <= '9') res = res * 16 + (*s - '0');else if (*s >= 'a' && *s <= 'f') res = res * 16 + (*s - 'a' + 10);else if (*s >= 'A' && *s <= 'F') res = res * 16 + (*s - 'A' + 10);else return 0; s++;}return res;
}int main() {char s[] = {"e567"};cout << stoi(s) << endl;;
}

3.6 LRU算法（高频）

146. LRU 缓存

思路：双向链表+哈希表

参考https://leetcode.cn/problems/lru-cache/solutions/863539/146-lru-huan-cun-ji-zhi-cxiang-xi-ti-jie-ulv8/

class LRUCache {
public:// 定义双向链表，每个结点有key、value值，且有指向左结点和右节点的指针，最近使用过的结点放在左侧，最久未使用放在右侧/* 使用双向链表的原因：如果使用单向链表，只能获取后继结点，不能获取前驱结点，删除结点时需要遍历找到前驱结点，时间复杂度为O(n)；而是用双向链表可以直接获得前驱结点*/struct ListNode {int key;int value;ListNode* left;ListNode* right;ListNode(int k, int v) : key(k), value(v), left(nullptr), right(nullptr) {}};ListNode* L = new ListNode(-1, -1);  // 虚拟头结点ListNode* R = new ListNode(-1, -1);  // 虚拟尾结点int n;  // 存储容量大小LRUCache(int capacity) {// 初始时，虚拟头结点和尾结点相接L->right = R;R->left = L;n = capacity;}// 定义哈希表，key为链表结点中的key，value为链表结点unordered_map umap;// 删除双向链表中的某个结点void remove(ListNode* node) {node->left->right = node->right;node->right->left = node->left;}// 在双向链表进行头插结点（最近使用的放在左侧，即链表头）void insert(ListNode* node) {node->right = L->right;node->left = L;L->right->left = node;L->right = node;}// 如果在哈希表中找不到key则返回-1。如果找到key的话，将对应的结点移动到链表头（先删再插）int get(int key) {if (umap.find(key) == umap.end()) return -1;ListNode* node = umap[key];remove(node);insert(node);return node->value;}// 如果要put的key在哈希表中，则更新哈希表中该结点value，将对应的结点移动到链表头（先删再插）；如果不在哈希表中且缓存已满，先删除链表中最后一个结点和哈希表中该值，再构建新的结点，并插入链表头和哈希表void put(int key, int value) {if (umap.find(key) != umap.end()) {ListNode* node = umap[key];node->value = value;remove(node);insert(node);} else {if (umap.size() == n) {ListNode* node = R->left;remove(node);umap.erase(node->key);delete node;}ListNode* node = new ListNode(key, value);insert(node);umap[key] = node;}}
};/*** Your LRUCache object will be instantiated and called as such:* LRUCache* obj = new LRUCache(capacity);* int param_1 = obj->get(key);* obj->put(key,value);*/

3.7 接雨水（高频）

42. 接雨水

思路：单调栈

计算方法：按行来计算雨水体积，使用单调栈，从栈顶到栈底的顺序应该是从小到大的顺序，因为如果将要添加的元素大于栈顶元素，则出现凹槽：栈顶元素是凹槽的底部柱子，栈顶的第二个元素是凹槽左侧柱子，要添加的元素是凹槽右侧柱子。由于通过宽*高来计算雨水的体积，既需要知道元素值，又需要知道元素的下标，因此单调栈中存储元素下标，元素值则通过下标来获得。

单调栈逻辑：

  • 当前遍历的元素小于栈顶元素：压入新元素的下标
  • 当前遍历的元素等于栈顶元素：弹出栈顶的下标，压入新元素的下标
  • 当前遍历的元素大于栈顶元素：计算栈顶元素雨水体积，弹出栈顶的下标，并压入新元素的下标
class Solution {
public:int trap(vector& height) {stack st;int res = 0;st.push(0);for (int i = 1; i < height.size(); i++) {if (height[i] < height[st.top()]) st.push(i);else if (height[i] == height[st.top()]) {st.pop();st.push(i);} else {while (!st.empty() && height[i] > height[st.top()]) {int mid = st.top();st.pop();if (!st.empty()) {int h = min(height[st.top()], height[i]) - height[mid];int w = i - st.top() - 1;res += h * w;} }st.push(i);}}return res;}
};

3.8 合并有序链表

剑指 Offer 25. 合并两个排序的链表

**迭代：**当list1和list2都不是空链表时，判断list1和list2哪一个链表的头节点的值更小，将较小值的节点添加到结果里，当一个节点被添加到结果里之后，将对应链表中的节点向后移一位。

/*** 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* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode* dummyHead = new ListNode(0);ListNode* pre = dummyHead;while (list1 != nullptr && list2 != nullptr) {if (list1->val <= list2->val) {pre->next = list1;list1 = list1->next;} else {pre->next = list2;list2 = list2->next;}pre = pre->next;}pre->next = list1 == nullptr ? list2 : list1;return dummyHead->next;}
};

3.9 二进制求和

67. 二进制求和

class Solution {
public:string addBinary(string str1, string str2) {int n1 = str1.size();int n2 = str2.size();if (n1 < n2) {swap(str1, str2);swap(n1, n2);}while (n2 < n1) {str2 = '0' + str2;n2++;}for(int j = n1 - 1; j > 0; j--) {str1[j] = str1[j] - '0' + str2[j];if (str1[j] >= '2') {str1[j] = (str1[j] - '0') % 2 + '0';str1[j - 1] = str1[j - 1] + 1;}}str1[0] = str1[0] - '0' + str2[0];if(str1[0] >= '2') {str1[0] = (str1[0] - '0') % 2 + '0';str1 = '1' + str1;}return str1;}
};

3.10 实现strStr()

28. 找出字符串中第一个匹配项的下标

class Solution {
public:void getNext(int* next, string s) {int j = -1;next[0] = j;for (int i = 1; i < s.size(); i++) {while (j >= 0 && s[i] != s[j + 1]) j = next[j];if (s[i] == s[j + 1]) j++;next[i] = j;}}int strStr(string haystack, string needle) {int next[needle.size()];getNext(next, needle);int j = -1;for (int i = 0; i < haystack.size(); i++) {while (j >= 0 && haystack[i] != needle[j + 1]) j = next[j];if (haystack[i] == needle[j + 1]) j++;if (j == needle.size() - 1) return i - needle.size() + 1;}return -1;}
};

3.11 华为0913机试

https://mp.weixin.qq.com/s/BlpsEoitip7ugQYgezCd3g

3.11.1 快递中转站

快递公司有一个业务要求，所有当天下发到快递中转站的快递，最迟在第二天送达用户手中。

假设已经知道接下来n天每天下发到快递中转站的快递重量。快递中转站负责人需要使用快递运输车运输给用户，每一辆运输车最大只能装k重量的快递。

每天可以出车多次，也可以不出车，也不要求运输车装满。当天下发到快递中转站的快递，最晚留到第二天就要运输走送给用户。

快递中转站负责人希望出车次数最少，完成接下来n天的快递运输。

解答要求

时间限制: C/C++ 1000ms,其他语言: 2000ms内存限制: C/C++256MB其他语言: 512MB

输入

输入第一行包含两个整数n(1<= n<=200000)，k(1<=k<=100000000)

第二行包含n个整数ai，表示第i天下发到快递中转站的快递重量。

输出

输出最少需要的出车次数。

样例1

输入

3 2
3 2 1

输出

3

解释

第一天的快递出车一次送走2个重量，留1个重量到第二天

第二天送走第一天留下的1个重量和当前的1个重量，留1个重量到第三天送走。

解题思路：直接模拟

#include 
#include 
using namespace std;int main() {int n, k;cin >> n >> k;vector vec(n);for (int i = 0; i < n; i++) cin >> vec[i];long long res = 0;long long left = 0;for (int i = 0; i < n; i++) {long long val = vec[i] + left;long long t1 = val / k;long long t2 = val % k;if (t1 == 0 && left != 0) {t1++;t2 = 0;}res += t1;left = t2;}if (left != 0) res++;cout << res << endl;
}

3.11.2 互通设备集

局一局域网内的设备可以相互发现，具备直连路由的两个设备可以互通。假定设备A和B互通，B和C互通，那么可以将B作为中心设备，通过多跳路由策略使设备A和C互通。这样，A、B、C三个设备就组成了一个互通设备集。其中，互通设备集包括以下几种情况:

  1. 直接互通的多个设备
  2. 通过多跳路由第略间接互通的多个设备
  3. 没有任何互通关系的单个设备现给出某一局域网内的设备总数以及具备直接互通关系的设备，请计算该局域网内的互通设备集有多少个?

输入

第一行: 某一局域网内的设备总数M，32位有符号整数表示。1<= M<=200

第二行:具备直接互通关系的数量N，32位有符号整数表示。0<= N<200

第三行到第N+2行: 每行两个有符号32位整数，分别表示具备直接互通关系的两个设备的编号，用空格隔开。每个设备具有唯一的编号，0<设备编号< M

输出

互通设备集的数量，32位有符号整数表示。

样例1

输入

3
2
0 1
0 2

输出

1

解释:

编号0和1以及编号0和2的设备直接互通，编号1和2的设备可通过编号0的设备建立互通关系，互通设备集可合并为1个。

#include 
#include 
#include 
using namespace std;void dfs(int i, vector> connected, unordered_set& processed) {processed.insert(i);for (auto j : connected[i]) {if (processed.find(j) == processed.end()) dfs(j, connected, processed);}
}
int main() {int M, N;cin >> M >> N;vector> connected(M);for (int i = 0; i < N; i++) {int val1, val2;cin >> val1 >> val2;connected[val1].insert(val2);connected[val2].insert(val1);}int res = 0;unordered_set processed;for (int i = 0; i < M; i++) {if (processed.find(i) == processed.end()) {dfs(i, connected, processed);res++;}}cout << res << endl;return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/196347.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

北邮22级信通院数电：Verilog-FPGA（9）第九周实验（4）实现寄存器74LS374

北邮22级信通院数电：Verilog-FPGA（9）第九周实验（4）实现寄存器74LS374

北邮22信通一枚~ 跟随课程进度更新北邮信通院数字系统设计的笔记、代码和文章 持续关注作者 迎接数电实验学习~ 获取更多文章&#xff0c;请访问专栏&#xff1a; 北邮22级信通院数电实验_青山如墨雨如画的博客-CSDN博客 目录 一.代码部分 1.1 reg_74LS374.v 1.2 reg_LS3…
阅读更多...
Adobe Illustrator——原创设计的宝藏软件

Adobe Illustrator——原创设计的宝藏软件

今天&#xff0c;我们来谈谈一款在Adobe系列中曾经多次给大家都提到的原创性极强的设计理念丰富的矢量图形编辑软件——Adobe Illustrator。 Adobe Illustrator&#xff0c;其定位是一款与Photoshop相类似对矢量图形进行编辑的软件。 Adobe Illustrator&#xff0c;作为全球最著…
阅读更多...
镀膜与干刻中的平均自由程是什么？

镀膜与干刻中的平均自由程是什么？

在芯片制造中&#xff0c;镀膜和干刻是其中的重要环节&#xff0c;通常要用到CVD&#xff0c;RIE等技术&#xff0c;对材料表面进行纳米级的精细操作。在这些工序中&#xff0c;原子&#xff0c;分子&#xff0c;离子等&#xff0c;会在气体或真空中进行自由运动&#xff0c;直…
阅读更多...
C++类与对象(1)—初步认识

C++类与对象(1)—初步认识

目录 一、面向过程和面向对象 二、类 1、定义 2、类的两种定义方式 3、访问限定符 4、命名规范化 5、类的实例化 6、计算类对象的大小 7、存储方式 三、this指针 1、定义 2、存储位置 3、辨析 四、封装好处 一、面向过程和面向对象 C语言是面向过程的&#xf…
阅读更多...
基于单片机的温度控制器系统设计

基于单片机的温度控制器系统设计

**单片机设计介绍&#xff0c; 基于单片机的温度控制器系统设计 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机的温度控制器系统是一种利用单片机来检测环境温度并控制温度的系统。它通常由以下几个部分组成&#xff…
阅读更多...
Zookeeper Java 开发，自定义分布式锁示例

Zookeeper Java 开发，自定义分布式锁示例

文章目录 一、概述二、导入依赖包三、创建锁的过程3.1 通过 create 创建节点信息3.2 AsyncCallback.StringCallback 回调函数3.3 AsyncCallback.Children2Callback 的回调函数3.4 Watcher 的回调函数 四、完整示例4.1 完整分布式锁代码4.2 测试类 如果您还没有安装Zookeeper请看…
阅读更多...
让你的Mac体验更便捷，快速启动工具Application Wizard为你助力！

让你的Mac体验更便捷，快速启动工具Application Wizard为你助力！

亲爱的Mac用户们&#xff0c;你是否经常感到在繁琐的软件启动过程中浪费了太多时间&#xff1f;你是否希望能够以更快的速度找到并启动你所需的应用程序&#xff1f;如果是的话&#xff0c;那么不要犹豫&#xff0c;让我们来介绍一款强大的软件快速启动工具——Application Wiz…
阅读更多...
uniapp app tabbar 页面默认隐藏

uniapp app tabbar 页面默认隐藏

1.在page.json 中找到tabbar visible 默认为true,设为false则是不显示 uni.setTabBarItem({ index: 1, //列表索引 visible:true //显示或隐藏 })
阅读更多...
12-1- GAN -简单网络-线性网络

12-1- GAN -简单网络-线性网络

功能 随机噪声→生成器→MINIST图像。 训练方法 0 损失函数：gan的优化目标是一个对抗损失，是二分类问题，用BCELoss 1 判别器的训练，首先固定生成器参数不变，其次判别器应当将真实图像判别为1，生成图像判别为0 loss=loss(real_out, 1)+loss(fake_out, 0) 2 生成器的…
阅读更多...
开源简历生成器OpenResume

开源简历生成器OpenResume

什么是 OpenResume &#xff1f; OpenResume 是一个功能强大的开源简历生成器和简历解析器。OpenResume 的目标是为每个人提供免费的现代专业简历设计&#xff0c;让任何人都能充满信心地申请工作。 OpenResume 有 5 个核心特点&#xff1a; 特征描述1. 实时UI更新当您输入简历…
阅读更多...
高德地图系列（一）：vue项目如何使用高德地图、入门以及基本控件使用

高德地图系列（一）：vue项目如何使用高德地图、入门以及基本控件使用

目录 第一章 前言 第二章 准备工作 2.1 账号注册 2.2 高德地图开发平台文档 2.3 创建应用 第三章 使用地图 3.1 地图使用步骤 3.2 理解几个地图基础控件 3.3 基础类理解 第一章 前言 小编都是在vue项目中使用高德地图的&#xff0c;每一个功能都会亲测可用之后才会…
阅读更多...
【机器学习10】循环神经网络

【机器学习10】循环神经网络

1循环神经网络 RNN通过将神经元串行起来处理序列化的数据。 由于每个神经元能用它的内部变量保存之前输入的序列信息&#xff0c;因此整个序列被浓缩成抽象的表示&#xff0c; 并可以据此进行分类或生成新的序列。 2 循环神经网络的梯度消失或梯度爆炸问题 传统的循环神经网…
阅读更多...
WPF xaml Command用法介绍

WPF xaml Command用法介绍

WPF (Windows Presentation Foundation) 中的命令设计模式是一种用于分离用户界面逻辑和业务逻辑的方法。在WPF中&#xff0c;这种模式通过命令接口&#xff08;如 ICommand&#xff09;实现&#xff0c;使得用户界面组件&#xff08;如按钮、菜单项等&#xff09;可以触发不直…
阅读更多...
k8s ingress高级用法一

k8s ingress高级用法一

前面的文章中&#xff0c;我们讲述了ingress的基础应用&#xff0c;接下来继续讲解ingress的一些高级用法 一、ingress限流 在实际的生产环境中&#xff0c;有时间我们需要对服务进行限流&#xff0c;避免单位时间内访问次数过多&#xff0c;常用的一些限流的参数如下&#x…
阅读更多...
深度学习（五）softmax 回归之：分类算法介绍，如何加载 Fashion-MINIST 数据集

深度学习（五）softmax 回归之：分类算法介绍，如何加载 Fashion-MINIST 数据集

Softmax 回归 基本原理 回归和分类&#xff0c;是两种深度学习常用方法。回归是对连续的预测&#xff08;比如我预测根据过去开奖列表下次双色球号&#xff09;&#xff0c;分类是预测离散的类别&#xff08;手写语音识别&#xff0c;图片识别&#xff09;。 现在我们已经对回…
阅读更多...
JAVAEE 初阶 多线程基础(一)

JAVAEE 初阶 多线程基础(一)

多线程基础 一.线程的概念二.为什么要有线程三.进程和线程的区别和关系四.JAVA的线程和操作系统线程的关系五.第一个多线程程序1.继承Thread类 一.线程的概念 一个线程就是一个 “执行流”. 每个线程之间都可以按照顺讯执行自己的代码. 多个线程之间 “同时” 执行着多份代码 同…
阅读更多...
CV计算机视觉每日开源代码Paper with code速览-2023.11.14

CV计算机视觉每日开源代码Paper with code速览-2023.11.14

点击CV计算机视觉&#xff0c;关注更多CV干货 论文已打包&#xff0c;点击进入—>下载界面 点击加入—>CV计算机视觉交流群 1.【基础网络架构&#xff1a;Transformer】Aggregate, Decompose, and Fine-Tune: A Simple Yet Effective Factor-Tuning Method for Vision…
阅读更多...
流媒体协议

流媒体协议

◆ RTP(Real-time Transport Protocol)&#xff0c;实时传输协议。 ◆ RTCP(Real-time Transport Control Protocol)&#xff0c;实时传输控制协议。 ◆ RTSP(Real Time Streaming Protocol)&#xff0c;实时流协议。 ◆ RTMP(Real Time Messaging Protocol)&#xff0c;实时…
阅读更多...
【Proteus仿真】【Arduino单片机】LM35温度计

【Proteus仿真】【Arduino单片机】LM35温度计

文章目录 一、功能简介二、软件设计三、实验现象联系作者 一、功能简介 本项目使用Proteus8仿真Arduino单片机控制器&#xff0c;使用PCF8574、LCD1602液晶、LM35传感器等。 主要功能&#xff1a; 系统运行后&#xff0c;LCD1602显示传感器检测温度。 二、软件设计 /* 作者&a…
阅读更多...
单片机的冷启动、热启动、复位

单片机的冷启动、热启动、复位

一文看懂STC单片机冷启动和复位有什么区别-电子发烧友网 单片机的冷启动、热启动和复位是不同的启动或重置方式&#xff0c;它们在系统状态和初始化方面有所不同&#xff1a; 1.冷启动&#xff08;Cold Start&#xff09;&#xff1a; 定义&#xff1a; 冷启动是指系统从完全关…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023