C++文件操作

简单C++文件操作

#include <stdio.h>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>
#include <fstream>
using namespace std;
int main()
{
    //const char* ifile ="/Users/yangshucheng/Desktop/C++/fushi/fushi/in.txt";
    const char* ofile ="/Users/yangshucheng/Desktop/C++/fushi/fushi/out.txt";
    char name[100];
    string age;
    ofstream outfile;
    outfile.open(ofile);
    cout << "Write" << endl;
    cout << "name:";
    cin.getline(name, 100);
    outfile << name <<endl;
    cout << "age:";
    cin >> age;
    cin.ignore();
    outfile << age <<endl;
    outfile.close();
    ifstream infile;
    infile.open(ofile);
    cout << "Reading from the file" << endl;
    infile >> name;
    cout << name << endl;
    infile >> age;
    cout << age << endl;
    infile.close();
    return 0;
}

Write

name:zara

age:12

Reading from the file

zara

12

约瑟夫环+文件处理

#include <stdio.h>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>
#include <fstream>
#include <queue>
using namespace std;
int arr[100][3];
int main()
{
    const char* ifile ="/Users/yangshucheng/Desktop/C++/fushi/fushi/in.txt";
    const char* ofile ="/Users/yangshucheng/Desktop/C++/fushi/fushi/out.txt";
    ifstream in(ifile);
    ofstream out(ofile);
    int length = 0;
    for (int i = 0; i < 100; ++i) {
        for (int j = 0; j < 3; ++j) {
            in >> arr[i][j];
        }
        if(arr[i][0] == 0 && arr[i][0] == 0 && arr[i][0] == 0){
            length = i + 1;
            break;
        }
    }
    int m,n,p;
    for (int i = 0; i < length; i++) {
        n = arr[i][0];
        p = arr[i][1];
        m = arr[i][2];
        if (m == 0 && n == 0 && p == 0) {
            break;
        }
        queue<int> children;
        for (int i = 1; i <= n; ++i) {//将1,2,3...n入队
            children.push(i);
        }
        for (int i = 1; i < p; ++i) {//for循环线判断中间的判断式子是否为真再决定是否继续执行
            children.push(children.front());//从编号p开始计算,需要编号p放到队头
            children.pop();
        }
        while (!children.empty()) {
            for (int i = 1; i < m; ++i) {//m-1个小孩依次重新入队
                children.push(children.front());
                children.pop();
            }
            int x = children.front();
            if (children.size() == 1) {//最后一个小孩的输出不同
                out << x <<endl;
                //printf("%d\n",x);
            } else{
                out << x <<",";
            }
                //printf("%d,",x);}
            children.pop();
        }
    }
    return 0;
  
}

经典基础

反序数

#include <stdio.h>
#include <iostream>
#include <math.h>
using namespace std;
int converseNum(int num){
    int a = 0;
    while (num!=0) {
        a *= 10;
        a += num % 10;
        num /= 10;
    }
    return a;
}
int main(){
    int x;
    for (int n = 1; n<=9999; n++) {
        x = converseNum(n);
        if(x == 9 * n){
         printf("%d\n",n);
    }
    }
    return 0;
}

对称平方数

#include <stdio.h>
#include <iostream>
#include <math.h>
using namespace std;
int converseNum(int num){
    int a = 0;
    while (num!=0) {
        a *= 10;
        a += num % 10;
        num /= 10;
    }
    return a;
}
int main(){
    int x,y;
    for (int n = 0; n<=256; n++) {
        x = n * n;
        y = converseNum(x);
        if(x == y){
         printf("%d\n",n);
    }
    }
    return 0;
}

叠框

#include <stdio.h>
#include <iostream>
#include <math.h>
using namespace std;
char G[100][100];
void change(char* x,char* y){
    char* tmp = x;
    x = y;
    y = tmp;
}
int main(){
    int n;
    char a,b;
    bool flag = true;
    char c;//当前填充的字符
    int len;//当前填充的长度
    while (scanf("%d %c %c",&n,&a,&b)!=EOF) {
        for (int i = 0; i < 99; ++i) {
            for (int j = 0; j < 99; ++j) {
                G[i][j] = ' ';
            }
        }
        if (flag) {
            flag = false;
        } else{
            printf("\n");
        }
        for (int i = 0; i <= (n/2); i++) {
            int j = n - i - 1;
                if ((n/2 - i) % 2 == 0 ) {
                    c = a;
                } else{
                    c = b;
                }
                len = n - 2*i;
                for (int k = 0; k < len; k++) {
                    G[i][i + k] = c;//上方
                    G[i + k][i] = c;//左方
                    G[j][j - k] = c;//下方
                    G[j - k][j] = c;//右方
                }
          
          
        }
        G[0][0] = G[0][n-1] = G[n-1][0] = G[n-1][n-1] = ' ';
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                printf("%c",G[i][j]);
            }
            printf("\n");
        }
      
    }
    return 0;
}

日期累加

#include <stdio.h>
#include <iostream>
#include <math.h>
using namespace std;
int daytab[2][13] = {
    {0,31,28,31,30,31,30,31,31,30,31,30,31},
    {0,31,29,31,30,31,30,31,31,30,31,30,31}
};
bool isLeapYear(int year){
    return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
};
int NumOfYear(int year){
    if (isLeapYear(year)) {
        return 366;
    } else{
        return 365;
    }
};
int main(){
    int caseNum;
    int year,month,day,dayNum;
    scanf("%d",&caseNum);
    while (caseNum--) {
        scanf("%d %d %d %d",&year,&month,&day,&dayNum);
        int row = isLeapYear(year);
        for (int i = 0; i < month ; i++) {
            dayNum += daytab[row][i];
        }
        dayNum += day;
        while (dayNum > NumOfYear(year)) {
            dayNum -= NumOfYear(year);
            year++;
        }
        int j;
        row = isLeapYear(year);
        for (j = 0; dayNum > daytab[row][j]; ++j) {
            dayNum -= daytab[row][j];
        }
        printf("%04d-%02d-%02d\n",year,j,dayNum);
      
    }
    return 0;
}

排序

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
int a[100];
int main(){
    int num;
    while(scanf("%d",&num)!=EOF){
        for (int i = 0; i < num; i++) {
            scanf("%d",&a[i]);
        }
        sort(a, a + num);
        for (int i = 0; i < num; i++) {
            printf("%d ",a[i]);
        }
        printf("\n");

    }
        return 0;
}

快速排序

#include<iostream>
#include<vector>
#include <algorithm>
using namespace std;
void QuickSort(vector<int>& arr, int begin, int end)
{
    if (begin >= end)return;
    int first = begin;
    int last = end;
    int key = arr[first];
    while (first < last)
    {
        while (first < last && key <= arr[last])
            last--;
        arr[first] = arr[last];
        while (first < last && key >= arr[first])
            first++;
        arr[last] = arr[first];
    }
    arr[first] = key;
    QuickSort(arr, first + 1, end);
    QuickSort(arr, begin, first - 1);
}

int main()
{
    vector<int>a = { 6,5,7,8,1,3,4,9,2,0 };
    QuickSort(a, 0, a.size() - 1);
    for (int i = 0; i < a.size(); ++i) {
        cout << a[i] << " ";
    }
    return 0;
}
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
int a[100];
void QuickSort(int a[],int low,int high){
    if(low<high){
        int  i =low,j = high;
        int temp;
        temp = a[i];
        while(i<j){
            while(i<j&&a[j]>=temp) j--;
            if(i<j){
                a[i] = a[j];
                i++;
            }
            while(i<j&&a[i]<=temp) i++;
            if(i<j){
                a[j] = a[i];
                j--;
            }
        }
        a[i] = temp;
        QuickSort(a,low,i-1);
        QuickSort(a,i+1,high);
    }
}
int main(){
    int num;
    while(scanf("%d",&num)!=EOF){
        for (int i = 0; i < num; i++) {
            scanf("%d",&a[i]);
        }
        QuickSort(a, 0, num - 1);
        for (int i = 0; i < num; i++) {
            printf("%d ",a[i]);
        }
        printf("\n");
    }
  
    return 0;
}

快速排序,mid

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
int a[110];
void quicksort(int a[], int left, int right) {
    if (left >= right) {
        return;
    }//递归结束条件
    int i = left, j = right;
    int mid = left + (right - left) / 2;
    swap(a[left], a[mid]);
    while (i != j) {
        while (i < j && a[i] < a[left]) i++;
        while (i < j && a[j] >= a[left]) j--;
        swap(a[i], a[j]);
    }
    mid = j;
    swap(a[left], a[mid]);
    quicksort(a, left, mid - 1);//i左边递归
    quicksort(a, mid + 1, right);//j右边递归
}
int main() {
    int num;
    while (scanf("%d", &num) != EOF) {
        for (int i = 0; i < num; i++) {
            scanf("%d", &a[i]);
        }
        quicksort(a, 0, num - 1);
        for (int i = 0; i < num; i++) {
            printf("%d ", a[i]);
        }
        printf("\n");
    }
  
    return 0;
}

成绩排序

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
struct Student{
    int grade;
    int id;
    string name;
};
bool Ascend(Student a,Student b){
    if (a.grade == b.grade) {
        return a.id < b.id;
    } else{
        return a.grade < b.grade;
    }
}
bool Descend(Student a,Student b){
    if (a.grade == b.grade) {
        return a.id < b.id;
    } else{
        return a.grade > b.grade;
    }
}
int main() {
    int number;
    int way;
    while(scanf("%d %d",&number,&way)!=EOF){
    Student Stu[number];//在这里产生学生数组,防止数组溢出
    for (int i = 0; i < number; i++) {
        cin>>Stu[i].name>>Stu[i].grade;
        Stu[i].id = i;
    }
    if (way == 0) {
        sort(Stu, Stu + number, Descend);
     
    } else{
        sort(Stu, Stu + number, Ascend);
    }
        for (int j = 0; j < number; j++ ) {
            cout<<Stu[j].name<<" "<<Stu[j].grade<<endl;
        }
    }
    return 0;
}

二分查找

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
bool BinarySearch(int a[],int n,int x){
    int left = 0,right = n - 1;
    while (left <= right) {//left = right时也要确定是否a[left] = x
        int mid = left + (right - left) / 2;
        if (a[mid] < x) {
            left = mid + 1;
        }else if (a[mid] > x){
            right = mid - 1;
        }else{
            return true;
        }
    }
    return false;
}
int main() {
    int num,m;
    while(scanf("%d",&num)!=EOF){
        int arr[num];
        for (int i = 0; i < num; i++) {
            scanf("%d",&arr[i]);
        }
        sort(arr,arr + num);
        scanf("%d",&m);
        int m_arr[m];
        for (int i = 0; i < m; i++) {
            scanf("%d",&m_arr[i]);
            if(BinarySearch(arr, num,m_arr[i]) == true){
                printf("YES\n");
            } else {
                printf("NO\n");
            };
        }
    }
    return 0;
}

特殊乘法

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int main() {
    string a,b;
    while(cin>>a>>b){
    int sum = 0;
    for (int i = 0; i < a.length(); i++) {
        for (int j = 0; j < b.length(); j++) {
            sum += (a[i] - '0')*(b[j] - '0');
        }
    }
    cout<<sum;
    }
    return 0;
}

简单密码

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int main() {
    string str;
    while (getline(cin,str)) {
        if (str == "ENDOFINPUT") {
            break;
        }
        getline(cin, str);
        for (int i = 0; i < str.size(); ++i) {
            if (str[i] >='A' && str[i] <='Z' ) {
                str[i] = 'A' + (str[i] - 'A' - 5 + 26) % 26;//原来字母往前找5位为正确字母
            }
        }
        cout<<str<<endl;
        getline(cin, str);
    }
  
    return 0;
}

字符统计

#include <stdio.h>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int number[128];
int main() {
    string Fstr,str;
    while (getline(cin, Fstr)) {
        if (Fstr == "#") {
            break;
        }
        memset(number, 0, sizeof(number));
        getline(cin, str);
        for (int j = 0; j < str.size(); ++j) {
                number[str[j]]++;
            }
        for (int i = 0; i < Fstr.size(); ++i) {
            cout<<Fstr[i]<<" "<<number[Fstr[i]]<<endl;
        }
    }

    return 0;
}

字母统计

#include <stdio.h>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int number[26];
int main() {
    string str;
    while (getline(cin, str)) {
        memset(number, 0, sizeof(number));
        for (int j = 0; j < str.size(); ++j) {
            if ('A' <= str[j] && str[j] <= 'Z') {
                number[str[j]-'A']++;
            }
            }
        for (int i = 0; i < 26; i++) {
            printf("%c:%d\n",'A' + i,number[i]);
        }
    }

    return 0;
}

KMP算法

image-20200301093704712

image-20200301093831856

image-20200301093857744

KMP简单匹配

#include <stdio.h>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
//const int MAXN = 10000;
//const int MAXM = 1000000;
int nextTable[20];
void GetNextTable(string pattern){
    int n = pattern.size();
    int j = 0;
    nextTable[j] = -1;
    int t = nextTable[j];//t保存当前已经算好的next数组的值(next数组存的是pattern的下标)
    while(j < n) {
        if (t == -1 || pattern[t] == pattern[j]) {
            ++j;
            ++t;
            nextTable[j] = t;
        } else{
            t = nextTable[t];//不匹配t返回上一个next数组的值继续进行比较
        }
    }
    return;
}
int KMP(string pattern,string text){
    GetNextTable(pattern);
    int m = text.size();//必须把数组长度先赋值给int型变量,不然后面循环判断会出错
    int n = pattern.size();
    int i = 0;
    int j = 0;
    while (j < n && i < m) {//一直匹配直到匹配结束
        if (j == -1 || pattern[j] == text[i]) {
            ++i;
            ++j;
        } else{
            j = nextTable[j];
        }
    }
    if (j == pattern.size() ) {//完全匹配成功后 j 小标为数组长度
        return i-j;
    }else{
        return -1;
    }
}
int main() {
    string a = "i love you ";
    string b = "you";
    int x = KMP(b, a);
    printf("%d",x);
    return 0;
}

记录字符串匹配次数

#include <stdio.h>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
//const int MAXN = 10000;
//const int MAXM = 1000000;
int nextTable[1000];
void GetNextTable(string pattern){
    int n = pattern.size();
    int j = 0;
    nextTable[j] = -1;
    int t = nextTable[j];
    while(j < n) {
        if (t == -1 || pattern[t] == pattern[j]) {
            ++j;
            ++t;
            nextTable[j] = t;
        } else{
            t = nextTable[t];//不匹配返回上一个next数组的下标继续进行比较
        }
    }
    return;
}
int KMP(string pattern,string text){
    GetNextTable(pattern);
    int m = text.size();//必须把数组长度先赋值给int型变量,不然后面循环判断会出错
    int n = pattern.size();
    int i = 0;
    int j = 0;
    int times = 0;
    while (i < m) {//记录匹配次数,需要一直匹配直到i到了文本的最后一个字符
            if (j == -1 || pattern[j] == text[i]) {
                ++i;
                ++j;
            } else{
                j = nextTable[j];
            }
        if (j == n ) {//完全匹配成功一次后 j 小标为数组长度,统计成功数目
            j = nextTable[j];
            times++;
        }
        }
    return times;
}
int main() {
    int caseNumber;
    scanf("%d",&caseNumber);
    while (caseNumber--) {
        string text, pattern;
        cin >> pattern >> text;
        printf("%d\n",KMP(pattern, text));
    }
    return 0;
}

完数与盈数

#include <stdio.h>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
vector<int> numG;
vector<int> numE;
int Sum(int n){
    int sum = 0;
    for (int i = 1; i < n; ++i) {
        if ((n % i) == 0) {
            sum += i;
        }
    }
    return sum;
}
int main() {
    for (int i = 2; i <= 60; ++i) {
        if (Sum(i) == i) {
            numE.push_back(i);
        } else if (Sum(i) > i){
            numG.push_back(i);
        }
    }
    printf("E: ");
    for (int i = 0; i < numE.size(); ++i) {
        printf("%d ",numE[i]);
    }
    printf("\n");
    printf("G: ");
    for (int i = 0; i < numG.size(); ++i) {
        printf("%d ",numG[i]);
    }
    return 0;
}

约瑟夫问题

队列解法

#include <stdio.h>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;

int main() {
    int n,m,p,x;
    while(scanf("%d%d%d",&n,&p,&m)!=EOF){
        if (m == 0 && n == 0 && p == 0) {
            break;
        }
        queue<int> children;
        for (int i = 1; i <= n; ++i) {//将1,2,3...n入队
            children.push(i);
        }
        for (int i = 1; i < p; ++i) {//for循环线判断中间的判断式子是否为真再决定是否继续执行
            children.push(children.front());//从编号p开始计算,需要编号p放到队头
            children.pop();
        }
        while (!children.empty()) {
            for (int i = 1; i < m; ++i) {//m-1个小孩依次重新入队
                children.push(children.front());
                children.pop();
            }
            x = children.front();
            if (children.size() == 1) {//最后一个小孩的输出不同
                printf("%d\n",x);
            } else{
                printf("%d,",x);}
            children.pop();
        }
}
    return 0;
}

数组解法

#include <stdio.h>
using namespace std;
#define N 100
int main()
{
    int n,m,s;
    scanf("%d%d%d",&n,&m,&s);//s是数组起点
    int a[N] = {0};//数组初始化
    int i,j;
    for(i = 0; i < n; i++)//数组遍历
    {
        a[i] = i+1;
    }
    i=s-1;//数组起点
    while (n > 1)
    {
        i = (i + m - 1) % n;// 淘汰的人
        printf("%d\n",a[i]);
        for(j = i+1; j < n; j++)//淘汰后将后面的数字往前移动
        {
            a[j-1] = a[j];
        }
        n--;
        if(i == n)//终点后,开始起点
        {
            i = 0;
        }
    }
    printf("%d\n", a[i]);
    return 0;
}

文件操作

简单打开文件,写入char数组

