算法基础

算法（Algorithm）是指用来操作数据、解决程序问题的一组方法。对于同一个问题，使用不同的算法，也许最终得到的结果是一样的，比如排序就有前面的十大经典排序和几种奇葩排序，虽然结果相同，但在过程中消耗的资源和时间却会有很大的区别，比如快速排序与猴子排序。
复杂度解析

哈希表

b站基本原理讲解
C++应用
unordered_map 容器用法
原理
hash_map基于hash table（哈希表）。 哈希表最大的优点，就是把数据的存储和查找消耗的时间大大降低，几乎可以看成是常数时间；而代价仅仅是消耗比较多的内存。
例子
leetcode 1：两数之和

  1.  vector<int> twoSum(vector<int>& nums, int target) {
  2.         unordered_map<int, int> hashtable;//创建哈希表
  3.         for (int i = 0; i < nums.size(); ++i) {
  4.             auto it = hashtable.find(target - nums[i]);//查找哈希表中是否有目标数
  5.             if (it != hashtable.end()) {//如果存在，返回该哈希值位置和当前值
  6.                 return {it->second, i};
  7.             }
  8.             hashtable[nums[i]] = i;//如果没有，将当前位的数字存入哈希表，防止重复返回位置
  9.         }
  10.         return {};
  11.     }
  1.  unordered_map<key,T>::iterator it;
  2.     (*it).first;   //the key value
  3.     (*it).second   //the mapped value
  4.     for(unordered_map<key,T>::iterator iter=mp.begin();iter!=mp.end();iter++)
  5.           cout<<"key value is"<<iter->first<<" the mapped value is "<< iter->second;
  7.     //也可以这样
  8.     for(auto& v : mp)
  9.         cout<< v.first <<" "<< v.second<<endl;

hash_set：
lettcode142:

  1. unordered_set<ListNode *> visited;
  2. while (head != nullptr) {
  3.     if (visited.count(head)) {
  4.         return head;
  5.     }
  6.     visited.insert(head);
  7.     head = head->next;
  8. }
  9. return nullptr;

vector

寻找元素的位置

  1. int findPosVector(vector <int> input , int number)
  2. {
  3.     vector<int>::iterator iter=std::find(input.begin(),input.end(),number);//返回的是一个迭代器指针
  4.     if(iter == input.end())
  5.     {
  6.         return -1;
  7.     } else{
  8.         return std::distance(input.begin(),iter);
  9.     }
  10. }

排序

快排

原理
在待排序的数列中，找一个数字作为基准数（这只是个专用名词）。接下来我们需要把这个待排序的数列中小于基准数的元素移动到待排序的数列的左边，把大于基准数的元素移动到待排序的数列的右边。
代码

  1. class Solution {
  2. public:
  4.     int partition(vector<int>& nums,int start,int end){
  5.         int index=(rand()%(end-start+1))+start;
  6.         swap(nums[start],nums[index]);
  7.         int pivot=nums[start];
  8.         int left=start,right=end;
  9.         while(left!=right){
  10.             while(left<right && nums[right]>pivot) --right;
  11.             while(left<right && nums[left]<=pivot) ++left;
  12.             if(left<right) swap(nums[left],nums[right]);
  13.         }
  14.         swap(nums[start],nums[left]);
  15.         return left;
  16.     }
  18.     void quickSort(vector<int>& nums,int start,int end){
  19.         if(start==end) return;
  20.         if(start<end){
  21.             int index=partition(nums,start,end);
  22.             quickSort(nums,start,index-1);
  23.             quickSort(nums,index+1,end);
  24.         }
  25.     }
  27.     vector<int> sortArray(vector<int>& nums) {
  28.         if(nums.size()==0) return nums;
  29.         int size=nums.size()-1;
  30.         quickSort(nums,0,size);
  31.         return nums;
  32.     }
  33. };

堆排

图解
实现

  • 此排序方法不适用于个数少的序列，因为初始构建堆需要时间；
  • 不稳定算法(unstable sort)
  • 性质：若一个结点的下标为k，那么它的父结点为(k-1)/2，其子节点为2k+1和2k+2；（注意是整除）
  • 复杂度分析：

