经典C++算法题目 |21xrx.com

经典C++算法题目

2023-07-10 20:45:38 深夜i -- --

C++ 经典算法题目数据结构编程练习

C++是一门流行且广泛应用的编程语言，许多经典的算法题目也是使用这种语言来实现的。下面介绍几道经典的C++算法题目。

1. 二分查找

二分查找算法是一种非常高效的查找算法，其时间复杂度为O(log n)。该算法通过在有序数据中逐步缩小待查找区间，从而找到目标值。

利用C++ STL库中的lower_bound()函数可以轻松实现二分查找算法。例如：


int binarySearch(vector<int>& nums, int target) {
  int low = 0, high = nums.size() - 1;
  while (low <= high) {
    int mid = (low + high) / 2;
    if (nums[mid] == target) return mid;
    else if (nums[mid] > target) high = mid - 1;
    else low = mid + 1;
  }
  return -1; // 没有找到目标值
}

2. 快速排序

快速排序算法是一种高效的排序算法，其时间复杂度为O(nlogn)。该算法通过每次选取一个pivot元素来将待排序数组划分为两个子数组，一个小于pivot，一个大于等于pivot，再递归地对两个子数组进行快速排序。

下面是一个使用C++实现的快速排序算法：


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

3. 最大子序和

最大子序和是一个经典的动态规划问题，其目的是在给定的整数序列中，找到一个子序列，使其和最大。

利用动态规划思想，可以轻松实现该算法。例如：


int maxSubArray(vector<int>& nums) {
  int n = nums.size();
  int maxSum = nums[0];
  vector<int> dp(n, 0);
  dp[0] = nums[0];
  for (int i = 1; i < n; i++) {
    dp[i] = max(dp[i-1] + nums[i], nums[i]);
    maxSum = max(maxSum, dp[i]);
  }
  return maxSum;
}

以上三道经典C++算法题目，可以帮助我们更好地理解C++语言的使用和算法实现。如果你对算法和编程感兴趣，不妨试试这些题目，提升自己的技能水平。

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

下一篇: C++程序员必备的知识指南

评论区

()

相似文章