数据结构思想与算法（二）-171主机测评

数据结构思想与算法（二）.1

资料来源：LeetCode BiliBili LeetCode每日一题洛谷

哈希表的应用

哈希表本质上并非一种基本数据结构，而是利用现有数据结构来创建一个映射关系，我们常用数组来创建映射关系，有效的数独是哈希表具体应用的一个例题

class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
bool ex[9];
for(int i = 0;i<9;i++)
{
memset(ex,0,sizeof(ex));
for(int j = 0;j < 9;j++)
{
if(board[i][j] == '.')continue;
int t = board[i][j] – '1';
if(ex[t])return false;
ex[t] = true;
}
}
for(int i = 0;i < 9;i++)
{
memset(ex,0,sizeof(ex));
for(int j = 0;j < 9;j++)
{
if(board[j][i] == '.')continue;
int t = board[j][i] – '1';
if(ex[t])return false;
ex[t] = true;
}
}
for(int i = 0;i<9;i+=3)
{
for(int j = 0;j<9;j+=3)
{
memset(ex,0,sizeof(ex));
for(int x = 0;x<3;x++)
{
for(int y = 0;y<3;y++)
{
if(board[i+y][j+x] == '.')continue;
int t = board[i+y][j+x] – '1';
if(ex[t])return false;
ex[t] = true;
}
}
}
}
return true;
}
};

哈希表通常用key->value这样的键值对来表示映射关系，这里我们复用ex数组(bool类型)来构建该数组索引(key)与是否被找寻过(value)的映射

这里说的是程序显露的映射，如果我说程序悄悄还隐藏了一个映射，不知道大家会不会关注到，没错，他就是字符与数组索引之间的映射，数字字符通过ASCII码的计算可以映射到数组索引，数组索引再映射曾经是否被映射，如果是就返回false，证明在这一层循环中(某一行、某一列、或某一个九宫格)，数字重复了，否则就会继续遍历下一个情况，映射情况的value设计的也很巧妙，它像专门为某一元素打造的身份证，一旦第那个数字元素进来，就会把其他的元素拒之门外，这里是用判断实现的，我们开始把ex[t]都设为false，直到有一个数字字符指向了那个位置，我们就把那个数组的值设为true，而一旦为true了，其他相同的元素就不能改变这个ex[t]的值了，反而会因为出现两个一样的元素而抛出异常，这里指return false

Question：为什么元素为‘.’的时候直接continue

这是因为在隐藏的数字字符映射数组索引关系中，并没有’.‘的映射，它并不属于数字字符，不需要进入下一个映射的判断，因为数独中是允许多个.出现的，所以它的存在对整个判断并没有什么影响，而相反，如果它强行进入数组索引与是否已映射的判断，反而会出现问题，首先我们基于ASCII码的差值来确定数字字符与数组索引的映射关系，所以bool ex[9]在一开始就定死了只能是那9个数字字符的映射，如果让’.‘来映射的话，很可能会出现数组访问越界的情况，假设我绕过这层逻辑，他指向了某个数组索引，那我下次有一个第一次出现的元素来访问该索引时就会出现已经访问过的情况，实际上是’.'错误地占据了它的位置，这属于误判，在逻辑上是错误的

递归的应用

我认为递归可以分为两个状态，一个是回溯(即递归返回到上一层之前我应该做什么)，一个我称之为任务(即进入到下一层之前我应该做什么)

外观数列是一个典型的在回溯层面做主要逻辑的递归应用

class Solution {
public:
string countAndSay(int n) {
string combine = "";
return outlist(n,combine);
}

string outlist(int n,string& combine)
{
if(n == 1)
{
combine = "1";
return "1";
}
outlist(n-1,combine);
int length = 1;
string temp = "";
for(int i = 0;i<combine.size();i++)
{
if(combine[i] == combine[i+1] && i+1 < combine.size())
length++;
else
{
temp.push_back(length + '0');
temp.push_back(combine[i]);
length = 1;
}
}
combine = temp;
return temp;
}
};

