【Q剑指offer20】(md) 表示数值的字符串
 
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。
例如，字符串"+100"、“5e2”、"-123"、“3.1416”、"-1E-16"、“0123"都表示数值，但"12e”、“1a3.14”、“1.2.3”、"±5"及"12e+5.4"都不是。

本题使用有限状态自动机。根据字符类型和合法数值的特点，先定义状态，再画出状态转移图，最后编写代码即可。

class Solution {/**【有限状态自动机】*/public boolean isNumber(String s) {Map[] states = {new HashMap<>() {{ put(' ', 0); put('s', 1); put('d', 2); put('.', 4); }}, // 0.new HashMap<>() {{ put('d', 2); put('.', 4); }},                           // 1.new HashMap<>() {{ put('d', 2); put('.', 3); put('e', 5); put(' ', 8); }}, // 2.new HashMap<>() {{ put('d', 3); put('e', 5); put(' ', 8); }},              // 3.new HashMap<>() {{ put('d', 3); }},                                        // 4.new HashMap<>() {{ put('s', 6); put('d', 7); }},                           // 5.new HashMap<>() {{ put('d', 7); }},                                        // 6.new HashMap<>() {{ put('d', 7); put(' ', 8); }},                           // 7.new HashMap<>() {{ put(' ', 8); }}                                         // 8.};int p = 0;char t;for(char c : s.toCharArray()) {if(c >= '0' && c <= '9') t = 'd';else if(c == '+' || c == '-') t = 's';else if(c == 'e' || c == 'E') t = 'e';else if(c == '.' || c == ' ') t = c;else t = '?';if(!states[p].containsKey(t)) return false;p = (int)states[p].get(t);}return p == 2 || p == 3 || p == 7 || p == 8;}
}

本题题解原地址(作者Krahets)

 
 

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

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

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

class Solution {/***【八皇后】【回溯】* 1. x不能重复* 2. y不能重复* 3. x-y不能重复* 4. x+y不能重复* 不妨使用4个used数组，分别记录下这个4个规律*/public List<List<String>> solveNQueens(int n) {boolean[] usedX = new boolean[n];               // 横boolean[] usedY = new boolean[n];               // 竖boolean[] usedDiff = new boolean[2*n - 1];      // 斜boolean[] usedSum = new boolean[2*n - 1];       // 斜char[][] tempRes = new char[n][n];for(int i = 0; i < n; i++){Arrays.fill(tempRes[i], '.');}traceBack(tempRes, 0, n, usedX, usedY, usedDiff, usedSum);return res;}private List<List<String>> res = new ArrayList<>();// tempRes为暂存数组(记录数组)，layer为层数(实际就是行数)，以及used数组private void traceBack(char[][] tempRes, int layer, int n, boolean[] usedX, boolean[] usedY, boolean[] usedDiff, boolean[] usedSum){if(layer == n){res.add(transform(tempRes, n));return;}int i = layer;for(int j = 0; j < n; j++){if(!usedX[i] && !usedY[j] && !usedDiff[i - j + n - 1] && !usedSum[i + j]){tempRes[i][j] = 'Q';usedX[i] = true;usedY[j] = true;usedDiff[i - j + n - 1] = true;usedSum[i + j] = true;traceBack(tempRes, layer + 1, n, usedX, usedY, usedDiff, usedSum);tempRes[i][j] = '.';usedX[i] = false;usedY[j] = false;usedDiff[i - j + n - 1] = false;usedSum[i + j] = false;// 不要忘记手动回溯>_<}}}// 将数组char[][]转化为题目要求的List<String>private List<String> transform(char[][] tempRes, int n){List<String> realRes = new ArrayList<>();for(int i = 0; i < n; i++){realRes.add(new String(tempRes[i]));}return realRes;}
}

 
 

 

 

 

 

 

 

 

 

 
 

 

 

Qs from https://leetcode-cn.com
♠ loli suki
♥ end