#include <stdio.h>
#include <cstring>
#include <iostream>
#include <string>
using namespace std;
int main()
{
    const char* filename ="/Users/yangshucheng/Desktop/C++/fushi/fushi/test.txt";
    FILE* fp = fopen(filename, "wb");
    char a[] = "hello number";
    if (fp == NULL) {
        cout << "文件打开失败!" << endl;
        exit(0);
    }
    fwrite(a, 1, sizeof(a), fp);
    fclose(fp);

    return 0;
}

猫狗收容所

回文数组判断

#include <iostream>
#include <stack>
#include <string>
using  namespace std;
string match(string str){
    string pa = str;
    for (int i = 0; i < str.size(); i++) {
        pa[i] = str[str.size() - 1 - i];
    }
    return pa;
}
int main()
{
    string str;//size_t 为unsigned int
    cout << "请输入需要判断的字符串"<<endl;
    cin >> str;
    if( str == match(str)  ){
        cout << "YES";
    }else{
        cout << "NO";
    }
    return 0;
}

利用栈的方法

#include <iostream>
#include <stack>
#include <string>
using  namespace std;
int main()
{
    string str;//size_t 为unsigned int
    cout << "请输入需要判断的字符串"<<endl;
    cin >> str;
    stack<char> pa ;
    string paa;
    for (int i = 0; i < str.size(); i++) {
        pa.push(str[i]);
    }
    for (int i = 0; i < str.size(); i++) {
        if (pa.top() != str[i]) {
            cout << "NO";
            return 0;
        } else{
            pa.pop();
        }
    }
    cout << "YES";
    return 0;
}

表达式括号匹配判断

#include <iostream>
#include <stack>
#include <string>
using  namespace std;
bool match(string str){
    stack<char> sta;
    for (int i = 0; i < str.size(); i++) {
        if (str[i] == '(' || str[i] == '[' || str[i] == '{') {
            sta.push(str[i]);
        }else if (str[i] == ')' || str[i] == ']' || str[i] == '}'){
            char a = sta.top();
            if ( (a == '(' && str[i] == ')') || 
                (a == '{' && str[i] == '}') || 
                (a == '[' && str[i] == ']')) {
                sta.pop();
            } else{
                return false;
            }
        }
      
    }
    if (!sta.empty()) {
        return false;
    }
    return true;
}
int main()
{
    string str;//size_t 为unsigned int
    cout << "请输入需要配对的字符串"<<endl;
    cin >> str;
    if(match(str)){
        cout << "YES";
    } else{
        cout << "NO";
    }
    return 0;
}

转换为后缀表达式求值

转换为后缀表达式(字母+括号+四则运算)

#include <iostream>
#include <map>
#include <stack>
#include <string>
#include <ctype.h>
using namespace std;
int main(){
    string s;
    cin>>s;
    stack<char> S;
    map<char,int> P;
    P['+'] = P['-'] = 1;
    P['*'] = P['/'] = 2;
    for(int i=0;i<s.length();i++){
        if(s[i] == '('){
            S.push(s[i]);
            continue;
        }
        if (s[i] == ')') {
            while(S.top() != '('){
                cout<<S.top();
                S.pop();
            }
                S.pop();
            }
        if(isalpha(s[i]))
            cout<<s[i];
        else{
            while(!S.empty() && P[s[i]]<=P[S.top()]  && s[i]!= ')'){
                cout<<S.top();
                S.pop();
            }
            if (s[i] != ')') {
                S.push(s[i]);
            }
        }
    }
    while(!S.empty()){
        cout<<S.top();
        S.pop();
    }
    cout<<endl;
    return 0;
}

转换为后缀表达式(数字+括号+四则运算)

#include <iostream>
#include <map>
#include <stack>
#include <string>
#include <ctype.h>
using namespace std;
int main(){
    string s;
    cin>>s;
    stack<char> S;
    map<char,int> P;
    P['+'] = P['-'] = 1;
    P['*'] = P['/'] = 2;
    for(int i=0;i<s.length();i++){
        if(s[i] == '('){
            S.push(s[i]);
            continue;
        }
        if (s[i] == ')') {
            while(S.top() != '('){
                cout<<S.top();
                S.pop();
            }
                S.pop();
            }
        if(isdigit(s[i])){
            int num = 0;
        do {
            num = num * 10 + (s[i] - '0'); // ch - 48根据ASCAII码,字符与数字之间的转换关系
            i++; // 下一个字符
        }while(isdigit(s[i]));
            cout << num;
            i--;
        }else{
            while(!S.empty() && P[s[i]]<=P[S.top()]   && S.top() != '(' && s[i]!= ')'){
                cout<<S.top();
                S.pop();
            }
            if (s[i] != ')') {
                S.push(s[i]);
            }
        }
    }
    while(!S.empty()){
        cout<<S.top();
        S.pop();
    }
    cout<<endl;
    return 0;
}

中缀转后缀,后缀再求值

#include <iostream>
#include <map>
#include <stack>
#include <string>
#include <ctype.h>
using namespace std;
string infixTosuffix(string s){//中缀表达式转后缀表达式
    stack<char> S;
    string algo;
    map<char,int> P;//优先级表
    P['+'] = P['-'] = 1;
    P['*'] = P['/'] = 2;
    for(int i=0;i<s.length();i++){
        if(s[i] == '('){//遇到‘(’直接入栈
            S.push(s[i]);
            continue;
        }
        if (s[i] == ')') {//遇到‘)’,把栈中‘(’前的运算字符依次输出
            while(S.top() != '('){
                algo += S.top();
                algo += " ";//空格为了之后后缀表达式求值能够确定多位数的边界
                S.pop();//依次弹出栈中运算字符
            }
            S.pop();//弹出‘(’符号
        }
        if(isdigit(s[i])){//遇到数字,则需要把这个数字直接保存在后缀表达式中
            int num = 0;
            do {
                num = num * 10 + (s[i] - '0'); // ch - 48根据ASCAII码,字符与数字之间的转换关系
                algo += s[i];
                i++; // 下一个字符
            }while(isdigit(s[i]));
            algo += " ";//确定数字的边界
            i--;//注意要变回当前扫描的字符
        }else{
            while(!S.empty() && P[s[i]]<=P[S.top()]   && S.top() != '(' && s[i]!= ')'){
                algo += S.top();
                algo += " ";
                S.pop();//扫描到符号的时候,如果当前扫描的符号优先级小于等于栈中符号,则出栈
            }
            if (s[i] != ')') {//当前扫描的符号优先级大于栈中符号,则入栈
                S.push(s[i]);
            }
        }
    }
    while(!S.empty()){//若栈中还有运算符号,则依次出栈
        algo += S.top();
        algo += " ";
        S.pop();
    }
    return algo;
}
int calculate(int a,int b,char ch){//根据符号来确定运算值
    switch (ch) {
        case '+':
            return a + b;
        case '-':
            return a - b;
        case '*':
            return a * b;
        case '/':
            return a / b;
    }
    return 0;
}
int result(string str){
    stack<int> S;
    for (int i = 0; i < str.size(); ++i) {//依次扫描后缀表达式
        if (isdigit(str[i])) {//遇到数字,则压入栈
            int num = 0;
            while (isdigit(str[i])) {
                num = num * 10 ;
                num += (str[i] - '0');
                ++i;
            }
            --i;
            S.push(num);
        }else if(str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/' ){
            int x = S.top();//遇到运算符号,则把栈中前两个数字拿出来进行相应的运算,得到结果后放回栈中
            S.pop();
            int y = calculate(S.top(), x, str[i]);
            S.pop();
            S.push(y);
        }
    }
    int x = S.top();
    S.pop();//栈中最后一个元素就是后缀表达式的运算结果
    return x;
}
int main(){
    string s;
    cin>>s;
    s = infixTosuffix(s);
    cout << s <<endl;
    cout <<result(s);
    return 0;
}
//16+2*30/4-(26-12*3)

前置表达式求值

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
double exp(){
    char s[20];
    cin >> s;
    switch (s[0]) {
        case '+':
            return exp()+exp();
        case '-':
            return exp()-exp();
        case '*':
            return exp()*exp();
        case '/':
            return exp()/exp();
        default:
            return atof(s);
        break;
    }
}
int main() {
    printf("%lf",exp());
    return 0;
}

样例输入* + 11.0 12.0 + 24.0 35.0

样例输出1357.000000

// 提示:(11.0+12.0)*(24.0+35.0)

中缀表达式求值

==数据流单调栈四则运算==

给一个用字符串表示的表达式数组,求出这个表达式的值。

样例

样例 1:

对于表达式 `2*6-(23+7)/(1+2)`,
输入:
["2", "*", "6", "-", "(","23", "+", "7", ")", "/", "(", "1", "+", "2", ")"]
输出:
2
class Solution {
public:
    /**
     * @param expression: a list of strings
     * @return: an integer
     */
   int Calculate(string chh, int a, int b) {
        int result = 0;
        char ch = chh[0];
        switch(ch) {
            case '+':
                result = b + a;
                break;
            case '-':
                result = b - a;
                break;
            case '*':
                result = b * a;
                break;
            case '/':
                result = b / a;
                break;
            default:
                break;
        } // switch结束
        return result; // 返回计算得到的结果
    }
int evaluateExpression(vector<string> &expression) {
    if(expression.size() == 0) return 0;
        map<string,int> p;
        p["+"] = 1;p["-"] = 1;p["*"] = 2;
        p["/"] = 2;p["("] = 0;p[")"] = 3;
        stack<string> operation;
        stack<int> nums;
        for(int i = 0;i < expression.size();++i){
            string c = expression[i];
            if(p.count(c) == 1){
                if(operation.empty()){
                    operation.push(c);
                    continue;
                }else{
                    if(c != "(" && c != ")"){
                    while(!operation.empty()){
                        if(p[c] <= p[operation.top()]){
                            int a = nums.top();
                            nums.pop();
                            int b = nums.top();
                            nums.pop();
                            int x = Calculate(operation.top(),a,b);
                            nums.push(x);
                            operation.pop();
                        }else{
                            break;
                        }
                    }
                        operation.push(c);
                }
                    if(c == "("){
                        operation.push(c);
                    }
                    if(c == ")"){
                        while(operation.top() != "(") {
                            string cc = operation.top(); // 取出栈顶操作符
                            int result = 0;
                            int a = nums.top(); // 第二个操作数,因为栈是后进先出
                            nums.pop();
                            int b = nums.top(); // 第一个操作数
                            nums.pop();
                            result = Calculate(cc, a, b); // 计算
                            nums.push(result);// 把计算结果压入栈中
                            operation.pop(); // 把操作符推出栈
                        }
                        operation.pop(); // 把左括号(推出栈
                    }
                }
            }else{
                int x = stoi(c);
                nums.push(x);
            }
        }
        while(!operation.empty()){
            string c = operation.top();
            int a = nums.top();
            nums.pop();
            int b = nums.top();
            nums.pop();
            int x = Calculate(c,a,b);
            nums.push(x);
            operation.pop();
        }
        if(nums.size() == 0){
            return 0;
        }
        return nums.top();
    }
};

求众数以及它的重数*

问题:在一个由元素组成的表中,出现次数最多的元素称为众数,试写一个寻找众数的算法

方法:1)对输入数据进行排序
2)从每个数字出现的第一个位置开始计数,计算出现的次数,记为count,如果大于最大众数MaxCount则更新MaxCount,并记下索引位置index

#include <iostream>
#include <algorithm> 
using namespace std;
int main()
{
    int n;
    cin >> n;
    int* a = new int[n];
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];//输入数据
    }
    sort(a, a + n);//数据由低到高进行排序
    for (int i = 0; i < n; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
    int i = 0;
    int MaxCount = 1;
    int index = 0;
    while (i < n - 1)//遍历
    {
        int count = 1;
        int j ;
        for (j = i; j < n - 1; j++)
        {
            if (a[j] == a[j + 1])//存在连续两个数相等,则众数+1
            {
                count++;
            }else
            {
                break;
            }
        }
        if (MaxCount < count)
        {
            MaxCount = count;//当前最大众数
            index = j;//当前众数标记位置
        }
        ++j;
        i = j;//位置后移到下一个未出现的数字
    }
    cout << a[index] << " " << MaxCount << endl;
    return 0;
}

数制转换

翻转字符串里的单词

给定一个字符串,逐个翻转字符串中的每个单词。

示例 1:

输入: "the sky is blue"
输出: "blue is sky the"

示例 2:

输入: " hello world! "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不能包括。

示例 3:

输入: "a good example"
输出: "example good a"
解释: 如果两个单词间有多余的空格,将反转后单词间的空格减少到只含一个。

class Solution {
public:
    string reverseWords(string s) {
        // 反转整个字符串
        reverse(s.begin(), s.end());

        int n = s.size();
        int idx = 0;
        for (int start = 0; start < n; ++start) {
            if (s[start] != ' ') {
                // 填一个空白字符然后将idx移动到下一个单词的开头位置
                if (idx != 0) s[idx++] = ' ';

                // 循环遍历至单词的末尾
                int end = start;
                while (end < n && s[end] != ' ') s[idx++] = s[end++];

                // 反转整个单词
                reverse(s.begin() + idx - (end - start), s.begin() + idx);

                // 更新start,去找下一个单词
                start = end;
            }
        }
        s.erase(s.begin() + idx, s.end());
        return s;
    }
};

递归相关

走楼梯

树老师爬楼梯,他可以每次走1级或者2级,输入楼梯的级数,求不同的走法数

思路:

n级台阶的走法 =先走一级后, n-1级台阶的走法 +先走两级后, n-2级台阶的走法
f(n) = f(n-1)+f(n-2)
边界条件:

n < 0 0 n = 0 1 n = 1 1
n = 0 1 n = 1 1 n = 2 2

#include <iostream>
#include <cstdio>
using namespace std;
int staris(int n){
    if (n < 0) {
        return 0;
    }else if (n == 0) {
        return 1;
    }else{
        return staris(n - 1) + staris(n - 2);
    }
}
int main(){
    int n;
    scanf("%d",&n);
    cout << staris(n);
    return 0;
}

算24

输入
输入数据包括多行,每行给出一组测试数据,包括4个小于10个正整数。最后一组测试数据中包括4个0,表示输入的结束,这组数据不用处理。
输出
对于每一组测试数据,输出一行,如果可以得到24,输出“YES” ;否则,输出“NO” 。

样例输入
5 5 5 1
1 1 4 2
0 0 0 0
样例输出
YES
NO

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
#define EPS 1e-6
bool isZero(double x){
    return fabs(x) <= EPS;
}
double a[5];
bool count24(double a[],int n){//用数组a里的n个数,计算24
    if (n == 1) {
        if (isZero( a[0] - 24)) {//判断是否为24
            return true;
        }else{
            return false;
        }
    }
    double b[5];
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {//枚举两个数的组合
            int m = 0;//还剩下m个数
            for (int k = 0; k < n; ++k) {
                if (m != i && m != j) {
                    b[m++] = a[k];//把其余数放入b中
                }
            }
            b[m] = a[i] + a[j];
            if (count24(b, m + 1)) {
                return true;
            }
            b[m] = a[i] - a[j];
            if (count24(b, m + 1)) {
                return true;
            }
            b[m] = a[i] * a[j];
            if (count24(b, m + 1)) {
                return true;
            }
            if (!isZero(a[i])) {
                b[m] = a[j] / a[i];
                if (count24(b, m + 1)) {
                    return true;
                }
            }
            if (!isZero(a[j])) {
                b[m] = a[i] / a[j];
                if (count24(b, m + 1)) {
                    return true;
                }
            }
        }
    }
    return false;
}
int main(){
    while (true) {
        for (int i = 0; i < 4; ++i) {
            cin >> a[i];
        }
        if (isZero(a[0])) {
            break;//第一个数为0则跳出
        }
        if (count24(a, 4)) {
            cout << "YES\n";
        }else{
            cout << "NO\n";
        }
    }
    return 0;
}

寻找第k大的数

#include<iostream>
#include<vector>
#include <algorithm>
using namespace std;
int QuickSortK(vector<int>arr, int begin, int end,int k)
{
    if (begin == end)return arr[begin];
    int first = begin;
    int last = end;
    int key = arr[first];
    while (first < last)
    {
        while (first < last && key <= arr[last])
            last--;
        arr[first] = arr[last];
        while (first < last && key >= arr[first])
            first++;
        arr[last] = arr[first];
    }
    arr[first] = key;
    if (first+1 == k)return arr[first];
    else if (first+1 < k)return QuickSortK(arr, first + 1, end, k);
    else return QuickSortK(arr, begin, first - 1, k);
}
int findk(vector<int>arr,int k)
{
    int len = arr.size();
    return QuickSortK(arr, 0, len - 1, k);
}
int main()
{
    vector<int>a = { 6,5,7,8,1,3,4,9,2,0 };
    int No = findk(a, 9);
    sort(a.begin(), a.end());//对vector的排序方法
    cout << No << endl;
    cout << a[8];
    return 0;
}

汉诺伊塔

经典汉诺伊塔

#include <iostream>
using namespace std;
void Hanoid(int n,char a,char b,char c){
    if(n == 1){//只剩下一个盘子,从A移动到C
        cout << a << " move to " << c <<endl;
    }else{
    Hanoid(n - 1, a, c, b);//还有些盘子,先把前n - 1个盘子从A经过C移动到B
    cout << a << " move to " << c << endl;//将A上的最后一个盘子移动到C上
    Hanoid(n - 1, b, a, c);//将B上的盘子经过A移动到C
        return;}
}
int main(){
    int n;
    cout << "n : ";
    cin >> n;
    Hanoid(n, 'A', 'B', 'C');
    return 0;
}

斐波那契非递归

#include <iostream>
#include <cstdio>
using namespace std;
int Fib(unsigned int n){
    unsigned int f,f1,f2;
    f = f1 = f2 = 1;
    if (n == 1 || n == 2) {
        return f;
    }
    for (int i = 3; i <= n; ++i) {
        f = f1 + f2;
        f2 = f1;
        f1 = f;
    }
    return f;
}
int main(){
    unsigned int n;
    cin >> n;
    cout << Fib(n) << endl;
    return 0;
}

放苹果