外观数列的本层行程长度编码依赖于下一层的行程长度编码，分层解决问题，每一层的解决逻辑一样（即返回上一层的行程长度编码）这决定我们考虑使用递归解决问题，下一层处理的结果就会影响到上一层，这属于逆序的解决方式，所以我们考虑递归的回溯来解决问题

我们在递归到最后一层的时候，返回字符串1，这时开始回溯，通过length变量记录相同字符的长度，当遇到不同字符的时候记录结果，同时重置length变量，最后返回记录的字符串结果，这就可以在上一层执行回溯的时候，把这一层改变的字符串又作为遍历数组，再进行记录回溯，以此往复，直到第一次调用递归时就可以退出了，这样返回的结果就是上一层的遍历结果，符合题目表达的逻辑。

DFS剪枝的再应用

组合总和

为了方便定位，接下来的题目我都会附带位置和图片

39. 组合总和 – 力扣（LeetCode）

在这里插入图片描述

DFS的关键在于，我先往深递归，找到尽可能多符合条件的选项，如果没有的话再在同级迭代，遍历其他所有的可能，对于所有元素之和==target的数组子集，我们可以从当前元素寻找，尽可能地找多的满足条件的元素（递归），如果下一个不满足的话，在迭代到下一个继续查找，递归决定深度，表示我可以找到的极限情况，迭代决定广度，决定我能找到多少个符合条件的数组，两者结合，就可以实现dfs的剪枝，因为满足递归返回条件的，不会再继续递归，所以减少了很多不必要的计算，迭代，又可以是我们在不满足返回条件的情况下继续寻找更多符合条件的数组，所以，它就转换成了对于每一层，这里对应固定的元素个数的情况下，我一共有多少个解，然后我加起来就是完全的解的个数

接下来，我们看看递归怎么实现

class Solution {
vector<vector<int>> Sums;
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<int> combine;
int ans = 0,index = 0;
dfs(candidates,combine,ans,index,target);
return Sums;
}
void dfs(vector<int>& candidates,vector<int> combine,int& ans,int& index,int target)
{
if(ans > target)
return;
if(ans == target)
{
Sums.push_back(combine);
return;
}
for(int i = index;i < candidates.size();i++)
{
ans = ans + candidates[i];
combine.push_back(candidates[i]);
dfs(candidates,combine,ans,i,target);
combine.pop_back();
ans = ans – candidates[i];
}
return;
}
};

因为自身这个数字也可以选择，所以我在使用for循环迭代的时候还是从自身开始，等不满足条件的时候，再在同层找下一个满足条件的数

小知识点：引用传递和拷贝传递(非引用)

在整个递归范围，对于引用传递的变量，不开辟新的内存空间，所有使用的变量，都是引用你上一次递归的那个变量，也就是第一次递归的那个变量，这样可以节省内存空间，但缺点是你需要自己维护，比如这里的ans在递归之前需要加上当前的数组索引值，在递归之后需要还原（减去当前的数组索引值），不然就会出现回溯的后续递归收到前面递归的影响，导致当前的ans值混乱，对于拷贝传递来说，可以避免ans的这个问题，因为对于每一层，它都会开辟一个额外的空间，只需要传ans + candidates[i]进去，就可以了，这样下一层的ans就会是当前元素值得总和，且当前层的ans层不会发生改变，但不是每一个都适用，就比如combie.push_back(candidates[i])后面还是要pop的，因为当前值已经改变了，所以说，要不要还原，具体还是看问题要求以及当前层有没有发生改变，对于一些变量来说，不用维护是它的优点，但缺点是需要开辟新的内存空间，增大了空间复杂度

组合总和二

在这里插入图片描述

这个题目和组合总和一的原理是一样的，依然用的是dfs剪枝的方法，不过在细节实现上，它们是有差异的，首先，它要求解集中不能包含重复的组合