最差时间复杂度O(n log n)
最优时间复杂度O(n log n)
平均时间复杂度O(n log n)
最差空间复杂度O(n)

  1. void Swap(int &a, int &b)
  2. {
  3.     int temp = a;
  4.     a = b;
  5.     b = temp;
  6. }
  8. //堆排序的核心是建堆,传入参数为数组，根节点位置，数组长度
  9. void Heap_build(int a[],int root,int length)
  10. {
  11.     int lchild = root*2+1;//根节点的左子结点下标
  12.     if (lchild < length)//左子结点下标不能超出数组的长度
  13.     {
  14.         int flag = lchild;//flag保存左右节点中最大值的下标
  15.         int rchild = lchild+1;//根节点的右子结点下标
  16.         if (rchild < length)//右子结点下标不能超出数组的长度(如果有的话)
  17.         {
  18.             if (a[rchild] > a[flag])//找出左右子结点中的最大值
  19.             {
  20.                 flag = rchild;
  21.             }
  22.         }
  23.         if (a[root] < a[flag])
  24.         {
  25.             Swap(a[root],a[flag]);//交换父结点和比父结点大的最大子节点
  26.             Heap_build(a,flag,length);//从此次最大子节点的那个位置开始递归建堆
  27.         }
  28.     }
  29. }
  31. void Heap_sort(int a[],int len)
  32. {
  33.     for (int i = len/2; i >= 0; --i)//从最后一个非叶子节点的父结点开始建堆
  34.     {
  35.         Heap_build(a,i,len);
  36.     }
  38.     //j表示数组此时的长度，因为len长度已经建过了，从len-1开始
  39.     for (int j = len-1; j > 0; --j){
  40.         Swap(a[0],a[j]);//交换首尾元素,将最大值交换到数组的最后位置保存
  42.         //去除最后位置的元素重新建堆，此处j表示数组的长度，最后一个位置下标变为len-2
  43.         Heap_build(a,0,j);}
  45. }
  46. int main(int argc, char **argv)
  47. {
  48.     clock_t Start_time = clock();
  49.     int a[10] = {12,45,748,12,56,3,89,4,48,2};
  50.     Heap_sort(a,10);
  51.      for (size_t i = 0; i != 10; ++i)
  52.      {
  53.          cout<<a[i]<<" ";
  54.      }
  55.     clock_t End_time = clock();
  56.     cout<<endl;
  57.     cout<<"Total running time is: "<<static_cast<double>(End_time-Start_time)/CLOCKS_PER_SEC*1000<<" ms"<<endl;
  58.     cin.get();
  59.     return 0;
  60. }

归并排序

实现
leetcde - 图1

  1. void Merge(int arr[], int l, int q, int r){
  2.     int n=r-l+1;//临时数组存合并后的有序序列
  3.     int* tmp=new int[n];
  4.     int i=0;
  5.     int left=l;
  6.     int right=q+1;
  7.     while(left<=q && right<=r)
  8.         tmp[i++] = arr[left]<= arr[right]?arr[left++]:arr[right++];
  9.     while(left<=q)
  10.         tmp[i++]=arr[left++];
  11.     while(right<=r)
  12.         tmp[i++]=arr[right++];
  13.     for(int j=0;j<n;++j)
  14.         arr[l+j]=tmp[j];
  15.     delete [] tmp;//删掉堆区的内存
  16. }
  18. void MergeSort(int arr[], int l, int r){
  19.     if(l==r)
  20.         return;  //递归基是让数组中的每个数单独成为长度为1的区间
  21.     int q = (l + r)/2;
  22.     MergeSort(arr, l, q);
  23.     MergeSort(arr, q + 1, r);
  24.     Merge(arr, l, q, r);
  26. }
  28. int main(){
  29.     int a[8] = {3,1,2,4,5,8,7,6};
  30.     MergeSort(a,0,7);
  31.     for(int i=0;i<8;++i)
  32.         cout<<a[i]<<" ";
  33. }

搜索

二分查找