把M个同样的苹果放在N个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法? 5, 1, 1和1, 5, 1 是同一种分法。
输入
第一行是测试数据的数目t(0 <= t <= 20)。以下每行均包含二个整数M和N,以空格分开。 1<=M, N<=10。
输出
对输入的每组数据M和N,用一行输出相应的K。
样例输入
1
7 3
样例输出
8

设i个苹果放在k个盘子里放法总数是 f(i,k),则:
k > i 时, f(i,k) = f(i,i)
k <= i 时,总放法 = 有盘子为空的放法+没盘子为空的放法
f(i,k) = f(i,k-1) + f(i-k,k)

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int setApple(int n,int m){
    if (n < m) {//如果盘子比苹果数量更多,则放置方法和一样多的时候一样
        return setApple(n, n);
    }
    if (n == 0) {//没有苹果的时候只有一种方法
        return 1;
    }
    if (m == 0) {//没有盘子的时候没有放置的方法
        return 0;
    }//返回 没有空盘子的情况 加上 空一个盘子的情况
    return setApple(n - m, m) + setApple(n, m - 1);
}
int main(){
    int caseNumber;
    cin >> caseNumber;
    while (caseNumber--) {
        int n,m;
        cin >> n >> m;
        int sum = setApple(n, m);
        cout << sum << endl;
    }
    return 0;
}

杨辉三角

递归算法

#include <iostream>
#include <cstdio>
#include <cmath>
#include <iomanip>
using namespace std;
int yanghui(int i,int j){
    if (j > i){
        return 0;
    }else if (j == 0) {
        return 1;
    }else {
        return yanghui(i - 1, j - 1) + yanghui(i - 1, j);
    }
}
int main(){
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cout << setw(n-i);
        for (int j = 0; j <= i; ++j) {
            cout << yanghui(i, j) <<" ";
        }
        cout << endl;
    }
    return 0;
}

队列算法

#include <iostream>
#include <queue>
#include <iomanip>
using  namespace std;
void yanghuitriangle(int n)
{
    queue<int> Q;
    int space = n;//空格
    Q.push(1);//第一行元素
    for (int j = 1; j <= n; j++) {//打印第n行数列,产生第n+1行数列
        Q.push(1);//第n+1行的第一个元素
        cout << setw(space--);//输出每行前面的空格
        for (int i = 1; i < j ; i++) {//第n行输出前n-1个数据
            cout << Q.front()<<" ";//输出队列第一个元素
            int fro = Q.front();//保存队列第一个元素的数据
            Q.pop();//弹出队列第一个数据
            Q.push(fro + Q.front());//将每次循环时的最前面的两个数据的和放入队列末尾
        }
        cout << Q.front() <<endl;//输出最后一个元素
        Q.pop();
        Q.push(1);//最后一个元素永远是1
    }
}

int main()
{
    int N;//size_t 为unsigned int
    cout << "请输入杨辉三角的行数:";
    cin >> N;
    yanghuitriangle(N);
    return 0;
}

全排练问题*

#include <cstdio>
#include <iostream>
using namespace std;
const int MAXN = 20;
int P[MAXN],n;
bool hashmap[MAXN];
void generateP(int index){
    if (index == n + 1) {//递归边界,已经处理完排列的1~n位
        for (int i = 1; i <= n; ++i) {//输出当前排列
            cout << P[i] << " ";
        }
        cout << endl;
    }else{
        for (int x = 1; x <= n; ++x) {//枚举1~n,试图将x填入到P[index]
            if (hashmap[x] == false) {//如果x不在P[0]~P[index - 1]中
                P[index] = x;//令P的第index位为x,即把x加入到当前排列
                hashmap[x] = true;//记x已经在P中
                generateP(index + 1);//处理排列的第index+1号位置
                hashmap[x] = false;//已经处理完P[index]为x的子问题,还原状态
            }
        }
    }
}
int main(){
    cin >> n;
    generateP(1);//从P[1]开始填充
    return 0;
}

归并排序

#include <iostream>
#include "cstdio"
using namespace std;
const int MAXN = 100;
void Mergesort(int A[],int L1,int R1,int L2,int R2){
    int temp[MAXN];
    int idx = 0;
    int i,j;//分别指向开头
    for ( i = L1,j = L2; i <= R1 && j <= R2 ;) {
        if (A[i] <= A[j]) {//小的那个加入临时数组
            temp[idx++] = A[i++];
        } else {
            temp[idx++] = A[j++];
        }
    }
    //L1,R1,L2,R2指的是数组的下标
//有可能i等于前列的最后一个元素的数组下标,放入临时数组中
    while(i <= R1) {temp[idx++] = A[i++];}
    while(j <= R2) {temp[idx++] = A[j++];}
    for (int i = 0; i < idx; i++) {
        A[i + L1] = temp[i];
    }
}
void Merge(int A[],int left,int right){
    if (left < right) {//递归跳出条件
        int mid = left + (right - left) / 2;
        Merge(A,left,mid);//前半部分排好序
        Merge(A,mid+1,right);//后半部分排好序
        Mergesort(A, left, mid, mid+1, right);//归并d   
    }  
}
int main(){
    int A[8] = {2,24,76,102,44,15,59,13};
    Merge(A, 0, 7);
    for (int i = 0; i < 8; i++) {
        cout << A[i] << " ";
    }
    return 0;
}

分治法求最大子序列和

#include <iostream>
#include <cstdio>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;
const int MAXN = 99999999;
int a[MAXN];
int MaxSequ(int low,int high){
    if (high <= low ) {//分治到最小单位,返回其中任意一个
        return a[low];
    }
    int mid = (low + high)>>1;//找中间数
    int tmp1 = -INF,tmp2 = -INF;//一开始为负无穷大,方便后面的比较
    int Midleft = MaxSequ(low,mid);//左边最大子序列和
    int Midright = MaxSequ(mid + 1 ,high);//右边最大子序列和
    int sum = 0;
    for (int i = mid; i >= low; i--) {//从中间开始,往前计算最大子序列和,实现跨中间元素相加
        sum += a[i];//计算当前扫描到的数与中间数之间的序列和
        tmp1 = sum > tmp1 ? sum : tmp1;//选出 原先的子序列的最大值 与 现在的 更大的一个
    }
    sum = 0;
    for (int i = mid + 1; i <= high; i++) {//从中间开始,往后计算最大子序列和,实现跨中间元素相加
        sum += a[i];//计算当前扫描到的数与中间数之间的序列和
        tmp2 = sum > tmp2 ? sum : tmp2;//选出 原先的子序列的最大值 与 现在的 更大的一个
    }
    sum = tmp1 + tmp2;//sum是跨越中间序列的最大值
    int x = max(Midleft, sum);//选出三者最大值
    return max(x,Midright);
}
int main(){
    int n;
    while ( cin >> n )
    {
        for ( int i = 0; i < n; i ++ )
            cin >> a[i];
        cout << MaxSequ(0, n-1)<< endl;
    }
    return 0;
}

无优先级运算

最多需要多少个数字

小明游戏

#include <vector>
#include <cstdio>
#include <iostream>
#define N 4
using namespace std;
int n[100];
vector<int> num_v, renum;
vector<char> char_v, rechar;
int max_len = 0;
double re;
char oper[N] = { '/', '*', '-', '+'};
void seq(int k, int len, double sum) {//k为利用的数字的位数
    if (sum == re && k > max_len) {
        //如果当前计算结果sum=re要求的结果并且第一次满足,则跳出递归,保存结果
        renum = num_v;          //数字结果存入renum
        rechar = char_v;        //字符结果存入rechar
        max_len = k;            //递归一次就好了
    }
    if (k >= len) return;       //k大于总长度时,退出递归,表示找不到正确的结果
    num_v.push_back(n[k]);      //将第k位数字加入num_v
    for (int i = 0; i < N; i++) {//对字符进行选择,先往符号数组加入,再递归调用
        char op = oper[i];
        if (op == '+') {
            char_v.push_back('+');
            seq(k + 1, len, sum + n[k]);
        }
        else if (op == '*') {
            char_v.push_back('*');
            seq(k + 1, len, sum * n[k]);
          
        }
        else if (op == '-') {
            char_v.push_back('-');
            seq(k + 1, len, sum - n[k]);
        }
        else if (op == '/') {
            char_v.push_back('/');
            seq(k + 1, len, sum / n[k]);
        }
        char_v.pop_back();//都试过却不可以得出正确结果则把符号弹出
    }
    num_v.pop_back(); 
}
int main() {
    int len;
    double m;//m 小明手上牌的数字, re 运算结果的要求  ,len  桌上牌的个数
    scanf("%lf %lf %d", &m, &re, &len);
    for (int i = 0; i < len; i++)// 桌上牌的数字
        scanf("%d", &n[i]);
    int k = 0;
    double sum = m;//sum为当前的计算结果
    seq(k, len, sum);
    cout << m <<" ";
    for (int i = 0; i < rechar.size() ; ++i) {
        if( i < renum.size()){
            cout << rechar[i] << " ";
        }
        cout << renum[i] << " ";
    }
    return 0;
}
#include <vector>
#include <cstdio>
#include <iostream>
#define N 4
using namespace std;
int n[100];
vector<int> num_v, renum;
vector<char> char_v, rechar;
int max_len = 0;
double re;
double m;
char oper[N] = { '/', '*', '-', '+'};
void seq(int k, int len) {//k为利用的数字的位数
    if (k == len) {
        double sum = m;
        for (int i = 0,j = 0; i < num_v.size() && j < char_v.size(); i++,j++) {
            char op = char_v[j];
            if (op == '+') {
                sum += num_v[i];
            }else if (op == '*') {
                sum *= num_v[i];
            }else if (op == '-') {
                sum -= num_v[i];
            }else if (op == '/') {
                sum /= num_v[i];
            }
            if (sum == re && i  + 1 > max_len) {
                //如果当前计算结果sum=re要求的结果并且用的纸牌数量比原来的大保存结果
                renum.clear();
                rechar.clear();
                renum.insert(renum.begin(), num_v.begin(), num_v.begin() + i + 1);
                //数字结果存入renum
                rechar.insert(rechar.begin(),char_v.begin(), char_v.begin() + i + 1);
                //字符结果存入rechar
                max_len = i + 1;            //递归一次就好了
            }
        }
      
        return;
    }
    num_v.push_back(n[k]);      //将第k位数字加入num_v
    for (int i = 0; i < N; i++) {//对字符进行选择,先往符号数组加入,再递归调用
        char_v.push_back(oper[i]);
        seq(k + 1, len);
        char_v.pop_back();//都试过却不可以得出正确结果则把符号弹出
    }
    num_v.pop_back();
}
int main() {
    int len;
    //m 小明手上牌的数字, re 运算结果的要求  ,len  桌上牌的个数
    scanf("%lf %lf %d", &m, &re, &len);
    for (int i = 0; i < len; i++)// 桌上牌的数字
        scanf("%d", &n[i]);
    seq(0, len);
    cout <<"最多需要的纸牌数为 : " << max_len << endl;
    cout << m <<" ";
    for (int i = 0; i < rechar.size() ; ++i) {
        if( i < renum.size()){
            cout << rechar[i] << " ";
        }
        cout << renum[i] << " ";
    }
    return 0;
}

//5 13 6 1 3 9 4 2 2

输出所有结果

#include <vector>
#include <cstdio>
#include <iostream>
#define N 4
using namespace std;
int n[100];
vector<int> num_v, renum;
vector<char> char_v, rechar;
int max_len = 0;
double re;
char oper[N] = { '/', '*', '-', '+'};
void seq(int m,int k, int len, double sum) {//k为利用的数字的位数
    if (sum == re ) {//如果当前计算结果sum=re要求的结果并且第一次满足,则跳出递归,保存结果
        renum = num_v;          //数字结果存入renum
        rechar = char_v;        //字符结果存入rechar
        cout << m <<" ";
        for (int i = 0; i < rechar.size() ; ++i) {
            if( i < renum.size()){
                cout << rechar[i] << " ";
            }
            cout << renum[i] << " ";
        }
        cout << endl;
        return;
    }
    if (k >= len) return;       //k大于总长度时,退出递归,表示找不到正确的结果
    num_v.push_back(n[k]);      //将第k位数字加入num_v
    for (int i = 0; i < N; i++) {//对字符进行选择,先往符号数组加入,再递归调用
        char op = oper[i];
        if (op == '+') {
            char_v.push_back('+');
            seq(m,k + 1, len, sum + n[k]);
        }
        else if (op == '*') {
            char_v.push_back('*');
            seq(m,k + 1, len, sum * n[k]);
          
        }
        else if (op == '-') {
            char_v.push_back('-');
            seq(m,k + 1, len, sum - n[k]);
        }
        else if (op == '/') {
            char_v.push_back('/');
            seq(m,k + 1, len, sum / n[k]);
        }
        char_v.pop_back();//都试过却不可以得出正确结果则把符号弹出
    }
    num_v.pop_back();
}
int main() {
    int len;
    double m;//m 小明手上牌的数字, re 运算结果的要求  ,len  桌上牌的个数
    scanf("%lf %lf %d", &m, &re, &len);
    for (int i = 0; i < len; i++)// 桌上牌的数字
        scanf("%d", &n[i]);
    int k = 0;
    double sum = m;//sum为当前的计算结果
    seq(m, k, len, sum);
    return 0;
}

贪心算法

岸边雷达扫描海中岛屿

image-20200316171041139

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAXN = 1010;
struct Position{//岛屿雷达范围与岸边的交点坐标
    double left;
    double right;
};
Position island[MAXN];//岛屿的坐标数组
bool Compare(Position a,Position b){
    return a.left < b.left;//坐标较小的排在前面
}
int main(){
    int n,m;//n为岛屿的个数,m为雷达的扫描半径
    int caseNumber = 0;
    while(scanf("%d%d",&n,&m)!=EOF){
        bool flag = true;
        if (n == 0 && m == 0) {
            break;
        }
        for (int i = 0; i < n; ++i) {//赋值
            int x,y;
            scanf("%d%d",&x,&y);
            if (y > m) {
                flag = false;
            } else{//计算岛屿雷达范围与岸边的交点坐标
                island[i].left = x - sqrt(m * m - y * y * 1.0);
                island[i].right = x + sqrt(m * m - y * y * 1.0);
            }
        }
        if (flag == true) {
            sort(island, island + n, Compare);
            int ans = 1;
            double current = island[0].right;
            for (int i = 1; i < n;  ++i) {
                if (current >= island[i].left) {
                //如果当前岛屿可以用之前的雷达扫描到,那就返回岸边轴较左边的雷达范围
                    current = min(island[i].right,current);
                } else{//如果岛屿相距太远,则增加一个雷达来扫描
                    current = island[i].right;
                    ans++;
                }
            }
            printf("Case %d: %d\n",++caseNumber,ans);
        }else{
            printf("Case %d: -1\n",++caseNumber);
        }
      
    }
    return 0;
}

疯狂的奶牛

建了n个隔间,有坐标,把c头奶牛放到隔间中,求隔间相差的最大距离

#include <iostream>
#include <cstdio>
#include <cmath>
#include "cstring"
#include <algorithm>
using namespace std;
const int MAXN = 1e5 + 10;
int stall[MAXN];//存储栅栏的位置
bool judge(int n,int c,int span){
    int current = stall[0];//当前位置为第一个隔间
    int count = 1;//记录可以用span距离填充的奶牛
    for (int i = 1; i < n; ++i) {
        //从前往后遍历,遇到满足距离要求的,就放入奶牛,修改当前位置为最后一只奶牛的位置
        if (stall[i] - current >= span) {
            current = stall[i];
            count++;//记录满足距离的奶牛数量
        }
    }
    if (count >= c) {//满足距离的奶牛数量大于等于放置奶牛数量
        return true;
    }else{
        return false;
    }
}
int main(){
    int n,c;
    scanf("%d%d",&n,&c);
    for (int i = 0; i < n; ++i) {
        scanf("%d",&stall[i]);
    }
    sort(stall, stall + n);//将隔间的位置从小到大排序
    int left = 1,right = stall[n - 1];
    while (left <= right) {//二分查找
        int mid = left + (right - left) / 2;
        if (judge(n, c, mid)) {//如果距离满足要求
            left = mid + 1;//试着增大距离
        }else{//不满足要求则减少距离
            right = mid - 1;
        }
    }
    printf("%d",right);//若left=right时,不满足要求,right才是正确距离
    return 0;
}

Drying

晾衣服,自然风干每小时干1升,烘干机每小时烘干k升,多件衣服,求最短弄干时间

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAXN = 100010;
int water[MAXN];
bool judge(int n,int k,int time){
    //在time时间内烘干,意味着自然风干了time升
    //运算剩下的水分中用烘干机烘干的时间
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        if (water[i] > time) {//如果当前衣服在预计时间风干不了,则用烘干机
            //烘干机每小时比自然风干多贡献k-1的水分,取上届整数
            sum += ceil((water[i] - time) * 1.0 / (k - 1));
        }
        if (sum > time ) {
            return false;
        }
    }
    return true;
}
int main(){
    int n;
    scanf("%d",&n);
    for (int i = 0; i < n; ++i) {
        scanf("%d",&water[i]);
    }
    int k;
    scanf("%d",&k);
    sort(water,water + n);
    if (k == 1) {//如果烘干机烘干速度e等于自然风干速度,则返回最湿衣服的晾干时间
        printf("%d",water[n - 1]);
    }else{
    int left = 1,right = water[n - 1];//晾干时间最短为1,最长为最湿衣服的晾干时间
    while (left <= right) {//二分策略
        int mid = left + (right - left) / 2;
        if (judge(n, k, mid)) {//当前时间能够吹干所有衣服
            right = mid - 1;//试着用更少时间
        }else{//时间过短不够,试着增加时间
            left = mid + 1;
        }
    }
    printf("%d",left);
}
    return 0;
}

箱子打包

有一组 1 维的物品需要打包进一批同样的箱子中。所有的箱子有完全一样的长度 l 以及每一个物品长度 li<=l. 我们要找到一个最小的数字 q, 使得 :
(1) 每个箱子最多包含两个物品
(2) 每个物品要被包含在 q 个箱子中的一个中
(3) 在箱子中物品的总长度不能超过 l
你的任务是,给定 n 个整数,l,l1,l2....ln, 计算最小的箱子总数 q.
输入格式
第一行包含一个数字 n(1<= n <= 10^5), 表示有几个物品。第二行包含一个整数表示了箱子的长度 l (l<=10000). 接下去的 n 行是表示了每个物品的长度。
输出格式
输出一个整数,表示能够包含所有物品的最小的箱子总数。