我们首先需要知道这里的重复是什么意思，对于整个数组来说，它是可以包含重复的元素的，就比如[1,1,6]和[1,2,5]，这是一个target为8的所有子集当中的两个，我们可以看到[1,1,6]其中是包含了两个1的，这是属于两个不同的深度，所以判断重复的逻辑，不是在递归，那么，在迭代？我们再思考，如果对于第二重迭代来说，如果后面也有1，它必然是会重复的，因为对于第三个递归深度6来说，它都可以push进去，那么这里一定会重复，所以我们排序之后（确保相同元素排序在一起），对每一次迭代进行判重处理，如果重复，就continue这次循环，同时在这次的递归我们必须把index+1传进去，因为它要求candidates中的每个数字只能使用一次，由此，我们在组合总和1的代码上稍作修改

class Solution {
vector<vector<int>> Sums;
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<int> combine;
int ans = 0,index = 0;
sort(candidates.begin(),candidates.end());
dfs(candidates,combine,ans,index,target);
return Sums;
}
void dfs(vector<int>& candidates,vector<int> combine,int& ans,int index,int target)
{
if(ans > target)
return;
if(ans == target)
{
Sums.push_back(combine);
return;
}
for(int i = index;i < candidates.size();i++)
{
if(i > index && candidates[i] == candidates[i-1])
continue;
ans = ans + candidates[i];
combine.push_back(candidates[i]);
dfs(candidates,combine,ans,i + 1,target);
combine.pop_back();
ans = ans – candidates[i];
}
return;
}
};

字符串相乘

43. 字符串相乘 – 力扣（LeetCode）

在处理字符串相乘这类问题的时候，我们需要知道，字符串相乘所能转化的最大数值是多少，对于两个字符串来说，他们相乘的最大长度应该是num1.size() + num2.size()，所以我们开辟一个num1.size() + num2.size()的空间，用来存储字符串相乘的值，我们把当前位赋值为结果相乘加上进位，并将计算的十位设置为进位，因为每一次，是一个数与一个数相乘，所以最多只有一个十位。计算后的结果就是字符串相乘的结果

class Solution {
public:
string multiply(string num1, string num2) {
vector<int> strtoint(num1.size() + num2.size(),0);
string str = "";
if(num1 == "0" || num2 == "0")return "0";
for(int i = num1.size() – 1;i >= 0;i–)
{
for(int j = num2.size() – 1;j >= 0;j–)
{
int value = (((num1[i] – '0') * (num2[j] – '0')) + strtoint[i+j+1])%10;
int ans = (((num1[i] – '0') * (num2[j] – '0')) + strtoint[i+j+1])/10;
strtoint[i+j+1] = value;
strtoint[i+j] += ans;
}
}
int start = 0;
while(strtoint[start] == 0)start++;
for(int i = start;i < strtoint.size();i++)
{
str += (strtoint[i] + '0');
}
return str;
}
};

我们注意到在处理进位的时候用的是+=，在处理当前位的时候就直接加上当前位。因为当前位的处理逻辑就包含了上一次进位的相加，所以不用+=，而下一次进位的+=，主要是因为这里的进位不单单只是两个数相乘产生的进位，还有可能是上一轮乘完所保存在当前空间的数，这些数在逻辑上应该是相加取余

贪心算法的应用——跳跃游戏II

45. 跳跃游戏 II – 力扣（LeetCode）

在这里插入图片描述

对于一个明确能够到达n-1的数组，要求它跳跃的最短路径，我们可以用贪心算法来求解

我们每次规定在当前范围内所能到达的跳跃到下一次的最大范围，当跳出当前范围时，我们继续寻找下一个最大范围，对于整个数组来说，它只需要做一次遍历，所以时间复杂度是O(n),同时它不需要开辟额外的数组空间，所以空间复杂度是O(1),在整个遍历的过程当中，我们需要做两件事情

