枚举

本质上就是遍历所有可能

  • 根据实际条件确定条件和范围，在范围里面通过特定方法（二分，顺序，树等）搜索
  • 在局部有界范围内用最好
  • 规模越大，计算效率越低

例题（洛谷p1151）子树整数

对于一个五位数 abcdef, 可将其拆分为三个子数：

sub1 = abc ,sub2 = bcd ,sub3 = def

现在给定一个正整数 K，要求你编程求出 10000 到 30000 之间所有满足下述条件的五位数，条件是这些五位数的三个子数 sub1,sub2,sub3 都可被 K 整除。

最终输出应该为正整数

每一行为一个满足条件的五位数，要求从小到大输出。不得重复输出或遗漏。如果无解，则输出 No。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <stdio.h>
void sub(int k) {
    int p = 0;
    int a, b, c;
    for (int i = 10000; i <= 30000; i++)//注意范围 
    {
        a = i / 10000 * 100 + i / 1000 % 10 * 10 + i / 100 % 10;
        b = i / 1000 % 10 * 100 + i / 100 % 10 * 10 + i / 10 % 10;
        c = i / 100 % 10 * 100 + i / 10 % 10 * 10 + i % 10;//以上为重点公式 
        if (a % k == 0 && b % k == 0 && c % k == 0)
        {
            printf("%d 满足条件\n", i);
            p = 1;//做标记 
        }

    }
    if (p == 0)printf("不存在");

}

int main()
{
	int a;
    printf("请输入一个整数: ");
	scanf_s("%d", &a);
    sub(a);
	return 0;

}

这个方法一般是很暴力的，但是也有优化空间，主要是在范围里面通过特定方法（二分，顺序，树等）搜索等优化，一般的思路是空间换时间。

贪心

在问题求解的时候，总是做出当前最优解，但有可能不是整体问题的最优解

  • 把问题拆成几个子问题
  • 对每个问题求解，的出局部最优解
  • 将局部合成整体问题最优解

leetcode121 买彩票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

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

示例 2：

1
2
3
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <stdio.h>
int main() {
    int prices[5];
    int i = 0;
    int count = 0;
    printf("输入数组：");
    for (i = 0; i < 5; i++) {
        scanf_s("%d", &prices[i]);
        if (prices[i] == -1) {
            break;
        }
        count++;
    }

    int a = prices[0];
    int money = 0;
    i = 1; // 重新初始化 i
    while (i < count) {
        if (money < prices[i] - a  && prices[i] > a) {
            money = prices[i] - a;
            a = prices[i];
        }
        else if(prices[i] < a) {
            a = prices[i];  
        }
        
        i++;
    }

    printf("%d\n", money);
    return 0;
}