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

数据结构和算法八股文

第一章 数据结构

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指向temp
            ListNode* 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;
}

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【shardingjdbc】sharding-jdbc分库分表入门demo及原理分析

【shardingjdbc】sharding-jdbc分库分表入门demo及原理分析

文章目录 场景配置&#xff1a;概念及原理:代码:思考: 本文中&#xff0c;demo案例涉及场景为sharding jdbc的分库情况。 通俗点说就是由原来的db0_table水平拆分为 db1 t_table &#xff0c;db2.t_table。 demo本身很简单&#xff0c;难点在于分片策略配置到底该怎么写&#x…
阅读更多...
SQL练习01

SQL练习01

1.游戏玩法分析 SQL Create table If Not Exists Activity (player_id int, device_id int, event_date date, games_played int); Truncate table Activity; insert into Activity (player_id, device_id, event_date, games_played) values (1, 2, 2016-03-01, 5); insert …
阅读更多...
以太网和局域网

以太网和局域网

计算机网络的定义 计算机网络是一个将分散的、具有独立功能的计算机&#xff0c;通过通信设备与线路连接起来&#xff0c;由根据协议编写的软件来实现的资源共享和信息传递的系统 计算机网络的分类 广域网是互联网的核心部分 局域网 常见的局域网拓扑结构有4大类&#xff1a…
阅读更多...
C# datagridView 控件使用心得

C# datagridView 控件使用心得

首先本人的需求是&#xff0c;通过UI编辑一个表格文件&#xff0c;然后将其存储起来。 同时也可以对其进行载入,话不多说先上图片 dataGridView1 的初始化&#xff0c;这个控件的初始化可以使用UI界面的设置&#xff0c;也可以使用程序&#xff1a; Column1 new System.Window…
阅读更多...
基于LDPC编译码和FP-MAP球形检测算法的协作MIMO系统误码率matlab仿真

基于LDPC编译码和FP-MAP球形检测算法的协作MIMO系统误码率matlab仿真

目录 1.算法运行效果图预览 2.算法运行软件版本 3.部分核心程序 4.算法理论概述 4.1 LDPC码 4.1 Fincke-Pohst-MAP球形检测算法 5.算法完整程序工程 1.算法运行效果图预览 2.算法运行软件版本 matlab2017b 3.部分核心程序 .........................................…
阅读更多...
新增文件收藏夹、回收站、终端等功能，1Panel开源面板v1.8.0发布

新增文件收藏夹、回收站、终端等功能，1Panel开源面板v1.8.0发布

2023年11月13日&#xff0c;现代化、开源的Linux服务器运维管理面板1Panel正式发布v1.8.0版本。 在这一版本中&#xff0c;1Panel新增文件收藏夹、回收站、终端功能&#xff0c;面板设置时支持设置面板监听地址。此外&#xff0c;1Panel开源项目组还进行了60多项功能更新和问题…
阅读更多...
【数据结构】经典单链表OJ题！！

【数据结构】经典单链表OJ题！！

学习完单链表&#xff0c;习题就成了最好的巩固方式 目录 1.链表分割:思路&#xff1a;代码实现&#xff1a; 2.随机链表的复制:思路1&#xff1a;代码实现&#xff1a;思路2&#xff1a;代码实现&#xff1a; 3.环形链表:3.1环形链表1:思路&#xff1a;代码实现&#xff1a; 3…
阅读更多...
『MySQL快速上手』-⑧-内置函数

『MySQL快速上手』-⑧-内置函数

文章目录 1.日期函数1.1 获得年月日1.2 获得时分秒1.3 获得时间戳1.4 在日期的基础上加日期1.5 在日期的基础上减去时间1.6 计算两个日期之间相差多少天案例1案例22.字符串函数案例3.数学函数4.其他函数1.日期函数 1.1 获得年月日
阅读更多...
【C++】——运算符重载

【C++】——运算符重载

&#x1f383;个人专栏&#xff1a; &#x1f42c; 算法设计与分析&#xff1a;算法设计与分析_IT闫的博客-CSDN博客 &#x1f433;Java基础&#xff1a;Java基础_IT闫的博客-CSDN博客 &#x1f40b;c语言&#xff1a;c语言_IT闫的博客-CSDN博客 &#x1f41f;MySQL&#xff1a…
阅读更多...
promise多请求并发

promise多请求并发

