@TOC

前言

Hello！
非常感谢您阅读海轰的文章，倘若文中有错误的地方，欢迎您指出～
 
自我介绍 ଘ(੭ˊᵕˋ)੭
昵称：海轰
标签：程序猿｜C++选手｜学生
简介：因C语言结识编程，随后转入计算机专业，获得过国家奖学金，有幸在竞赛中拿过一些国奖、省奖…已保研。
学习经验：扎实基础 + 多做笔记 + 多敲代码 + 多思考 + 学好英语！
 
唯有努力💪
 

知其然 知其所以然！

 
本文仅记录自己感兴趣的内容

参考：https://www.cnblogs.com/SiriusZHT/p/14310776.html

汉诺塔问题

#include<iostream>
using namespace std;
static int counts=1;
void move(char src,char dest)
{
	cout<<"第"<<counts<<"步：  "<<src<<"------->"<<dest<<endl;
	counts++;
}
// hanoi: 从src 全部移动至 dest 
void hanoi(int n,char src,char medium,char dest)
{
	if(n==1)
		move(src,dest);
	else
	{
        // 分为两部分 上面n-1块 最下面1块
       
        // 先把上半部分（n-1） 从src移动至medium
		hanoi(n-1,src,dest,medium);
        // 再把最后一部分（1）移动至dest
		move(src,dest);
        // 最后再把上半部分（n-1） 从medium移动至dest
		hanoi(n-1,medium,src,dest);
	}
}
int main()
{
	int m;
	//cin>>m;
	cout<<"请输入汉诺塔  层数："<<endl;
    cin>>m;
	cout<<"步骤是："<<endl;
	hanoi(m,'A','B','C');

	return 0;
}

汉诺塔问题

class Solution {
public:
    void move(vector<int>& src, vector<int>& dest) {
        dest.push_back(src.back());
        src.pop_back();
    }
    void hanoi(int n, vector<int>& src, vector<int>& medium, vector<int>& dest) {
        if(n == 1) {
            move(src, dest);
        } else {
            hanoi(n-1, src, dest, medium);
            move(src, dest);
            hanoi(n-1, medium, src, dest);
        }
    }
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
        int n = A.size();
        hanoi(n, A, B, C);
    }
};

搜索问题

二分查找

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        while(left <= right) {
            int mid = left + (right - left)/2;
            if(nums[mid] == target) {
                return mid;
            } else if(nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
};

排序问题

快速排列

#include <iostream>
#include <vector>
using namespace std;
int partition(vector<int> &nums, int left, int right)
{
    srand((unsigned)time(NULL));
    int randomIndex = rand() % (right - left + 1) + left;
    swap(nums[left], nums[randomIndex]);

    int pivot = nums[left];
    int lt = left;
    for (int i = left + 1; i <= right; ++i)
    {
        if (nums[i] < pivot)
        {
            ++lt;
            swap(nums[i], nums[lt]);
        }
    }
    swap(nums[left], nums[lt]);
    return lt;
}
void quickSort(vector<int> &nums, int left, int right)
{
    if (left < right)
    {
        int pIndex = partition(nums, left, right);
        quickSort(nums, left, pIndex - 1);
        quickSort(nums, pIndex + 1, right);
    }
};

int main()
{
    vector<int> test(20);
    srand((unsigned)time(NULL));
    for (int i = 0; i < test.size(); ++i)
    {
        test[i] = rand() % (100);
    }
    cout << "排序前:" << endl;
    for (int i = 0; i < test.size(); ++i)
    {
        cout << test[i] << " ";
    }
    cout << endl;
    cout << "排序后:" << endl;
    quickSort(test, 0, test.size() - 1);
    for (int i = 0; i < test.size(); ++i)
    {
        cout << test[i] << " ";
    }
    cout << endl;
    return 0;
}

选择问题

数组中的第K个最大元素

class Solution
{
public:
  int partition(vector<int> &nums, int left, int right)
  {
    srand((unsigned)time(NULL));
    int randomIndex = rand() % (right - left + 1) + left;
    swap(nums[left], nums[randomIndex]);

    int pivot = nums[left];
    int lt = left;
    for (int i = left + 1; i <= right; ++i)
    {
      if (nums[i] < pivot)
      {
        ++lt;
        swap(nums[i], nums[lt]);
      }
    }
    swap(nums[left], nums[lt]);
    return lt;
  }
  int quickSort(vector<int> &nums, int left, int right, int k)
  {
    int pIndex = partition(nums, left, right);
    if (pIndex == nums.size() - k)
    {
      return nums[pIndex];
    }
    else
    {
      return pIndex < nums.size() - k ? quickSort(nums, pIndex + 1, right, k) : quickSort(nums, left, pIndex - 1, k);
    }
  }
  int findKthLargest(vector<int> &nums, int k)
  {
    int n = nums.size();
    return quickSort(nums, 0, n - 1, k);
  }
};

整数划分

#include <iostream>
using namespace std;
int a[50] = {0};
int n, sum = 1;
bool flag = true;
void dfs(int num, int step) {
	if(num == n) {
		if(sum % 4 != 1) cout << ";";
		cout << num << "=" << a[1];
		for(int i = 2; i < step; i++) cout << "+" << a[i];
		if(sum % 4 == 0) cout << endl;
		sum++;
	}
	if(num > n) return ;
	for(int i = 1; i <= n; i++) {
		a[step] = i;
		if(a[step] >= a[step - 1]) dfs(num + i, step + 1);
	}
}
int main() {
	cin >> n;
	dfs(0, 1);
	return 0;
}

结语

文章仅作为个人学习笔记记录，记录从0到1的一个过程

希望对您有一点点帮助，如有错误欢迎小伙伴指正