Java每日一练(20230417)

简介: Java每日一练(20230417)

1. N 皇后


n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。

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


每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1:

cc74a8b59b9a8fe64bb7a741774c2ad1.jpeg


输入: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:

eb4ca0d861f87843d6d732b4525b0acc.jpeg

输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3

输出:true


示例 2:

f22033e9dda21437197f5e414c912a3d.jpeg

输入: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元。

目录
打赏
0
0
0
0
74
分享
相关文章
|
10月前
|
CSDN每日一练(Java)--小艺的英文名
CSDN每日一练(Java)--小艺的英文名
|
10月前
|
2023-3-25 java选择题每日一练
2023-3-25 java选择题每日一练
60 1
|
10月前
|
Rust 编程小技巧摘选(6)
Rust 编程小技巧摘选(6)
118 1
Rust 编程小技巧摘选(6)
|
10月前
|
Rust 重载运算符|复数结构的“加减乘除”四则运算
Rust 重载运算符|复数结构的“加减乘除”四则运算
129 0
Rust 重载运算符|复数结构的“加减乘除”四则运算
|
10月前
|
Linux 终端命令之文件浏览(1) cat
Linux 终端命令之文件浏览(1) cat
79 0
Linux 终端命令之文件浏览(1) cat
|
10月前
|
Rust 编程小技巧摘选(7)
Rust 编程小技巧摘选(7)
147 0
Rust 编程小技巧摘选(7)
|
10月前
|
Windows 使用 Linux 子系统,轻轻松松安装多个linux
Windows 使用 Linux 子系统,轻轻松松安装多个linux
853 0
Windows 使用 Linux 子系统,轻轻松松安装多个linux
|
10月前
|
Rust 数据类型 之 类C枚举 c-like enum
Rust 数据类型 之 类C枚举 c-like enum
88 0
Rust 数据类型 之 类C枚举 c-like enum
|
10月前
|
Golang每日一练(leetDay0120) 反转字符串中的元音字母、前K个高频元素
Golang每日一练(leetDay0120) 反转字符串中的元音字母、前K个高频元素
94 0
Golang每日一练(leetDay0120) 反转字符串中的元音字母、前K个高频元素
|
10月前
|
Golang每日一练(leetDay0116) 路径交叉、回文对
Golang每日一练(leetDay0116) 路径交叉、回文对
76 0
Golang每日一练(leetDay0116) 路径交叉、回文对

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等