预览

这是一篇CVPRW2019的论文，作者将Attention机制引入到人脸表情识别中。提出Attention model，并写出了一个合成图片的生成器，模型对噪声有较强的鲁棒性，并在CK+，BU-3DFE数据集上有一定的性能提升。

原文地址和github源码地址

原文地址 github源码地址

Problem

Recent developments for the facial expression recognition problem consider processing the entire image regardless of the face crop location within the image. Such developments bring in extraneous artifacts, including noise,which might be harmful for classification as well as incur in unnecessary additional computational cost. This is problematic as the minutiae that characterizes facial expressions can be affected by elements such as hair, jewelry, and other environmental objects not defining the actual face and as part of the image background.

作者认为现在存在的很多研究关注在整张人脸，带来不必要的计算，并引入了一些噪声可能对识别性能产生影响，引入的一些因素像头发，珠宝等并不能决定表情识别的结果，应该作为图片的背景。

Method

引入Attention机制，像人类的视觉感知一样，只关注目标区域的处理，与之无关的信息直接丢弃。如图所示。

Network architecture

网络结构由4部分组成：注意力模块，特征提取模块，重建模块和分类表示模块。

Attention Module

Attention模块将传统的人脸检测来用图像分割来代替。用了U-net来对图片进行分割，输出的是人脸的掩模。如图所示

Feature extration Module

Four ResBlocks were used to extract high-dimensional features for image attention and to maintain spatial information; no pooling or strided convolutional layers were used.

使用4个ResBlocks来提取高维度特征，保留空间信息。如图所示。

Reconstruction Module

The reconstruction layer adjusts the attention map to create an enhanced input to the representation module. This module has two convolutional layers, a Relu layer, and an Average Pooling layer which, by design choice, resizes the input image of 128 × 128 to 32 × 32.

Representation and classification module

the network function, builds a representation for a sample image $x \\in R^D$ 主要是建立一个网络，对图片进行再表示，它的分类结果要与原图的分类结果足够接近。 详细过程参照论文，比较复杂。

损失函数

expriments

实验部分主要进行Rep模块的对照实验，数据集上的性能比较及算法对噪声的鲁棒性实验。

Datasets

Our image renderer R creates a synthetic larger dataset using real face datasets by making background changes and geometric transformations of face images.

将真实的人脸数据背景进行更换，然后再对人脸图片进行几何变换得到合成数据集。具体过程如图所示。 使用的数据集有CK+、BU-3DFE、COCO dataset.其中COCO dataset 用作背景图。最后合成的数据集部分如图所示。

Expression recognition results

Baseline为PreActResNet18，将其与FERAtt+Cls 和FERAtt + Rep + Cls两种方法进行性能比较，发现再表示对性能的提升有明显的效果。

Rebustness to noise

FERAtt + Rep + Cls算法对噪声的鲁棒性较好，在$\\sigma = 0 - 0.10$对于识别性能几乎无影响，继续增大$\\sigma$的值时，它的识别的精度也一直处于其它算法之上。

Contribution

1. Attention model
2. A generator of synthetic images
3. Gaussian Manifold Loss

预览

这是一篇CVPR2018关于表情识别的论文，作者可谓是独辟蹊径，从“De-expression”这一角度进行表情识别的研究。作者通过一些事实和文献发现，人的表情可以分解为Neutral Compoent和Expressive Componet两部分。作者的想法是将人脸经过一个GAN网络得到一张与之对应的中性表情，然后对residue(残余特征)进行训练学习，进一步进行表情分类。

原文地址

原文地址 没有相应的源代码:sweat:

Challenge

现在的大部分研究关注的都是光照，姿态，遮挡等对表情识别的影响。作者关注的是个体差异像年龄，性别，种族背景等因素对表情识别的影响（the current main challenge comes from the large variations of individuals in attributes such as: age, gender, ethnic background and personality.）

Inspriation

1. people are capable of recognizing facial expressions by comparing a subject’s expression with a reference expression (i.e., neutral expression) of the same subject[1].
2. a facial expression can be decomposed to an expressive component and neutral component[2] 人们可以通过一个参考表情来识别其它表情（这里参考表情用的是中性表情）；一个人脸表情可以分为中性部分和表情部分。如图所示。

Network architecture

网络结构大体可分为两部分：GAN(Generator)用来生成中性表情，并保存有residue，用于训练学习；第二部分是学习残余特征，然后进行表情分类。 网络结构有很多细节没有体现，比如説学习残余特征的网络结构还有5个损失函数都没详细说明，论文中也没有细说。这里主要是学习的是它分解表情的思想。

Generator

cGAN[3]被用来从一个给定的图片生成一个中性人脸表情。 cGAN训练的输入是一个图像对$$，而生成器的输出为$I_{output}$。其中$I_{target}$是图片的中性表情的ground truth。$I_{output}$输出的是GAN生成的中性表情 The discriminator tries to distinguish the $< I_{input}, I_{target} >$ from the $< I_{input}, I_{output} >$ 判别器是为了尽力区分输出表情与ground truth之间的差别 the generator tries to not only maximally confuse the discriminator but also generate an image as close to the target image as possible. 而生成器则是尽可能使输出与ground truth足够接近，进而混淆视听。 Generator的目标函数 Discriminator的目标函数 cGAN的目标函数

Classification

直接将ganerator的中间层的De-Expression Residue作为CNN分类器的输入进行表情分类。 具体是将Generator中所有尺寸大小一样的特征图合并在一起，分别输入到4个local的CNN分类器

损失函数

单个loss的系数大小取决于local classifier的表情分类效果

Experiments

Visualization of Expressive Component

各个表情的残余特征可视化（从左到右是愤怒，厌恶，害怕，高兴，悲伤，惊讶）

Visualization of Regenerated Neutral Faces

实验中采用的数据集CK+, MMI, Oulu-CASIA, BP4D+, BU-3DFE , BP4D, BU-4DFE.后2个用于预训练，前面5个方法用于比较实验，体现方法性能 生成器由输入图片得到中性图片

Accuracy on the CK+ database

CK+与各个方法准确率比较 CK+混淆矩阵 作者后面还在4个数据集上进行相同的实验，都取得比较好的性能，实验结果都处于前2的位置。

5303. 解码字母到整数映射

题目描述

给你一个字符串 s，它由数字（’0’ - ‘9’）和 ‘#’ 组成。我们希望按下述规则将 s 映射为一些小写英文字符： 字符（’a’ - ‘i’）分别用（’1’ - ‘9’）表示。 字符（’j’ - ‘z’）分别用（’10#’ - ‘26#’）表示。 返回映射之后形成的新字符串。 题目数据保证映射始终唯一。 示例 1： 输入：s = “10#11#12” 输出：”jkab” 解释：”j” -> “10#” , “k” -> “11#” , “a” -> “1” , “b” -> “2”. 示例 2： 输入：s = “1326#” 输出：”acz” 示例 3： 输入：s = “25#” 输出：”y” 示例 4： 输入：s = “12345678910#11#12#13#14#15#16#17#18#19#20#21#22#23#24#25#26#” 输出：”abcdefghijklmnopqrstuvwxyz” 提示： 1 <= s.length <= 1000 s[i] 只包含数字（’0’-‘9’）和 ‘#’ 字符。 s 是映射始终存在的有效字符串。

题解1

a-i对应的是1-9，即一个字母对应一个字符；j-z对应的是10#-26#即一个字母对应三个字符，且以#结尾。现在我们反向遍历字符串，遇到#，找到其前面2个数字字符对应的字母，否则，直接将对应的字符转成字母即可。最后再将字符串反转即可。

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    string freqAlphabets(string s) {
        int len = s.size(), num;
        string res;
        for(int i = len - 1; i >= 0; --i){
            if(s[i] == '#'){//遇到#，找到其前面的2个字符对应的字母
                num = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
                i = i - 2;
            }
            else{
                num = s[i] - '0';
            }
            res.push_back('a' + num - 1);
        }
        reverse(res.begin(), res.end());//反转
        return res;
    }
};

1310. 子数组异或查询

题目描述

有一个正整数数组 arr，现给你一个对应的查询数组 queries，其中 queries[i] = [Li, Ri]。 对于每个查询 i，请你计算从 Li 到 Ri 的 XOR 值（即 arr[Li] xor arr[Li+1] xor … xor arr[Ri]）作为本次查询的结果。 并返回一个包含给定查询 queries 所有结果的数组。 示例 1： 输入：arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]] 输出：[2,7,14,8] 解释： 数组中元素的二进制表示形式是： 1 = 0001 3 = 0011 4 = 0100 8 = 1000 查询的 XOR 值为： [0,1] = 1 xor 3 = 2 [1,2] = 3 xor 4 = 7 [0,3] = 1 xor 3 xor 4 xor 8 = 14 [3,3] = 8 示例 2： 输入：arr = [4,8,2,10], queries = [[2,3],[1,3],[0,0],[0,3]] 输出：[8,0,4,4] 提示： 1 <= arr.length <= 3 * 10^4 1 <= arr[i] <= 10^9 1 <= queries.length <= 3 * 10^4 queries[i].length == 2 0 <= queries[i][0] <= queries[i][1] < arr.length

题解1

思路类似求任意区间的数字和，首先用vec[i]存储从arr[0]到arr[i]这些元素的异或，然后对于区间[a, b]的所有元素异或值为$vec[b] \oplus vec [a - 1]$

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
        vector<int>res, vec;
        int len = arr.size();
        for(int i = 0; i < len; ++i){
            if(i == 0){
                vec.push_back(arr[0]);
            }
            else{
                vec.push_back(vec[i - 1] ^ arr[i]);
            }
        }
        for(auto que:queries){
            if(que[0] == 0){
                res.push_back(vec[que[1]]);
            }
            else{
                res.push_back(vec[que[1]] ^ vec[que[0] - 1]);
            }
        }
        return res;
    }
};

1311. 获取你好友已观看的视频

题目描述

