51. N 皇后

class Solution { List<List<String>> res = new ArrayList<>(); public List<List<String>> solveNQueens(int n) { if (n<=0) return res; char[][] board = new char[n][n]; for (char[] chars : board) Arrays.fill(chars,'.'); backtrack(board,0); return res; } public void backtrack(char[][] board,int row){ if(board.length==row){ res.add(charToStr(board)); return; } int n = board[row].length; for(int col = 0;col < n;col++){ if(!isValid(board,row,col)) continue; board[row][col] = 'Q'; backtrack(board,row+1); board[row][col] = '.'; } } public List<String> charToStr(char[][] board){ List<String> result = new ArrayList<>(); for (char[] c : board){ result.add(String.valueOf(c)); } return result; } public boolean isValid(char[][] board,int row,int col){ int rows= board.length; for (char[] c : board){ if (c[col]=='Q'){ return false; } } // 左上角 for (int i = row-1,j = col-1;i >=0 && j >= 0;i--,j--){ if (board[i][j]=='Q') return false; } // 右上角 for (int i = row-1,j = col+1;i >=0 && j < rows;i--,j++){ if (board[i][j]=='Q') return false; } return true; } }

剑指 Offer 20. 表示数值的字符串

class Solution { public boolean isNumber(String s) { if (s.length()==0 || s == null){ return false; } s = s.trim(); boolean numFlag = false; boolean dotFlag = false; boolean eFlag = false; for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); // 判断为数字 numFlag 标记为true if (c >= '0' && c <= '9'){ numFlag = true; // 判断为 . 时，之前需要没有出现过 . 和 e }else if (c=='.' && !dotFlag && !eFlag){ dotFlag = true; // 判断为e时，之前需要出现过数字，但是没有出现过e }else if ((c=='e' || c=='E') && numFlag && !eFlag){ eFlag = true; numFlag = false; }else if ((c=='+' || c=='-') && (i==0 || s.charAt(i-1)=='e' || s.charAt(i-1)=='E')){ }else { return false; } } return numFlag; } }

剑指 Offer 41. 数据流中的中位数

class MedianFinder { PriorityQueue<Integer> left; PriorityQueue<Integer> right; /** initialize your data structure here. */ public MedianFinder() { left = new PriorityQueue<>((n1,n2)->n2-n1); right = new PriorityQueue<>(); } public void addNum(int num) { left.add(num); right.add(left.poll()); if(left.size()+1 < right.size()){ left.add(right.poll()); } } public double findMedian() { if(right.size()>left.size())return right.peek(); return (left.peek()+right.peek())/2.0; } } class MedianFinder { Queue<Integer> A, B; public MedianFinder() { A = new PriorityQueue<>(); // 小顶堆，保存较大的一半 B = new PriorityQueue<>((x, y) -> (y - x)); // 大顶堆，保存较小的一半 } public void addNum(int num) { if(A.size() != B.size()) { A.add(num); B.add(A.poll()); } else { B.add(num); A.add(B.poll()); } } public double findMedian() { return A.size() != B.size() ? A.peek() : (A.peek() + B.peek()) / 2.0; } }

你知道的越多，你不知道的越多。