当前位置: 首页 > news >正文

服务行业做网站舆情服务公司

服务行业做网站,舆情服务公司,杭州市做网站的公司,vs做的网站源代码Leetcode 51. N皇后 题目链接:51 N皇后 题干:按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n 皇后问题 研究的是如何将 n 个皇后放置在 nn 的棋盘上,并且使皇后彼此之间不能相互攻击。 给你一个整…

Leetcode 51. N皇后

题目链接:51 N皇后

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

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

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

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

思考:回溯法。先定义结果集result,再考虑回溯函数:

函数参数含义
参数含义
n题目给定皇后个数
chessboard当前棋盘摆放情况
row当前处理行数

 终止条件:如果当前处理行数row等于n时说明皇后已全部摆放完毕,将当前棋盘摆放情况chessboard存放到结果集result中。

单层搜索逻辑:从下标0开始循环处理每个二维坐标位置,若当前行row当前列col存放皇后合法则摆放皇后,递归处理,最后回溯。

验证row行col列摆放皇后合法性:参数当前行列值,当前棋盘以及皇后个数。三处标准判断合法性:不能同行(每次处理都是不同行故此标准不用验证)、不能同列、不能同斜线 (45度和135度角)。

  • 判断同列:当前row行前面的所以行对应的col列是否摆放过皇后
  • 判断45°线:当前row行col列45°斜方向是否摆放过皇后
  • 判断135°线:当前row行col列135°斜方向是否摆放过皇后

代码:

class Solution {
public:vector<vector<string>> result;//n : 皇后个数  chessboard : 当前棋盘摆放情况   row : 当前处理行数void backtracking(const int n, vector<string>& chessboard, int row) {if (row == n) {result.push_back(chessboard);return;}for (int col = 0; col < n; col++) {if (isValid(n, chessboard, row, col)) {chessboard[row][col] = 'Q';     //摆放皇后backtracking(n, chessboard, row + 1);chessboard[row][col] = '.';     //回溯}}}//判断row行col列摆放皇后是否合法bool isValid(const int n, vector<string>& chessboard, int row, int col) {//检查此行是否摆放过皇后for (int i = 0; i < row; i++)       if (chessboard[i][col] == 'Q')return false;//检查45°线是否摆放过皇后for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)      if (chessboard[i][j] == 'Q')return false;//检查135°线是否摆放过皇后for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++)if (chessboard[i][j] == 'Q')return false;return true;}vector<vector<string>> solveNQueens(int n) {result.clear();vector<string> chessboard(n, string(n, '.'));backtracking(n, chessboard, 0);return result;}
};

回溯法专题总结:

  •  熟悉回溯法代码整体框架。把回溯问题抽象为树形结构,其搜索的过程:for循环横向遍历,递归纵向遍历,回溯不断调整结果集。
  • 确定是否使用startIndex。对于组合问题,如果是一个集合来求组合的话,就需要startIndex;如果是多个集合取组合,各个集合之间相互不影响,那么就不用startIndex。
  • 熟悉同层去重两种方式。排序后相邻元素比较以及set容器记录使用情况。了解到节点去重,但未归纳。
  • 明确在树形结构中子集问题是要收集所有节点的结果,而组合问题是收集叶子节点的结果。
http://www.dinnco.com/news/5965.html

相关文章:

  • 珠海建站谷歌推广培训
  • 外汇网站怎么做优化google官方入口
  • 设计logo的软件推荐新乡seo网络推广费用
  • 淘宝客 网站建设seo 的原理和作用
  • 中山精品网站建设方案惠州短视频seo
  • 郑州pc网站开发企业qq怎么申请
  • 做b2b网站品牌推广公司
  • 高德地图实况街景怎么打开百度seo排名优化系统
  • 网站建设怎么购买域名江西seo推广
  • 可做市值曲线的网站天津百度推广中心
  • 一个人免费看的高清电影在线观看谈谈对seo的理解
  • 知名的网络推广无线网络优化
  • 谷城建设局网站广告宣传方式有哪些
  • 阿里巴巴做网站营销有没有用网络推广加盟
  • 移动互联网开发大作业东莞seo网络营销
  • 在演示文稿上网站怎么做惠州seo排名优化
  • 优化网站排名公司青岛谷歌推广
  • 手机端网站首页怎么做seo关键词优化平台
  • 千图网素材免费为什么seo工资不高
  • 制作网站可以赚钱吗太原关键词优化软件
  • 新闻类网站开发难点上海抖音seo
  • 建设项目环境影响登记网站湖北百度在线客服中心
  • 小企业想做网站推广找哪家强如何查询百度搜索关键词排名
  • 精品课程网站建设现状网站关键词优化系统
  • 广州哪家做网站价格好一呼百应推广平台
  • 电子商务网站建设规划书seo外贸网站制作
  • 谁知道苏州溪城水处理网站谁做的seo交流网
  • 做网站最好的语言厦门seo全网营销
  • 淘宝客网站必须备案吗网盘资源大全
  • 建的企业网站如何在百度搜到网站关键词排名快速提升