精选留言(9)

• 
  niubility

  2019-03-27

  照例发一下我的java代码吧.很low但是好歹独立解决的.
  public class Solution {
      /**
       * 皇后可以攻击竖着的横着的,左斜线,右斜线的对手.
       *
       * @param n
       * @return
       */
      public List<List<String>> solveNQueens(int n) {
          List<List<String>> result = new ArrayList<>();
          if (n == 0) return result;
          Set<Integer> pie = new HashSet<>();
          Set<Integer> na = new HashSet<>();
          dfs(0,n,pie,na,new HashSet<>(),result,new ArrayList<>());
          return result;
      }
  
      private void dfs(int level, int n, Set<Integer> pie, Set<Integer> na,Set<Integer> col,List<List<String>> results, List<String> tempList) {
          if (level > n - 1) {
              if (tempList.size() == n){
                  List<String> result = new ArrayList<>(tempList);
                  results.add(result);
              }
              return;
          }
  
          boolean exists = false;
          // 遍历列
          for (int j = 0; j < n; j++) {
              if (pie.contains(level + j) || na.contains(j - level) || col.contains(j)) {// 会被攻击的位置!
                  continue;
              }
  
              exists = true;
  
              pie.add(level + j);
              na.add(j - level);
              col.add(j);
  
              String temp = getStr(n,j);
  
              tempList.add(temp);
  
              dfs(level + 1,n,pie,na,col,results,tempList);
  
              pie.remove(level + j);
              na.remove(j - level);
              col.remove(j);
              tempList.remove(temp);
          }
          if (!exists){
              return;
          }
      }
  
      private String getStr(int n, int j) {
          StringBuilder stringBuilder = new StringBuilder();
          for (int i = 0; i < n; i++) {
              if (i == j){
                  stringBuilder.append("Q");
              }else
                  stringBuilder.append(".");
          }
          return stringBuilder.toString();
      }
  
      public static void main(String[] args){
          Solution solution = new Solution();
  
          System.out.println(solution.solveNQueens(5));
      }
  }
  

  展开

  作者回复: 看起来不错！！

  

   3
• 
  Chaos👾

  2018-12-24

  想问下老师cur_state在这里有什么用

   1

   2
• 
  Aliliin

  2019-11-13

  PHP 实现：
  
  class Solution
  {
  
      /**
       * @param Integer $n
       * @return String[][]
       */
      /**
       * @var array 结果值
       */
      public $res = [];
      /**
       * @var array 列值
       */
      public $cols = [];
      /**
       * @var array 撇值
       */
      public $pie = [];
      /**
       * @var array 纳值
       */
      public $na = [];
  
      /**
       * @param $n
       * @return array
       */
      function solveNQueens($n)
      {
          if ($n < 1) return [];
          $this->queens($n, 0, []);
          return $this->_generate_result($n);
      }
  
      /**
       * @param $n 数量
       * @param $i 坐标
       * @param $curState 结果值
       */
      function queens($n, $i, $curState)
      {
          if ($i == $n) {
              array_push($this->res, $curState);
              return;
          }
          for ($j = 0; $j < $n; $j++) {
              if (in_array($j, $this->cols)
                  || in_array($i + $j, $this->pie)
                  || in_array($i - $j + $n, $this->na)) {
                  continue;
              }
              array_push($this->cols, $j);
              array_push($this->pie, $i + $j);
              array_push($this->na, $i - $j + $n);
              $curState[$i] = $j;
              $this->queens($n, $i + 1, $curState);
              array_pop($this->cols);
              array_pop($this->pie);
              array_pop($this->na);
          }
      }
  
      /**
       * 拼接结果值
       * @param $n 循环的次数
       * @return array
       */
      function _generate_result($n)
      {
          $ret = [];
          if (!empty($this->res)) {
              foreach ($this->res as $v) {
                  for ($i = 0; $i < $n; $i++) {
                      $str = '';
                      foreach ($v as $val) {
                          if ($val == $i) {
                              $str .= 'Q';
                          } else {
                              $str .= '.';
                          }
                      }
                      array_push($ret, $str);
                  }
              }
          }
          return array_chunk($ret, $n);
      }
  }

  展开

  作者回复: Nice code !

  

   1
• 
  不记年

  2018-11-17

  我觉得虽然网上的那个解法看上去很简洁，但实际开销比作者的更大，一是函数内定义了函数，而是，每次递归调用时都重新生成了数组，这些内部的开销对python 开讲都不小。emmm如果实际用的话我更推荐老师的

  

   1
• 
  白了少年头

  2018-11-12

  老师，N皇后的第二题，有跟第一种问题不一样的快速的算法吗？

  

   1
• 
  AF

  2019-06-23

  老师，这个空间复杂度会不会太高了，一下子申请了四个数据结构？

  

  
• 
  这得从我捡到一个鼠标...

  2019-06-16

  为了简洁而简洁的代码，可读性不好

  

  
• 
  战五渣

  2019-05-30

  感觉体会递归，回溯代码就像练功一样，灵光一闪就打通了，就发现不难了，但这个只能自己体会，光靠看和听不够，得写得分析。贴个c#版本的代码，写得不算好，希望得到指点，谢谢啦
  public class Solution {
      List<IList<string>> returnLt = new List<IList<string>>();
      HashSet<int> _lie = new HashSet<int>();
      HashSet<int> _pie = new HashSet<int>();
      HashSet<int> _na = new HashSet<int>();
      Dictionary<int, int> _state = new Dictionary<int, int>();
      
      public IList<IList<string>> SolveNQueens(int n) {
          Gen(0, n);
          return returnLt;
      }
      
      void Gen(int row, int n){
          if (row == n){
              Append(n);
              return;
          }
          
          for (int i = 0; i < n; i++){
              // check
              if(_lie.Contains(i) || _pie.Contains(row + i) || _na.Contains(row - i))
                  continue;
              
              //store state
              _lie.Add(i);
              _pie.Add(row + i);
              _na.Add(row - i);
              _state.Add(row, i);
      
              Gen(row + 1, n);
                  
              //reset state
              _lie.Remove(i);
              _pie.Remove(row + i);
              _na.Remove(row - i);
              _state.Remove(row);
          }
      }
      
      void Append(int n){
          if (_state.Count < n)
              return;
          
          List<string> lt = new List<string>();
          for (int i = 0; i < n; i++){
              int queenIndex = _state[i];
              string str = "";
              for (int j = 0; j < n; j++){
                  str += j == queenIndex ? "Q": ".";
              }
              lt.Add(str);
          }
          returnLt.Add(lt);
      }
  }

  展开

  

  
• 
  zhulogic

  2019-02-18

  是否可以根据结论来写呢？针对这个特殊的棋盘来说:将棋盘围绕中心点依次旋转90°就是可以放皇后的位置。

  

  