在到达当前的最远点之前，我们需要寻找当前范围内所能跳跃到的下一次的最大范围

在到达最远点的时候，记录步数，并将end点设置在当前范围找到的下一个范围的最远点

class Solution {
public:
int jump(vector<int>& nums) {
int end = 0;int maxpos = 0;int ans = 0;
for(int i = 0;i< nums.size() – 1;i++)
{
maxpos = max(maxpos,nums[i] + i);
if(end == i)
{
ans++;
end = maxpos;
}
}
return ans;
}
};

Question：为什么遍历到最后一个元素的前一个就不遍历了

因为前一个的结果就已经能够代表整个最短路径了，终点反而不能代表我的最短路径

如果你仔细观察的话，就可以发现，我们是先加上步数，再开始进行跳跃的，这就意味我即使待在end点没有动，我的步数也+1了，也就是说，这是一个将来态，如果我遍历到最后一个元素会发生什么，其实对于最后一个元素而言，它是不是end已经不重要了，因为到这里就已经截止了，不需要再往后跳跃，如果这里是end的话，反而会导致程序误判，以为我还要跳跃。事实上，如果是将来态的话，对于最后一个元素的前一个元素是比较重要的，因为逻辑上是说的通的，如果我的end正好在最后一个元素的前一个，那我确实还将跳一步才能到达终点，如果不是的话，就说明end >= nums.size() – 1,那么这样的话就说明当前范围内可以直接到达终点，不需要再额外跳跃了

class Solution {
vector<int> results;
public:
vector<int> findSubstring(string s, vector<string>& words) {
int l = s.length();int m = words.size();int w = words[0].length();
unordered_map<string,int> word;
for(int i = 0;i < m;i++)
word[words[i]]++;
for(int i = 0;i < w;i++)
{
unordered_map<string,int> temp;
int cnt = 0;
for(int j = i;j+w <= l;j += w)
{
if(j – i >= m * w)
{
string s1 = s.substr(j – m * w,w);
temp[s1]–;
if(temp[s1] < word[s1])cnt–; //word[s1]中没有该字符串时，不满足该条件
}
string ss = s.substr(j,w);
temp[ss]++;
if(temp[ss] <= word[ss])cnt++; //word[s1]中有该字符串时，满足该条件
if(cnt == m)results.push_back(j – (m – 1)*w);
}
}
return results;
}
};

递归的应用——回溯算法

数组去重排列

回溯算法实质上是dfs遍历+剪枝优化的结果，它实现了在回溯的过程中，对已标记过的元素不会再次递归，从而实现剪枝的效果

在全排列这道题目中，我们对已经加入combine数组中的元素进行剪枝，避免对已经用过元素的重复使用

除此之外，我们还可以在算法里面加入权重的思维，当然，他并不是权重计算相关的算法，只是我们可以将出现的相同字符看成是严格按照权重排序的字符，也就是说先出现的权重最高，进行全排列时，必须按照从高到低的权重排列，比如对于这样一个数组

[

]

{[1,1,2]}

$[1, 1, 2]$ 如果按照简单的回溯算法去重的话，肯定会遇到这样的问题