思路:

从小到大排序,优先选择大的,然后如果有空间从小到大塞进小的物品

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAXN = 1e5 + 10;
int box[MAXN];//存储物品长度
int main(){
    int n,wid;//n为物品个数,wid为箱子的长度
    scanf("%d%d",&n,&wid);
    for (int i = 0; i < n; ++i) {
        scanf("%d",&box[i]);
    }
    sort(box, box + n);//从小到大排序
    int right = n - 1;
    int left = 0;
    int count = 0;
    while (left <= right) {
        if (box[right] <= wid) {
            if (box[right] + box[left] <= wid) {
                count++;//当可以满足大包加小包时,计数加一,左右边界内缩
                right--;
                left++;
            } else{//只够大包时,计数加一,只让右边界内缩
                count++;
                right--;
            }
        }else{
            break;
        }
    }
    printf("%d",count);
    return 0;
}

部分背包(肥鼠交易)

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 1e3 + 10;
struct JavaBean{
    double weight;//咖啡豆重量
    double value;//咖啡豆价格(猫粮)
};
bool Compare(JavaBean a,JavaBean b){
    //性价比 = (物品)/(花费价格)
    return (a.weight/a.value) > (b.weight/b.value);
}
JavaBean J[MAXN];//存储物品长度
int main(){
    int m,n;
    while(scanf("%d%d",&m,&n)!=EOF){
        if (m == -1 && n == -1) {
            break;
        }
        for (int i = 0; i < n; ++i) {
            scanf("%lf%lf",&J[i].weight,&J[i].value);
        }//对性价比进行排序
        sort(J, J + n, Compare);
        double sum = 0;
        //优先选择性价比高的房间
        for (int i = 0; i < n; ++i) {
            if (m >= J[i].value) {//如果钱够买整个房间,则全部买下
                m -= J[i].value;
                sum += J[i].weight;
            } else if(m < J[i].value){//钱不够,则买下部分
                sum += J[i].weight * (m / J[i].value);
                break;
            }
        }
        printf("%.3f\n",sum);
    }
    return 0;
}

赏金猎人

打怪兽,获得赏金为 攻击力减去防御力,求最大赏金额。

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 1e5 + 10;
long long attack[MAXN];
long long defensive[MAXN];
bool Compare(long long a,long long b){
    return a > b;
}
int main(){
    int caseNum;
    scanf("%d",&caseNum);
    while (caseNum--) {
        int m,n;
        scanf("%d%d",&n,&m);
        for (int i = 0; i < n; ++i) {
            scanf("%lld",&attack[i]);
        }
        for (int i = 0; i < m; ++i) {
            scanf("%lld",&defensive[i]);
        }//枪的威力从大到小排序,怪兽防御从小到大排序
        sort(attack, attack + n,Compare);
        sort(defensive, defensive + m);
        long long sum = 0;
        for (int i = 0; i < n; ++i) {
            if (i >= m || attack[i] <= defensive[i]) {
                break;//如果怪兽打完了或者打不过怪兽则跳出
            }//先判断可能跳出的条件
            sum += (attack[i] - defensive[i]);//获得赏金
        }
        printf("%lld\n",sum);
    }
    return 0;
}

搬桌子*

某教学大楼一层有n个教室,从左到右依次编号为1、2、…、n。现在要把一些课桌从某些教室搬到另外一些教室,每张桌子都是从编号较小的教室搬到编号较大的教室,每一趟,都是从左到右走,搬完一张课桌后,可以继续从当前位置或往右走搬另一张桌子。输入数据:先输入n、m,然后紧接着m行输入这m张要搬课桌的起始教室和目标教室。输出数据:最少需要跑几趟。
Sample Input
10 5
1 3
3 9
4 6
6 10
7 8
Sample Output
3

分析:贪心算法,把课桌按起点从小到大排序,每次都是搬离当前位置最近的课桌。

#include<stdio.h>
int main()
{
    struct
    {
        int start;
        int end;
    }a[100];
    int i,j;
    int n,m,min,num,temp,used[100]={0};
    scanf("%d%d",&m,&n);
    for(i=0;i<n;i++)
        scanf("%d%d",&a[i].start,&a[i].end);
    sort(a,a + n);         //按start从小到大对数组a排序
    min=0;
    num=0;
    while(num<n)
    {
        temp=0;
        for(i=0;i<n;i++)
            if(used[i]==0&&a[i].start>=temp)
            {
                temp=a[i].end;
                used[i]=1;
                num++;
            }
        min++;
    }
    printf("%d",min);
}

堆石头*

【问题】
抓石子游戏又称为巴什博奕,简单描述一下,有一堆n个物品,两个人轮流从这堆物品中取物,规定每次至少取一个,最多取m个。取到最后一个物品者得胜。
【解法】
显然,如果n=m+1,那么由于一次最多只能取m个,所以,无论先取者拿走多少个,后取者都能够一次拿走剩余的物品,后者取胜。因此我们发现了如何取胜的法则:分段来进行讨论,如果n<=m,先手的赢,在n>m中再分情况讨论,如果n为m+1的整数i倍,假想一下,把物品平均分为i堆,一堆m+1个,不就是把前面提到的过程重复i次嘛,所以,后手者是肯定赢的。如果n=(m+1)i+j,当然可以知道 j < m + 1 ,j的范围是[1,m]中的整数,就是把物品按一堆 m + 1 个分,又多出来 j 个。结果就相反,先手的人可以直接把 j 个东西全部拿走,剩下( m + 1 ) i 个,就到上面分析的那种情况了,于是乎这种情况下后手者就被动了。
所以要判断这个游戏的结果,只需知道石子的开始个数、一次最多能拿多少和谁先手就可以了。
【实现】
由于和先手有关,为了简化实现过程,在这里按照自己先手来编写。

#include<iostream>
using namespace std;
void myfunction(int m,int n)
{
    if (n % (m + 1) == 0)
        cout << "你将失败" << endl;
    else
        cout << "你将胜利" << endl;
}
int main()
{
    int m, n;
    cout << "请分别输入最初石子数和一次最多拿的石子数:";
    cin >> n >> m;
    myfunction(m, n);
}

活动安排*

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct Program{
    int starttime;
    int endtime;
};
Program arr[100];
bool compare(Program A,Program B){
    return A.endtime < B.endtime;
}
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        if(n == 0){break;}
        for (int i = 0; i < n; ++i) {
            scanf("%d%d",&arr[i].starttime,&arr[i].endtime);
        }
        sort(arr, arr + n, compare);
        int currentTime = 0;
        int count = 0;
        for (int i = 0; i < n; ++i) {
            if (currentTime <= arr[i].starttime) {
                currentTime = arr[i].endtime;
                count++;
            }
        }
        cout << count;
  
    }
    return 0;
}

马踏棋盘*

深度优先搜索

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
using namespace std;
const int MAXN = 30;
int p,q;
bool visit[MAXN][MAXN];
int direction[8][2]{
    {-1,-2},{1,-2},
    {-2,-1},{2,-1},
    {-2,1},{2,1},
    {-1,2},{1,2}
};
bool DFS(int x,int y,int step,string ans){
    if (step == p * q) {
        cout << ans << endl <<endl;
        return true;
    }else{
        for (int i = 0; i < 8; ++i) {
            int nx = x + direction[i][0];
            int ny = y + direction[i][1];
            char col = ny + 'A';
            char row = nx + '1';
            if (nx < 0 || nx >= p || ny < 0 || ny >= q || visit[nx][ny]) {
            //边界之外或者已经走过的格子则跳过
                continue;
            }
            visit[nx][ny] = true;
            if (DFS(nx,ny,step + 1,ans + col + row)) {
                return true;
            }
            visit[nx][ny] = false;
        }
    }
    return false;
}
int main(){
    int n;
    scanf("%d",&n);
    int caseNumber = 0;
    while (n--) {
        scanf("%d%d",&p,&q);
        memset(visit, false, sizeof(visit));
        cout << "Scenario #" << ++caseNumber << ":" << endl;
        visit[0][0] = true;
        if (!DFS(0,0,1,"A1")) {
            cout << "impossible" <<endl<<endl;
        }
    }
    return 0;
}

递归解法+深度优先搜索

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <iomanip>
using namespace std;
int visit[8][8];//标记矩阵
int direction[8][2]{//下一步走的位置
    {-1,-2},{1,-2},
    {-2,-1},{2,-1},
    {-2,1},{2,1},
    {-1,2},{1,2}
};
void printChess(){
    for (int i = 0; i < 8; ++i) {
        for (int j = 0; j < 8; ++j) {
            cout <<setw(3)<< visit[i][j] ;
        }
        cout << endl;
    }
}
bool DFS(int x,int y,int step){
    if (step > 64) {//搜索成功
        printChess();
        return true;
    }else{
        for (int i = 0; i < 8; ++i) {//遍历邻居结点
            int nx = x + direction[i][0];//扩展坐标状态
            int ny = y + direction[i][1];
            if (nx < 0 || nx >= 8 || ny < 0 || ny >= 8 || visit[nx][ny] != 0) {
                //边界之外或者已经走过则跳过
                continue;
            }
            visit[nx][ny] = step;//标记该点
            if (DFS(nx,ny,step + 1)) {
                return true;
            }
            visit[nx][ny] = 0 ;//取消标记
        }
    }
    return false;
}
int main(){
    memset(visit, 0, sizeof(visit));
    visit[0][0] = 1;//标记A1点
    if (DFS(0,0,2)) {
        cout << "OK" <<endl<<endl;
    }else{
        cout << "NO" <<endl<<endl;
    }
    return 0;
}

递归深度优先搜索+贪心解法

#include <iostream>
#include <iomanip>
#include <algorithm>
using namespace std;
typedef struct Node {
    int x, y, w;
    Node(){}
    Node(int x, int y, int w) :x(x), y(y), w(w){}
};
int visit[8][8];//标记矩阵
Node nextxy[8];//下一点要走的位置以及下一点的可能走的下一位置的个数
int direction[8][2]{//下一步走的位置
    {-1,-2},{1,-2},
    {-2,-1},{2,-1},
    {-2,1},{2,1},
    {-1,2},{1,2}
};
void printChess() {
    for (int i = 0; i < 8; ++i) {
        for (int j = 0; j < 8; ++j) {
            cout << setw(3) << visit[i][j];
        }
        cout << endl;
    }
}
bool cmp(Node a, Node b) {
    return a.w < b.w;
}
void next(int x, int y) {
    for (int i = 0; i < 8; ++i) {
        nextxy[i] = Node(-1, -1, 100);
        // 将初始值的坐标定位(-1,-1),即不合法的位置
        //w为下一位置可能的落点数,w定很大另它排序到后面
    }
    for (int i = 0; i < 8; ++i) {// 遍历邻居结点
        int nx = x + direction[i][0];// 扩展坐标状态
        int ny = y + direction[i][1];
        if (nx < 0 || nx >= 8 || ny < 0 || ny >= 8 || visit[nx][ny] != 0) {
            // 边界之外或者已经走过则跳过
            continue;
        }else {
            nextxy[i].x = nx;
            nextxy[i].y = ny;
            nextxy[i].w = 1 ;
        }
        for (int j = 0; j < 8; ++j) {
            int nx2 = nx + direction[j][0];// 扩展坐标状态
            int ny2 = ny + direction[j][1];
            if (nx2 < 0 || nx2 >= 8 || ny2 < 0 || ny2 >= 8 || visit[nx2][ny2] != 0) {
                // 边界之外或者已经走过则跳过
                continue;
            }
            nextxy[i].w++;
        }
    }
    sort(nextxy, nextxy + 8, cmp);
}
bool DFS(int x, int y, int step) {
    if (step > 64) {//搜索成功
        printChess();
        return true;
    }else {
        next(x, y);
        int i = 0;
        while (i < 8 && (nextxy[i].x != -1 && nextxy[i].y != -1) ) // 位置可行
        {
            visit[nextxy[i].x][nextxy[i].y] = step;
            if (DFS(nextxy[i].x, nextxy[i].y, step + 1)) // 进入新位置
                return true;
            i++;
        }
            visit[nextxy[i].x][nextxy[i].y] = 0; // 此路不可走,回退
        return false;
    }
}
int main() {
    memset(visit, 0, sizeof(visit));
    visit[1][1] = 1;//标记起点
    if (DFS(1, 1, 2)) {
        cout << "OK" << endl << endl;
    }else {
        cout << "NO" << endl << endl;
    }
    return 0;
}

非递归遍历

中序非递归遍历

//中序遍历
void InOrderWithoutRecursion2(BTNode* root)
{
    //空树
    if (root == NULL)
        return;
    //树非空
    BTNode* p = root;
    stack<BTNode*> s;
    while (!s.empty() || p)
    {
        if (p)
        {
            s.push(p);
            p = p->lchild;
        }
        else
        {
            p = s.top();
            s.pop();
            cout << setw(4) << p->data;
            p = p->rchild;
        }
    }
}

二叉树建立

给定一棵二叉树的前序遍历和中序遍历,求其后序遍历(提示:给定前序遍历与中序遍历能够唯一确定后序遍历)

#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
struct TreeNode{
    char c;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char c):c(c),left(nullptr),right(nullptr){};
};
TreeNode *Build(string PreOrder,string InOrder){
    if (PreOrder.size() == 0) {
        return nullptr;
    }
    char c = PreOrder[0];
    TreeNode* root = new TreeNode(c);//新建一个结构体
    int position = InOrder.find(c);
    root->left = Build(PreOrder.substr(1,position), InOrder.substr(0,position));
    root->right = Build(PreOrder.substr(position + 1), InOrder.substr(position + 1));
    return root;
}
void PostOrder(TreeNode* root){
    if (root == nullptr) {
        return;
    }
    PostOrder(root->left);
    PostOrder(root->right);
    cout << root->c;
    return;
}

int main(){
    string a,b;
    while (cin >> a >> b) {
        TreeNode* root = Build(a, b);
        PostOrder(root);
        cout << endl;
    }
    return 0;
}

二叉排序树

输入一系列整数,建立二叉排序树,并进行前序,中序,后序遍历。

#include <iostream>
#include <cstdio>
using namespace std;
struct TreeNode{
    int data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int data):data(data),left(nullptr),right(nullptr){};
};
TreeNode* Insert(TreeNode* root,int x){
    if (root == nullptr) {
        root = new TreeNode(x);//找到空结点,插入数据
    }else if(x < root->data){//数据小,往左找位置
        root->left = Insert(root->left, x);
    }else if(x > root->data){//数据大,往右找位置
        root->right = Insert(root->right, x);
    }
    return root;
}
void PostOrder(TreeNode* root){
    if (root == nullptr) {
        return;
    }
    PostOrder(root->left);
    PostOrder(root->right);
    cout << root->data <<" ";
    return;
}
void PreOrder(TreeNode* root){
    if (root == nullptr) {
        return;
    }
    cout << root->data <<" ";
    PreOrder(root->left);
    PreOrder(root->right);
    return;
}
void InOrder(TreeNode* root){
    if (root == nullptr) {
        return;
    }
    InOrder(root->left);
    cout << root->data <<" ";
    InOrder(root->right);
    return;
}
int main(){
    int n;
    while (scanf("%d",&n)!=EOF) {
        TreeNode* root = nullptr;
        for (int i = 0; i < n; ++i) {
            int x;
            scanf("%d",&x);
            root = Insert(root, x);
        }
        PreOrder(root);
        cout << endl;
        InOrder(root);
        cout << endl;
        PostOrder(root);
        cout << endl;
    }
    return 0;
}

优先队列

复数集合

一个复数(x+iy)集合,两种操作作用在该集合上:

1、Pop 表示读出集合中复数模值最大的那个复数,如集合为空 输出 empty ,不为空就输出最大的那个复数并且从集合中删除那个复数,再输出集合的大小SIZE;

2、Insert a+ib 指令(a,b表示实部和虚部),将a+ib加入到集合中 ,输出集合的大小SIZE; 最开始要读入一个int n,表示接下来的n行每一行都是一条命令。

#include <iostream>
#include <cstdio>
#include <queue>
#include <string>
using namespace std;
struct Complex{
    int real;//实部
    int imag;//虚部
    Complex(int real,int imag):real(real),imag(imag){};
    bool operator< (Complex b) const{//重载小于号,优先队列才可以按要求排序
        return real * real + imag * imag < b.real * b.real + b.imag * b.imag;
    }
};

int main(){
    int n;
    while (scanf("%d",&n)!=EOF) {
        priority_queue<Complex> mypriority;
        for (int i = 0; i < n; ++i) {
            string x;
            cin >> x;
            if (x == "Pop") {
                if (mypriority.empty()) {
                    cout << "empty" << endl;
                }else{
                    Complex cur = mypriority.top();
                    mypriority.pop();
                    printf("%d+i%d\n",cur.real,cur.imag);
                    printf("SIZE = %d\n",mypriority.size());
                }
            }else{
                int a,b;
                scanf("%d+i%d",&a,&b);//输入Insert 1+i2 ,读入相应的数字
                mypriority.push(Complex(a,b));
                printf("SIZE = %d\n",mypriority.size());
            }
        }
    }
    return 0;
}

哈夫曼树

哈夫曼树,第一行输入一个数n,表示叶结点的个数。需要用这些叶结点生成哈夫曼树,根据哈夫曼树的概念,这些结点有权值,即weight,题目需要输出所有结点的值与权值的乘积之和

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;

int main(){
    int n;
    while (scanf("%d",&n) != EOF) {
        priority_queue<int,vector<int>,greater<int>> mypriority;//优先队列按升序排列
        while (n--) {
            int x;
            scanf("%d",&x);
            mypriority.push(x);
        }
        int ans = 0;//记录哈夫曼值
        while (1 < mypriority.size()) {//当优先队列中存在的元素不止一个的时候
            int a = mypriority.top();
            mypriority.pop();
            int b = mypriority.top();
            mypriority.pop();
            ans += (a+b);
            mypriority.push(a + b);
          
        }
        printf("%d\n",ans);
    }
    return 0;
}