有 n 个人，每个人都有一个 0 到 n-1 的唯一 id 。 给你数组 watchedVideos 和 friends ，其中 watchedVideos[i] 和 friends[i] 分别表示 id = i 的人观看过的视频列表和他的好友列表。 Level 1 的视频包含所有你好友观看过的视频，level 2 的视频包含所有你好友的好友观看过的视频，以此类推。一般的，Level 为 k 的视频包含所有从你出发，最短距离为 k 的好友观看过的视频。 给定你的 id 和一个 level 值，请你找出所有指定 level 的视频，并将它们按观看频率升序返回。如果有频率相同的视频，请将它们按名字字典序从小到大排列。 示例 1： 输入：watchedVideos = [[“A”,”B”],[“C”],[“B”,”C”],[“D”]], friends = [[1,2],[0,3],[0,3],[1,2]], id = 0, level = 1 输出：[“B”,”C”] 解释： 你的 id 为 0 ，你的朋友包括： id 为 1 -> watchedVideos = [“C”] id 为 2 -> watchedVideos = [“B”,”C”] 你朋友观看过视频的频率为： B -> 1 C -> 2 示例 2： 输入：watchedVideos = [[“A”,”B”],[“C”],[“B”,”C”],[“D”]], friends = [[1,2],[0,3],[0,3],[1,2]], id = 0, level = 2 输出：[“D”] 解释： 你的 id 为 0 ，你朋友的朋友只有一个人，他的 id 为 3 。 提示： n == watchedVideos.length == friends.length 2 <= n <= 100 1 <= watchedVideos[i].length <= 100 1 <= watchedVideos[i][j].length <= 8 0 <= friends[i].length < n 0 <= friends[i][j] < n 0 <= id < n 1 <= level < n 如果 friends[i] 包含 j ，那么 friends[j] 包含 i

题解1

BFS。首先利用BFS找到和起始id距离为level的所有朋友，然后统计这些朋友的观影情况，按观看频率升率返回，相同的，按字典序从小到大排列。

代码1

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

struct Node{
    int id;
    int level;
    Node(int id, int level):id(id), level(level){}
};
class Solution {
public:
    vector<string> watchedVideosByFriends(vector<vector<string>>& watchedVideos, vector<vector<int>>& friends, int id, int level) {
        vector<int>ids;
        vector<string>res;
        map<string, int>myMap;
        queue<Node>que;
        vector<int>mark(watchedVideos.size(), 0);
        set<pair<int, string>>tmp;

        /*
        BFS寻找距离为level的朋友们的id
        */
        que.push(Node(id, 0));
        mark[id] = 1;
        Node frt(0, 0), next(0, 0);
        while(!que.empty()){
            frt = que.front();
            que.pop();
            if(frt.level > level){
                break;
            }
            else if(frt.level == level){
                ids.push_back(frt.id);
            }
            for(int i = 0; i < friends[frt.id].size(); ++i){
                next.id =friends[frt.id][i];
                next.level = frt.level + 1;
                if(!mark[next.id]){
                    mark[next.id] = 1;
                    que.push(next);
                }
            }
        }
        //统计朋友们的观影频率
        for(auto id:ids){
            for(auto video:watchedVideos[id]){
                if(myMap.find(video) == myMap.end()){
                    myMap[video] = 1;
                }
                else{
                    myMap[video] = myMap[video]+ 1;
                }
            }
        }

        //放入set中自动排序
        for(auto iter:myMap){
            tmp.insert(make_pair(iter.second, iter.first));
        }
        for(auto iter:tmp){
            res.push_back(iter.second);
        }
        return res;
    }
};

1312. 让字符串成为回文串的最少插入次数

题目描述

给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。 请你返回让 s 成为回文串的 最少操作次数 。 「回文串」是正读和反读都相同的字符串。 示例 1： 输入：s = “zzazz” 输出：0 解释：字符串 “zzazz” 已经是回文串了，所以不需要做任何插入操作。 示例 2： 输入：s = “mbadm” 输出：2 解释：字符串可变为 “mbdadbm” 或者 “mdbabdm” 。 示例 3： 输入：s = “leetcode” 输出：5 解释：插入 5 个字符后字符串变为 “leetcodocteel” 。 示例 4： 输入：s = “g” 输出：0 示例 5： 输入：s = “no” 输出：1 提示： 1 <= s.length <= 500 s 中所有字符都是小写字母。

题解1

动态规划。 题目实际上是最长回文子序列的变形。求出最长回文子序列的长度，再用原长度len - 回文子序列的长度即可。

代码1

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

/*
找出s中最长回文子序列len1
题目中要求的是len - len1
*/
class Solution {
public:
    int minInsertions(string s) {
        int len = s.size();
        vector<vector<int>>dp(len + 1, vector<int>(len + 1, 0));
        for(int i = 0; i < len; ++i){//长度为1的串，最长回文序列就是它本身即长度为1
            dp[i][i] = 1;
        }
        for(int i = 1; i < len; ++i){
            for(int j = 0; j < len; ++j){
                if(j + i < len){
                    if(s[j] == s[j + i]){
                        dp[j][j + i] = dp[j + 1][j + i - 1] + 2;
                    }
                    else{
                        dp[j][j + i] = max(dp[j + 1][j + i], dp[j][j + i - 1]);
                    }
                }
            }
        }
        return len - dp[0][len - 1];
    }
};

图灵机(TM)

有穷自动机与图灵机区别：图灵机在带子上能写能读；读写头即能左移也能右移；带子无限长；进入拒绝和接受状态立即停机。

定义

格局 图灵可判定：有限步骤内，可知结果是yes或者no. 图灵可识别：有限步骤内，可知结果是yes.对于no的可能进入死循环. 图灵可补识别：有限步骤内，可知结果是no.对于yes的可能进入死循环. 识别语言$0^{2^n}$的图灵机如图. 每次减半，直到1个0结束。中间出现奇数个0且不为1个，则进入拒绝态。

图灵可判定性

$A_{DFA}$显然可判定，因为DFA对于每个输入的串要不进入接受态，要不进入拒绝态。$E_{DFA}$采用的是标记法，类似于图中遍历。因为正则语言对于交，并，补运算都是封闭的，所以$EQ_{DFA}$可以转成$E_{DFA}$，而$ALL_{DFA}$又能转成$EQ_{DFA}$ CFG的相关的可判定性问题，很大程度上依赖于乔姆斯基范式。$A_{CFG}$使用乔姆斯基范式能有限步内（2n-1步）判断能否识别某串。$A_{\epsilon CFG}$直接借用$A_{CFG}$可判定的结论，来判断是否能派生$\epsilon$串。$E_CFG}$可判定同样采用标记法，不过是逆向标记。 证明思路类似于$E_{CFG}$的证明.

可归约性

定义

证明$A_{TM}$不可判定，使用的是对角化方法。

笔记教材及答案

github地址

上下文无关文法(CFG)

定义

前面提到的$0^n1^n$可以用上下文无关文法表示如下： $S\rarr 0S1\vert \epsilon$.

设计CFG

CFG的设计很难对于多个简单CFG的合并或者语言本身是DFA都较容易设计。 有些很难的CFG是在一些基础的CFG上发展来的，所以需要记住一些常见的CFG的形式。 一些常见的CFG表示如图所求.

乔姆斯基范式

乔姆斯基范式有两个特点：一分为二；终级化. 将任意一个上下文无关文法转为乔姆斯基范式的步骤如下： 1. 引入新的起始变元 2. 删除$\epsilon$规则，相同的只替换一次，不循环替换 3. 去掉单一规则 4. 添加终结符规则 5. 添加新变元，使得所有变量规则都是一分为二 具体可参考65页的例3.7. 乔姆斯基范式有一个很重要的性质，在后面证$A_{CFG}$图灵可判定及多项式时间内判定某个串是否可以派生，都要用到乔姆斯基范式。因为乔姆斯基范式派生任何长为n的串，只需要$2n-1$步。 证明如图所求。

下推自动机(PDA)

下推自动机相比NFA多了一个栈（可以压入与弹出）。可以进行简单的串的数量的统计。

定义

常见的PDA

泵引理

与正则语言相同，上下文无关语言也有泵引理。

定义

用泵引理证明非上下文无关语言

“抽进”+“抽出” 注意：上下文 无关语言对并运算是封闭的，而对交，补，差都不是封闭的.

笔记教材及答案

github地址

确定性有穷自动机（DFA）

定义

注意：允许没有接受状态，此时接受语言为空集；转移函数对每一个状态和每一个可能的输入都恰好指定了一个状态。 定义正则运算的并、连结和星号 正则运算的并，连结和星号都是封闭的，后面在证明DFA与NFA等价后，会用NFA对其进行证明。

常见语言的DFA状态图举例

c题含某子串，首先画出对应的子串，然后再判断其它输入的状态转换即可。 f题不含某个子串，首先画出含某个子串的DFA，然后将接受态转为非接受态，将非接受态转为接受态。这里运用了DFA的补是封闭这一性质。 对于l这种类型的题即DFA的或和且运算，画图比较麻烦，有时采用横1纵0不失为一种好方法。 对于n的倍数余m，首先画出n个状态围成的圈，然后从起始状态数起，将第m个状态标为接受态即可。对于这道题有个变形。画出长度除以3余2且除以4余1的DFA，这里先用中国剩余定理求出长度规律为$12n+5(n = 0, 1, \cdots,)$也就是画出长度除以12余5的DFA。 注意：DFA一般不能对保证串中字符a与字符b相等，如$a^nb^n$不是正则语言，通过后面学习知道它是上下无关语言。但是它能表示一个很特殊的串，即串中01和10子串个数相等，它等价于串以相同的字符开始和结尾。（可以把01和10想象成波形图中的下升与下降，现在下升段与下降段相等，那么开始与结尾的值一定相等，同为0或同为1），DFA如图。

非确定性有穷自动机（NFA）

NFA与DFA的不同：

1. 一入多出。NFA中一个状态对于每个符号可能有0个，1个或多个转换的箭头。而DFA中每一个状态对于每个符号有唯一的转换箭头（状态转换）
2. 加入空漂。NFA的输入字符比DFA多了一个$\epsilon$，即空漂。

定义

与DFA的定义同为五元组，但仍存在一定差异。$\Sigma$中新增了$\epsilon$；$\delta$的映射结果属于状态集的幂集，即一入多出，同一个符号，可能对应多个状态转换。 注意：由于NFA加入非确定性，一个输入产生了多条路径，只要求所有路径中至少有一条路径能到达接受状态即可，这点与DFA也有所不同。

DFA与NFA的等价性。

