Java每日一练(20230417)
JAVA 每日
2023-09-14 09:01:28 时间
目录
1. N 皇后 🌟🌟🌟
2. 搜索二维矩阵 🌟🌟
3. 发奖金问题 🌟
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.length
n == matrix[i].length
1 <= 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元。
🌟 每日一练刷题专栏 🌟
✨ 持续,努力奋斗做强刷题搬运工!
👍 点赞,你的认可是我坚持的动力!
🌟 收藏,你的青睐是我努力的方向!
✎ 评论,你的意见是我进步的财富!
☸ 主页:https://hannyang.blog.csdn.net/
![]() | Golang每日一练 专栏 |
![]() | Python每日一练 专栏 |
![]() | C/C++每日一练 专栏 |
![]() | Java每日一练 专栏 |
相关文章
- Java多线程--线程操作范例
- Java IO 之 InputStream源码
- Java实现 LeetCode 739 每日温度(暴力循环)
- Java实现 LeetCode 508 出现次数最多的子树元素和
- Java实现复数运算
- Java实现 蓝桥杯 历届真题 数字拆分
- Java实现 蓝桥杯VIP 算法训练 斜率计算
- Java并发教程(Oracle官方资料)
- [Java Spring] Controlling API Exposure & Override Endpoint Name
- 【Java每日一练】总目录(更新至2023.4.20)
- Java每日一练(20230420)
- Java每日一练(20230413)
- Java每日一练(20230402)
- Java每日一练(20230331)
- Java每日一练(20230330)
- Java每日一练(20230326)
- Java每日一练(20230322)
- Java每日一练(20230320)
- Java每日一练(20230319)
- Java每日一练(20230318)
- Java每日一练(20230317)
- Java每日一练(20230312)
- Java每日一练(20230311)
- 浅析Java各种变量线程安全问题
- Java基础--内部类及匿名内部类
- 常见Java面试题 程序中如何决定使用 HashMap 还是 TreeMap?
- 还在手动发早安吗?教你用java实现每日给女友微信发送早安
- 【腾讯阿里最全面试题】Java 线程池的实现原理,ThreadPoolExecutor关键参数解释...
- JAVA数组的定义及用法
- Java如何处理异常层次结构?