1递归

#include<iostream>
using namespace std;
int f(int n)
{
	int res;
	if(n==1)
	{
		res=1; 
	}
	else
	{
		res=f(n-1)+3;
	}
    return num;
}
int main()
{
	int a;
	cin>>a;
	cout<<f(a)<<endl;
}

#include<iostream>
using namespace std;
int f(int n)
{
	int num;
	if(n==1)
	{
		num=2;
	}
	else
	{
		num=f(n-1)*2;
	}
	return num;
}
int main()
{
    int a;
    cin>>a;
    cout<<f(a)<<endl;
	
}

#include<iostream>
using namespace std;
int f(int n)
{
	int num;
	if(n<=1)//include 0 and 1
	{
		num=1;
	}
	else
	{
		num=n*f(n-1);
	}
	return num;
}
int main()
{
	int a;
	cin>>a;
	cout<<f(a)<<endl;
}

2递推（利用数组）

斐波那契数列

输出n小于五十的斐波那契数列之和

#include<iostream>
using namespace std;
int main()
{
	long long arr[60];
	arr[1]=1;
	arr[2]=1;
	long long sum=1;
	for(int i=3;i<51;i++)
	{
		
		arr[i]=arr[i-1]+arr[i-2];
		sum+=arr[i];
	}
	cout<<sum<<endl;
	
	return 0;
}

#include<iostream>
using namespace std;
int main()
{
	int n;
	cin>>n;//输入层数 
	int level=1;
	long long sum=1;//初始化为1 
	for(int i=2;i<n+1;i++)//从2开始 
	{
	  level = level+i;//后一层比前一层多i，右边先成立，再是左边被赋值 
	  sum+=level;
	}
	cout<<sum<<endl;
	return 0;
	
}

3二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果 target 存在返回下标，否则返回 -1。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left=0;
        int right=nums.size()-1;//()不要忘了！！！
        while(left<=right)
        {
            int mid=(right-left)/2+left;//!!!!
            int num=nums[mid];
            if(num==target)
            {
                return mid;
                //为什么不用break
            }
            else if(num<target)
            {
                left=mid+1;
            }
            else
            {
                right=mid-1;
            }
        }
        return -1;//会和上面的return冲突吗？
    }
};

当两个指针都停下时，a[i] 和 a[j] 都是放错位置的数，交换它们就能让数组更有序。

5动态规划之数塔问题

vector<vector<int>>：一个存放 vector<int> 的 vector，也就是二维数组

#include<iostream>
using namespace std;
int n;
int dp[110][110];
int t[110][110];
void d()
{
    for(int j=1;j<n+1;j++)//bottom
    {
        dp[n][j]=t[n][j];
    }
    for(int i=n-1;i>=1;i--)
    {
        for(int j=1;j<=i;j++)
        {
            dp[i][j]=t[i][j]+max(dp[i+1][j],dp[i+1][j+1]);
        }
    }
    cout<<dp[1][1]<<endl;
}
int main()
{
    
    cin>>n;
    for(int i=1;i<n+1;i++)
    {
        for(int j=1;j<i+1;j++)
        {
            cin>>t[i][j];
        }
    }
    d();
    return 0;
}

• return mid;：直接结束整个函数，并把 mid 返回给调用者。函数一旦执行 return，后面的所有代码都不会执行，不需要也不能再写 break。

• 不会冲突。因为：

• 如果循环里找到了目标，return mid; 会立刻结束函数，return -1; 永远不会被执行。

• 如果循环全部走完都没找到目标，循环正常退出，然后才会执行 return -1;。

• 4快速排序

• 快速排序的完整过程

• 选基准（你已会）

• 分区：把比基准小的放左边，比基准大的放右边（你已会）

• 递归：对左右两部分分别再做同样的操作，直到每部分只剩一个数

• class Solution {
  public:
      void sortColors(vector<int>& nums) {
          int p0=0;
          int p1=0;
          int n=nums.size();
          for(int i=0;i<n;i++)
          {
              if(nums[i]==1)
              {
                  swap(nums[i],nums[p1]);
                  p1++;
              }
              else if(nums[i]==0)
              {
                  swap(nums[i],nums[p0]);
                 
                  if(p0<p1)
                  {
                      swap(nums[i],nums[p1]);
                  }
                  p0++;
                  p1++;
              }
          }
      }
  };