首先DFA是特殊的NFA，即一入一出，没有空漂的NFA。 下面主要是将一个NFA转换成与之对应的DFA。 已知$DFA\space A = \lbrace Q,\Sigma, \delta, q_0, F\rbrace$，现在要构造出一台与之对应的$NFA\space B = \lbrace Q^{\prime},\Sigma^{\prime}, \delta^{\prime}, q_0^{\prime}, F^{\prime}\rbrace$ 首先原来的DFA有n个状态，那NFA有$2^n$个状态（即状态的组合）$Q^{\prime} = \lbrace Q_{00\dots0}, Q_{10\dots0},\cdots,Q_{11\dots1}\rbrace$，$\Sigma^{\prime}$很简单就为$\lbrace0,1\rbrace$，$\delta^{\prime}$要随$Q^{\prime}$相应的改变，多个状态经过相同的输入的结果要进行位与，最后接受态$F^{\prime}$含有$2^{n-1}$即只是含$q_1$即可（第一个二进制位为1）。这样就构造出一台DFA与NFA对应。 即证DFA与NFA是等价的。

NFA证正则语言的并、连接、星号运算为封闭的。

证明并运算，加入一个新的起始态，然后空漂到两台DFA的接受态即可。连接运算，将$M_1$中接受态全转为非接受态，然后将其空漂到$M_2$的起始态。星号运算，首先加入一个新的起始态（也是接受态）空漂到$M_1$的起始态，然后再将$M_1$的所有接受态空漂到新加入的起始态即可。

正则表达式（RE）

定义

NFA转成RE

利用法则：用力拉首尾，拓扑变形，以星换圈，以并换多路，逐步减少内态。最后得到就是RE。具体可以参考书上46页的2张图。

RE转成NFA

从最小的子表达式到大一点的子表达式逐步建立，直到获得关于原始表达式的NFA. 所以NFA与RE是等价的.

DFA,NFA与RE三者的关系

三者关系如图所求.

泵引理

定义

应用泵引理证明非正则语言

上述定义是一个正则语言的必要不充分条件，即如果一个语言是正则语言，则它一定满足泵引理。如果不满足泵引理，一定不是正则语言。 注意： 1. 泵引理只能用来证明非正则语言，不能证正则语言。 2. 泵引理只能将“相等”抽成“不等”，“是”抽成“不是”，不能反过来。可能先利用正则语言的交，并，补运算是封闭的，先进行转换。 下面是一些例子 另外证明$1^{n^2}$或者$1^{2^p}$这种形式语言，可以在序列中相邻两串长度间隔在不能增大作文章，因为长度间隔的离散性，一定不能满足任意抽取均能满足原语言。

笔记教材及答案

github地址

5291. 统计位数为偶数的数字

题目描述

给你一个整数数组 nums，请你返回其中位数为 偶数 的数字的个数。 示例 1： 输入：nums = [12,345,2,6,7896] 输出：2 解释： 12 是 2 位数字（位数为偶数） 345 是 3 位数字（位数为奇数） 2 是 1 位数字（位数为奇数） 6 是 1 位数字 位数为奇数） 7896 是 4 位数字（位数为偶数） 因此只有 12 和 7896 是位数为偶数的数字 示例 2： 输入：nums = [555,901,482,1771] 输出：1 解释： 只有 1771 是位数为偶数的数字。 提示： 1 <= nums.length <= 500 1 <= nums[i] <= 10^5

题解1

我用to_string将数字先转成字符串，然后判断字符串的长度是否为偶数。

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13

//to_string
class Solution {
public:
    int findNumbers(vector<int>& nums) {
        int cnt = 0;
        for(auto num:nums){
            if(to_string(num).size()% 2 == 0){//判断num对应的字符串的长度是否为偶数
                ++cnt;
            }
        }
        return cnt;
    }
};

5292. 划分数组为连续数字的集合

题目描述

给你一个整数数组 nums 和一个正整数 k，请你判断是否可以把这个数组划分成一些由 k 个连续数字组成的集合。 如果可以，请返回 True；否则，返回 False。 示例 1： 输入：nums = [1,2,3,3,4,4,5,6], k = 4 输出：true 解释：数组可以分成 [1,2,3,4] 和 [3,4,5,6]。 示例 2： 输入：nums = [3,2,1,2,3,4,3,4,5,9,10,11], k = 3 输出：true 解释：数组可以分成 [1,2,3] , [2,3,4] , [3,4,5] 和 [9,10,11]。 示例 3： 输入：nums = [3,3,2,2,1,1], k = 3 输出：true 示例 4： 输入：nums = [1,2,3,4], k = 3 输出：false 解释：数组不能分成几个大小为 3 的子数组。 提示： 1 <= nums.length <= 10^5 1 <= nums[i] <= 10^9 1 <= k <= nums.length

题解1

先用map统计每个数字出现的次数。然而遍历map(key已自动从小到大排列)，当发现某个数的个数cnt不为0，则连续k个数字(含当前数)都减去cnt，如果出现负数，则表示不能划分。 最后再遍历一次map,检查是否每一个数的个数都为0。（这步其实不需要）

代码1

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
34
35
36
37
38
39
40
41
42
43
44

class Solution {
public:
    bool isPossibleDivide(vector<int>& nums, int k) {
        int len = nums.size();
        map<int, int>myMap;
        if(len % k != 0){//数字的个数不能将每组都划分成k个
            return false;
        }
        for(auto num:nums){//统计每个数字出现的次数
            if(myMap.find(num) == myMap.end()){
                myMap[num] = 1;
            }
            else{
                ++myMap[num];
            }
        }
        bool flag = true;
        for(auto iter = myMap.begin(); iter != myMap.end(); ++iter){//遍历map
            if(iter->second != 0){
                int num = iter->first;
                int cnt = myMap[num];
                myMap[num] = 0;
                for(int i = num + 1; i < num + k; ++i){//分组，一个数不为0，连续k个数字一组，个数不足表示不能划分
                    if(myMap[i] < cnt){
                        flag = false;
                        break;
                    }
                    else{
                        myMap[i] = myMap[i] - cnt;
                    }
                }
            }
        }
        /*这步其实不需要
        for(auto iter = myMap.begin(); iter != myMap.end(); ++iter){
            if(iter->second != 0){//表示有多余数字
                flag = false;
                break;
            }
        }
        */
        return flag;
    }
};

5293. 子串的最大出现次数

题目描述

给你一个字符串 s ，请你返回满足以下条件且出现次数最大的 任意 子串的出现次数： 子串中不同字母的数目必须小于等于 maxLetters 。 子串的长度必须大于等于 minSize 且小于等于 maxSize 。 示例 1： 输入：s = “aababcaab”, maxLetters = 2, minSize = 3, maxSize = 4 输出：2 解释：子串 “aab” 在原字符串中出现了 2 次。 它满足所有的要求：2 个不同的字母，长度为 3 （在 minSize 和 maxSize 范围内）。 示例 2： 输入：s = “aaaa”, maxLetters = 1, minSize = 3, maxSize = 3 输出：2 解释：子串 “aaa” 在原字符串中出现了 2 次，且它们有重叠部分。 示例 3： 输入：s = “aabcabcab”, maxLetters = 2, minSize = 2, maxSize = 3 输出：3 示例 4： 输入：s = “abcde”, maxLetters = 2, minSize = 3, maxSize = 3 输出：0 提示： 1 <= s.length <= 10^5 1 <= maxLetters <= 26 1 <= minSize <= maxSize <= min(26, s.length) s 只包含小写英文字母。

题解1

代码1

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

class Solution {
public:
    int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
        int len = s.size();
        int maxLen = 0;
        map<string, int>res;
        bool mark[26];
        for(int i = 0; i < len; ++i){
            if(i + minSize - 1 < len){
                memset(mark, false, sizeof(mark));
                int cnt = 0;
                for(int j = i; j < i + minSize; ++j){
                    if(!mark[s[j] - 'a']){
                        ++cnt;
                        mark[s[j] - 'a'] = true;
                    }
                }
                if(cnt <= maxLetters){
                    res[s.substr(i, minSize)]++;
                }
            }
        }
        for(auto &iter:res){
            maxLen = max(maxLen, iter.second);
        }
        return maxLen;
    }
};

5294. 你能从盒子里获得的最大糖果数

题目描述

给你 n 个盒子，每个盒子的格式为 [status, candies, keys, containedBoxes] ，其中： 状态字 status[i]：整数，如果 box[i] 是开的，那么是 1 ，否则是 0 。 糖果数 candies[i]: 整数，表示 box[i] 中糖果的数目。 钥匙 keys[i]：数组，表示你打开 box[i] 后，可以得到一些盒子的钥匙，每个元素分别为该钥匙对应盒子的下标。 内含的盒子 containedBoxes[i]：整数，表示放在 box[i] 里的盒子所对应的下标。 给你一个 initialBoxes 数组，表示你现在得到的盒子，你可以获得里面的糖果，也可以用盒子里的钥匙打开新的盒子，还可以继续探索从这个盒子里找到的其他盒子。 请你按照上述规则，返回可以获得糖果的 最大数目 。 示例 1： 输入：status = [1,0,1,0], candies = [7,5,4,100], keys = [[],[],[1],[]], containedBoxes = [[1,2],[3],[],[]], initialBoxes = [0] 输出：16 解释： 一开始你有盒子 0 。你将获得它里面的 7 个糖果和盒子 1 和 2。 盒子 1 目前状态是关闭的，而且你还没有对应它的钥匙。所以你将会打开盒子 2 ，并得到里面的 4 个糖果和盒子 1 的钥匙。 在盒子 1 中，你会获得 5 个糖果和盒子 3 ，但是你没法获得盒子 3 的钥匙所以盒子 3 会保持关闭状态。 你总共可以获得的糖果数目 = 7 + 4 + 5 = 16 个。 示例 2： 输入：status = [1,0,0,0,0,0], candies = [1,1,1,1,1,1], keys = [[1,2,3,4,5],[],[],[],[],[]], containedBoxes = [[1,2,3,4,5],[],[],[],[],[]], initialBoxes = [0] 输出：6 解释： 你一开始拥有盒子 0 。打开它你可以找到盒子 1,2,3,4,5 和它们对应的钥匙。 打开这些盒子，你将获得所有盒子的糖果，所以总糖果数为 6 个。 示例 3： 输入：status = [1,1,1], candies = [100,1,100], keys = [[],[0,2],[]], containedBoxes = [[],[],[]], initialBoxes = [1] 输出：1 示例 4： 输入：status = [1], candies = [100], keys = [[]], containedBoxes = [[]], initialBoxes = [] 输出：0 示例 5： 输入：status = [1,1,1], candies = [2,3,2], keys = [[],[],[]], containedBoxes = [[],[],[]], initialBoxes = [2,1,0] 输出：7 提示： 1 <= status.length <= 1000 status.length == candies.length == keys.length == containedBoxes.length == n status[i] 要么是 0 要么是 1 。 1 <= candies[i] <= 1000 0 <= keys[i].length <= status.length 0 <= keys[i][j] < status.length keys[i] 中的值都是互不相同的。 0 <= containedBoxes[i].length <= status.length 0 <= containedBoxes[i][j] < status.length containedBoxes[i] 中的值都是互不相同的。 每个盒子最多被一个盒子包含。 0 <= initialBoxes.length <= status.length 0 <= initialBoxes[i] < status.length

