day27 力扣332.重新安排行程 力扣51. N皇后 力扣37. 解数独 力扣455.分发饼干 力扣376. 摆动序列 力扣53. 最大子序和

重新安排行程

给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。

所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。

• 例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。

假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。

示例 1：

输入：tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
输出：["JFK","MUC","LHR","SFO","SJC"]

示例 2：

输入：tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
输出：["JFK","ATL","JFK","SFO","ATL","SFO"]
解释：另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"] ，但是它字典排序更大更靠后。

提示：

• 1 <= tickets.length <= 300
• tickets[i].length == 2
• fromi.length == 3
• toi.length == 3
• fromi 和 toi 由大写英文字母组成
• fromi != toi

第二道困难题，呃呃··· 好难。

我们将他给的二重数组，放入我们自定义的unordered_map targets（无序）<string,<string,int>> 第一个string是出发地，第二个string是终止点，int是从这个出发点到终点的航班次数。

主函数中要先把JFK传入result里，才能进行。

回溯三部曲：

第一步：确定返回值和参数， 由于答案唯一，只要我们找到一条正确的路线就可以，所以返回值我们使用bool。参数的话，有ticketNum（航班次数）以及result（结果路线）。

第二步：确定终止条件，由于我们要的是条完整路线，那么我们的result的数量应该等于ticketNum+1。

第三步：单层循环的内容， for的条件，我们选用C++11的新写法，用一个pair<string,int>来承接每一个targets中新加入result的值。（如第一次循环时，就是JFK对应的终点和航班次数）循环内判断航班次数是否>0（如果等于0，就说明这种航班已经使用完了）如果大于0，就把终点加进result里，再将次数--，递归+回溯。

这里说两点我自己遇到的问题：

 bool backtracking(int ticketsNum,vector<string>& result)

 参数的result也要引用，不然你每次push_back的值都传入的复制后的result，得到的result只有一个最开始的“JFK”值。

for(pair<const string,int>& target:targets[result[result.size()-1]])

这里要引用，不然会复制出一份target，循环内操作都是对复制的target修改，而原值不改变。 

class Solution {
public:unordered_map<string,map<string,int>> targets;bool backtracking(int ticketsNum,vector<string>& result){if(result.size()==ticketsNum+1) return true;for(pair<const string,int>& target:targets[result[result.size()-1]]){if(target.second>0){target.second--;result.push_back(target.first);if(backtracking(ticketsNum,result)) return true;target.second++;result.pop_back();}}return false;}vector<string> findItinerary(vector<vector<string>>& tickets) {int ticketsNum = tickets.size();for(const vector<string>& ticket:tickets){targets[ticket[0]][ticket[1]]++;}vector<string> result;result.push_back("JFK");backtracking(ticketsNum,result);return result;}
};

但是但是但是，回溯算法被力扣卡死了，leetcode无法通过这种代码。 ······

---

N皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1：

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1
输出：[["Q"]]

提示：

• 1 <= n <= 9

本题主要想明白如何递归二维数组。对于这个棋盘，我们用vector<string>来储存，string是列，数组是行，初始化如下：

 vector<string> chessboard(n, string(n, '.'));

如何验证放入棋子是否合法，按照如下标准去重：

1. 不能同行
2. 不能同列
3. 不能同斜线 （45度和135度角）

我们得到以下代码

bool isValid(int row,int col,int n,vector<string>& chessboard){for(int i = 0;i<row;i++){if(chessboard[i][col]== 'Q')return false;}for(int i= row-1, j = col-1;i>=0 && j>=0;i--,j--){if(chessboard[i][j]=='Q')return false;}for(int i= row-1, j = col+1;i>=0 && j<n;i--,j++){if(chessboard[i][j]=='Q')return false;}return true;}

别的就很好理解了，这里给出完整代码：

class Solution {
public:vector<vector<string>> result;bool isValid(int row,int col,int n,vector<string>& chessboard){for(int i = 0;i<row;i++){if(chessboard[i][col]== 'Q')return false;}for(int i= row-1, j = col-1;i>=0 && j>=0;i--,j--){if(chessboard[i][j]=='Q')return false;}for(int i= row-1, j = col+1;i>=0 && j<n;i--,j++){if(chessboard[i][j]=='Q')return false;}return true;}void backtracking(int row,int n,vector<string>& chessboard){if(row == n){result.push_back(chessboard);return;}for(int i = 0;i<n;i++){if(isValid(row,i,n,chessboard)){chessboard[row][i] = 'Q';backtracking(row+1,n,chessboard);chessboard[row][i] = '.';}}}vector<vector<string>> solveNQueens(int n) {vector<string> chessboard(n, string(n, '.'));backtracking(0,n,chessboard);return result;}
};

---

解数独

这道题不需要终止条件，因为如果得到结果，就必须全部遍历一遍到最终点，所以如果有答案，board填满的时候即可。

还是三种判断插入字符是否合理的情况：

