C++ 面试常见算法题及答案 |21xrx.com

C++ 面试常见算法题及答案

2023-06-24 21:00:12 深夜i -- --

C++ 算法题面试常见答案

在C++面试中，算法题是必不可少的部分。为了帮助你更好地准备面试，本文将介绍一些常见的C++算法题及其答案。希望能帮助你在面试中取得成功。

1. 反转链表

题目描述：给定一个单向链表，将其反转并返回新的头节点。

解题思路：使用三个指针，分别指向当前节点、上一个节点和下一个节点，依次翻转每个节点。

ListNode* reverseList(ListNode* head) {
  if (head == nullptr) return nullptr;
  ListNode* prev = nullptr;
  ListNode* curr = head;
  while (curr != nullptr) {
    ListNode* next = curr->next;
    curr->next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
}

2. 两数之和

题目描述：给定一个整数数组和一个目标值，找到数组中两个数的和等于目标值并返回这两个数的下标。

解题思路：使用哈希表记录每个数的下标，遍历数组，判断目标值减去当前值在哈希表中是否存在，如果存在，则返回两个数的下标。

vector<int> twoSum(vector<int>& nums, int target) {
  unordered_map<int, int> mp;
  for (int i = 0; i < nums.size(); ++i) {
    int complement = target - nums[i];
    if (mp.count(complement)) {
      return {mp[complement], i};
    }
    mp[nums[i]] = i;
  }
  return {};
}

3. 二叉树的最大深度

题目描述：给定一个二叉树，返回其最大深度。

解题思路：递归求解，每次递归先求出左子树的深度和右子树的深度，取其中较大的值加上一即为当前节点的深度。

int maxDepth(TreeNode* root) {
  if (root == nullptr) return 0;
  int left_depth = maxDepth(root->left);
  int right_depth = maxDepth(root->right);
  return max(left_depth, right_depth) + 1;
}

4. 快速排序

题目描述：对给定的数组进行快速排序。

解题思路：快速排序采用分治的思想，先选定一个基准元素，将数组分成小于基准元素的部分和大于基准元素的部分，对两个部分继续递归进行快速排序。具体实现时，使用双指针法来进行分区，然后递归处理左右子数组。

void quickSort(vector<int>& nums, int left, int right) {
  if (left >= right) return;
  int i = left;
  int j = right;
  int pivot = nums[left];
  while (i < j) {
    while (i < j && nums[j] >= pivot) --j;
    if (i < j) nums[i++] = nums[j];
    while (i < j && nums[i] < pivot) ++i;
    if (i < j) nums[j--] = nums[i];
  }
  nums[i] = pivot;
  quickSort(nums, left, i - 1);
  quickSort(nums, i + 1, right);
}

总结

本文介绍了一些常见的C++算法题及其解题思路。这些算法题涵盖了链表、数组、树和排序等多个方面，希望能帮助读者更好地准备面试并取得成功。

上一篇: idea打包java可执行jar包

下一篇: C++实现字符型转换成整型的方法

评论区

相似文章