#mermaid-svg-diB1jsSb4MuQFAdA{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-diB1jsSb4MuQFAdA .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-diB1jsSb4MuQFAdA .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-diB1jsSb4MuQFAdA .error-icon{fill:#552222;}#mermaid-svg-diB1jsSb4MuQFAdA .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-diB1jsSb4MuQFAdA .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-diB1jsSb4MuQFAdA .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-diB1jsSb4MuQFAdA .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-diB1jsSb4MuQFAdA .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-diB1jsSb4MuQFAdA .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-diB1jsSb4MuQFAdA .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-diB1jsSb4MuQFAdA .marker{fill:#333333;stroke:#333333;}#mermaid-svg-diB1jsSb4MuQFAdA .marker.cross{stroke:#333333;}#mermaid-svg-diB1jsSb4MuQFAdA svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-diB1jsSb4MuQFAdA p{margin:0;}#mermaid-svg-diB1jsSb4MuQFAdA .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-diB1jsSb4MuQFAdA .cluster-label text{fill:#333;}#mermaid-svg-diB1jsSb4MuQFAdA .cluster-label span{color:#333;}#mermaid-svg-diB1jsSb4MuQFAdA .cluster-label span p{background-color:transparent;}#mermaid-svg-diB1jsSb4MuQFAdA .label text,#mermaid-svg-diB1jsSb4MuQFAdA span{fill:#333;color:#333;}#mermaid-svg-diB1jsSb4MuQFAdA .node rect,#mermaid-svg-diB1jsSb4MuQFAdA .node circle,#mermaid-svg-diB1jsSb4MuQFAdA .node ellipse,#mermaid-svg-diB1jsSb4MuQFAdA .node polygon,#mermaid-svg-diB1jsSb4MuQFAdA .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-diB1jsSb4MuQFAdA .rough-node .label text,#mermaid-svg-diB1jsSb4MuQFAdA .node .label text,#mermaid-svg-diB1jsSb4MuQFAdA .image-shape .label,#mermaid-svg-diB1jsSb4MuQFAdA .icon-shape .label{text-anchor:middle;}#mermaid-svg-diB1jsSb4MuQFAdA .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-diB1jsSb4MuQFAdA .rough-node .label,#mermaid-svg-diB1jsSb4MuQFAdA .node .label,#mermaid-svg-diB1jsSb4MuQFAdA .image-shape .label,#mermaid-svg-diB1jsSb4MuQFAdA .icon-shape .label{text-align:center;}#mermaid-svg-diB1jsSb4MuQFAdA .node.clickable{cursor:pointer;}#mermaid-svg-diB1jsSb4MuQFAdA .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-diB1jsSb4MuQFAdA .arrowheadPath{fill:#333333;}#mermaid-svg-diB1jsSb4MuQFAdA .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-diB1jsSb4MuQFAdA .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-diB1jsSb4MuQFAdA .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-diB1jsSb4MuQFAdA .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-diB1jsSb4MuQFAdA .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-diB1jsSb4MuQFAdA .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-diB1jsSb4MuQFAdA .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-diB1jsSb4MuQFAdA .cluster text{fill:#333;}#mermaid-svg-diB1jsSb4MuQFAdA .cluster span{color:#333;}#mermaid-svg-diB1jsSb4MuQFAdA div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-diB1jsSb4MuQFAdA .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-diB1jsSb4MuQFAdA rect.text{fill:none;stroke-width:0;}#mermaid-svg-diB1jsSb4MuQFAdA .icon-shape,#mermaid-svg-diB1jsSb4MuQFAdA .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-diB1jsSb4MuQFAdA .icon-shape p,#mermaid-svg-diB1jsSb4MuQFAdA .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-diB1jsSb4MuQFAdA .icon-shape rect,#mermaid-svg-diB1jsSb4MuQFAdA .image-shape rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-diB1jsSb4MuQFAdA .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-diB1jsSb4MuQFAdA .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-diB1jsSb4MuQFAdA :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

DFS

112

121

112

121

211

我们会发现这样的会出现多个112，211，121，实际上，如果对于同一个数，它会产生

{2!}

$2!$ 个，因为如果把这几个1看成不一样的话，对于同一个数，它会有2!种排列组合,那怎么让它只有一个呢，聪明的你一定想到了只要我遵循一种排列方式不就只有一个了嘛，好吧，那么我就遵循权重大的放在后面，权重小的放在前面吧，就比如对于11，我们就假设它有权重

{1_11_2}

$1_{1} 1_{2}$ ,这种排列是可以的，但是

{1_21_1}