哈密顿图

简单回路

并查集

求能够连通需要的边数

#include <iostream>
#include <cstdio>
using namespace std;
//连通问题:并查集,观察是否在同一个集合当中
const int MAXN = 1000;
int father[MAXN];
int height[MAXN];
void initial(int n){
    for (int i = 1; i <= n; ++i) {
        father[i] = i;
        height[i] = 0;
    }
}
int findFather(int x){
    if (x != father[x]) {
        x = findFather(father[x]);
    }
    return x;
}
void UnionP(int a,int b){
    int x = findFather(a);
    int y = findFather(b);
    if (height[x] < height[y]) {
        father[x] = father[y];
    }else if (height[x] > height[y]){
        father[y] = father[x];
    }else{
        father[y] = father[x];
        height[y]++;
    }
}
int main(){
    int n,m;
    while (scanf("%d",&n)!=EOF) {
        initial(n);
        scanf("%d",&m);
        while (m--) {
            int x,y;
            scanf("%d %d",&x,&y);
            UnionP(x, y);
        }
        int ans = -1;
        for (int i = 1; i <= n; ++i) {
            if (i == father[i]) {
                ans++;
            }
        }
        printf("%d",ans);
    }
}

求是否为无向连通图

#include <iostream>
#include <cstdio>
using namespace std;
//连通问题:并查集,观察是否在同一个集合当中
const int MAXN = 1000;
int father[MAXN];
int height[MAXN];
void initial(int n){
    for (int i = 1; i <= n; ++i) {
        father[i] = i;
        height[i] = 0;
    }
}
int findFather(int x){
    if (x != father[x]) {
        x = findFather(father[x]);
    }
    return x;
}
void UnionP(int a,int b){
    int x = findFather(a);
    int y = findFather(b);
    if (height[x] < height[y]) {
        father[x] = father[y];
    }else if (height[x] > height[y]){
        father[y] = father[x];
    }else{
        father[y] = father[x];
        height[y]++;
    }
}
int main(){
    int n,m;
    while (scanf("%d",&n)!=EOF) {
        initial(n);
        scanf("%d",&m);
        while (m--) {
            int x,y;
            scanf("%d %d",&x,&y);
            UnionP(x, y);
        }
        int ans = -1;
        for (int i = 1; i <= n; ++i) {
            if (i == father[i]) {
                ans++;
            }
        }
        if (ans == 0) {
            printf("YES\n");
        }else{
            printf("NO\n");
        }
    }
}

求是否为有向树

#include <iostream>
#include <cstdio>
using namespace std;
//无向连通图问题:并查集,观察是否在同一个集合当中
const int MAXN = 1000;
int father[MAXN];   //父亲节点
int height[MAXN];   //结点高度
bool visited[MAXN]; //标记
int indegree[MAXN]; //入度
void initial(int n){//初始化
    for (int i = 1; i <= n; ++i) {
        father[i] = i;
        height[i] = 0;
        visited[i] = false;
        indegree[i] = 0;
    }
}
int findFather(int x){  //查找根节点
    if (x != father[x]) {
        x = findFather(father[x]);
    }
    return x;
}
void UnionP(int a,int b){       // 合并集合
    int x = findFather(a);      // 找最原始结点
    int y = findFather(b);
    if (x != y) {   //原始结点不一样
        if (height[x] < height[y]) {//短的并上长的,高度不变
            father[x] = father[y];
        }else if (height[x] > height[y]){
            father[y] = father[x];
        }else{
            father[y] = father[x];
            height[y]++;//两个长度相同结点并为一个,高度+1
        }
    }
    return;
}
bool isTree(int n){
    bool flag = true;
    int component = 0;  //连通分量数目
    int root = 0;       //根结点数
    for (int i = 1; i <= n; ++i) {
        if (!visited[i]) {  //如果没有被访问过,则逃过
            continue;
        }
        if (i == father[i]) {   //找到了最原始结点
            component++;        //连通分量+1
        }
        if (indegree[i] == 0){  //入度为0,则是根节点
            root++;
        }else if (indegree[i] > 1) {    //入度大于1,不是树
            flag = false;
        }
        if (root != 1 || component != 1) {  //不符合树的定义
            flag = false;
        }
        if (root == 0 && component == 0) {  //空集也是树
            flag = true;
        }
    }
    return flag;
}
int main(){
    int n,m,caseNum = 1;
    initial(MAXN);
    while (scanf("%d %d",&n,&m)!=EOF) {
        if (n == -1 && m == -1) {
            break;
        }
        if (n == 0 && m == 0) {
            if (isTree(MAXN)) {
                printf("Case %d is a tree.\n",caseNum++);
            }else{
                printf("Case %d is not a tree.\n",caseNum++);
            }
            initial(MAXN);//本次结果完毕,开始新的判断,需要重置所有数据
        }else{
            UnionP(n, m);
            indegree[m]++;
            visited[n] = true;
            visited[m] = true;
        }
    }
    return 0;
}

求有向图强连通图

连通图着色*

广义表->二叉链表*

最小生成树

未修好路

输入描述:
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 );随后的N(N-1)/2行对应村庄间的距离,每行给出一对正整数,分别是两个村庄的编号,以及此两村庄间的距离。为简单起见,村庄从1到N编号。当N为0时,输入结束,该用例不被处理。
输出描述:
对每个测试用例,在1行里输出最小的公路总长度。

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
struct Edge{
    int from;
    int to;
    int length;
    bool operator < (const Edge& a)const{
        return length < a.length;
    }
};
const int MAXN = 100;
Edge edge[MAXN];
int father[MAXN];
int height[MAXN];
void initialA(int n){
    for (int i = 0; i <= n; ++i) {
        father[i] = i;//一开始单个结点的父亲是自己
        height[i] = 0;
    }
}
int Find(int x){
    if (x != father[x]) {
        father[x] = Find(father[x]);//查找根节点
    }
    return father[x];
}
void UnionP(int a,int b){
    int x = Find(a);
    int y = Find(b);
    if (x!=y) {//当两个结点不同的时候
        if (height[x] < height[y]) {
            father[x] = y;
        }else if(height[x] > height[y]){
            father[y] = x;
        }else{
            father[y] = x;
            height[x]++;
        }
    }
    return;
}
int Kruskal(int n,int edgeNum){
    initialA(n);//先初始化
    int sum = 0;
    sort(edge, edge + edgeNum);//按权值排序
    for (int i = 0; i < edgeNum; ++i) {
        Edge current = edge[i];//确定当前边
        if (Find(current.from) != Find(current.to)) {//确定当前边起始结点的根节点
            UnionP(current.from, current.to);//若短边没有在最小生成树集合中,则将他们归并其中
            sum += current.length;
        }
    }
    return sum;
}
int main(){
    int n;
    while (scanf("%d",&n) != EOF) {
        if (n == 0) {
            break;
        }
        int edgeNum = n * (n - 1) / 2;
        for (int i = 0; i < edgeNum; ++i) {
            scanf("%d%d%d",&edge[i].from,&edge[i].to,&edge[i].length);
        }
        int ans = Kruskal(n, edgeNum);
        printf("%d\n",ans);
    }
    return 0;
}

修部分路

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 100;
struct Edge{
    int from;
    int to;
    int length;
    bool operator <(const Edge &a)const{
        return length < a.length;
    }
};
int father[MAXN];
int height[MAXN];
Edge edge[MAXN*MAXN];
void initial(int n){
    for (int i = 0; i < n; ++i) {
        father[i] = i;
        height[i] = 0;
    }
}
int findf(int x){//寻找根节点
    if (x != father[x]) {
        father[x] = findf(father[x]);
    }
    return father[x];
}
void Union(int x,int y){
    x = findf(x);
    y = findf(y);
    if (x != y) {
        if (height[x] < height[y]) {
            father[x] = y;
        }else if (height[x] > height[y]){
            father[y] = x;
        }else{
            father[y] = x;
            height[x]++;
        }
    }
}
int Kruskal(int n,int edgeNumber){
    initial(n);
    int sum = 0;
    sort(edge, edge + edgeNumber);
    for (int i = 0; i < edgeNumber; ++i) {
        Edge current = edge[i];
        if (findf(current.from) != findf(current.to)) {
            Union(current.from, current.to);
            sum += current.length;
        }
    }
    return sum;
}
int main(){
    int n;
    while (scanf("%d",&n)!=EOF) {
        if (n == 0) {
            break;
        }
        int edgeNumber = n * (n - 1) / 2;
        for (int i = 0; i < edgeNumber; ++i) {
            int status;
            scanf("%d%d%d%d",&edge[i].from,&edge[i].to,&edge[i].length,&status);
            if (status == 1) {
                edge[i].length = 0;
            }
        }
        int ans = Kruskal(n, edgeNumber);
        printf("%d\n",ans);
    }
    return 0;
}

最短路径

Dijkstra

单纯最短路径

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
const int INF = 99999999;
const int MAXN = 200;
struct Edge{
    int to;//边的终点
    int length;//边的权值
    Edge(int t,int l):to(t),length(l){}
};
vector<Edge> graph[MAXN];
int dis[MAXN];
struct Point{
    int number;//点的编号
    int distance;//点到源点的距离
    Point(int n,int d):number(n),distance(d){}
    bool operator <(const Point& a)const{
        return distance>a.distance;
    }
};
void Dijkstra(int n){
    priority_queue<Point> myQueue;
    dis[n] = 0;
    myQueue.push(Point(n,dis[n]));
    while (!myQueue.empty()) {
        int num = myQueue.top().number;//找出与当前最短路径点集合中相连边权值最小的点序号num
        myQueue.pop();//弹出
        for (int i = 0; i < graph[num].size(); ++i) {
//遍历与num相连的边的点v,如果包含最短路径,则更新v的最短距离
            int v = graph[num][i].to;
            int w = graph[num][i].length;
            if (dis[v] > dis[num] + w) {
                dis[v] = dis[num] + w;
                myQueue.push(Point(v, dis[v]));//如果有更短的路径,则加入最短路径点集合
            }
        }
    }
    return;
}
int main(){
    int n,m;
    while (scanf("%d%d",&n,&m)!=EOF) {
        memset(graph, 0, sizeof(graph));//图初始化
        fill(dis, dis + n, INF);//初始化距离为正无穷
        while (m--) {
            int a,b,x;
            scanf("%d%d%d",&a,&b,&x);
            graph[a].push_back(Edge(b,x));//加入边的数据
            graph[b].push_back(Edge(a,x));
        }
        int from,to;
        scanf("%d%d",&from,&to);
        Dijkstra(from);
        if(dis[to] == INF){
            dis[to] = -1;
        }
        printf("%d\n",dis[to]);
    }
    return 0;
}

最短路径下的最少花费

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
const int INF = 99999999;
const int MAXN = 1001;
struct Edge{
    int to;//边的终点
    int length;//边的权值
    int price;//边的花费
    Edge(int t,int l,int p):to(t),length(l),price(p){}//构造函数
};
vector<Edge> graph[MAXN];//图的h数组
int dis[MAXN],cost[MAXN];//距离数组,花费数组
struct Point{
    int number;//点的编号
    int distance;//点到源点的距离
    Point(int n,int d):number(n),distance(d){}
    bool operator <(const Point& a)const{//距离小的优先级高
        return distance>a.distance;
    }
};
void Dijkstra(int n){
    priority_queue<Point> myQueue;//存储起点到各个点的最短路径数据(编号与距离)
    dis[n] = 0;
    cost[n] = 0;
    myQueue.push(Point(n,dis[n]));//放入起点
    while (!myQueue.empty()) {
        int num = myQueue.top().number;//找出与当前最短路径点集合中相连边权值最小的点序号num
        myQueue.pop();//弹出
        for (int i = 0; i < graph[num].size(); ++i) {
            //遍历与num相连的边的点v,如果包含最短路径,则更新v的最短距离
            int v = graph[num][i].to;
            int w = graph[num][i].length;
            int p = graph[num][i].price;
            if (dis[v] == dis[num] + w && cost[v] > cost[num] + p
                || dis[v] > dis[num] + w) {
                //优先选择距离短的,在距离相等时选择花费更少的
                dis[v] = dis[num] + w;
                cost[v] = cost[num] + p;
                myQueue.push(Point(v, dis[v]));//如果有更短的路径,则加入最短路径点集合
            }
        }
    }
    return;
}
int main(){
    int n,m;
    while (scanf("%d%d",&n,&m)!=EOF) {
        if (n == 0 && m == 0) {
            break;
        }
        memset(graph, 0, sizeof(graph));//图初始化
        fill(dis, dis + n + 1, INF);//初始化距离为正无穷
        fill(cost, cost + n + 1, INF);//初始化花费为正无穷
        while (m--) {
            int a,b,x,p;
            scanf("%d%d%d%d",&a,&b,&x,&p);
            graph[a].push_back(Edge(b,x,p));//加入边的数据
            graph[b].push_back(Edge(a,x,p));
        }
        int from,to;
        scanf("%d%d",&from,&to);
        Dijkstra(from);
        if(dis[to] == INF){
            dis[to] = -1;
        }
        printf("%d%d\n",dis[to],cost[to]);
    }
    return 0;
}

Floyd多点最短路径

当dis[i][j] < dis[i][k] + dis[k][j]时

dis[i][j] = dis[i][k] + dis[k][j];//找到更短的路径

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = INT_FAST32_MAX;
const int MAXN = 200;//最大顶点数目
int dis[MAXN][MAXN];//dis[i][j]表示顶点i到顶点j的最短距离
void Floyd(int n){
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (dis[i][k] != INF && dis[k][j] != INF && dis[i][j] > dis[i][k] + dis[k][j]) {
                    dis[i][j] = dis[i][k] + dis[k][j];//找到更短的路径
                }
            }
        }
    }
}
int main(){
    int n,m;//n为定点数,m为边数
    int u,v,w;//分别为边的起点,终点,权值
    fill(dis[0],dis[0] + MAXN * MAXN,INF);//初始化dis数组
    scanf("%d%d",&n,&m);//顶点数n,边数m
    for (int i = 0; i < m; ++i) {
        scanf("%d%d%d",&u,&v,&w);
        dis[u][v] = w;//以有向图输出为例
    }
    for (int i = 0; i < n; ++i) {//顶点i到顶点i的距离为0
        dis[i][i] = 0;
    }
    Floyd(n);
    for (int i = 0; i < n; ++i) {//输出dis数组
        for (int j = 0; j < n; ++j) {
            printf("%d ",dis[i][j]);
        }
        printf("\n");
    }
    return 0;
}

TSP单源最短路径*

中国邮递员问题

选址问题

拓扑排序*

判断能否产生拓扑序列

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;
const int MAXN = 500;
int indegree[MAXN];//存储入度的数组
vector<int> graph[MAXN];//邻接表
bool TopologicalSort(int n){//拓扑排序
    queue<int> node;//此队列存放入度为0的点序号
    for (int i = 0; i < n; ++i) {//遍历n个点
        if (indegree[i] == 0) {//入度为0则入队
            node.push(i);
        }
    }
    int number = 0;//拓扑序列定点个数
    while (!node.empty()) {//如果队列中含有入度为0的元素
        int x = node.front();//保存队头元素并且出队
        node.pop();
        number++;//拓扑序列定点加1
        for (int i = 0; i < graph[x].size(); ++i) {
            int y = graph[x][i];
            indegree[y]--;//后继顶点入度减1
            if (indegree[y] == 0) {//新来个入度为0的点,入队
                node.push(y);
            }
          
        }
    }
    return number == n;//判断能否产生拓扑序列
}
int main(){
    int n,m;
    while (scanf("%d%d",&n,&m)!=EOF) {
        if (n == 0 && m == 0) {
            break;
        }
        memset(indegree, 0, sizeof(indegree));//初始化入度
        memset(graph, 0, sizeof(graph));//初始化图
        while (m--) {//建立邻接表
            int a, b;
            scanf("%d%d",&a,&b);
            graph[a].push_back(b);
            indegree[b]++;
        }
        if (TopologicalSort(n)) {
            printf("YES\n");
        }else{
            printf("NO\n");
        }
    }
    return 0;
}

产生拓扑序列

主要思想是引入priority_queue,每次出队都记录在<vector>中

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;
const int MAXN = 500;
int indegree[MAXN];//存储入度的数组
vector<int> graph[MAXN];//邻接表
vector<int> TopologicalSort(int n){//拓扑排序
    vector<int> Topo;
    priority_queue<int,vector<int>,greater<int>> node;//此队列存放入度为0的点序号,以编号小为优先的优先队列
    for (int i = 1; i <= n; ++i) {//遍历n个点x,序号从1~n
        if (indegree[i] == 0) {//入度为0则入队
            node.push(i);
        }
    }
    while (!node.empty()) {//如果队列中含有入度为0的元素
        int x = node.top();//保存队头元素并且出队,优先队列priority_queu的首元素是top()
        node.pop();
        Topo.push_back(x);//加入拓扑序列
        for (int i = 0; i < graph[x].size(); ++i) {
            int y = graph[x][i];
            indegree[y]--;//后继顶点入度减1
            if (indegree[y] == 0) {//新来个入度为0的点,入队
                node.push(y);
            }
          
        }
    }
    return Topo;//判断能否产生拓扑序列
}
int main(){
    int n,m;
    while (scanf("%d%d",&n,&m)!=EOF) {
        memset(indegree, 0, sizeof(indegree));//初始化入度
        memset(graph, 0, sizeof(graph));//初始化图
        while (m--) {//建立邻接表
            int a, b;
            scanf("%d%d",&a,&b);
            graph[a].push_back(b);
            indegree[b]++;
        }
        vector<int> ans = TopologicalSort(n);//产生拓扑序列
        for (int i = 0; i < ans.size(); ++i) {
            if (i == 0) {
                printf("%d",ans[i]);
            }else{
                printf(" %d",ans[i]);
            }
        }
        printf("\n");
    }
    return 0;
}

关键路径

最早开始时间与最晚开始时间的计算

