app软件下载站seo教程,wordpress实现专题,在线编辑图片加字,有没有专门的网站做品牌授权的目录
1 131. 分割回文串
2 51. N 皇后 菜鸟做题#xff0c;语言是 C#xff0c;感冒好了 ver. 1 131. 分割回文串
题眼#xff1a;给你一个字符串 s#xff0c;请你将 s 分割 成一些子串。
根据题眼可知#xff0c;我们需要做的是将字符串 s 连续分割 为几段#…目录
1 131. 分割回文串
2 51. N 皇后 菜鸟做题语言是 C感冒好了 ver. 1 131. 分割回文串
题眼给你一个字符串 s请你将 s 分割 成一些子串。
根据题眼可知我们需要做的是将字符串 s 连续分割 为几段并且 每段 都应该是回文串。而非对字符串 s 任意截取使得截取出的部分都是回文串。 值得注意的是单个字符也被算作回文串。 解题思路
设置变量 begin 作为子串的开头end begin 作为子串的结尾判断 begin 和 end 之间的内容即子串是否是回文串若是则将 begin 移至 end 后面然后递归处理第二个子串反之则 end继续判断 begin 和 end 之间的内容即子串是否是回文串 为什么将 begin 移至 end 后面因为 end 前面的字母是属于前一个子串的下一个子串只能接在前一个子串的后面。 递归返回条件字符串 s 被遍历完毕时
① 可能找出了一组符合题目要求的分割结果立即返回② 也可能找不到一组符合题目要求的分割结果不得不返回 返回到上一层函数后让 end 继续向后移动以寻找新的回文串即新的分割方式。若找到新的回文串则又递归进入下一层处理下一个子串。 思路说明图观看顺序是从左到右从上到下 第一层函数的功能是找出第一个回文串。由于 a 是回文串因此接着递归寻找第二个回文串。第二层函数的功能是找出第二个回文串。由于 a 是回文串因此也接着递归寻找第三个回文串。以此类推。当对整个字符数组处理完毕时递归层层返回。
重新回到第一层函数上次我们找的是 a那么这次 end 1判断 aa 是否是回文串。由于 aa 是回文串因此接着递归寻找第二个回文串。以此类推。 本题中的 “选择”是指从 “可能的回文串” 中选择。比如第一层函数能分割出的回文串不止一种它可以是 a 也可以是 aa因此 end 要不断后移以遍历所有可能的选择。 class Solution {
public:vectorvectorstring ans;vectorstring son;void helper(string s, int begin) {if (begin s.size()) {ans.push_back(son);return;}for (int end begin; end s.size(); end) {if (isPalindrome(s, begin, end)) {son.push_back(s.substr(begin , end - begin 1));helper(s, end 1);son.pop_back();}}}bool isPalindrome(string s, int p, int q) {while (p q) {if (s[p] ! s[q--])return false;}return true;}vectorvectorstring partition(string s) {helper(s, 0);return ans;}
};
说明判断当前分割出的字符串是否为回文串代码如下
bool isPalindrome(string s, int p, int q) {while (p q) {if (s[p] ! s[q--])return false;}return true;
} 其实就是从左往右和从右往左的字母要一样。 2 51. N 皇后
思路说明图 解题思路
模仿 46. 全排列将棋盘的每一行视为一个坑位将每一行的每个格子视为一种选择。
Q如何判断当前格子是否可以填入皇后
A根据 c、r - c 和 r c 来判断。 位于同一主对角线上的棋格的 r - c 相同位于同一副对角线上的棋格的 r c 相同。因此每填入一个皇后我们记录它的 c、r - c 和 r c以避免新皇后与其产生冲突。 class Solution {
public:unordered_setint cols, diag1, diag2;vectorstring output;vectorvectorstring ans;void helper(vectorstring output, int n, int r) {if (r n) {ans.push_back(output);return;}for (int c 0; c n; c) {if (cols.count(c) || diag1.count(r - c) || diag2.count(r c))continue;output[r][c] Q;cols.insert(c);diag1.insert(r - c);diag2.insert(r c);helper(output, n, r 1);output[r][c] .;cols.erase(c);diag1.erase(r - c);diag2.erase(r c);}}vectorvectorstring solveNQueens(int n) {for (int i 0; i n; i) {string s (n, .);output.push_back(s);}helper(output, n, 0);return ans;}
};
说明判断当前格子是否可以填入皇后的代码如下
if (cols.count(c) || diag1.count(r - c) || diag2.count(r c))continue; 使用三个集合 cols、diag1 和 diag2 分别记录 c、r - c 和 r c若当前棋格的位置信息与其中的值重复则跳过该棋格。