$1_{2} 1_{1}$ 这种排列就不行了，因为它不符合权重小的在前面，权重大的在后面，那么这样子的话，即使我有1111111，它也只能按照1234567排列。事实上，我们无论按照哪一种排列，1234567也好，7654321也好，都是可以的，只要保证它的排列方式唯一就可以了，从小到大是最直观的，也是最容易实现的，我们只需要保证当前重复数字的权重大于被使用的，也就是说，如果前面的数字没有使用，就不能使用这个数字，这就保证了唯一排列，接下来我们看看代码怎么实现

class Solution {
vector<vector<int>> results;
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<bool> used(nums.size());
sort(nums.begin(),nums.end());
vector<int> combine;
dfs(nums,used,combine);
return results;
}

void dfs(vector<int>& nums,vector<bool>& used,vector<int>& combine)
{
if(nums.size() == combine.size())
{
results.push_back(combine);
return;
}
for(int i = 0;i < nums.size();i++)
{
if(i && nums[i] == nums[i-1] && !used[i-1])continue;
if(used[i])continue;
used[i] = true;
combine.push_back(nums[i]);
dfs(nums,used,combine);
used[i] = false;
combine.pop_back();
}
}
};

我们维护了一个记录使用元素的数组，它有两个作用，第一个是普通回溯，也就是判断我当前的元素有没有被使用，第二个作用就是判断在前面的元素与当前相同的时候，前面的元素有没有被使用，这样就可以保证唯一性，同时进行剪枝优化

N皇后问题

51. N 皇后 – 力扣（LeetCode）

N皇后问题，也是一道经典的回溯算法问题，不同的是，它将数学问题与回溯相结合

我们首先对这个问题进行数学建模，如果要保证皇后不能攻击同一行、列以及斜线，我们就可以定义棋盘上这些位置的标记数组，行列都是比较容易定义的，对于n行或者n列我们只需要定义row[n]或者col[n],重要的是斜线，这里的斜线包括对角线，反对角线，那么我们该如何知道N皇后是不是处于同一条对角线呢或者反对角线呢？

我们可以将整个棋盘的左部分和下部分为基准建立一个直角坐标系，通过绘制函数可以知道，整个棋盘的对角线和反对角线共有2*n – 1条，且函数表达式为

对角线：y = -x + b\\\\反对角线:y = x+b

处于同一条对角线的b应该是相同的，所以我们可以定义反对角线和对象线的标记数组的大小为2*n-1，那么对角线一样的点在一条y+x函数上面，所以b是相同的，所以对角线的判重可以是deg[y+x],那么反对角线的判重也是udeg[y+x]吗？其实不然，我们注意到反对角线的b有小于0的部分，而数组不存在小于零的索引，所以我们要将反对角线进行转化，我们要让它再+(n – 1)，这样才能保证数组索引永远>=0

以下是具体代码实现

class Solution {
vector<vector<string>> ans;
vector<string> result;
vector<bool>row,deg,udeg;
public:
vector<vector<string>> solveNQueens(int n) {
result = vector<string>(n,string(n,'.'));
row = vector<bool>(n);
deg = udeg = vector<bool>(2*n – 1);
dfs(0,n);
return ans;
}
void dfs(int x,int n)
{
if(x == n)
{
ans.push_back(result);
return;
}
for(int y = 0;y < n;y++)
{
if(row[y] || deg[y + x] || udeg[y – x + (n – 1)])continue;
row[y] = deg[y + x ] = udeg[y – x + (n – 1)] = true;
result[y][x] = 'Q';
dfs(x+1,n);
result[y][x] = '.';
row[y] = deg[y + x] = udeg[y – x + (n – 1)] = false;
}
}
};

public: vector<vector> dp; vector<pair<int,int>> goods;