题解1

这个题很好理解，第一反应是个递归，写完才发现爆栈了。然后又把程序改成了循环判断boxs(拥有的盒子)是否存在能够打开的，打开后，如果有新钥匙，则将对应盒子的状态修改为1，有新盒子，则添加到boxs中。如此下去，直到boxs中剩下的盒子都已打开或者不存在能够打开的盒子为止。

代码1

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
34
35

int sum = 0;
set<int>boxs;
bool mark[1005];
class Solution {
public:
    int maxCandies(vector<int>& status, vector<int>& candies, vector<vector<int>>& keys, vector<vector<int>>& contains, vector<int>& init) {
        sum = 0;
        boxs.clear();//拥有的盒子
        memset(mark, false, sizeof(mark));
        for(int i = 0; i < init.size(); ++i){
            boxs.insert(init[i]);
        }
        while(boxs.size() != 0){//一直循环
            bool flag = true;
            for(auto iter = boxs.begin(); iter != boxs.end(); ++iter){
                int idx = *iter;
                if(!mark[idx] && status[idx]){
                    flag = false;
                    mark[idx] = true;
                    sum += candies[idx];
                    for(int j = 0; j < keys[idx].size(); ++j){//更新钥匙，也就是使对应盒子的status值为1。
                        status[keys[idx][j]] = 1; 
                    }
                    for(int j = 0; j < contains[idx].size(); ++j){//更新拥有的盒子
                        boxs.insert(contains[idx][j]);
                    }
                }
            }
            if(flag) {//flag为true表示盒子都已打开或不存在能够打开的盒子
                break;
            }
        }
        return sum;
    }
};

成绩

首先晒一下成绩。 成绩单

认证经历

这是第二次参加CCF认证，第一次是在大四的时候，部分考研的同学需要用CCF的成绩作为考研复试机试成绩，找班主任（也是院长）请假去其它学校参加考试。院长一听，就去了解一下CCF认证，觉得还不错，就向那边将我们学校申请为CCF考点，但是一次CCF考试的报名的人数需要达到一定人数才能进行，然后就出现了下面戏剧性的一幕：院长要求XX，XX和XX几个专业的所有大四学生必须参加第16次的CCF考试，并且免报名费，学院出钱。我就这样参加了CCF的考试。第一次参加CCF考试，经验不足。虽然平时有刷天梯赛和蓝桥杯的题目，但是两者的出题思路及考查点不太一样，特别是CCF第3题的题目长度在蓝桥杯和天梯赛基本见不到。并且第16次认证的题目比往年难多了，第2题求中缀表达式的值，这是栈的常见的应用，当时比较执拗，想的是如何用栈将中缀表达式转成后缀表达式，然后再用栈对后缀表达式的值，在这道题上花费了太长时间，到了最后才选择暴力的方法，看了第3题和第4题的题目，选择做了第4题，与进程死锁有关。当时很快有了模拟的思路，写完时间也差不多了，赛后第4题得了80分还不错。但是第1题却破天荒的错了，后来分析错误原因：用了g%的格式控制符。但最后提交只得了一点分，所以，这里需要提醒各位的是，考试建议使用常用的写法，有一些写法不同的编译器不一定能通过。总的来说，第一次认证考试体验感不是很好，题目长（3 4题都很大，并且涉及专业知识看了比较难受）并且题目有些问题，中途组委会通知改的。考试时采用的策略也不够明智，在第2道上花费太长时间，很大一部分时间是想着如何用常规解法去解题，而忽略了快捷的暴力解法。 周日参加的第二次CCF认证考试，题意很好理解。很快把1、2和4题做出来了（大概花了一个半小时），这里大概说一下解题思路。

201912-1报数 题解

题目大意是4个人轮流报数从1开始，遇到7的倍数或含7的数就跳过。题目输入是n表示的4个人总共报的数（不含跳过的数）。 思路很简单：模拟用idx表示当前报数人的编号，num表示当前报的数，i计数（不含路过的数）。如果当前数是7的倍数或含7的数，则idx跳过的数加1，然后i不变。反之，idx跳过的数不变，i+1。

201912-1报数 考试时代码（100分）

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
34
35
36

#include<bits/stdc++.h>
using namespace std;

bool judge(int num){
    if(num % 7 == 0){
        return true;
    }
    int tmp = num;
    while(tmp){
        if(tmp % 10 == 7){
            return true;
        }
        tmp = tmp / 10;
    }
    return false;
}
int main(){
//  freopen("D://a.txt", "r", stdin);
    int n, cnt[4], num = 0, idx = 0;
    memset(cnt, 0, sizeof(cnt));
    scanf("%d", &n);
    for(int i = 0; i < n;){
        ++num;
        if(judge(num)){
            ++cnt[idx];
        }
        else{
            ++i;
        }
        idx = (idx + 1) % 4;
    }
    for(int i = 0; i < 4; ++i){
        printf("%d\n", cnt[i]);
    }
    return 0;
}

201912-2回收站选址 题解

题目大意：先给所有垃圾堆的坐标，然后从这些垃圾堆中选出回收站，回收站需满足：首先上下左右必须都是垃圾堆，然后4个对角的垃圾堆的个数表示该回收站的分数。最后需要统计的是得分为0， 1， 2， 3， 4回收站的个数。 思路：首先选用map对所有垃圾堆的坐标进行标记（因为垃圾堆的坐标可能为负值，用int数组不能直接标记，除非用哈希函数映射），并用vector存下所有垃圾堆的坐标。然后遍历vector中按题目给出的要求判断即可。注意这里vector中的元素和map的键都是pair类型。

201912-2回收站选址 考试时的代码（100分）

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

#include<bits/stdc++.h>
using namespace std;

map<pair<int, int>, bool>myMap;
vector<pair<int, int>>vec;
int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
int dir2[4][2] = {{-1, -1}, {-1, 1}, {1, 1}, {1, -1}};
int cnt[5];
int main(){
//  freopen("D://a.txt", "r", stdin);
    int n, x, y, nx, ny;
    scanf("%d", &n);
    myMap.clear();
    vec.clear();
    memset(cnt, 0, sizeof(cnt));
    for(int i = 0; i < n; ++i){
        scanf("%d%d", &x, &y);
        vec.push_back(make_pair(x, y));
        myMap[make_pair(x, y)] = true;
    }
    for(int i= 0; i < n; ++i){
        x = vec[i].first;
        y = vec[i].second;
        bool flag = true;
        int num = 0;
        for(int i = 0; i < 4; ++i){
            nx = x + dir[i][0];
            ny = y + dir[i][1];
            if(myMap.find(make_pair(nx, ny)) == myMap.end()){
                flag = false;
                break;
            }
        }
        if(flag){
            for(int i = 0; i < 4; ++i){
                nx = x + dir2[i][0];
                ny = y + dir2[i][1];
                if(myMap.find(make_pair(nx, ny)) != myMap.end()){
                    ++num;
                }
            }
            cnt[num]++;
        }
    }
    for(int i = 0; i < 5; ++i){
        printf("%d\n", cnt[i]);
    }
    return 0;
}

201912-4区块链 题解

我的理解是：首先根据题意可以建图，然后图中的每个结点都维持了一条链，每个结点初始时，链上都有一个编号为0的初始块。然后有两个操作：查询操作和更新操作。在进行查询操作和更新操作都需要检查在此之前，是否存在其它节点的更新操作的信息传过来，如果有的话，则需要判断传播节点的主链$l_1$与当前节点的主链$l_2$关系，$l_1$的长度大于$l_2$的长度，直接令$l_2$ = $l_1$。如果$len(l_1)=len(l_2)$且$l_1$的最后一个元素的值小于$l_2$的最后一个值，则令$l_2$ = $l_1$。注意，一旦结点维持的主链的信息更新，就需要将其传播给相邻节点（存在传播时长）。我考试的时侯是用一个队列来维持这个传播的更新信息，存储的元素包含节点值，信息到达节点的时刻，主链三个信息。我估计可能是数据太大的时候，队列可能会内存超限。

201912-4区块链 考试时的代码（70分）

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

#include<bits/stdc++.h>
using namespace std;
struct Node{
    int time;
    int u;
    vector<int>vec;
};
queue<Node>que;
vector<vector<int>>gra(505, vector<int>());
vector<vector<int>>block(505, vector<int>());
void toNum(string s, vector<int>& res){
    res.clear();
    int num = 0;
    for(int i = 0; i < s.size(); ++i){
        if(isdigit(s[i])){
            num = num * 10 + s[i] - '0';
        }
        else{
            res.push_back(num);
            num = 0;
        }
    }
    if(num != 0)
        res.push_back(num);
}
int main(){
//  freopen("D://a.txt", "r", stdin);
    int n, m, t, k;
    int u, v, a, b, c;
    string s;
    vector<int>res;
    while(!que.empty()){
        que.pop();
    }
    gra.clear();
    block.clear();
    for(int i = 0; i < 505; ++i){
        block[i].push_back(0);
    }
    scanf("%d%d",&n, &m);
    for(int i = 0; i < m; ++i){
        scanf("%d%d", &u, &v);
        gra[u].push_back(v);
        gra[v].push_back(u);
    }
    scanf("%d%d", &t, &k);
    getchar();
    for(int i = 0; i < k; ++i){
        getline(cin, s);
        toNum(s, res);
        while(!que.empty()){
            Node frt = que.front();
            if(frt.time <= res[1]){
                que.pop();
                int u = frt.u, v;
                for(int i = 0; i < gra[u].size(); ++i){
                    v = gra[u][i];
                    if(block[v].size() < frt.vec.size()){
                        block[v] = frt.vec;
                        Node tmp;
                        tmp.time = frt.time + t;
                        tmp.u = v;
                        tmp.vec = block[v];
                        que.push(tmp);
                    }
                    else if(block[v].size() == frt.vec.size()){
                        if(block[v].back() > frt.vec.back()){
                            block[v] = frt.vec;
                            Node tmp;
                            tmp.time = frt.time + t;
                            tmp.u = v;
                            tmp.vec = block[v];
                            que.push(tmp);
                        }
                    }
                }
            }
            else{
                break;
            }
        }

        if(res.size() == 3){//update
            block[res[0]].push_back(res[2]);
            Node tmp;
            tmp.time = res[1] + t;
            tmp.u = res[0];
            tmp.vec = block[res[0]];
            que.push(tmp);
        }
        else{
            int u = res[0];
            printf("%d", block[u].size());
            for(int i = 0; i < block[u].size(); ++i){
                printf(" %d", block[u][i]);
            }
            printf("\n");
        }
    }
    return 0;
}