求关键路径长度:

  • 求最早开始时间:根据拓扑序列逐一求出每个活动的最早开始时间
  • 求最晚开始时间:根据拓扑序列的逆序求出每个活动的最晚开始时间
  • 关键活动:所有活动中最早开始时间和最晚开始时间相同的活动为关键活动
  • 关键路径长度:所有活动中最早开始时间的最大值便是关键路径长度

初始化:所有结点初始化为0,汇点的最晚开始时间初始化为它的最早开始时间,其余结点初始化INF

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
const int INF = INT_FAST16_MAX;
const int MAXN = 1001;
struct Edge{
    int to;//终点
    int length;//长度
    Edge(int t,int l):to(t),length(l){}
};
vector<Edge> graph[MAXN];
int indegree[MAXN];
int earliest[MAXN];//最早开始时间
int latest[MAXN];//最晚开始时间
void CriticalPath(int n){
    vector<int> Topo;//拓扑排序
    queue<int> node;
    for (int i = 0; i < n; ++i) {//将入度为0的结点入队
        if (indegree[i] == 0) {
            node.push(i);
            earliest[i] = 1;//初始化最早开始活动时间为1
        }
    }
    while (!node.empty()) {//计算出拓扑序列并且算出最早开始时间earliest[]
        int x = node.front();//将队列首元素找出来
        Topo.push_back(x);
        node.pop();
        for (int i = 0; i < graph[x].size(); ++i) {//从队首元素开始,遍历其相连的每一条边
            int v = graph[x][i].to;
            int l = graph[x][i].length;
            earliest[v] = max(earliest[v], earliest[x] + l);//最早开始时间
            indegree[v]--;//相邻点的入度减1
            if (indegree[v] == 0) {//入度为0则入队
                node.push(v);
            }
        }
    }
        for (int i = Topo.size() - 1; i >= 0; --i) {
            int u = Topo[i];//拓扑序列的最后一个元素开始,从后往前推算
            if (graph[u].size() == 0) {//如果是汇点,则最晚时间与最早时间相同
                latest[u] = earliest[u];
            } else {//非汇点的最晚开始时间初始化
                latest[u] = INF;
            }
            for (int j = 0; j < graph[u].size(); ++j) {//从u结点的邻接边开始计算
                int v = graph[u][j].to;
                int l = graph[u][j].length;
                latest[u] = min(latest[u], latest[v] - l);
            }
        }
}
int main(){
    int n,m;
    while (scanf("%d%d",&n,&m)) {
        memset(graph, 0, sizeof(graph));
        memset(indegree, 0, sizeof(indegree));
        memset(earliest, 0, sizeof(earliest));
        memset(latest, 0, sizeof(latest));
        while (m--) {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            graph[x].push_back(Edge(y,z));
            indegree[y]++;
        }
        CriticalPath(n);
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = max(ans,earliest[i]);
        }
        printf("%d\n",ans);
    }
    return 0;
}

搜索

八皇后问题

递归解法

#include <iostream>
#include <cmath>
using namespace std;
int N;
int queen[100];  // 用来存放算好的皇后的位置,最左上角是(0,0),最多有100个皇后
void NQueen(int k){ // 在0~k-1行皇后已经摆好的情况下,摆第k行及其后的皇后
    int i;
    if (k == N) {
        for (i = 0; i < N; i++) {
            cout << queen[i] + 1 << " ";
        }
        cout << endl;
        return;
    }
    for ( i = 0; i < N ; i++ ) {// i表示列
        int j;
        for ( j = 0; j < k; j++) {
            // 和已经摆好的k个皇后位置比较,看是否冲突
            if ( queen[j] == i // 避免同列,queen[j]存第j+1行皇后所在的列
                || abs(queen[j] - i) == abs(k - j)) { // 避免在一条斜线上,即行差不能等于列差 |queen[j] - i| !=|k-j|
                break;// 冲突,测试下一个位置
            }
        }
        if (j == k) {// 当前选的位置i不冲突
            queen[k] = i;// 将第k个皇后摆放在位置i
            NQueen(k+1);// 摆放后续的皇后
        }
    }// for ( i = 0; i < N ; i++ )
}
int main() {
    cin >> N;
    NQueen(0);   // 从第0行开始摆皇后
    return 0;
}

回溯解法

设计一种算法,打印 N 皇后在 N × N 棋盘上的各种摆法,其中每个皇后都不同行、不同列,也不在对角线上。这里的“对角线”指的是所有的对角线,不只是平分整个棋盘的那两条对角线。

注意:本题相对原题做了扩展

示例:

输入:4
输出:[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释: 4 皇后问题存在如下两个不同的解法。
[
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],

["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
思路:
回溯法:

冲突判断,对应当前row和col只需要判断是否和已存在的queen位置是否冲突,而
1,queen_pos记录之前放置的所有皇后的位置,索引i表示行信息,对应的值记录的为列信息,size表示有几个皇后。
2,行和列分别通过row和col是否与i和queen_pos[i]相等来判断
3,左斜线冲突通过row和col之和判断,右斜线通过两点的row和col交叉和判断

同时回溯
vector<string>& ans
vector<int>& queen_pos

class Solution {
public:
    bool valid(vector<int>& queen_pos, int row, int col) {//对位置(row,col)进行合法性判断
      for (int i = 0; i < queen_pos.size(); ++i) {//对已排好的皇后位置一一扫描
        if (i == row || //如果行或列与之前的皇后所在行或列相同,说明不合法
            col == queen_pos[i] ||
            abs(i - row) == abs(queen_pos[i]-col)) {//与皇后在同一个斜线上也是不合法的
          return false;
        }
      }
      return true;
    }
//n是皇后个数,index_i是当前摆放的皇后所在行,queen_pos记录之前各行皇后列位置,ans当前解
    void inner(int n, int index_i, 
               vector<int>& queen_pos, vector<string>& ans,
               vector<vector<string>>& res) {
      if (n == index_i) {//到达叶结点
        res.push_back(ans);//将一个解放入解集合中
        return;
      }

      for (int j = 0; j < n; ++j) {//子集树搜索,对每一列进行判断
        if (valid(queen_pos, index_i, j)) {//如果当前位置合法
          ans[index_i][j] = 'Q'; //记录新皇后位置
          queen_pos.push_back(j);//记录新的皇后列位置
          inner(n, index_i + 1, queen_pos, ans, res);//继续搜索下一个皇后
          queen_pos.pop_back();//回溯复原
          ans[index_i][j] = '.'; //回溯复原
        }
      }
    }
    vector<vector<string>> solveNQueens(int n) {
      vector<int> queen_pos;
      vector<string> ans(n, string(n, '.'));//先将所有n个字符串全赋值为'.'
      vector<vector<string>> res;
      inner(n, 0, queen_pos, ans, res);
      return res;
    }
};

迷宫问题(广度优先搜索)

#include <cstdio>
#include <cstring>
using namespace std;
int map[6][6]; //地图
int vis[6][6]; //判重
int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
//坐标优先级:往下走>往上走>往左走>往右走
//能往下走就往下走,如果下走遇到墙壁,往右走
struct node{
    int x,y; //坐标
    int c;   //上一点
}queue[6*6];
void print(int head) //输出坐标点,一开始的head值为终点坐标点的head,
{                                  //它往上找的点,head指向的都是最短路径的坐标
    while(queue[head].c != -1)  //上一点存在时
    {
        print(queue[head].c);//先输出上一点坐标
        printf("(%d, %d)\n",queue[head].x,queue[head].y);//输出该点坐标
        return;
    }
    printf("(0, 0)\n");
}
void bfs(int x,int y)
{
    int head = 0,tail = 1;//一开始队列为空
    int i;
    queue[0].x = 0;
    queue[0].y = 0;
    queue[0].c = -1;
    struct node now;//当前点
    while(head < tail)
    {
        if(queue[head].x == 4 && queue[head].y == 4)
        {//到达终点,直接输出
            print(head);
            return;
        }
        for(i = 0;i < 4;i++)
        {//先确定当前的可能坐标
            now.x = queue[head].x + dir[i][0];
            now.y = queue[head].y + dir[i][1];
            now.c = head;//上一点为head
            if(now.x >= 0 && now.x <= 4 && now.y >= 0 && now.y <= 5)
            {// 当前点位置符合要求
                if(!vis[now.x][now.y] && !map[now.x][now.y])
                {//如果没有被访问过,并且地图上也是可以走的
                    vis[now.x][now.y] = 1;//置访问为为1,标记访问过,[0][0]没能有机会被标记
                    queue[tail] = now;//加入路径队列队尾
                    tail++;
                }
            }
        }
        head++;
    }
}
int main()
{
    int i,j;
    for(i = 0;i < 5;i++)
    {
        for(j = 0;j < 5;j++)
        {
            scanf("%d",&map[i][j]);
        }
    }
    memset(vis,0,sizeof(vis));
    bfs(0,0);
    return 0;
}

ROAD

N个城市,编号1到N。城市间有R条单向道路。
每条道路连接两个城市,有长度和过路费两个属性。
Bob只有K块钱,他想从城市1走到城市N。问最短共需要走多长的路。如果到不了N,输出-1
2<=N<=100
0<=K<=10000
1<=R<=10000
每条路的长度 L, 1 <= L <= 100
每条路的过路费T , 0 <= T <= 100

输入:
K N R s1
e1 L1 T1
s1 e2 L2 T2
...
sR eR LR TR
s e是路起点和终点

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int K,N,R;
struct Road {
    int d,L,t;
};
vector<vector<Road> > cityMap(110); //邻接表。 cityMap[i]是从点i有路连到的城市集合
int minLen = 1 << 30; //当前找到的最优路径的长度
int totalLen; //正在走的路径的长度
int totalCost ; //正在走的路径的花销
int visited[110]; //城市是否已经走过的标记
int minL[110][10100]; //minL[i][j]表示从1到i点的,花销为j的最短路的长度11
void Dfs(int s) //从 s开始向N行走
{
    if( s == N ) {
        minLen = min(minLen,totalLen);
        return ;
    }
    for( int i = 0 ;i < cityMap[s].size(); ++i ) {
        int d = cityMap[s][i].d; //s 有路连到d
        if(! visited[d] ) {
            int cost = totalCost + cityMap[s][i].t;
            if( cost > K)
                continue;
            if( totalLen + cityMap[s][i].L >= minLen ||
               totalLen + cityMap[s][i].L >= minL[d][cost])
                continue;
            totalLen += cityMap[s][i].L;
            totalCost += cityMap[s][i].t;
            minL[d][cost] = totalLen;
            visited[d] = 1;
            Dfs(d);
            visited[d] = 0;
            totalCost -= cityMap[s][i].t;
            totalLen -= cityMap[s][i].L;
        }
    }
}
int main()
{
    cin >>K >> N >> R;
    for( int i = 0;i < R; ++ i) {
        int s;
        Road r;
        cin >> s >> r.d >> r.L >> r.t;
        if( s != r.d )
            cityMap[s].push_back(r);
    }
    for( int i = 0;i < 110; ++i )
        for( int j = 0; j < 10100; ++ j )
            minL[i][j] = 1 << 30;
    memset(visited,0,sizeof(visited));
    totalLen = 0;
    totalCost = 0;
    visited[1] = 1;
    minLen = 1 << 30;
    Dfs(1);
    if( minLen < (1 << 30))
        cout << minLen << endl;
    else
        cout << "-1" << endl;
}

八数码*

在3×3的棋盘上,摆有八个棋子,每个棋子上标有1至8的某一数字。棋盘中留有一个空格,空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是:给出一种初始布局(初始状态)和目标布局(为了使题目简单,设目标状态为123804765),找到一种最少步骤的移动方法,实现从初始布局到目标布局的转变。

#include<cstdio>
#include<cstring>
#include<set>
using namespace std;
typedef int State[9];//定义一个数组,专门存储九宫格的数字变成一维后的数组
const int MAXSTATE=1000000;
State st[MAXSTATE],goal={1,2,3,8,0,4,7,6,5};
int dist[MAXSTATE];
set<int> vis;//vis存储每一步的移动过程
void init_lookup_table() { vis.clear(); }//初始化
int try_to_insert(int s)
{//第s种方案是否满足要求
    int v=0;//将st中的第s中方案的数组组合变为数字
    for(int i=0;i<9;i++) v=v*10+st[s][i];
    if(vis.count(v)) return 0;//如果vis里面有v这个数字,则返回
    vis.insert(v);//如果没有v这种方案,则插入
    return 1;
}
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};//dx,dy分别存储移动一格时的x轴y轴变化
int bfs()
{
    init_lookup_table();//初始化vis集合
    int front=1,rear=2;
    while(front<rear)
    {
        State& s=st[front];//s为st的当前状态
        if(memcmp(goal,s,sizeof(s))==0) return front;
        //对目标goal状态与当前s状态进行比较,如果相同则说明完成移动状态,返回front
        int z;//如果不相同,说明需要继续调整
        for(z=0;z<9;z++) if(!s[z]) break;//遍历当前状态,找到空格的坐标
        int x=z/3,y=z%3;//将空格坐标转化为3*3九宫格的x,y坐标
        for(int d=0;d<4;d++)
        {//移动新的位置,每个方向都试一试
            int newx=x+dx[d];
            int newy=y+dy[d];
            int newz=newx*3+newy;//空格移动到的新位置
            if(newx>=0 && newx<3 && newy>=0 && newy<3)
            {//如果移动的位置满足要求,则记录当前的状态到st[rear]
                State& t=st[rear];//利用指针改变st[rear]存储一维数字,改变的只是空格的移动位置关系
                memcpy(&t,&s,sizeof(s));
                //必须先复制front位置s到st[rear]上,之后的t指针的复制操作才有意义
                t[newz]=s[z];//新空格的位置为原来空格位置的值即   t[new] = 0;
                t[z]=s[newz];//新位置的原来空格位置是原来位置的数字
                dist[rear]=dist[front]+1;//rear代表前一个位置front改变到当前状态时的移动次数
                if(try_to_insert(rear)) rear++;//将当前可移动状态加入到set中
            }
        }
        front++;
    }
    return 0;
}
int main()
{
    char s[15];
    scanf("%s",s);
    for(int i=0;i<9;i++)
        st[1][i]=s[i]-'0';//存储初始状态
    //  for(int i=0;i<9;i++) printf(" %d ",st[1][i]);
    int ans = bfs();
    printf("%d\n", dist[ans]);
    return 0;
}

动态规划

最长回文子串

给定一个字符串s,找到其中最长的回文子序列。可以假设s的最大长度为1000。

示例 1:
输入:

"bbbab"

输出:

4

一个可能的最长回文子序列为 "bbbb"。

示例 2:
输入:

"cbbd"

输出:

2

一个可能的最长回文子序列为 "bb"。

思路:

状态
f[i][j] 表示 s 的第 i 个字符到第 j 个字符组成的子串中,最长的回文序列长度是多少。

转移方程
如果 s 的第 i 个字符和第 j 个字符相同的话

f[i][j] = f[i + 1][j - 1] + 2

如果 s 的第 i 个字符和第 j 个字符不同的话

f[i][j] = max(f[i + 1][j], f[i][j - 1])

然后注意遍历顺序,i 从最后一个字符开始往前遍历,j 从 i + 1 开始往后遍历,这样可以保证每个子问题都已经算好了。

初始化
f[i][i] = 1 单个字符的最长回文序列是 1

结果
f[0][n - 1]
遍历顺序:
1、遍历的过程中,所需的状态必须是已经计算出来的。
2、遍历的终点必须是存储结果的那个位置。

回文子序列问题,详见前文「子序列问题模板」,我们通过过对 dp 数组的定义,确定了 base case 处在中间的对角线,dp[i][j] 需要从 dp[i+1][j], dp[i][j-1], dp[i+1][j-1] 转移而来,想要求的最终答案是 dp[0][n-1],如下图:

img

这种情况根据刚才的两个原则,就可以有两种正确的遍历方式:

img

要么从左至右斜着遍历,要么从下向上从左到右遍历,这样才能保证每次 dp[i][j] 的左边、下边、左下边已经计算完毕,得到正确结果。

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size();
        int dp[n][n];//从i到j的最长回文子序列
        memset(dp,0,sizeof(dp));
        for(int i = n - 1;i >= 0;--i){
            for(int j = i;j < n;++j){
                if( i == j){
                    dp[j][i] = 1;
                }else{
                    if(s[i] == s[j]){
                        dp[i][j] = dp[i + 1][j - 1]+ 2;
                    }else{
                        dp[i][j] = max(dp[i + 1][j - 1],max(dp[i + 1][j],dp[i][j - 1]));
                    }
                }
            }
        }
        return dp[0][n - 1];
    }
};

凑硬币问题

问题描述

现有面值为c1,c2,...,cm

c1,c2,...,cm元的m种硬币,求支付n元时所需硬币的最少枚数。各面值的硬币可重复使用任意次。

输入:
n m
c1 c2 … cm
第1行输入整数n和整数m,用1个空格隔开。第2行输入各硬币的面值,相邻面值间用1个空格隔开。
输出:
输出所需硬币的最少枚数,占1行。
限制:
1 ≤ n ≤ 50000
1 ≤ m ≤ 20
1 ≤ 面值 ≤ 10000
各面值均不相同,其中必包含1

解法:

C[m]:一维数组,C[i]表示第 i 种硬币的面值
T[j]:一维数组,T[j]表示使用第0至第 i 种硬币支付 j 元时的最少硬币枚数。

支付 j 元时的最少枚数可以作为一维数组元素T[j],由下面的式子求得:

T[j]=min(T[j],T[j−C[i]]+1)

#include<iostream>
#include<algorithm>
using namespace std;
const int MMAX = 20;
const int NMAX = 50000;
const int INFTY = (1<<29);
int main(){
    int n, m;//n为总找钱值,m为硬币种类数目
    int w[MMAX + 1];//C存储着硬币的面值
    int dp[NMAX + 1];//dp[j]表示找钱价值为j时,所需要的最少纸币数目
    cin>>n>>m;
    for(int i = 1; i <= m; i++) {
        cin>>w[i];
    }
    for(int i = 0; i <= NMAX; i++) dp[i] = INFTY;//初始化
    dp[0] = 0;
    for(int i = 1; i <= m; i++) {
        for(int j = w[i]; j <= n; j++) { 
//可以看成是总容量为找零总额,物品重量为硬币面值,其物品价值为1 的 0-1背包问题
            dp[j] = min(dp[j], dp[j-w[i]] + 1);
        }
    }
    cout<<dp[n]<<endl;
    return 0;
}

