SCNU习题 总结与复习

1. P1:构建最大二叉树 【分治】 重点

构树函数需要注意的点；

前序遍历需要注意，本题的输出有点特点。若一个结点无左子，无右子就不再下去遍历； 其他情况都要下去遍历；

2. P2 寻找多数【分治】

没啥，注意unorder_map的使用
unordered_map 是 C++ STL 提供的一种哈希表实现，允许以常数时间复杂度进行查找、插入和删除操作。以下是 unordered_map 的几个常用方法及其简要说明：

ump常用方法

1. 构造函数

   • unordered_map<Key, T> ump;
     创建一个空的 unordered_map。

2. 插入元素

   • ump.insert({key, value});
     插入一个键值对。如果键已存在，则插入失败。
   • ump[key] = value;
     插入或更新键 key 的值为 value。如果键存在，则更新；如果不存在，则插入。

3. 访问元素

   • ump.at(key);
     返回键 key 对应的值。如果键不存在，会抛出 std::out_of_range 异常。
   • ump[key];
     返回键 key 对应的值，如果键不存在，会插入一个默认值。

4. 查找元素

   • ump.find(key);
     返回一个迭代器，指向键 key 的位置，如果键不存在，则返回 ump.end()。

5. 删除元素 【重要】

   • ump.erase(key);
     删除键 key 及其对应的值，返回删除的元素数量（0或1）。
   • ump.erase(iterator);
     删除指定迭代器指向的元素。

6. 检查元素是否存在 【重要】

   • ump.count(key);
     返回键 key 的出现次数（0或1），可用于检查元素是否存在。

7. 大小和容量

   • ump.size();
     返回 unordered_map 中元素的数量。
   • ump.empty();
     检查 unordered_map 是否为空。

8. 遍历元素 【重要】

   • 使用范围 for 循环：

     for (const auto& pair : ump) {
         cout << pair.first << ": " << pair.second << endl;
     }
     

9. 清空元素

   • ump.clear();
     删除 unordered_map 中的所有元素。

10. 自定义哈希和比较函数

    • 可以在创建时指定自定义哈希函数和比较函数：

      unordered_map<Key, T, HashFunc, EqualFunc> ump;
      

总结

unordered_map 提供了高效的键值对存储和查找功能，常用于需要快速访问和修改元素的场景。了解这些常用方法可以帮助你高效地使用 unordered_map 进行数据管理。

3.P3 找最大连续子序和 【贪心】

和为负数就丢弃，和为正数继续枚举，记录最大值；
INT_MIN 在<limits.h>里；

4 & 5.找k个最小数/找k个最大数

虽然可以更优化，但为了应付考试方便，直接用sort吧[/doge]
最后sort有个用法:

• sort(iter1,iter2) 本身是从小排序到大
• sort(iter1,iter2,great< int > () ) 加入仿函数，从大排序到小

6.换硬币 【动态规划】

dp[i] : 组成i需要的最少硬币数量
dp[i] = min(dp[i] , dp[i-7] , dp[i-5] , dp[i-2]) 前提i>=7,i>=5,i>=2分别

注意dp[0]不能初始化为dp[0] = 0；虽然dp[0]我们可以认为无需硬币就可以，但也可以认为0无法用硬币去表示；本题就是必须用到后者的意义；

7 & 8.走网格 & 走楼梯【动态规划】

dp[i][j]：走到(i,j)最少有多少种方法；
每次值都可以从两个地方来源；

if(j>1) dp[i][j] += dp[i][j-1]; //Right
if(i>1) dp[i][j] += dp[i-1][j]; //Dow

一个道理，一个二维一个一维

9.背包问题 【动态规划】 重点

拿东西的时候别忘记了加上价值哈（+V[i]）；

10.最长回文子串 【动态规划】

1.区间DP，记住s.substr(startidx,len)的用法，一个是开始下标，第二个是长度；
2.len = r-l +1 ; 又r<n，故l<n-len+1；

11. 最大连续子数组和 【动态规划】

和第2题一样；

12.分发饼干 【贪心】

很简单，将孩子从小到大排序，饼干也从小到大排序，尽可能贪心的满足最小要求去枚举；（可以通过数学证明确实如此）

13.反转69

没啥说的，尽可能从前面开始将6反为9

14.盛最多的水 【贪心】

15.括号生成 【回溯】 重点

16. K组合问题【回溯】

做烂了

17.求子集异或和 【回溯】

每次枚举都是不重复的，一定是一个子集，那么每次枚举后都需要进行计算异或和就行；

18.分割回文串 【回溯】 重点

枚举分割的位置i,若是回文串则加入；

19. 目标和 【回溯】

枚举每个数的两种选择就行了

20.电话号码组合 【回溯】

和19题一样的；

21.优美的数列【回溯-排列】

枚举全排列就行；在此基础上加上满足两个条件就行；

22.K组合 【回溯】

No need to say.

23.大礼包 【分支界限法】

1.过滤出有用礼包
2.枚举直接方式，枚举礼包，看最小；

24.分成K个相等子集 【回溯】 重要

注意隐含条件：

注意隐含条件；其次枚举的是每个数，然后选择放哪个篮子里，如果满了就要看下个篮子；

25.跳跃游戏 【贪心】

看代码了；就遍历i能够跳到的边界，并且在迭代的过程中，更新最大边界；

26.整数拆分 【动态规划】 重要

每个数，可以拆出一个数j作为拆分值，那么另外的i-j你可以选择继续拆，也可以选择不再继续拆； 对应的就是j x dp[i-j] , j x (i-j) 取max

27.打家劫舍 【动态规划】

nothing need to be toldn~

28.戳气球 【动态规划】 重点

为什么要倒叙遍历？因为大问题的解组成rec[i][k]实际上是由后部分组成的

如果我们从前往后遍历，那么其中的值是没有更新的；

29.分发糖果【贪心】

从左到右遍历一遍满足左规则；
从右到左遍历一遍满足右规则；
取并集；

30.三数之和 【双指针】 重点

num_i + num_j + num_k =0 变成 num_i + num_j = -num_k;
再去枚举i,j；不过注意一点，为了保证重复，需要做一点处理；

31.反转括号 【栈】 重点

记住一点：为什么要用栈？因为栈可以保存上次处理的数据，方便我们处理上一个数据；

32.跳跃游戏2 【贪心】

开始的边界应该设置为0，跳跃也为0；

33.颜色分类

应付考试，直接sort

34.找假币

应付考试，直接用unordered_map 去找少的那个；

35.最少操作使数组递增

找差距diff,并递增diff+1；继续遍历；

36.组合求和

没啥说的，组合就完事了；

37.完全平方数

for a : 1->n dp[i] = min(dp[i],dp[i - a*a]);