int manyBag(int K,int V,int N)
{
goods = vector<pair<int,int>>(N);
for(int i = 0;i< N;i++)
{
cin >> goods[i].first >> goods[i].second;
}
dp = vector<vector<int>>(V + 1,(vector<int>(K,INF)));
dp[0][0] = 0;
for(auto& good : goods)
{
int w = good.first;
int v = good.second;
for(int j = V;j >= w;j–)
{
int idx1 = 0;int idx2 = 0;
vector<int> temp;
while(temp.size() < K)
{
int val1 = (idx1 < K) ? dp[j][idx1] : INF;
int val2 = INF;
if(idx2 < K && dp[j – w][idx2] != INF)
val2 = dp[j-w][idx2] + v;
if(val1 > val2)
{
if(val1 != INF)temp.push_back(val1);
idx1++;
}else
{
if(val2 != INF)temp.push_back(val2);
idx2++;
}
if(val1 == INF && val2 == INF)
break;
cout << "\\t" << "val1:" << val1 << " val2:" << val2 << endl;
}
while(temp.size() < K)temp.push_back(INF);
cout << "contain is " << j << ":";
for(int i : temp)cout << i << " ";
cout << endl;
dp[j] = temp;
}
cout << endl;

}
int ans = 0;
for(int a : dp[V])
{
if(a != INF)
ans += a;
}
return ans;
}

};

int main() { int K,V,N; cin >> K >> V >> N; Solution sol; cout << sol.manyBag(K,V,N); }

这里将不放和放两种情况分开了，并用两个指针(idx1 和 idx2)专门处理，由于dp\\[i][j]设计为在总容量为i的情况下，第j中最大解，所以idx1和idx2从0遍历，就是在寻找最优解和次优解的过程，而且会对idx、idx2指向的val1、val2进行比较。所以保证每次都是最优解

当然，我这么讲太笼统了，接下来，我们分析整个代码，看看多人背包的流程到底是什么样子的，我们从mybag这个函数开始讲解

从遍历物品到处理固定容量下的最优解，总共可以分为三次循环，对应三个专门的处理过程

1. 最外层循环：处理整个物品，它对于内层循环的意义就是所有有效背包容量的情况下，该物品的放置情况
2. 第二层循环：遍历处理每一个有效背包容量的情况
3. 第三层循环：具体处理流程，通过idx1和idx2这两个指针的轮替来处理固定容量下的第k最优解

最后我们将背包容量固定（装满背包）的情况下，所有的k的最优解（多个背包）进行相加，就可以得到多个背包下的每个背包固定容量的最优解

我们保证只有当val的值不是INF的时候，才存入temp，这主要是为了避免错误的最优值存入，我们可以发现这种情况，如果val1和val2都是最小值，那么val2可能会被错误地存入temp数组当中，事实上，这并不是最优解

### Question1：为什么要使用逆序遍历

因为正序遍历可能会处理到重复的情况

~~~c++
//当j=2时
val = dp[2][0] //可能会遇到这样一种情况，val1 || val2
//当j=4时
val = dp[4-2][0] + v //可能会遇到这种情况，val1 || val2

那么对于同一个temp来说，他可能同时拿取两件（dp[2][0]），因为dp[2][0]在之前已经处理过了（可能已经加了一个v），所以对于同一个背包来说，它装了两件一样的物品，这是不符合题意的

逆序不会出现这样一种情况,因为在逆序的过程当中，它本身不会把同一个物品放入背包当中，因为当处理同一个物品的时候，前一个物品是没有处理的，也就是说，它不可能+v，因为还没有遍历到那里来

Question2：为什么val1 和 val2同为INF的时候break

因为对于val1和val2来说，当它同时为INF的时候，就说明对于该容量来说此时已经没有最优解，不需要再去寻找下面的k-（已经搜索过的解）

Question3：为什么当temp.size() < k的时候需要循环填充

这是为了保证每种容量都有k种解，这样可以使得在添加其他物品的情况下也能访问到固定容量的k次解，从而保证程序的健壮性，事实上，当我去掉这行代码的时候，也能解答出正确结果，我不确定这是否为个例，不过加上这行代码更保险一点

数据结构思想与算法（二）