0-1背包问题

N 种物品和一个容量是 V 的背包,每种物品只有一件可用

第 i 种物品的体积是 v[i] ,价值是 w[i]

求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。输出最大价值。

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
int main()
{
    int N,M;// N为物品个数,M为背包总容量
    scanf("%d%d",&N,&M);
    int i,j;
    int dp[15000]={0};// dp[x]存储容量为x时的最大价值
    int w[5000],v[5000];// 第i件物品的体积w[i],价值是v[i]
    for (i=0;i<=N-1;i++)
        scanf("%d%d",&w[i],&v[i]);// 输入每件物品的体积、价值
    for (i=0;i<=N-1;i++)
    {
       for (j=M;j>=w[i];j--)// 往背包放东西,剩余空间大于所选择的物品才可以放
        {
            dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
//   如果放入背包后的价值大于当前容积的价值,则放入背包,更新dp[j]
        }
    }
    printf("%d\n",dp[M]);
    return 0;
}

割绳子问题

给你一根长度为 n 的绳子,请把绳子剪成整数长度的 m 段(m、n都是整数,n>1并且m>1),每段绳子的长度记为 k[0],k[1]...k[m] 。请问 k[0]*k[1]*...*k[m] 可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。

示例 1:

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1

示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

思路:

  • ==dp[i]表示i的最大子段乘积==
  • dp[i]依赖前置的每个状态dp[j] (1 <= j < i)
  • 从dp[j]转移到dp[i]又有两种状态,j要么分割,要么不分割。其中dp[j]存放分割情况下的最大值,而j刚好为不分割的值。
  • 因此dp[i]从dp[j]转移过来的方程为 dp[i] =max(dp[i - j] * dp[j]); 1 <= j < i
  • i前面所有的j都转移过来的最大值dp[i] = max(dp[i], dp[i - j] * dp[j]);
#include<iostream>
#include <cstring>
using namespace std;
int main(){
    int n,dp[70]={0};
    cin >> n;
    dp[1] = 1;
    for (int i = 2; i <= n; ++i) {
        for (int j = 1; j < i; ++j) {
            dp[i] = max(dp[i], dp[i - j] * dp[j]);
        }
        if (i != n) {
            dp[i] = max(dp[i], i);
        }
    }
    cout << dp[n];
    return 0;
}

股票利润问题

假设把某股票的价格按照时间先后顺序存储在数组中,请问买卖该股票一次可能获得的最大利润是多少?

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

方法1:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int Min = 99999999,Maxall = 0;
        int Max[100005] = {0};
        for(int i = 0; i < prices.size();++i){
            if(prices[i] < Min){
                Min = prices[i];
                continue;
            }
            Max[i] = prices[i] - Min;
        }
        for(int i = 1; i < prices.size();++i){
            if(Max[i] > Maxall){
                Maxall = Max[i];
            }
        }
        return Maxall;
    }
};

方法2:

使用动态规划算法之前,一般都需要先解决两个问题:

定义何种数组来表示各个阶段的状态

如何通过前阶段已有的状态,推出现阶段的状态
在这道题,我们定义一个二维数组 dp[n][2]来表示 n 个阶段的状态。

dp[i][0]表示前 i 天,没有持有股票状态下的大利润(经过i天后手上没有股票,要么今天卖了,要么之前已经卖过了)

转移方程:dpi=max(dpi−1,dpi−1+price[i])
dp[i][1] 表示前 i 天,持有股票状态下的最大利润(经过i天后手上还有股票,要么今天买了,要么之前已经买过了)

转移方程:dpi=max(dpi−1,0−price[i])
而我们需要的答案就是,前 n天没有持有股票状态下的最大利润:dp[n][0]

第二个状态转移方程,正常来讲应该写成:dp[i][1]=max(dp[i−1][1],dp[i][0]−price[i]),但上面 max 的第二个参数却是 0−price[i]

这是因为题目要求股票只能买卖一次,0 表示未进行股票交易时的初始金额,而 dp[i−1][0] 表示前 i−1天未持有股票状态下的最大利润,但前 i−1天可能完成了多次股票交易,所以不满足条件。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() == 0) {
            return 0;
        }
        int dp[200010][2];
        dp[0][0] = 0, dp[0][1] = -prices[0];
        for (int i = 1; i < prices.size(); i ++) {
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
            dp[i][1] = max(dp[i-1][1], 0 - prices[i]);
        }
        return dp[prices.size() - 1][0];
    }
};

优化动态规划:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int cur_0 = 0, cur_1 = INT_MIN;
        for (int i = 0; i < prices.size(); i ++) {
//没持有股票时的最大利润=昨天的没持有股票利润或把昨天持有的股票卖掉的利润 中更大值
            cur_0 = max(cur_0, cur_1 + prices[i]);
//持有股票时的最大利润=昨天的持有股票利润或把今天的股票买了(损失)的价钱 中更大值          
            cur_1 = max(cur_1, 0 - prices[i]);
        }
        return cur_0;
    }
};

完全背包问题

N 种物品和一个容量是 V 的背包,每种物品都有无限件可用

第 i 种物品的体积是 v[i],价值是 w[i]

求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。输出最大价值。

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
int main()
{
    int N,M;// N为物品个数,M为背包总容量
    scanf("%d%d",&N,&M);
    int i,j;
    int dp[15000]={0};// dp[x]存储容量为x时的最大价值
    int w[5000],v[5000];// 第i件物品的体积w[i],价值是v[i]
    for (i=0;i<=N-1;i++)
        scanf("%d%d",&w[i],&v[i]);// 输入每件物品的体积、价值
    for (i=0;i<=N-1;i++)
    {
       for (j=w[i];j<=M;j++)// 往背包放东西,剩余空间大于所选择的物品才可以放
        {// 从选择的物品的体积开始选择物品(从前往后)
            dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
//   如果放入背包后的价值大于当前容积的价值,则放入背包,更新dp[j]
        }
    }
    printf("%d\n",dp[M]);
    return 0;
}

多重背包

总体思路:多重背包主要把它转化成0-1背包问题,同一个种类的物品有多个,那就在数组里面重复存储就好,其他和0-1背包一样,也是从后往前推

#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 10000;
int dp[MAXN];
int v[MAXN];
int w[MAXN];
int k[MAXN];
int weight[MAXN];
int value[MAXN];
int main(){
    int CaseNumber;
    scanf("%d",&CaseNumber);
    while (CaseNumber--) {
        int n,m;
        scanf("%d%d",&m,&n);
        int number = 0;
        for (int i = 0; i < n; ++i) {
            scanf("%d%d%d",&w[i],&v[i],&k[i]);
            for (int j = 1; j <= k[i]; ++j) {
                weight[number] = w[i];
                value[number] = v[i];
                number++;
            }
        }
        for (int i = 0; i <= m; ++i) {
            dp[i] = 0;
        }
        for (int i = 0; i < number; ++i) {
            for (int j = m; j >= weight[i] ; --j) {
                dp[j] = max(dp[j], dp[j - weight[i]]+value[i]);
            }
        }
        printf("%d\n",dp[m]);
    }
    return 0;
}

最长上升子序列

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1010;
int a[MAXN];
int maxLen[MAXN];
int ans = -1;
int main()
{
    int N;// 序列的长度
    cin >> N;
    for (int i = 1; i <= N; ++i) {
        cin >> a[i];
        maxLen[i] = 1;
    }// 输入序列
    for (int i = 2; i <= N; ++i) {
    // 每次求以第i个数为终点的最长上升子序列
        for (int j = 1; j < i; ++j){
    // 查看以第j个数为终点的最长上升子序列
            if (a[i] > a[j]){// 若终点i比之前的最长序列的终点大
                maxLen[i] = max(maxLen[i], maxLen[j]+1);// 则最长序列+1
            }
        }
    }
    for(int i = 1; i <= N; i++)
        ans = max(ans, maxLen[i]);
    printf("%d\n",ans);
    //cout << * max_element(maxLen, maxLen + N + 1);
      //max_element是用来来查询最大值所在的第一个位置。
    return 0;
}                                             

最长公共子序列

image-20200307170718151

image-20200307170758843

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
char sz1[1000];
char sz2[1000];
int maxLen[1000][1000];
int main()
{
    while (cin >> sz1 >> sz2) {
        int length1 = strlen(sz1);
        int length2 = strlen(sz2);
        int i,j;// 设置边界条件
        for (i = 0; i <= length1; ++i) {
            maxLen[i][0] = 0;
        }
        for (j = 0; j <= length2; ++j) {
            maxLen[0][j] = 0;
        }
        for (i = 1; i <= length1; ++i) {
            for (j = 1; j <= length2; ++j) {
                if (sz1[i-1] == sz2[j-1]) {
                    maxLen[i][j] = maxLen[i-1][j-1] + 1;
                }else{
                       maxLen[i][j] = max(maxLen[i][j-1],
                                          maxLen[i-1][j]);
                    }
            }
        }
        cout << maxLen[length1][length2] << endl;
    }
    return 0;
}

最大连续子序列和

直接找最大

#include<stdio.h>
#include<algorithm>
using namespace std;
int main(){
    int N,i;
    while(scanf("%d",&N)!=EOF){
        long sum=0,Max=-999999999,x;
        for(i=0;i<N;i++){
            scanf("%ld",&x);
            sum=max(sum+x,x);
            Max=max(Max,sum);
        }
        printf("%ld\n",Max);
    }
}

简单动态规划

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[1000010];
int a[1000010];
long long maxx;
int main()
{
    int n ;
    while(cin>>n){
        for(int i=0;i<n;i++){
            cin>>a[i];
        }
        dp[0] = a[0];
        maxx = 0;
        for(int i=1;i<n;i++){
            dp[i] = max(dp[i-1]+a[i],a[i]);
            if(maxx<dp[i]){
                maxx = dp[i];
            }
        }
        cout<<maxx<<endl;
    }
   return 0;
}

最大子序列和的起点和终点

输入描述:

    测试输入包含若干测试用例,每个测试用例占2行,第1行给出正整数K( K< 10000 ),第2行给出K个整数,
    中间用空格分隔。当K为0时,输入结束,该用例不被处理。

输出描述:

    对每个测试用例,在1行里输出最大和、最大连续子序列的第一个和最后一个元素,中间用空格分隔。
    如果最大连续子序列不唯一,则输出序号i和j最小的那个(如输入样例的第2、3组)。
    若所有K个元素都是负数,则定义其最大和为0,输出整个序列的首尾元素。

小技巧:

  • 用==Sum[i]==表示x[1:i]子序列之和
  • 如果x[1:last]的序列和 - x[1:i]的序列和,说明找到了最大子序列和的起点i+1
#include<stdio.h>
#define max(a,b) a>b?a:b
int a[10005],Sum[10005];
int main(){
    int n,i,Max,sum,flag,last;
    //n为数字个数,Max为最大子序列和,sum为当前最大子序列和,flag标记是否出现正数
    while(scanf("%d",&n) != EOF && n){
        sum = 0,Max = -999999999,flag = 1;
        for(i = 1;i <= n;i++){
            scanf("%d",&a[i]);//输入n个数字a[1:n]
            if(a[i] >= 0) flag = 0;//如果大于0,则要进行正常输出
            sum = max(sum + a[i],a[i]);//sum为当前最大子序列和
            if(Max < sum){//找到比Max更大的数,将Max和尾节点更新
                Max = sum;
                last = i;//更新尾节点
            }
            Sum[i] = a[i] + Sum[i - 1];//Sum[i]为a[1:i]的序列之和
        }
        if(flag == 1) printf("0 %d %d\n",a[1],a[n]);//全是负数,输出0和整个序列的首尾元素
        else{//含有正数
            for(i = 0;i <= n;i++)//寻找头结点
                if(Sum[last] - Sum[i] == Max) break;
            //如果x[1:last]的序列和 - x[1:i]的序列和,说明找到了最大子序列和的起点i+1
            printf("%d %d %d\n",Max,a[i + 1],a[last]);
        }
    }
}

最大上升子序列和

动态规划求解
开始假设所有的数自成最大递增子序列,也就是sum[i]=num[i];
后面再从前向后遍历,如果前面某个数小于当前的数,那么那个数的最大递增子序列的和加上当前的数会构成更大的递增子序列和,找出所有这样的和的最大值作为以当前数为尾的最大递增子序列的和。

#include <iostream>
using namespace std;
int main()
{
    int n;
    int num[1001];
    int sum[1001];
    while(cin>>n)
    {
        int  maxsum = 0;
        for(int i = 0; i<n; i++)
        {
            cin>>num[i];
            sum[i] = num[i]; //初始化,所有数自成一个最大递增子序列
        }
        sum[0] = num[0];
        for(int i = 1; i<n; i++)
        {
            for(int j = i-1; j>=0; j--)
            {
                if(num[j]<num[i])   //符合递增子序列
                    sum[i] = max(sum[j]+num[i], sum[i]);
            }
        }
        maxsum = sum[0];
        for(int i = 1; i<n; i++)
        {
            if(maxsum<sum[i]) maxsum = sum[i];
        }
        cout<<maxsum<<endl;
    }
    return 0;
}

拦截导弹

#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 25;
int height[MAXN];   //导弹高度
int dp[MAXN];
int main(){
    int n;
    while (scanf("%d",&n)!=EOF) {
        for (int i = 0; i < n; ++i) {
            scanf("%d",&height[i]);
        }
        int answer = 0;
        for (int i = 0; i < n; ++i) {
            dp[i] = 1;  //初始化为1
            for (int j = 0; j < i ; ++j) {
                if (height[i] <= height[j]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            answer = max(answer, dp[i]);    //dp数组最大值
        }
        printf("%d\n",answer);
    }
    return 0;
}

最大子矩阵

思路:

  • 当 i = j 时,求最大子矩阵和就转换成了求第i行元素的最大连续子序列和
  • 当 i != j 时,把从第i行到第j行的所有元素按列分别求和,得到只有一行,n列的一维数组,这个一维数组的最大连续子序列和便是最大子矩阵和

技巧:

  • 当 i != j 时,不必将原始矩阵中的第i行到第j行的所有元素按列分别求和,累加起来的到一维数组,而事先用一个==辅助二维矩阵记录原始矩阵从上到下加起来的累加矩阵total[i][j]==,于是求从第i行到第j行的一维数组只需要将辅助矩阵进行一行减法便可以得到,而不需要逐行地进行多次累加
#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 100;
int matrix[MAXN][MAXN];//原始矩阵
int total[MAXN][MAXN];
//辅助矩阵,total[i][j]记录原始矩阵中第j列从第1行到第i-1行到加起来的数,即从上到下加起来的累加矩阵
int arr[MAXN];//arr[k]表示k列中,i行到j行的子序列和,从0计算
int dp[MAXN];//dp[i]表示以arr[i]结尾的连续序列最大和
int MaximumSequence(int n){//寻找一维数组最大连续子序列和
    int maxsum = 0;
    for (int i = 0; i < n; ++i) {
        if (i == 0) {
            dp[i] = arr[i];
        }else{
            dp[i] = max(dp[i-1] + arr[i], arr[i]);
        }
        maxsum = max(maxsum, dp[i]);
    }
    return maxsum;
}
int MaxSubMatrix(int n){
    int maximal = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; ++j) {
            for (int k = 0; k < n; ++k) {//获得arr[]一维数组
                if (i == 0) {
                    arr[k] = total[j][k];
                }else{
                    arr[k] = total[j][k] -total[i - 1][k];//k列中,i行到j行的子序列和
                }
            }
            int current = MaximumSequence(n);
            //i行到j行的矩阵中,找出行数固定的部分最大子矩阵和(行数:j-i+1,列数不一定)
            maximal = max(maximal, current);//更新最大子矩阵和
        }
    }
    return maximal;
}
int main(){
    int n;
    while (scanf("%d",&n)!=EOF) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                scanf("%d",&matrix[i][j]);
            }
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == 0) {//初始化辅助函数
                    total[i][j] = matrix[i][j];
                }else{//累加矩阵
                    total[i][j] = total[i - 1][j] + matrix[i][j];
                }
            }
        }
        int ans = MaxSubMatrix(n);
        printf("%d\n",ans);
    }
    return 0;
}

循环矩阵的最大子矩阵和

题目大意:给出一个矩阵,矩阵的上下边, 左右边使联通的, 要求在这个矩阵上找到一个子矩阵, 要求该子矩阵上所有元素的和最大。

解题思路:uva108 - Maximum Sum的升级版,将矩阵复制三份, 用四层循环遍历过所有满足条件的区间,遍历的过程中记录出现的最大值。

#include <stdio.h>
#include <string.h>
const int N = 200;
const int Min = -2147483645;
 
int n, Max, num[N][N], sum[N];
 
void input() {
    Max = Min;
    memset(num, 0, sizeof(num));
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) {
        scanf("%d", &num[i][j]);
        num[i + n][j + n] = num[i + n][j] = num[i][j + n] = num[i][j];
    }
}
 
int solve() {
    for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        memset(sum, 0, sizeof(sum));
        for (int k = i; k < n + i; k++) {//矩阵左上角为(i,j)
        int now = 0;
        for (int t = j; t < n + j; t++) {
            sum[t] += num[k][t];//sum[t]表示t列上i行到k行的数字和
            now +=sum[t];//now表示子矩阵左上角(i,j)到右下角(k,t)的数字和
            if (Max < now)//更新最大子矩阵和Max的值
            Max = now;
        }
        }
    }
    }
    return Max;
}
int main() {
    int cas;
    scanf("%d", &cas);
    while (cas--) {
    input();
    printf("%d\n", solve());
    }
    return 0;
}

数塔问题