• 同行是否重复
• 同列是否重复
• 9宫格里是否重复

 bool isValid(int row,int col,char num,vector<vector<char>>& board){for(int i = 0;i<9;i++){if(board[i][col]==num)return false;}for(int i = 0;i<9;i++){if(board[row][i]==num)return false;}int pos_row = (row/3)*3;int pos_col = (col/3)*3;for(int i = pos_row ;i<pos_row+3;i++){for(int j = pos_col;j<pos_col+3;j++){if(board[i][j]==num)return false;}}return true;}

 注意，这里行列判断的时候不能只判断前面，因为棋盘本身就随机存在一些数，这些数可能在我们判断位置的行列的后面。

这道题用了三层循环嵌套，“”行 、列、字符数字”。

下面给出完整代码：

class Solution {
public:bool isValid(int row,int col,char num,vector<vector<char>>& board){for(int i = 0;i<9;i++){if(board[i][col]==num)return false;}for(int i = 0;i<9;i++){if(board[row][i]==num)return false;}int pos_row = (row/3)*3;int pos_col = (col/3)*3;for(int i = pos_row ;i<pos_row+3;i++){for(int j = pos_col;j<pos_col+3;j++){if(board[i][j]==num)return false;}}return true;}bool backtracking(vector<vector<char>>& board){for(int i = 0;i<9;i++){for(int j = 0;j<9;j++){if(board[i][j]!='.')continue;for(char k = '1';k<='9';k++){if(isValid(i,j,k,board)){board[i][j] = k;if(backtracking(board))return true;board[i][j] = '.';}}return false;}}return true;}void solveSudoku(vector<vector<char>>& board) {backtracking(board);}
};

---

分发饼干 

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是满足尽可能多的孩子，并输出这个最大数值。

 

示例 1:

输入: g = [1,2,3], s = [1,1]
输出: 1
解释: 
你有三个孩子和两块小饼干，3 个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是 1，你只能让胃口值是 1 的孩子满足。
所以你应该输出 1。

示例 2:

输入: g = [1,2], s = [1,2,3]
输出: 2
解释: 
你有两个孩子和三块小饼干，2 个孩子的胃口值分别是 1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出 2。

提示：

• 1 <= g.length <= 3 * 104
• 0 <= s.length <= 3 * 104
• 1 <= g[i], s[j] <= 231 - 1

注意：本题与 2410. 运动员和训练师的最大匹配数 题相同。

贪心算法的第一题，尽可能达到局部最优解，从而实现整体最优。

本题是让大饼干尽可能满足胃口更大的小朋友。

首先将俩个数组排序，然后判断s和g的最后一个值那个大，如果最大的饼干可以满足胃口最大的小朋友，就给他；如果不满足，就判断胃口第二大的小朋友···循环往复。

同时也有另一种思路：让较小的饼干去满足胃口小的小朋友，基本逻辑同理。

贪心算法重点看思路，无固定逻辑，很多想法未必非常合理，但不需要严格证明，只需自洽举不出反例，可以跑过测试点即可。

class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {int count = 0;int index = s.size()-1;sort(g.begin(),g.end());sort(s.begin(),s.end());for(int i = g.size()-1;i>=0;i--){if(index >= 0 &&s[index]>=g[i]){count++;index--;}}return count;}
};

---

摆动序列

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

• 例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。

• 相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。

给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。

示例 1：

输入：nums = [1,7,4,9,2,5]
输出：6
解释：整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。

示例 2：

输入：nums = [1,17,5,10,13,15,10,5,16,8]
输出：7
解释：这个序列包含几个长度为 7 摆动序列。
其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。

示例 3：

输入：nums = [1,2,3,4,5,6,7,8,9]
输出：2

因为他说可以自己删除一些元素，但其实删不删都一样

贪心所贪的地方，让峰值尽可能的保持峰值，然后删除单一坡度上的节点

本题要考虑三种情况：

1. 情况一：上下坡中有平坡
2. 情况二：数组首尾两端
3. 情况三：单调坡中有平坡

class Solution {
public:int wiggleMaxLength(vector<int>& nums){if(nums.size()<=1) return nums.size();  int result = 1;int preDiff= 0;int curDiff = 0;for(int i = 0;i<nums.size()-1;i++){curDiff = nums[i+1]-nums[i];if((curDiff>0&&preDiff<=0)||(curDiff<0&&preDiff>=0)){result++;preDiff = curDiff;}}return result;}
};

 

---

最大子序和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

提示：

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。 

全局最优：选取最大“连续和”

局部最优的情况下，并记录最大的“连续和”，可以推出全局最优

class Solution {
public:int maxSubArray(vector<int>& nums) {int result =INT_MIN;int count = 0;for(int i = 0;i<nums.size();i++){count+=nums[i];if(count > result){result =count;}if(count<0)count=0;} return result;}
};

 贪心的代码很简单，但思路不好想。

后俩题时间有些紧张，写的简单了些。