<!DOCTYPE html> <html><head><meta charset"utf-8" /><title></title> </head><body><script>let p1 new Promise((resolve, reject) > {resolve(成功了)})let p2 new Promise((resolve, reject) > …
阅读更多...
JAVA基础语法编程详解---三目运算符

JAVA基础语法编程详解---三目运算符

6.判断体重指数 题目描述 - 描述 体重指数 体重 (kg) / ( 身高 (m) 身高 (m) )&#xff0c;小于18.5属于偏瘦&#xff0c;介于18.5和20.9之间&#xff08;左闭右开&#xff09;属于苗条&#xff0c;介于20.9和24.9之间&#xff08;左闭右闭&#xff09;属于适中&#xff0c;…
阅读更多...
云原生之使用Docker部署home-page个人导航页

云原生之使用Docker部署home-page个人导航页

云原生之使用Docker部署home-page个人导航页 一、home-page个人导航页介绍二、本地环境介绍2.1 本地环境规划2.2 本次实践介绍 三、本地环境检查3.1 检查Docker服务状态3.2 检查Docker版本3.3 检查docker compose 版本 四、下载home-page镜像五、部署home-page导航页5.1 创建挂…
阅读更多...
振南技术干货集：深入浅出的Bootloader（3）

振南技术干货集：深入浅出的Bootloader（3）

注解目录 1、烧录方式的更新迭代 1.1 古老的烧录方式 (怀旧一下&#xff0c;单片机高压烧录器。) 1.2 ISP 与ICP 烧录方式 (还记得当年我们玩过的 AT89S51?) 1.3 更方便的 ISP 烧录方式 1.3.1串口 ISP &#xff08;是 STC 单片机成就了我们&#xff0c;还是我们成就了…
阅读更多...
通配符SSL证书

通配符SSL证书

通配符SSL证书是一种特殊的数字证书&#xff0c;用于在互联网上建立安全的连接&#xff0c;其特点是可以保护多个子域名&#xff0c;并且具有很高的兼容性和扩展性。本文将详细介绍通配符SSL证书的相关概念、优点和应用等。 首先&#xff0c;我们需要了解什么是SSL证书。 SSL证…
阅读更多...
python入口文件方便在其它目录也能执行

python入口文件方便在其它目录也能执行

dir_path os.path.dirname(os.path.realpath(__file__)) parent_dir_path os.path.abspath(os.path.join(dir_path, os.pardir)) sys.path.insert(0, parent_dir_path)
阅读更多...
CPU vs GPU：谁更适合进行图像处理？

CPU vs GPU：谁更适合进行图像处理？

CPU 和 GPU 到底谁更适合进行图像处理呢&#xff1f;相信很多人在日常生活中都会接触到图像处理&#xff0c;比如修图、视频编辑等。那么&#xff0c;让我们一起来看看&#xff0c;在这方面&#xff0c;CPU 和 GPU 到底有什么不同&#xff0c;哪个更胜一筹呢&#xff1f; 一、C…
阅读更多...
股市助手：实时股市快讯，真人语音播报，助您第一时间获取最新资讯（自己写的分享给需要的人）

股市助手：实时股市快讯，真人语音播报，助您第一时间获取最新资讯（自己写的分享给需要的人）

文章目录 &#x1f4d6; 介绍 &#x1f4d6;&#x1f3e1; 使用环境 &#x1f3e1;&#x1f4d2; 使用方法 &#x1f4d2;&#x1f4dd; 软件设置&#x1f4dd; 软件运行 &#x1f4d6; 介绍 &#x1f4d6; 给大家分享一款自己写的软件《股市助手》&#xff0c;老规矩&#xff…
阅读更多...
【C++初阶（七）】类和对象（下）

【C++初阶（七）】类和对象（下）

本专栏内容为&#xff1a;C学习专栏&#xff0c;分为初阶和进阶两部分。 通过本专栏的深入学习&#xff0c;你可以了解并掌握C。 &#x1f493;博主csdn个人主页&#xff1a;小小unicorn ⏩专栏分类&#xff1a;C &#x1f69a;代码仓库&#xff1a;小小unicorn的代码仓库&…
阅读更多...
Linux安装MongoDB

Linux安装MongoDB

Download MongoDB Community Server | MongoDB 简单安装 百度网盘 链接&#xff1a;https://pan.baidu.com/s/1j7q0TtkpByfg8kqb2UCHZw 提取码&#xff1a;93zr --来自百度网盘超级会员V4的分享 解压文件 tar -xvf mongodb-linux-x86_64-4.0.10.tgz 移动解压后的文件到指…
阅读更多...
VS设置--查看引用库源代码

VS设置--查看引用库源代码

1.工具-->选项-->文本编译器-->C#-->高级-->勾选支持导航到反编译源(试验)
阅读更多...
最新文章

Copyright @ 2022~2023