c++的stl库中也有实现，但是只返回bool变量；

  1. int binarySearch(int x,int n)
  2. {
  3.     int left =0;
  4.     int right=n-1;
  5.     while(left<=right)
  6.     {
  7.         int mid =(left+right)/2;
  8.         if(x==a[mid])
  9.         {
  10.             return mid;
  11.         }
  12.         if(x>a[mid])
  13.         {
  14.             left=mid+1;
  15.         }
  16.         else
  17.         {
  18.             right =mid-1;
  19.         }
  20.     }
  21.     return -1;//未找到x
  22. }
  23. //二分搜索递归实现
  24. int recurisonBinarySearch(int left,int right,int x)
  25. {
  26.     if(left>right)
  27.     {
  28.         return -1;
  29.     }
  30.     int mid =(left+right)/2;
  31.     if(x==a[mid])
  32.     {
  33.         return mid;
  34.     }
  35.     if(x>a[mid])
  36.     {
  37.         return recurisonBinarySearch(mid+1,right,x);
  38.     }
  39.     else
  40.     {
  41.         return recurisonBinarySearch(left,mid-1,x);
  42.     }
  43. }

回溯

回溯是暴力搜索，基本等于递归。一般用来解决以下问题：

  • 组合
  • 分割
  • 子集
  • 排列
  • 棋盘

基本模板：

  1. vector<int>path;
  2.     vector<vector<int>>result;
  3.     void backtracking(int start,int n,int k){
  4.         if(path.size()==k){
  5.             int sum=0;
  6.             for(int i=0;i<path.size();i++){
  7.                 sum+=path[i];
  8.             }
  9.             if(sum==n)result.push_back(path);
  10.             return;
  11.         }
  12.         for(int i=start;i<10;i++){
  13.             path.push_back(i);
  14.             backtracking(i+1,n,k);
  15.             path.pop_back();
  16.         }
  17.     }
  18.     vector<vector<int>> combinationSum3(int k, int n) {
  19.         backtracking(1,n,k);
  20.         return result;
  21.     }

剪枝在于修改for循环，排除不可能的分支；

动态规划

基础

  • 背包问题
  • 打家劫舍
  • 股票问题
  • 子序列问题

关键：

  1. dp数组以及下标的含义
  2. 递推公式
  3. dp数组如何初始化
  4. 遍历顺序
  5. 打印dp数组（调试）

    背包问题

    学习01背包和完全背包
    image.png

    01背包

    二维数组：
    数组：
    使用二维数组，即dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
    递推：
  • 不放物品i：由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以被背包内的价值依然和前面相同。)
  • 放物品i：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值

所以递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

  1. //bagweight 是背包空间 weight是物品列表，物品顺序不影响结果
  2. vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));
  4. // 初始化
  5. for (int j = weight[0]; j <= bagweight; j++) {
  6.     dp[0][j] = value[0];
  7. }
  9. // weight数组的大小 就是物品个数
  10. for(int i = 1; i < weight.size(); i++) { // 遍历物品
  11.     for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
  12.         //如果放不下物品直接等于前值
  13.         if (j < weight[i]) dp[i][j] = dp[i - 1][j];
  14.         //否则去比较 不放新物品和放新物品的价值
  15.         else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
  16.     }
  17. }

一维数组：
在使用二维数组的时候，递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
其实可以发现如果把dp[i - 1]那一层拷贝到dp[i]上，表达式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]); 与其把dp[i - 1]这一层拷贝到dp[i]上，不如只用一个一维数组了，只用dp[j]（一维数组，也可以理解是一个滚动数组）。

定义：
在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。
递推：
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
初始化：
dp数组初始化的时候，都初始为0就可以了。

一维dp数组遍历顺序：
倒序遍历是为了保证每个物品只加入一遍。

  1.  // 初始化
  2.     vector<int> dp(bagWeight + 1, 0);//baweight设置
  3.     for(int i = 0; i < weight.size(); i++) { // 遍历物品
  4.         for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
  5.             dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
  6.         }
  7.     }

树

二叉查找树

二叉排序树，又称为二叉查找树、二叉搜索树
性质：若其左子树不为空，则左子树上的所有节点的值均小于它的根结点的值；若其右子树不为空，则右子树上的所有节点的值均大于它的根结点的值；左右子树又分别是二叉排序树。