#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 100;
int dp[MAXN][MAXN];
int matrix[MAXN][MAXN];
int main(){
    int n;
    scanf("%d",&n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= i ; ++j) {
            scanf("%d",&matrix[i][j]);
            dp[i][j] = matrix[i][j];
        }
    }//dp[i][j]i表示(i,j)出发到底部路径所有值之和的最大值,dp[0][0]是问题答案
//dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + dp[i][j]
//(i,j)的值为下方路径与右下方路径最大值加上(i,j)自身的权值
    for (int i = n - 1; i >= 0; --i) {
        for (int j = 0; j <= i; ++j) {
            dp[i][j] += max(dp[i+1][j], dp[i+1][j+1]);
        }
    }
    cout << dp[0][0];
    return 0;
}

神奇的口袋

有一个神奇的口袋,总的容积是40,用这个口袋可以变出一些物品,这些物品的总体积必须是40。

John现在有n(1≤n ≤ 20)个想要得到的物品,每个物品的体积分别是a1, a2……an。 John可以从这些物品中选择一些,如果选出的物体的总体积是40,那么利用这个神奇的口袋, John就可以得到这些物品。现在的问题是, John有多少种不同的选择物品的方式。
输入
输入的第一行是正整数n (1 <= n <= 20),表示不同的物品的数目。接下来的n行,每行有一个1到40之间的正整数,分别给出a1, a2……an的值。

输出
输出不同的选择物品的方式的数目

#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 100;
int dp[MAXN][MAXN];//dp[i][j]表示体积为i时,用了前面j种物品时最多的方案
int a[MAXN];
int main(){
    int n;
    scanf("%d",&n);
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= n; ++i) {//物品从a[1]开始放,a[i]表示第i件物品的体积
        scanf("%d",&a[i]);
        dp[0][i] = 1;//总体积为0的放法只有一种
    }
    dp[0][0] = 1;//补上漏掉的dp[0][0]
    for (int i = 1; i <= 40 ; ++i) {
        for (int j = 1; j <= n; ++j) {
            dp[i][j] = dp[i][j-1];//体积为i,用前j种方案时,至少有体积为i用前j-1种方案的次数
            if (i - a[j] >= 0) {
//如果第j件物品可以选下来(选择它体积不会溢出),则再加上没选上这件物品时的体积且用前j-1种方案的数量
                dp[i][j] += dp[i - a[j]][j-1];
            }
        }
    }
    cout << dp[40][n];
    return 0;
}

放苹果

/*
    M个苹果放在N个盘子里分法有:dp[M][N], 0 <= M,N <= 10
    设dp(m,n) 为m个苹果,n个盘子的放法数目,则先对n作讨论,
    当m<n:必定有n-m个盘子永远空着,去掉它们对摆放苹果方法数目不产生影响。dp(m,n) = dp(m,m)
    当m>=n:不同的放法可以分成两类:
        1、有至少一个盘子空着,即相当于dp(m,n) = dp(m,n-1);
        2、所有盘子都有苹果,相当于可以从每个盘子中拿掉一个苹果,不影响不同放法的数目,
        即dp(m,n) = dp(m-n,n).
        而总的放苹果的放法数目等于两者的和,即 dp(m,n) =dp(m,n-1)+dp(m-n,n)
    初始条件说明
        当m=0,n=0时,没苹果,没盘子,定为0种放法。这个条件在计算的时候用不到。题设至少一个盘子一个苹果。
        当m=0,n>0时,没苹果,有盘子,定为1种放法。这个有点抽象,考虑:dp[1][1]=dp[1][0]+dp[0][1]=0+1。
        当m>0,n=0时,有苹果,没盘子,定为0种放法。
        dp两条路,第一条n会逐渐减少,终会到达出口n=0;
        第二条m会逐渐减少,因为n>m时,会计算dp(m,m) 所以终会到达出口m=0.
*/
 
#include <stdio.h>
#if US_DP
int dp[11][11];
 
int main()
{
    int m, n;
 
    while (scanf("%d%d", &m, &n) != EOF) {
        for (int i = 1; i <= m; ++i)
            dp[i][0] = 0;
        for (int j = 1; j <= n; ++j)
            dp[0][j] = 1;
 
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (i >= j)
                    dp[i][j] = dp[i][j-1]+dp[i-j][j];
                else
                    dp[i][j] = dp[i][i];
            }
        }
        printf("%d\n", dp[m][n]);
    }
 
    return 0;
}
 
#else
 
int f(int m, int n)
{
    if (m >= 0 && n == 0)
        return 0;
    else if (m == 0 && n > 0)
        return 1;
    else if (m >= n)
        return f(m, n-1)+f(m-n, n);
    else
        return f(m, m);
}
 
int main()
{
    int m, n;
 
    while (scanf("%d%d", &m, &n) != EOF)
        printf("%d\n", f(m, n));
}
#endif

整数拆分

/*这道题确实可以用动态规划来解,它其实是一个完全背包求恰装满背包时的方案总数
问题.具体是,因为每一个拆分必须是1,2,4,2^3,...2^19(考虑n最大为10^6),
所以对于一个整数n,看它的这种拆分数有多少个,就相当于现在有20种物品,第i种物品
的花费是2^(i-1),每一种可以重复取, dp[i][j]表示前i种物品恰装满容量为j的物品时
的方案总数,从而dp[i][j] = dp[i-1][j] + dp[i][j-a[i]]
*/  
#include <iostream>
#include <string>
#include <vector>
#include <map>
 
#include <queue>
#include <stack>
#include <algorithm>
 
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>      //rand ( ), srand ( )
#include <ctime>        //time ( )
using namespace std;
 
int n, dp[1000002], a[21];
 
int main ( )
{
    int i, j, t;
    for ( i = 1; i <= 20; i ++ )
        a[i] = ( 1 << ( i - 1) );
    dp[0] = 1;
    while ( cin >> n )
    {
        memset ( dp + 1, 0, sizeof ( dp ) );
        for ( i = 1; i <= 20; i ++ )
        {
            for ( j = a[i]; j <= n; j ++ )
            {
                dp[j] += dp[j - a[i]];
                dp[j] %= 1000000000;
            }
        }
        cout << dp[n] << endl;
    }
    return 0;
}
 
  

石子游戏2

亚历克斯和李继续他们的石子游戏。许多堆石子 排成一行,每堆都有正整数颗石子 piles[i]。游戏以谁手中的石子最多来决出胜负。

亚历克斯和李轮流进行,亚历克斯先开始。最初,M = 1。

在每个玩家的回合中,该玩家可以拿走剩下的 前 X 堆的所有石子,其中 1 <= X <= 2M。然后,令 M = max(M, X)。

游戏一直持续到所有石子都被拿走。

假设亚历克斯和李都发挥出最佳水平,返回亚历克斯可以得到的最大数量的石头。

示例:

输入:piles = [2,7,9,4,4]
输出:10
解释:
如果亚历克斯在开始时拿走一堆石子,李拿走两堆,接着亚历克斯也拿走两堆。在这种情况下,亚历克斯可以拿到 2 + 4 + 4 = 10 颗石子。
如果亚历克斯在开始时拿走两堆石子,那么李就可以拿走剩下全部三堆石子。在这种情况下,亚历克斯可以拿到 2 + 7 = 9 颗石子。
所以我们返回更大的 10。

思路:

1,dpi 代表当前还剩下i堆石头,M为j的情况下能获取到的最大重量
2,状态转移方程为:
dpi = max{sums[N] - sums[i] - d[i - k][max(k, j)]} (1 <= k <= 2 * j)
sums[N] - sums[i]代表剩下i堆石头的总重量,若本次取k堆,那么下次取的时候M就变成了max(k, j),
下次能获取到的最大值对应到dp的定义就是dp[i - k][max(k, j)]
由此可得上面的转移方程

class Solution {
public:
    // dp[i][j] = max{sums[N] - sums[i] - dp[i - k][max(k, j)]} (1 <= k <= 2 * j)
    int stoneGameII(vector<int>& piles) {
        int N = piles.size();
        vector<int> sums(N + 1, 0);
        for (int i = 0; i < N; ++i) {
            sums[i + 1] = sums[i] + piles[i];
        }
        vector<vector<int> > dp(N + 1, vector<int>(N + 1, 0));
        for (int i = 0; i <= N; ++i) {
            for (int j = i; j <= N; ++j) {
                dp[i][j] = sums[N] - sums[N - i];
            }
        }
        for (int i = 1; i <= N; ++i) {
            for (int j = 1; j <= N; ++j) {
                for (int k = 1; k <= 2 * j && k <= i; ++k) {
                    dp[i][j] = max(dp[i][j], 
                                   sums[N] - sums[N - i] - dp[i - k][min(max(k, j), N)]);
                }
            }
        }
        return dp[N][1];
    }
};

石子游戏3

Alice 和 Bob 用几堆石子在做游戏。几堆石子排成一行,每堆石子都对应一个得分,由数组 stoneValue 给出。

Alice 和 Bob 轮流取石子,Alice 总是先开始。在每个玩家的回合中,该玩家可以拿走剩下石子中的的前 1、2 或 3 堆石子 。比赛一直持续到所有石头都被拿走。

每个玩家的最终得分为他所拿到的每堆石子的对应得分之和。每个玩家的初始分数都是 0 。比赛的目标是决出最高分,得分最高的选手将会赢得比赛,比赛也可能会出现平局。

假设 Alice 和 Bob 都采取 最优策略 。如果 Alice 赢了就返回 "Alice" ,Bob 赢了就返回 "Bob",平局(分数相同)返回 "Tie" 。

示例 1:

输入:values = [1,2,3,7]
输出:"Bob"
解释:Alice 总是会输,她的最佳选择是拿走前三堆,得分变成 6 。但是 Bob 的得分为 7,Bob 获胜。

示例 2:

输入:values = [1,2,3,-9]
输出:"Alice"
解释:Alice 要想获胜就必须在第一个回合拿走前三堆石子,给 Bob 留下负分。
如果 Alice 只拿走第一堆,那么她的得分为 1,接下来 Bob 拿走第二、三堆,得分为 5 。之后 Alice 只能拿到分数 -9 的石子堆,输掉比赛。
如果 Alice 拿走前两堆,那么她的得分为 3,接下来 Bob 拿走第三堆,得分为 3 。之后 Alice 只能拿到分数 -9 的石子堆,同样会输掉比赛。
注意,他们都应该采取 最优策略 ,所以在这里 Alice 将选择能够使她获胜的方案。

示例 3:

输入:values = [1,2,3,6]
输出:"Tie"
解释:Alice 无法赢得比赛。如果她决定选择前三堆,她可以以平局结束比赛,否则她就会输。

示例 4:

输入:values = [1,2,3,-1,-2,-3,7]
输出:"Alice"

示例 5:

输入:values = [-1,-2,-3]
输出:"Tie"

提示:

1 <= values.length <= 50000
-1000 <= values[i] <= 1000

class Solution {
public:
    string stoneGameIII(vector<int>& stoneValue) {
        int dp[50003] = {0};
        int sum = 0;
        for(int n = stoneValue.size(), i = n-1; i >= 0; i--) {
            dp[i] = INT_MIN;
            sum += stoneValue[i];
            for(int j = 1; j <= 3; j++) {
                dp[i] = max(dp[i], sum - dp[i+j]);
            }
        }
        if(sum - dp[0] == dp[0]) {
            return "Tie";
        } else if(sum - dp[0] > dp[0]) {
            return "Bob";
        }
        return "Alice";
    }
};

打家劫舍3

在上次打劫完一条街道之后和一圈房屋后,小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为“根”。 除了“根”之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫,房屋将自动报警。

计算在不触动警报的情况下,小偷一晚能够盗取的最高金额。

示例 1:

输入: [3,2,3,null,3,null,1]

     3
    / \
   2   3
    \   \ 
     3   1

输出: 7
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7

思路

和打家劫舍I一样,不能选择相邻的两个节点。所以对于一个子树来说,有两种情况:

包含当前根节点
不包含当前根节点
情况1:包含根节点

由于包含了根节点,所以不能选择左右儿子节点,这种情况的最大值为:当前节点 + 左儿子情况2 + 右二子情况2
情况2:不包含根节点

这种情况,可以选择左右儿子节点,所以有四种可能:

左儿子情况1 + 右儿子情况1
左儿子情况1 + 右儿子情况2
左儿子情况2 + 右儿子情况1
左儿子情况2 + 右儿子情况2
综合来说就是,max(左儿子情况1, 左儿子情况2) + max(右儿子情况1, 右儿子情况2)。
综合两种情况,深度优先,从叶子节点遍历到根节点即可。
代码实现

由于只有两种情况,可以选择使用pair来存储这两种情况的数据值。
pair的含义:<情况1包含当前节点的最大值,情况2不包含当前节点的最大值>

class Solution {
public:
    pair<int, int> dfs(TreeNode *root) {
        if (root == nullptr) {
            return { 0, 0 };
        }
        auto left_pair = dfs(root->left);
        auto right_pair = dfs(root->right);
        return { root->val + left_pair.second + right_pair.second, 
                max(left_pair.first, left_pair.second) + max(right_pair.first, right_pair.second) };
    }
  
    int rob(TreeNode* root) {
        auto p = dfs(root);
        return max(p.first, p.second);
    }
};

买卖k次股票

给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意: 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

示例 1:

输入: [2,4,1], k = 2
输出: 2
解释: 在第 1 天 (股票价格 = 2) 的时候买入,在第 2 天 (股票价格 = 4) 的时候卖出,这笔交易所能获得利润 = 4-2 = 2 。

示例 2:

输入: [3,2,6,5,0,3], k = 2
输出: 7
解释: 在第 2 天 (股票价格 = 2) 的时候买入,在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
随后,在第 5 天 (股票价格 = 0) 的时候买入,在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3

class Solution {
public:
    int maxProfit(int max_k, vector<int>& prices) {
        int n = prices.size();
        if(n == 0) return 0;
        if(max_k > n / 2) return maxProfit_inf(prices);
        int dp[n][max_k + 1][2];
        memset(dp,0,sizeof(dp));
        for(int i = 0; i < n; i++){
            for(int k = max_k ;k >= 1;k--){
                if(i == 0){
                    dp[i][k][0] = 0;
                    dp[i][k][1] = -prices[0];
                    continue;
                }
                dp[i][k][0] = max(dp[i - 1][k][0],dp[i - 1][k][1] + prices[i]);
                dp[i][k][1] = max(dp[i - 1][k][1],dp[i - 1][k-1][0] - prices[i]);
            }
    }
    return dp[n - 1][max_k][0];
}
int maxProfit_inf(vector<int>& prices){
    int n = prices.size();
    int dp[n][2];
    memset(dp,0,sizeof(dp));
    dp[0][0] = 0;
    dp[0][1] = -prices[0];
    for(int i = 1; i < n; i++){
        dp[i][0] = max(dp[i - 1][0],dp[i - 1][1] + prices[i]);
        dp[i][1] = max(dp[i - 1][1],dp[i - 1][0] - prices[i]);
    }
    return dp[n-1][0];
}
};

带限制的子序列和

给你一个整数数组 nums 和一个整数 k ,请你返回 非空 子序列元素和的最大值,子序列需要满足:子序列中每两个相邻的整数 nums[i]nums[j] ,它们在原数组中的下标 i 和 j 满足 i < j 且 j - i <= k 。

数组的子序列定义为:将数组中的若干个数字删除(可以删除 0 个数字),剩下的数字按照原本的顺序排布。
示例 1:

输入:nums = [10,2,-10,5,20], k = 2
输出:37
解释:子序列为 [10, 2, 5, 20] 。

示例 2:

输入:nums = [-1,-2,-3], k = 1
输出:-1
解释:子序列必须是非空的,所以我们选择最大的数字。

示例 3:

输入:nums = [10,-2,-10,-5,20], k = 2
输出:23
解释:子序列为 [10, -2, -5, 20] 。

解题思路

dp[i]为以nums[i]结尾的带限制的子序列和
deque<int> sta双向队列存储一个单调递减栈,栈中存储的是dp[i]的下标,越靠近队头,dp[i]值越大
每次扫描nums[i]时,取出dp[sta.front()],即完成了 前k个dp[]的值,选出最大的值 ,之后再加上nums[i]
得到dp[i]后需要更新单调递减栈,注意是否超出k个数

代码

class Solution {
public:
    int constrainedSubsetSum(vector<int>& nums, int k) {
        int n = nums.size();
        int ans = nums[0];
        int dp[n];
        dp[0] = nums[0];
        deque<int> sta;
        sta.push_back(0);
        for(int i = 1;i < n;++i){
            dp[i] = max(dp[sta.front()] + nums[i],nums[i]);
            ans = max(dp[i],ans);
            if(i - sta.front() == k) sta.pop_front();
            while(!sta.empty() && dp[sta.back()] < dp[i]) sta.pop_back();
            sta.push_back(i);
        }
        return ans;
    }
};

双指针

盛最多雨水的容器

给你 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明:你不能倾斜容器,且 n 的值至少为 2。

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。

在初始时,左右指针分别指向数组的左右两端,它们可以容纳的水量为 min⁡(1,7)∗8=8min(1, 7) * 8 = 8min(1,7)∗8=8。

此时我们需要移动一个指针。移动哪一个呢?直觉告诉我们,应该移动对应数字较小的那个指针(即此时的左指针)。这是因为,由于容纳的水量是由

两个指针指向的数字中较小值∗指针之间的距离两个指针指向的数字中较小值 * 指针之间的距离 两个指针指向的数字中较小值∗指针之间的距离

决定的。如果我们移动数字较大的那个指针,那么前者「两个指针指向的数字中较小值」不会增加,后者「指针之间的距离」会减小,那么这个乘积会减小。因此,我们移动数字较大的那个指针是不合理的。因此,我们移动 数字较小的那个指针。

class Solution {
public:
    int maxArea(vector<int>& height) {
        int l = 0, r = height.size() - 1;
        int ans = 0;
        while (l < r) {
            int area = min(height[l], height[r]) * (r - l);
            ans = max(ans, area);
            if (height[l] <= height[r]) {
                ++l;
            }
            else {
                --r;
            }
        }
        return ans;
    }
};
最后修改:2021 年 06 月 02 日 10 : 09 AM
如果觉得我的文章对你有用,请随意赞赏