201912-3化学方程式 题解

题目大意：化学方程式配平，检查两边的元素是否相等。 考试只考虑了60%的测试用例，带括号的一直调试不通（其实也算不上调试，我的调试有问题，只能用printf慢慢输出了）。具体见代码，过60%很容易。

201912-3化学方程式 考试时的代码（60分）

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

#include<bits/stdc++.h>
using namespace std;

map<string, int>myMap1, myMap2;

void deal(string s, map<string, int>& myMap){
    int num = 1, len = s.size();
    for(int i = 0; i < s.size(); ++i){
        if(isdigit(s[i])){
            num = 0;
            while(isdigit(s[i])){
                num = num * 10 + (s[i] - '0');
                ++i;
            }
            --i;
        }
        else if(isupper(s[i])){
            string tmp;
            int sum = num;
            tmp.push_back(s[i]);
            if(i < len - 1 && islower(s[i + 1])){
                ++i;
                tmp.push_back(s[i]);
            }
            if(i < len - 1 && isdigit(s[i + 1])){
                int tmpNum = 0;
                ++i;
                while(i < len && isdigit(s[i])){
                    tmpNum = tmpNum * 10 + (s[i] - '0');
                    ++i;
                }
                --i;
                sum = sum * tmpNum;
            }
            if(myMap.find(tmp) != myMap.end()){
                myMap[tmp] = myMap[tmp] + sum;
            }
            else{
                myMap[tmp] = sum;
            }
        }
    }

}
void cal(string s, map<string, int>& myMap){
    int idx = 0, tmp;
    string str;
    while((tmp = s.find('+', idx)) != -1){
        str = s.substr(idx, tmp - idx);
        deal(str, myMap);
        idx = tmp + 1;
    }
    str = s.substr(idx);
    deal(str, myMap);
//  for(auto iter = myMap.begin(); iter != myMap.end();++iter){
//      cout << iter->first << ":" << iter->second<<endl;   
//  }
}
int main(){
//  freopen("D://a.txt", "r", stdin);
    int n;
    string s;
    scanf("%d", &n);
    getchar();
    for(int i = 0; i < n; ++i){
        getline(cin, s);
        int idx = s.find('=');
        string str1 = s.substr(0, idx);
        string str2 = s.substr(idx+1);
        myMap1.clear();
        myMap2.clear();
        cal(str1, myMap1);
        cal(str2, myMap2);

        if(myMap1.size() != myMap2.size()){
            printf("N\n");
        }
        else{
            bool flag = true;
            for(auto iter1 = myMap1.begin(), iter2 = myMap2.begin(); iter1 != myMap1.end() && iter2 != myMap2.end(); ++iter1, ++iter2){
//              cout << iter1->first << ":" << iter1->second<<endl;
//              cout << iter2->first << ":" << iter2->second<<endl;
                if(iter1->first != iter2->first  iter1->second != iter2->second){
                    flag = false;
                    break;
                }

            }
            if(flag){
                printf("Y\n");
            }
            else{
                printf("N\n");
            }
        }
    }
    return 0;
}

这次在第3题仍然采用不太明智的策略，则开始就考虑了多重括号嵌套的情况，然后代码写了很长时间，真的很长时间，因为一直没有理清思路。后来写完了，运行一直有问题，排错很长时间无效，最后又只能放弃后40%的测试用例，专心调试前60%的用例，很快就通过。所以，在这里需要注意的是，对于用例层层递进的情形，代码如果一时不能处理所有情况，也可以逐渐完善，先保证通过最简单的测试用例，再考虑其它情况。

反思

可能是最后一次CCF，成绩离预期还是有点小差距，毕竟写题解的过程发现题目并不是很难，所以存在的问题还是要反省。 前一个半小时做完1，2，4题，后两个半小时做第3道题只得60分，对于时间利用率不高。做完1，2，4题大脑开始有点反应不过来（身体还是有点虚啊），第3题对于括号嵌套的情形迟迟没想清楚，导致代码Bug横生，如果及时调整思绪，从简单的情形做起，逐渐增加难度，完善代码，通过一重括号的测试用例应该没有问题。这里可以+20。第5题是大数模拟，听说水个20分没问题。用c++写个大数运算更应该没问题，只是麻烦，这里可以+20。最佳可达370+。 DEV的调试无法使用属于特殊情况，不应归咎。但个人的心态的调整，做题策略的更换，做题时间的分配却应该以时间，地点，条件为转移（巧妙将马克思原理应用于实践）。流水不腐，户枢不蠹。

经验分享

针对C++： 1. 头文件用万能头文件避免include一堆其它头文件，带来记忆负担。代码如下：

1
2

#include<bits/stdc++>
using namespace std;

1. 从文本读入数据，对于3， 4， 5题，题目的输入往往很长，而它的题目往往又是图片，不能用CV大法。这时，就能充分发挥文件读入的优势了。使用方法，在main函数的第一行加入以下代码freopen("D://a.txt", "r", stdin)然后将数据粘贴进入D盘下的a.txt，这个路径可以自定义，然后运行的时候，直接从文件输入，输出仍在控制台。 注意：提交的时候freopen("D://a.txt", "r", stdin)一行一定要注释掉，一定要注释掉，一定要注释掉，重要的事情说三遍，不然提交会是0分。 我常用的模板文件代码为：

1
2
3
4
5
6
7

#include<bits/stdc++>
using namespace std;

int main(){
    //freopen("E://a.txt", "r", stdin);
    return 0;
}

1. 常用的stl的数据结构及函数一定要牢记，考试的时候能事半功倍。比如：数据结构：map（这次的2 3 题都有用到），set，pair，stack，queue（其中优先队列蛮香的），string， vector等。函数如sort(排序)，binary_search(二分查找)，cctype的字符判断函数isdigit（是否为数字），isupper（是否为大写字母），islower（是否为小写字母）等，stoi（string转int），atoi（字符串转int），sprintf等。
2. c++11是真香的，里面有正则表达式，它能让字符串的处理更加简单。有unordered_map，unordered_set能有效解决查询超时的问题。
3. 掌握常见的算法：DFS，BFS，Prim，Dijstra，并查集等，虽然最近几次考的第4题模拟都能做的，不会涉及算法。

针对CCF考试： 1. 做题策略：我一般是1 2 4 3的顺序，如果第3题的题意比较容易理解，容易模拟，可以先做。第5题可以过前面简单规模，简单逻辑的用例。 2. 考试的时候无任何反馈，类似于蓝桥杯，与pat的在线评测不同，所以对于1，2题需仔细设计测试用例，保证得满分。 3. 注意输入输出的格式， 这个有时候很致命，201903-2的中缀表达式的那一题，当时我一个同学就把乘号当成常见的*，实际是x（小写的x），结果可想而知。对于输出YES和NO的，稍有不慎，会看成Yes和No。 这种情况理应避免。 4. 平常多练，注重首次通过率。 我要分享就这么多，这次200+，满足毕业答辨的要求了，2019太过平淡无奇，也算完成了一个小目标。，明天继续一天一道 LeetCode打卡任务，暂时告别CCF。

论文地址

1 引言

人脸表情是人们用来表达情感的最有力，最自然和最普通的方式之一。由于人脸表情识在社交机器人，医学治疗，疲劳驾驶检测和许多人机交互系统的实际应用价值，已经做了很多关于人脸表情识别的研究。早在20世纪，Ekman和Friesen基于人们对于相同表情的表达与种族无关的研究，定义了六种基本的表情。包括愤怒，厌恶，害怕，高兴，悲伤和惊讶。蔑视后来也被加入基本表情中。 尽管基于基本表情的模型在表达人们日常生活中的复杂表情和细微表情上的能力有所不足，像面部动作编码系统（FACS)等可以表示更宽范围，更丰富的表情。但基于基本表情的分类模型仍是FER中最流行的，在这篇综述中，我们也仅在这种分类模型上讨论FER。 FER系统可以根据特征表示被分成两个主要类别：静态图像FER和动态序列FER。在基于静态的方法其特征表示的编码仅包含单个图像的空间信息，而基于动态的方法的特征表示的编码考虑了输入表情序列的连续帧之间的时间关系。用于FER的大多数传统的方法使用的是手工特征或浅层学习（例如，局部二元模式（LBP），非负矩阵分解（NMF）和稀疏学习）。然而，自从2013年起，表情识别比赛，如FER2013和EmotiW，从现实的场景中，收集足够多的训练数据，促使FER从实验室走向实际场景。与此同时，由于芯片的处理能力的急速提高（例如，GPU）和好的网络架构，使得各个领域的研究已开始转移到深度学习的方法，取得了最好的识别精度并且大幅度超过传统方法的识别精度。在表情识别方面，近年来，相关的研究机构也提供了大量的训练数据集，越来越多的深度学习的方法被提出来解决表情识别中一些具有挑战的场景。在图1展示出的Fer相关的算法和数据集的演变。 近年来，关于人脸表情识别的综述有很多，这些综述建立了一系列关于FER的标准算法准则，但是，他们集中于对传统方法的论述，对深度方法很少提及。因此，在这篇文章，对基于静态单张图片的FER任务的深度方法进行了全面的研究。尽管深度学习具有强大的特征学习能力，但应用到FER仍然还存在着一些问题。首先，深度神经网络需要大量的训练数据来防止过拟合，然而，现存在的人脸表情数据集不够充分以致不能训练较好的神经网络模型。另外，由于不同人的年龄，性别，种族背景等导致个体间存在较大的差异。除了个体差异，光照、遮挡和姿态等因素对于人脸表情识别的性能具有较大的影响。 图X 人脸表情识别在数据集及方法上的演变 在这篇论文中，我们介绍一些用于解决以上问题的最新的深度FER的方法。首先，第2章介绍常用的人脸表情数据集，第3章介绍深度EFR系统中最主要的有三个步骤。……

2 人脸表情数据集

