1. N 皇后
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例 1：
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：
输入：n = 1
输出：[["Q"]]
提示：
1 <= n <= 9
皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。
代码：
import java.util.*; public class solveNQueens { public static class Solution { public List<List<String>> solveNQueens(int n) { List<List<String>> res = new ArrayList<List<String>>(); int[] queenList = new int[n]; placeQueen(queenList, 0, n, res); return res; } private void placeQueen(int[] queenList, int row, int n, List<List<String>> res) { if (row == n) { ArrayList<String> list = new ArrayList<String>(); for (int i = 0; i < n; i++) { String str = ""; for (int col = 0; col < n; col++) { if (queenList[i] == col) { str += "Q"; } else { str += "."; } } list.add(str); } res.add(list); } for (int col = 0; col < n; col++) { if (isValid(queenList, row, col)) { queenList[row] = col; placeQueen(queenList, row + 1, n, res); } } } private boolean isValid(int[] queenList, int row, int col) { for (int i = 0; i < row; i++) { int pos = queenList[i]; if (pos == col) { return false; } if (pos + row - i == col) { return false; } if (pos - row + i == col) { return false; } } return true; } } public static void main(String[] args) { Solution s = new Solution(); System.out.println(s.solveNQueens(4)); } }
输出：
[[.Q.., ...Q, Q..., ..Q.], [..Q., Q..., ...Q, .Q..]]
2. 搜索二维矩阵
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
- 每行中的整数从左到右按升序排列。
- 每行的第一个整数大于前一行的最后一个整数。
示例 1：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
示例 2：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false
提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 100-10^4 <= matrix[i][j], target <= 10^4
代码：
import java.util.*; public class searchMatrix { public static class Solution { public boolean searchMatrix(int[][] matrix, int target) { if (matrix.length == 0 || matrix[0].length == 0) return false; int begin, mid, end; begin = mid = 0; int len1 = matrix.length, len2 = matrix[0].length; end = len1 * len2 - 1; while (begin < end) { mid = (begin + end) / 2; if (matrix[mid / len2][mid % len2] < target) begin = mid + 1; else end = mid; } return matrix[begin / len2][begin % len2] == target; } } public static void main(String[] args) { Solution s = new Solution(); int[][] matrix = {{1,3,5,7},{10,11,16,20},{23,30,34,60}}; System.out.println(s.searchMatrix(matrix, 3)); int[][] matrix2 = {{1,3,5,7},{10,11,16,20},{23,30,34,60}}; System.out.println(s.searchMatrix(matrix2, 13)); } }
输出：
true
false
3. 发奖金问题
过年了，村里要庆祝。村长说，村里有一笔钱作为奖金，让每个人写一个纸条上来，谁写的数目与奖金最接近，就算猜中，这笔奖金就归谁，如果多人猜中，则平分。
编写程序，算算都有哪些人得到奖金？多少？
代码：
import java.util.Collections; import java.util.Comparator; import java.util.Arrays; import java.io.PrintStream; import java.nio.charset.StandardCharsets; class Solution1 { public static void main(String[] args) { int award = 100; String[] people = { "a", "b", "c", "d", "e", "f", "g", "h" }; Integer[] guess = { 75, 70, 80, 120, 100, 110, 100, 45 }; Integer[] ordered = new Integer[people.length]; for (int i = 0; i < ordered.length; i++) ordered[i] = i; Arrays.sort(ordered, new Comparator<Integer>() { @Override public int compare(Integer a, Integer b) { int x = guess[a] - award > 0 ? guess[a] - award : award - guess[a]; int y = guess[b] - award > 0 ? guess[b] - award : award - guess[b]; return x - y; } }); int maxp = 0; int i = 0; System.setOut(new PrintStream(System.out, true, StandardCharsets.UTF_8)); while (guess[ordered[i++]] == award) maxp++; if (maxp <= 1) System.out.println(people[ordered[0]] + "一人得奖" + award + "元。"); else { for (i = 0; i < maxp; i++) System.out.print(people[ordered[i]] + " "); System.out.println("共同得奖" + award / (float) (maxp) + "元。"); } } }
输出：
e g 共同得奖50.0元。