• 这段代码在干什么？

  快速排序的核心是“划分”：选一个基准值 p，把数组分成两部分，左边都 ≤ p，右边都 ≥ p。

  你的代码用 两个指针 i 和 j 从两端向中间扫描：

• i 从左边开始，找 大于或等于 基准的数（因为 while(a[i] < p) i++; 遇到 ≥p 就停）

• j 从右边开始，找 小于或等于 基准的数（因为 while(a[j] > p) j--; 遇到 ≤p 就停）

#include<iostream>
using namespace std;
int n;
int dp[110][110];
int t[110][110];
void d()
{
    for(int j=1;j<n+1;j++)//bottom
    {
        dp[n][j]=t[n][j];
    }
    for(int i=n-1;i>=1;i--)
    {
        for(int j=1;j<=i;j++)
        {
            dp[i][j]=t[i][j]+max(dp[i+1][j],dp[i+1][j+1]);
        }
    }
    cout<<dp[1][1]<<endl;
}
int main()
{
    
    cin>>n;
    for(int i=1;i<n+1;i++)
    {
        for(int j=1;j<i+1;j++)
        {
            cin>>t[i][j];
        }
    }
    d();
    return 0;
}

6动态规划最大子数组和

给定一个整数数组 nums，请找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

#include<iostream>
using namespace std;
int n;//数组个数 
int t[1000];//当前 
int dp[1000];//局部最值
int gm;//全部最值 
int main()
{
	cin>>n;
	for(int i=1;i<n+1;i++)
	{
		cin>>t[i];
	}
	dp[1]=t[1];
	gm=t[1];
	for(int i=2;i<n+1;i++)
	{
		dp[i]=max(dp[i-1]+t[i],t[i]);
		gm=max(dp[i],gm);
	}
	cout<<gm<<endl;
	return 0;
}

7冒泡排序

#include<iostream>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int a[1000];
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	for(int i=0;i<n-1;i++)
	{
		for(int j=0;j<n-i-1;j++)
		{
			if(a[j]>a[j+1])
			{
				int tem=a[j];
				a[j]=a[j+1];
				a[j+1]=tem;
			}
		}
	}
	for(int i=0;i<n;i++)
	{
		cout<<a[i]<<" ";
		
	 } 
	 cout<<endl;
	return 0;
}

8选择排序：为第一个位置找合适的人

#include<iostream>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int a[1000];
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
    for(int i=0;i<n-1;i++)//只需比较size-1
	{
		for(int j=i+1;j<n;j++)
		{
			if(a[i]>a[j])
			{
				int tem=a[i];
				a[i]=a[j];
				a[j]=tem;
			}
		}
	 } 
	for(int i=0;i<n;i++)
	{
		cout<<a[i]<<" ";
		
	 } 
	 cout<<endl;
	return 0;
}

9回文字符串（双指针）

#include<iostream>
#include<string>
using namespace std;
int main()
{
	string a;
	cin>>a;
	int i=0;
	int j=a.size()-1;
	while(i<j)
	{
		if(a[i]!=a[j])
		{
			cout<<"no"<<endl;
			return 0;
		}
		i++;
		j--;
	}
	cout<<"yes"<<endl;
	return 0;
}

1. 函数参数是常量指针/引用，且传入的是常量对象

cpp

复制

下载

void print(const string& s) { cout << s; }
int main() {
    const string name = "Alice";
    print(name);   // 如果 print 参数不加 const，这里编译失败
}

考点：只能把 const 对象传给 const 引用/指针参数。不加 const 就无法接收常量实参。

10质数判断 最大公约数

#include<iostream>
using namespace std;
int main()
{
	int n;
	cin>>n;
	for(int i=2;i*i<=n;i++)//!!!
	{
		if(n%i==0)
		{
			cout<<"false"<<endl;
			return 0;
		}
	
	}
	cout<<"true"<<endl;
	return 0;
}

#include<iostream>
using namespace std;
int main()
{
	int a,b;
	cin>>a>>b;
	while(b!=0)//!!
	{
		int r=a%b;
		a=b;
		b=r;
	}
	cout<<a<<endl;//!! 
	return 0;
}