拥有尽可能多的复杂环境的带标签的训练数据庥对于深度人脸表情识别系统的设计量至关重要的。在这一章，我们主要讨论那些包含基本表情，并广泛应用于深度学习算法评估的公共数据集。表X提供了这些数据集的概览。包含人的数量，图片或视频用例的数量，数据集收集的环境，表情的分布和其它信息。 表X 人脸表情数据集概览 CK+:CK+数据集是评估FER系统中应用最广泛的采集于实验室的数据集。CK+数据集包含来自123个人的593个视频序列，这些序列从10帧到60帧数量不等，并且展示出表情从中性到峰值的变化。这些视频序列都标有基于FACS的七个基本的表情标签（愤怒，蔑视，厌恶，害怕，高兴，悲伤，惊讶）。因为CK+并不提供特定的训练集，验证集和测试集，所有算法在这个数据集的评估方式存在差异，基于静态图片的最觉见的数据选取方法是提取每一个视频序列的第一帧，带有峰值信息的三帧及最后一帧。然后，将这些受试者被分成n组来进行n重交叉验证实验，通常选取的n值为5， 8， 10。 JAFFE:日本女性表情数集(JAFFE)是一个在实验室采集的图像数据集，其中包含来自10名日本女性的213张姿态表情。每一个人都有3-4张基本表情(愤怒，厌恶，害怕，高兴，悲伤和惊讶)，有一张中性的表情。由于该数据集拥有较少的图片，导致它具有一定的挑战性。 FER2013:FER2013数据集首次在ICML2013特征学习挑战赛中提出的。FER2013是使用谷歌图片搜索引擎自动收集的大规模，不受约束的数据集。所有的图片大小被调整到$48\times48$的。FER2013中包含28709张训练数据集，3589张验证数据集和3589张测试数据集，每张图片标注有七种标签(愤怒，厌恶，害怕，高兴，悲伤，惊讶和中性)之一。 AFEW:AFEW(Acted Facial Expression in the Wild)数据集自2013年起开始作为每年的EmotiW(Emotion Recognition in the Wild Challenge)的评测平台。AFEW包含来自不同的电影带有连续表情的电影片段，其中涉及姿态，遮挡和光照等复杂环境。每个样例标记有七个表情：愤怒，厌恶，恐惧，高兴，悲伤，惊讶和中性。表情的标签在持续更新，并有现实中的真人秀节目的数据不断增加进来。 EmotiW2017的AFEW 7.0数据集按照来自电影或真人秀的受试者将数据集分成三部分：训练集(773个)，验证集(383个)，测试集(653个)。 SFEW:SFEW(The Static Facial Expressions in the Wild)是基于脸部关键点计算关键帧从AFEW数据集中选取静态帧组成的。最常用的版本是SFEW2.0,其是EmotiW2015中SReco子挑战的基准数据集。SFEW2.0被分成三个数据集：训练数据集(958个)，验证数据集(436个)和测试数据集(372个)。每张图片都被标记为七种表情种类(愤怒，厌恶，害怕，中性，高兴，悲伤和惊讶)的一种。 BU-3DFE:BU-3DFE(Binghamton University 3D Facial Expression)包含来自100个人的606个人脸表情序列。对于每张图片，都显式的标出6种基本表情(愤怒，厌恶，害怕，高兴，悲伤和惊讶)的强度。和Multi-PIE相似，这个数据集通常被用于3D人脸表情分析。 Oulu-CASIA:Oulu-CASIA数据集包含来自80个个体共2880个视频序列，都标有六种基本表情标签：愤怒，厌恶，害怕，高兴，悲伤和惊讶等。环境为近红外光，可见光，三种不同的光照条件。同CK+数据集类似，它的第一帧是中性表情，最后一帧有峰值表情。特别是来自480个视频的最后三帧峰值表情和第一帧用来做10重交叉验证实验。 EmotionNet:EmotionNet是一个大型的数据集，它拥有100万张收自网络的人脸表情图片。其中的95万张图片用AU检测模型(action unit)来自动标注，剩下的25万张图片则是用11AUs去手动标注。在EmotinNet挑战赛上，提供了带有6种基本表情和10种综合表情标签的2478张图片。 RAF-DB:RAF-DB(Real-world Affective Face Database)是包含下载自互联网的29672张表情图片的真实世界的数据集。借助手动标注和可靠的估算，每个样例标有7个基本表情和11个综合表情标签。基本表情数据集中15339张图片被分成两组(12271个训练样例和3068个测试用例)用来评估算法性能。 AffectNet:AffectNet数据集包含来自网络的100多万张图片，每张图片使用不同的搜索引擎用与表情相关的关键字查询所获得。其中的45张图片已经被手式标注了8个基本表情标签。 ExpW:ExpW(Expression in-the-Wild Database)包含91793张使用google图片搜索引擎下载的人脸图片，每一张人脸的图片都被手动标注为7种基本表情的一种，无人脸的图片将在标注过程中移除掉。

3 深度人脸表情识别

这一章，我们将介绍了深度FER中最主要的三个步骤，预处理，深度特征提取和深度特征分类。我们简短的总结了每个步骤广泛使用的算法。

3.1 预处理

一些变量像不同的背景，光照和姿态等都与人脸表情不相关，但是在无约束的场景是普通存在的。因此，在训练神经网络去学习有用的特征之前，需要用预处理来对齐人脸并规范人脸所传达出的视觉语义信息。

3.1.1 人脸对齐

人脸对齐在很多与人脸相关的识别的任务中是一个预处理的步骤。我们列出了一些广泛应用深度FER并公开算法实现的算法。对于训练数据，首先第一步是检测人脸，然后去除人脸和不相关的区域。Viola-Jones(V&J)人脸检测器是一个经典的并广泛应用人脸检测的检测器，它具有很强鲁棒性，并且计算简单。 表X 在深度FER中广泛应用的人脸对齐检测器的总结 尽管人脸检测是特征学习前唯一的必不可少的过程，在检测后的人脸使用人脸对齐能进一步提高FER的性能。这一步是至关重要的，因为它能减小人脸规模和平面内旋转的变化。表X研究了广泛应用在深度FER中的人脸关键点检测算法并比较他们的执行效率及性能。主动外观模型(Active Appearance Model)是一个典型的生成式模型，优化全局的人脸外观和形状模型的参数。在判别式模型中，MoT(mixtures of trees)和DRMF(Disctiminative response map fitting)通过关键点周围的局部外观信息来表示人脸。另处，还有大量的差别式模型直接使用级联回归函数将图像外观特征映射到关键点位置，并显示更好的结果。比如在IntraFace中实现的SDM(supervised descent method)，3000 fps和增量人脸对齐等等。最近，深度网络也广泛应用于人脸对齐。级联CNN是第一个用级联的方式来预测人脸关键点的深度算法。基于此，TCDCN(Tasks-Constrained Deep Convolutional Network)和多任务CNN(MTCNN)进一步利用多任务学习来提升性能。一般情况下，级联回归由于其高速和高精确度已经成为最流行和最新的算法。

3.1.2 数据增强

深度卷积神经网络要求足够多的数据来确保模型在指定的识别任务下的泛化能力。然而大部分公开的人脸数据集并没有充分的人脸数据用于训练，因此，数据增强是深度FER中至关重要的一步。数据增增技术可分为两类：线下数据增强和在线数据增强。 通常情况下，线上数据增强被加入深度学习工具箱来防止过拟合。在训练过程中，输入的图片从图像的四角和中心随机裁剪，然后水平翻转，就能使得训练的数据集是原始的十倍。除了基础的线上数据增强，各种各样的离线数据增强被用来进一步扩充数据。最常用的操作包括：旋转，平移，尺寸变换，噪声，反转，畸变等。比如，常见的噪声模型像椒盐噪声，高斯噪声等被用于扩大数据量。多种操作相结合可以生成更多看不到的训练数据，使网络模型的鲁棒性更强。

3.1.3 人脸归一化

人脸图片中光照和头部姿态的变化对FER的性能有很大的影响，因此，我介绍了两种典型的人脸归一化方法来减少这些变化带来的影响：光照归一化和姿态归一化。 光照归一化：光照在不同的图片中都存在差异，即使是同一个人的相同表情也存在不同的光照，尤其在非限制的环境下，它会对结果产生很大影响。在[60]中，总结了几个常用的光照归一化方法：基于各向同性扩散归一化（isotropic diffusion-based normalization）、基于离散余弦变换归一化（DCT-based normalization）和高斯差分（DoG）。在[86]中使用了同态滤波归一化的方法，其相比其它方法，产生更加一致的结果。另外，有相关研究显示，将光照归一化与直方图均衡化相结合在人脸表情识别的性能比只使用光照归一化的性能要好。许多对深度FER的研究都在预处理阶段采用直方均衡图来增加图像整体的对比度。当图像的前景与背景的高度较接近时，这种方法是比较有效的。 姿态归一化：考虑到姿态变化在非受限的环境下是另一个常见的问题。一些研究采用姿态归一化技术来生成正面人脸图。其中Hassner提出的方法是最常用的，在对人脸的关键点进行定位后，对所有的人脸生成一个3D纹理参考模型估计可视人脸部分，然后将输入的人脸投影到参考的坐标系上，合成的人脸的正面图。最近，也提出了一些基于GAN的生成正面人脸的深度网络模型(FF-GAN，TP-GAN和DR-GAN)。

3.2 特征学习深度网络

深度学习最近是一个很火热的研究话题，在很多应用上都取得最新的性能表现。深度学习尝试使用多个非线性的转换和表示结构来捕获更高层次的特征抽象。在这一章，我们简短地介绍了应用于FER的深度学习技术。这些深度神经网络的结构如图X所示。 图X 深度表情识别系统的一般步骤 CNN在计算机视觉中广泛应用，一个CNN结构通常包含卷积层、池化层和全连接层等。在表X中我们列出了一些著名的CNN模型的构成和特征。除了这些神经网络，基于区域的CNN(R-CNN)也被用于FER中的特征学习，Faster R-CNN 通过生成高质量候选区域，识别面部表情。Ji et al提出的3D CNN通过3D卷积来对捕获多个相邻帧之间的动作信息来对动作进行识别。深度信念网络(DBN)是由Hinton提出的，学习提取训练数据的深度层次表示。DBN中，较高层的单元被训练去学习相邻低层的单元间的条件依赖，除了最高的两层，其余都没能直接连接。DBN的训练包含两个阶段：预训练和微调。首先用逐层贪婪训练方法初始化深度网络，可以在不需要大量标注数据的情况下防止局部最优解。然后，用有监督的梯度下降对网络的参数和输出进行微调。深度自编码器(Deep autoencoder)首次在[118]中提出来学习特征降维的有效编码，与之前的方法不同，DAE通过最小化重建误差来优化输入的重建。目前存在很多种DAE:降噪自编码器，可从部分损坏的数据中恢复原始未损坏数据；稀疏自编码网络，增强学习得到的特征表示的稀疏性；压缩式自编码器，增加活动相关正则项以提取局部不变特征；卷积自编码器，使用卷积层代替 DAE 中的隐藏层。循环神经网络(RNN)是联结主义的模型，能捕捉时间信息，对于任意长度的序列数据的预测是更合适的。时间的反向传播(BPTT)被用来训练RNN。由Hochreiter和Schmidhuber提出的LSTM是传统的RNN的一种特殊的形式被 用来解决常常出现在训练RNNs中的梯度消失和梯度爆炸的问题。LSTM能学习序列中的长时依赖，被广泛用于基于视频的表情识别的任务。

