临时做题总结

题目链接

4个物品，背包的体积为8，选出最大价值

打的表

代码

#include
#include

using namespace std;

const int N=1010,M=1010;
int dp[N][M];
int n,v;

int main(){
    cin>>n>>v;
    for(int i=1;i<=n;i++){
        int a,b;
        cin>>a>>b;
        for(int j=0;j<=v;j++){
            if(j>=a)dp[i][j]=max(dp[i-1][j],dp[i-1][j-a]+b);
            else dp[i][j]=dp[i-1][j];
        }
    }
    cout< 
纸牌博弈 
题目链接
 
样例 
输入：
 
4
1 2 100 4
 
输出：
 
101
 
输入：
 
5
1 2 100 4 2
 
输出：
 
101
 
暴力递归
 
 
 
函数fun1（int start,int end）代表绝顶聪明的人在局面为（start，end）先手会做出什么决策
 
 
函数fun2（int start,int end）代表绝顶聪明的人在局面为（start，end）后手会做出什么决策
 
 
#include

using namespace std;

const int N=5010;
int arr[N];
int n;

int fun2(int start,int end);

int fun1(int start,int end){
    if(start==end)return arr[start];
    int a=arr[start]+fun2(start+1,end);
    int b=arr[end]+fun2(start,end-1);
    return max(a,b);
}

int fun2(int start,int end){
    if(start==end)return 0;
    //后手的两种情况
    int a=fun1(start+1,end);
    int b=fun1(start, end-1);
    return min(a,b);
}

int main(){
    cin>>n;
    for(int i=0;i>arr[i];
    int a=fun1(0,n-1);
    int b=fun2(0,n-1);
    cout< 
备忘录优化
 
#include
#include

using namespace std;

const int N=5000;
int arr[N];
int f1[N][N],f2[N][N];
int n;

int fun2(int start,int end);

int fun1(int start,int end){
    if(f1[start][end]!=-1)return f1[start][end];
    if(start==end) f1[start][end]= arr[start];
    else{
        int a=arr[start]+fun2(start+1,end);
        int b=arr[end]+fun2(start,end-1);
        f1[start][end]=max(a,b);
    }
    return f1[start][end];
}

int fun2(int start,int end){
    if(f2[start][end]!=-1)return f2[start][end];
    if(start==end)f2[start][end]=0;
    else{
        int a=fun1(start+1,end);
        int b=fun1(start, end-1);
        f2[start][end]=min(a,b);
    }
    return f2[start][end];
}

int main(){
    cin>>n;
    for(int i=0;i>arr[i];
    memset(f1,-1,sizeof f1);
    memset(f2,-1,sizeof f2);
    int a=fun1(0,n-1);
    int b=fun2(0,n-1);
    cout< 
补充：博弈问题常见的先手胜负问题
 
#include

using namespace std;

const int N=5010;
int arr[N];
int n;

bool fun(int start,int end,int a,int b){
    if(start==end)return a+arr[start]>b;
    if(!fun(start+1,end,b,a+arr[start])||!fun(start,end-1,b,a+arr[end]))return true;
    return false;
}

int main(){
    cin>>n;
    for(int i=0;i>arr[i];
    bool flag=fun(0,n-1,0,0);
    cout< 
捡石头 
题目链接
 
题目解析
 
二维数组旋转打印 
题目链接
 
class Solution {
	public void rotate(int[][] matrix) {
		int l = 0;// top left
		int r = matrix.length - 1;// low right
		while (r > l) {
            fun(l,r,matrix);
			r--;
			l++;
		}
	}
    void fun(int l,int r,int[][] matrix){
        for (int i = l; i < r; i++) {
			int temp = matrix[l][i];
			matrix[l][i] = matrix[r - (i - l)][l];
			matrix[r - (i - l)][l] = matrix[r][r - (i - l)];
			matrix[r][r - (i - l)] = matrix[l + (i - l)][r];
			matrix[l + (i - l)][r] = temp;
		}
    }
}
 
螺旋矩阵 
题目链接
 
class Solution {
    public List spiralOrder(int[][] matrix) {
        int rc=0;
        int r2=matrix.length-1;
        int c2=matrix[0].length-1;
        ArrayListres=new ArrayList();
        while(r2>=rc&&c2>=rc){
            fun(rc,r2,c2,matrix,res);
            rc++;r2--;c2--;
        }
        return res;
    }

    void fun(int rc,int r2,int c2,int[][] matrix,ArrayListres){
        if(rc==r2&&rc==c2){
            res.add(matrix[rc][rc]);
            return;
        }
        if(rc==r2){
            for(int i=rc;i<=c2;i++)res.add(matrix[rc][i]);
            return;
        }
        if(rc==c2){
            for(int i=rc;i<=r2;i++)res.add(matrix[i][c2]);
            return;
        }
        for(int i=rc;irc;i--)res.add(matrix[r2][i]);
        for(int i=r2;i>rc;i--)res.add(matrix[i][rc]);
    }

}
 
字符串查找 
有两个字符串，子串/母串
 
子串=abc
 母串=dabef(cba)kkk
 让在母串中，找到子串第一次匹配位置
 注解：子串的位置可以变化
 
要求时间复杂度o(n)
 
//主要是将判断的时间复杂度化为常数
 
求超过1/2的元素 
 
 
思路：关键在于相互抵消之后存在的元素就是结果（两个互相不相同的元素可以相互抵消）
 
 
题目链接
 
class Solution {
    public int majorityElement(int[] nums) {
        int cnt=1;
        int num=nums[0];
        for(int i=1;i 
补充：求超过n/3次的元素
 
题目链接