3.4 人脸表情分类

在学习到深度特征后，FER的最后一步是将给定的人脸进行表情分类。传统深度的特征提取和特征分类是相互独立的，而深度网络用一种端到端的形式来完成FER任务。特别是，在网络的最后能加入损失层来减少反向传播的误差，并且在网络的最后能够直接给出每个实例的预测概率。 在CNN中，softmax损失函数是最常使用的用来最小化预测类别与ground truth之间的交叉熵。论文[130]表明在端到端训练中使用支持向量机(SVM)分类比交叉熵的表现要好。 除了端到端的学习方式，另一种可选用的方式是采用深度神经网络(CNN)进行特征提取，然后再使用额外的分类器进行特征分类，比如支持向量机或随机森林等。

4 最新方法

在这一章，我们对用于FER的深度神经网络和用于表情相关问题而提出的训练策略进行研究。我们提供了现在的深度FER系统在常见的数据集上的性能表现。由于一些数据集并没有提供明确的提供训练，测试和验证集，与之相关的研究可能在不同的数据集，不同的实验条件下进行的，所以，我总结了识别实验有关数据集的选取与分组方法的信息。在静态图片上进行的表情分类研究有很多，因为不用考虑时间信息，并且数据处理方便，与训练和测试有关的数据集易获得。我们首先介绍了FER中预训练和微调的技巧，然后研究了这个领域的深度神经网络，对最常评估的数据集，在表X中显示在最新方法的性能表现。

4.1 预训练和微调

在相当小的数据集上直接训练，容易造成过拟合。为了解决这种总是，很多研究先在其它数据集上进行预训练，然后在训练好的网络进行微调(如AlexNet，VGG，GoogleNet等)。Kahou et al.实验证明使用额外的数据集能够帮助模型避免过拟合，并且能够提升FER的性能表现。 比起直接在预训练或微调的模型上对目标数据集进行特征提取，一个多阶段的微调策略(如图X所示)能获得更好的性能。第一阶段在预训练模型上使用 FER2013 进行微调，第二阶段利用目标数据库的训练数据进行微调，使模型更切合目标数据库。 Ding 等人发现由于 FR 和 FER 数据库之间的差距，人脸主导的信息仍然遗留在微调的 FR 网络中，削弱了网络表示不同表情的能力。提出FaceNet2ExpNet的训练策略，如图X所示。微调的网络作为表情网络的初始值，仅能引导卷积层的学习，全连接层的训练则从头开始。

4.2 辅助网络块

基于CNN的基础架构，一些研究提出了一些设计好的辅助块或辅助层来增强学习到的与表情相关的特征的表达能力。 一个新颖的CNN网络HoloNet将CReLU与强有力的残差结构相结合，加深网络的深度。[165]设计出一个辅助块用于学习多尺度的特征来捕获人脸的变化。Hu 等人将 3 类有监督网络块嵌入 CNN 结构的实现浅层、中层和深层的监督。这些块根据原网络的层级特征表示能力设计。随后，每个块的类间评分在连接层进行累积，进行第二级的监督，如图所求。 图X [91]中三个不同的有监督网络块 FSN(Feature Selection Network)是在AlexNet中加入了一个特征选择机制，它能自动过滤掉不相关特征，然后根据对人脸表情特征图的学习突出相关特征。Zeng et al.提出了IPA2LT(Inconsistent Pseudo Annotations to Latent Truth)结构，它通过将人类标注与机器标注最大似然化来发现不同数据集间机器的潜在真值。Cai 等人提出岛损失层。如图X所求。特征提取层计算的岛损失层和决策层计算的 softmax 损失结合起来监督 CNN 训练。Liu 等人提出（N+M）组聚类损失层。如图X所求在训练过程中，身份感知的难分样本挖掘和积极样本挖掘技巧用于降低同一表情类别下身份内部的变化所带来的影响。 图X [140]中的岛损失层 图X [77]组聚类损失层

4.3 网络集成

之前的研究表现多个网络的集成性能优于单个网络，在网络集成时，有两点需要注意：(1)多个网络的集成应确保功能多样且互补，而不是相同功能的堆砌。(2)采用合适的集成方法来有效地发挥各个网络的作用。 对于第一点，采用前面提到的预处理方法能产生不同的数据来训练多样的网络，通过改变卷积核的大小，层数，神经元的数目，采用随机初始化的方法来初始网络权重能加强网络的多样性。除此之外，不同的网络结构也能增加多样性。比如将用有监督学习的CNN与无监督学习的CAE进行网络集成。 对于第二点，网络可以在两个不同层面上进行组合：特征层和决策层。对于特征层，最常采取的方法是将不同网络学习得到的特征连接起来，组成一个新的特征矢量，来表示图像。如图X所求。在决策层，常用的三种方法是：多数投票、简单平均和加权平均。Kim 等人提出 3 级组合结构，在决策层融合，获取充分的决策多样性。如图X所求。

4.4 多任务网络

现在存在的很多网络都是单任务网络，学习到的特征由于没有考虑其它潜在因素与表情的联系，对表情敏感。然而真实世界中，FER和多个因素相关，像头的姿态，光照，个体差异等。为了解决这类问题，引入了多任务学习，将知识从其他相关任务中迁移出来，消除不利因素。 Reed等构造了建造了一个高阶玻尔兹曼机（disBM）学习与表情相关因素的流形坐标并提出了一种训练策略消除与表情相关的因素的影响。其它研究，将FER与其它任务同时进行，比如脸部关键点定位和脸部的Aus检测，它们的结合能有效提高FER的性能。除此之外，IACNN(Identity-aware CNN)采用两个完全相同的子CNN，一个使用对比损失来学习判别式表情特征，另一个用对比损失学习个体相关特征，在 Zhang 等人提出的 MSCNN 中，在训练时一对图像输入 MSCNN 网络。表情识别任务使用交叉熵损失，学习表情变化特征，面部识别人任务使用对比损失，减少同类表情特征之间的变化。如图X所示。

4.5 注意力网络

Attention机制在近几年来在图像，自然语言处理等领域中都取得了重要的突破，被证明有益于提高模型的性能。Attention机制本身也是符合人脑和人眼的感知机制，聚焦于局部信息的机制。 图X FERAtt的网络结构 现在的很多研究，都是整张进行处理，引入噪声和不必要的计算。仿照人的注意力机制，Fernandez等人提出了一种注意力网络，如图X所求。共分为四个模块：注意力模块、特征提取模块、重建模块和分类再表示模块。并设计出高斯损失函数来优化特征表示。针对遮挡和姿态两大难题，Kai Wang等在FERplus，AffectNet、RAF-DB三个数据集的基础上筛选遮挡和姿态较大的图片创建了六个数据集Occlusion-FERPlus, Pose-FERPlus, Occlusion-AffectNet, Pose-AffectNet, Occlusion-RAF-DB, and Pose-RAF-DB。并设计出RAN(Region Attention Networks)，如图X所求。并设计了RB-Loss，来提升区域在特征表示上的权重。该方法在多个数据集均有较大的性能提升。陆续将会有更多基于Attention机制的FER网络被提出，它在某些问题上的性能表现优于一般的网络结构。 图X RAN网络结构 表X比较了不同类型的方法(预处理微调，辅助层，网络集成，多任务网络，注意力网络)对于数据大小的要求，在复杂环境(头的姿态，光照，遮挡和其它环境因素)的性能，计算效率，准确率，网络训练的难度。

总结

由于 FER 研究将其主要关注点转移到具有挑战性的真实场景条件下，许多研究人员利用深度学习技术来解决这些困难，如光照变化、遮挡、非正面头部姿势、身份偏差和低强度表情识别。考虑到 FER 是一个数据驱动的任务，并且训练一个足够深的网络需要大量的训练数据，深度 FER 系统面临的主要挑战是在质量和数量方面都缺乏训练数据。由于不同年龄、文化和性别的人以不同的方式做出面部表情，因此理想的面部表情数据集应该包括丰富的具有精确面部属性标签的样本图像，不仅仅是表情，还有其他属性，例如年龄、性别、种族，这将有助于跨年龄、跨性别和跨文化的深度 FER 相关研究。另一方面，对大量复杂的自然场景图像进行精准标注是构建表情数据库一个明显的障碍。

1275. 找出井字棋的获胜者

题目描述

A 和 B 在一个 3 x 3 的网格上玩井字棋。 井字棋游戏的规则如下： 玩家轮流将棋子放在空方格 (“ “) 上。 第一个玩家 A 总是用 “X” 作为棋子，而第二个玩家 B 总是用 “O” 作为棋子。 “X” 和 “O” 只能放在空方格中，而不能放在已经被占用的方格上。 只要有 3 个相同的（非空）棋子排成一条直线（行、列、对角线）时，游戏结束。 如果所有方块都放满棋子（不为空），游戏也会结束。 游戏结束后，棋子无法再进行任何移动。 给你一个数组 moves，其中每个元素是大小为 2 的另一个数组（元素分别对应网格的行和列），它按照 A 和 B 的行动顺序（先 A 后 B）记录了两人各自的棋子位置。 如果游戏存在获胜者（A 或 B），就返回该游戏的获胜者；如果游戏以平局结束，则返回 “Draw”；如果仍会有行动（游戏未结束），则返回 “Pending”。 你可以假设 moves 都 有效（遵循井字棋规则），网格最初是空的，A 将先行动。 示例 1： 输入：moves = [[0,0],[2,0],[1,1],[2,1],[2,2]] 输出：”A” 解释：”A” 获胜，他总是先走。 “X “ “X “ “X “ “X “ “X “ “ “ -> “ “ -> “ X “ -> “ X “ -> “ X “ “ “ “O “ “O “ “OO “ “OOX” 示例 2： 输入：moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]] 输出：”B” 解释：”B” 获胜。 “X “ “X “ “XX “ “XXO” “XXO” “XXO” “ “ -> “ O “ -> “ O “ -> “ O “ -> “XO “ -> “XO “ “ “ “ “ “ “ “ “ “ “ “O “ 示例 3： 输入：moves = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]] 输出：”Draw” 输出：由于没有办法再行动，游戏以平局结束。 “XXO” “OOX” “XOX” 示例 4： 输入：moves = [[0,0],[1,1]] 输出：”Pending” 解释：游戏还没有结束。 “X “ “ O “ “ “ 提示： 1 <= moves.length <= 9 moves[i].length == 2 0 <= moves[i][j] <= 2 moves 里没有重复的元素。 moves 遵循井字棋的规则。

题解1

模拟即可，判断横，竖，及对角线只否有连线成功，有则返回对应的胜利者，没有的话，就看还有没有空位可以继续行动，有的话，表示仍可以行动，没有的话，就是平局。

代码1

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

int deal(int arr[3][3]){
    for(int i = 0; i < 3; ++i){
        if(arr[i][0] == 0 && arr[i][1] == 0 && arr[i][2] == 0){//行  - A
            return 0;
        }
        if(arr[i][0] == 1 && arr[i][1] == 1 && arr[i][2] == 1){//行 - B
            return 1;
        }
        if(arr[0][i] == 0 && arr[1][i] == 0 && arr[2][i] == 0){// 列 - A
            return 0;
        }
        if(arr[0][i] == 1 && arr[1][i] == 1 && arr[2][i] == 1){// 列 － B
            return 1;
        }
    }
    if(arr[0][0] == 0 && arr[1][1] == 0 && arr[2][2] == 0){//主 对角线 - A
        return 0;
    }
    if(arr[0][0] == 1 && arr[1][1] == 1 && arr[2][2] == 1){//主对角线 - B 
        return 1;
    }
    if(arr[0][2] == 0 && arr[1][1] == 0 && arr[2][0] == 0){//副对角线 - A
        return 0;
    }
    if(arr[0][2] == 1 && arr[1][1] == 1 && arr[2][0] == 1){//副对角线 - B
        return 1;
    }
    return -1;
}
class Solution {
public:

    string tictactoe(vector<vector<int>>& moves) {
        int arr[3][3];
        for(int i = 0; i < 3; ++i){
            for(int  j = 0;j < 3; ++j){
                arr[i][j] = -1;
            }
        }
        for(int i = 0; i < moves.size(); ++i){
            if(i & 1 == 1){
                arr[moves[i][0]][moves[i][1]] = 1;
            }
            else{
                arr[moves[i][0]][moves[i][1]] = 0;
            }
        }
        int res = deal(arr);
        cout << res << endl;
        for(int i = 0; i < 3; ++i){
            for(int  j = 0;j < 3; ++j){
                cout << arr[i][i] << " ";
            }
            cout << endl;
        }
        if(res == -1){
            bool flag = false;
            for(int i = 0; i < 3; ++i){
                for(int j = 0; j < 3; ++j){
                    if(arr[i][j] == -1){//有空格
                        flag = true;
                        break;
                    }
                }
            }
            if(flag){
                return "Pending";
            }
            else{
                return "Draw";
            }
        }
        else{
            return deal(arr) == 0?"A":"B";
        }
    }
};

1276. 不浪费原料的汉堡制作方案

题目描述

圣诞活动预热开始啦，汉堡店推出了全新的汉堡套餐。为了避免浪费原料，请你帮他们制定合适的制作计划。 给你两个整数 tomatoSlices 和 cheeseSlices，分别表示番茄片和奶酪片的数目。不同汉堡的原料搭配如下： 巨无霸汉堡：4 片番茄和 1 片奶酪 小皇堡：2 片番茄和 1 片奶酪 请你以 [total_jumbo, total_small]（[巨无霸汉堡总数，小皇堡总数]）的格式返回恰当的制作方案，使得剩下的番茄片 tomatoSlices 和奶酪片 cheeseSlices 的数量都是 0。 如果无法使剩下的番茄片 tomatoSlices 和奶酪片 cheeseSlices 的数量为 0，就请返回 []。 示例 1： 输入：tomatoSlices = 16, cheeseSlices = 7 输出：[1,6] 解释：制作 1 个巨无霸汉堡和 6 个小皇堡需要 4_1 + 2_6 = 16 片番茄和 1 + 6 = 7 片奶酪。不会剩下原料。 示例 2： 输入：tomatoSlices = 17, cheeseSlices = 4 输出：[] 解释：只制作小皇堡和巨无霸汉堡无法用光全部原料。 示例 3： 输入：tomatoSlices = 4, cheeseSlices = 17 输出：[] 解释：制作 1 个巨无霸汉堡会剩下 16 片奶酪，制作 2 个小皇堡会剩下 15 片奶酪。 示例 4： 输入：tomatoSlices = 0, cheeseSlices = 0 输出：[0,0] 示例 5： 输入：tomatoSlices = 2, cheeseSlices = 1 输出：[0,1]

题解1

解二元一次方程组即可，注意两个变量的解均为非负值。

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    vector<int> numOfBurgers(int tom, int che) {
        vector<int>res;
        int tmp = tom - 2 * che;
        if(tmp < 0  tmp & 1 == 1){
            return res;
        }
        res.push_back(tmp >> 1);
        res.push_back(che - (tmp >> 1));
        if(res[0] < 0  res[1] < 0){
            res.clear();
        }
        return res;
    }
};

1277. 统计全为 1 的正方形子矩阵

题目描述

给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。 示例 1： 输入：matrix = [ [0,1,1,1], [1,1,1,1], [0,1,1,1] ] 输出：15 解释： 边长为 1 的正方形有 10 个。 边长为 2 的正方形有 4 个。 边长为 3 的正方形有 1 个。 正方形的总数 = 10 + 4 + 1 = 15. 示例 2： 输入：matrix = [ [1,0,1], [1,1,0], [1,1,0] ] 输出：7 解释： 边长为 1 的正方形有 6 个。 边长为 2 的正方形有 1 个。 正方形的总数 = 6 + 1 = 7. 提示： 1 <= arr.length <= 300 1 <= arr[0].length <= 300 0 <= arr[i][j] <= 1

题解1

模拟，固定正方形的左上角，改变它的边长，直接求解的时间复杂度为$o(n^4)$，可以用$o(n^2)$的空间来存储行和与列和，只需要判断序列和是否与边长相等即可。具体实现见代码。

代码1

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

int rowSum[305][305];
int colSum[305][305];
class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        memset(rowSum, 0, sizeof(rowSum));
        memset(rowSum, 0, sizeof(rowSum));
        int len1 = matrix.size();
        int len2 = matrix[0].size();
        for(int i = 0; i < len1; ++i){//行和
            for(int j = 0; j < len2; ++j){
                rowSum[i][j] = matrix[i][j] + (j == 0?0:rowSum[i][j - 1]);
            }
        }
        for(int i = 0; i < len1; ++i){//列和
            for(int j = 0; j < len2; ++j){
                colSum[i][j] = matrix[i][j] + (i == 0?0:colSum[i - 1][j]);
            }
        }
        long long int res = 0, num = 0;
        for(int i = 0; i < len1; ++i){
            for(int j = 0; j < len2; ++j){
                if(matrix[i][j] == 1){
                    ++num;
                    int tmp1, tmp2;
                    for(int m = i, n = j;m < len1, n < len2; m = m+1, n = n+1){//固定左上角顶，扩大边长
                        if(j - 1 < 0){
                            tmp1 = 0;
                        }
                        else{
                            tmp1 = rowSum[m][j - 1];
                        }
                        if(i - 1 < 0){
                            tmp2 = 0;
                        }
                        else{
                            tmp2 = colSum[i - 1][n];
                        }
                        if((rowSum[m][n] - tmp1 == n - j + 1) && (colSum[m][n] - tmp2 == m - i + 1)){
                            ++res;
                        }
                        else{
                            break;
                        }
                    }
                }
            }
        }
        return res;
    }
};

1278. 分割回文串 III

题目描述

给你一个由小写字母组成的字符串 s，和一个整数 k。 请你按下面的要求分割字符串： 首先，你可以将 s 中的部分字符修改为其他的小写英文字母。 接着，你需要把 s 分割成 k 个非空且不相交的子串，并且每个子串都是回文串。 请返回以这种方式分割字符串所需修改的最少字符数。 示例 1： 输入：s = “abc”, k = 2 输出：1 解释：你可以把字符串分割成 “ab” 和 “c”，并修改 “ab” 中的 1 个字符，将它变成回文串。 示例 2： 输入：s = “aabbc”, k = 3 输出：0 解释：你可以把字符串分割成 “aa”、”bb” 和 “c”，它们都是回文串。 示例 3： 输入：s = “leetcode”, k = 8 输出：0 提示： 1 <= k <= s.length <= 100 s 中只含有小写英文字母。

题解1

动态规划 dp[i][j]表示长度为j的字符串，划成i个回文串所需最少替换次数。 其中dp[i][j]的状态转换方程为 $dp[i][j] = min(dp[i][j], dp[i - 1][k] + deal(k, j - 1))\space k=i-1, \dots, j - 1$

代码1

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
34
35
36
37
38
39
40
41
42

#define MAX (1 << 30)
int cal(string s, int beg, int end){//计算变成回文串的步数
    int len = end - beg + 1, res = 0;
    if(len <= 0){
        return 0;
    }
    else{
        for(int i = beg, j = end; i < beg + (end - beg + 1) / 2; ++i, --j){
            if(s[i] != s[j]){
                ++res;
            }
        }
        return res;
    }
}


class Solution {
public:
    int palindromePartition(string s, int k) {
        int dp[105][105];//dp[i][j]表示将长为j的字符串分成i段
        int len =  s.size();
        for(int i = 0; i <= 100; ++i){//初始化
            for(int j = 0; j <= 100; ++j){
                if(i  >=  j){
                    dp[i][j] = 0;
                }
                else{
                    dp[i][j] = MAX;
                }
            }
        }
        for(int i = 1; i <= k; ++i){//分段
            for(int j = i; j <= len; ++j){//j的长度
                for(int k = i - 1; k <= j; ++k){
                    dp[i][j] = min(dp[i][j], dp[i - 1][k] + cal(s, k, j - 1));
                }
            }
        }
        return dp[k][len];
    }
};