标签：return scanner int DFS ++ static 回溯 new 合集
子集和问题
import java.util.Scanner;
public class Main {
static int n; // 元素个数
static int tarsum; // 目标和
static int remainSum = 0; // 当前元素加到最后一个元素的总和，剩余元素和
static int sesum = 0; // 已选元素之和
static int[] arr; // 原数组
static int[] choose; // 判断元素选不选
static boolean backtrack(int index) {
if (sesum == tarsum) return true; // 已选和等于目标和，找到
if (index >= n) return false; // 没有更多元素可以处理，没找到
remainSum -= arr[index]; // 先减去当前元素
if (sesum + arr[index] <= tarsum) { // 如果当前和加上该元素小于等于目标和，可以选
choose[index] = 1; // 选择该元素
sesum += arr[index]; // 更新当前和
if (backtrack(index + 1)) return true; // 如果找到则返回true
sesum -= arr[index]; // 否则减回去
}
if (sesum + remainSum >= tarsum) { // 即使不选择当前元素，加上剩余元素总和也足以达到或超过目标和
choose[index] = 0; // 不选当前元素
if (backtrack(index + 1)) return true; // 如果找到则返回true
}
remainSum += arr[index]; // 加回去当前元素
return false; // 未找到
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt(); // 读取元素个数
tarsum = scanner.nextInt(); // 读取目标和
arr = new int[n]; // 初始化数组
choose = new int[n]; // 初始化选择数组
for (int i = 0; i < n; i++) {
arr[i] = scanner.nextInt(); // 读取每个元素
remainSum += arr[i]; // 计算总和
}
if (!backtrack(0)) {
System.out.println("No Solution!"); // 如果找不到，输出无解
} else {
for (int i = 0; i < n; i++) {
if (choose[i] == 1) {
System.out.print(arr[i] + " "); // 输出选中的元素
}
}
}
}
}
最大子矩和
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in); // 创建扫描器对象读取输入
while (scanner.hasNext()) { // 检查是否有更多的输入
int rows = scanner.nextInt(); // 读取矩阵行数
int cols = scanner.nextInt(); // 读取矩阵列数
int[][] matrix = new int[rows][cols]; // 初始化矩阵
for (int i = 0; i < rows; i++) { // 遍历每一行
for (int j = 0; j < cols; j++) { // 遍历每一列
matrix[i][j] = scanner.nextInt(); // 读取矩阵元素
}
}
System.out.println(findMaxSubmatrixSum(matrix, rows, cols)); // 计算并输出最大子矩阵和
}
scanner.close(); // 关闭扫描器
}
private static int findMaxSubmatrixSum(int[][] matrix, int rows, int cols) {
//构建一个前缀和矩阵prefixSum为了计算方便，我们将前缀和矩阵多加一行一列作为边界
int[][] prefixSum = new int[rows + 1][cols + 1]; // 初始化前缀和数组
// 计算前缀和
for (int i = 1; i <= rows; i++) {
for (int j = 1; j <= cols; j++) {
//前缀和矩阵的i，j = 原矩阵对应点 + 前缀和矩阵左边一个 + 右边一个 - 左上角一个。
prefixSum[i][j] = matrix[i - 1][j - 1] + prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1];
}
}
int maxSum = Integer.MIN_VALUE; // 初始化最大子矩阵和为最小值
//计算最大子矩阵和，遍历每行每列
// 固定上边界
for (int top = 0; top < rows; top++) {
// 固定下边界
for (int bottom = top; bottom < rows; bottom++) {
int currentSum = 0; // 当前子矩阵和
// 遍历每一列
for (int col = 0; col < cols; col++) {
int submatrixSum = getSubmatrixSum(prefixSum, top, col, bottom, col); // 计算当前列在top和bottom之间的和
// 如果当前和大于0，累加，为什么？如果和都是负数了说明必不可能是最大子矩和，我们只要把所有正的累加即可
if (currentSum > 0) {
currentSum += submatrixSum;
// 如果当前和小于等于0，重置为当前列和
} else {
currentSum = submatrixSum;
}
//currentSum = (currentSum > 0) ? currentSum + submatrixSum : submatrixSum;
maxSum = Math.max(maxSum, currentSum); // 更新最大子矩阵和
}
}
}
return maxSum; // 返回最大子矩阵和
}
// 要计算子矩阵和，使用已经算出来的前缀和矩阵达到快速计算。
private static int getSubmatrixSum(int[][] prefixSum,int topRow, int leftCol, int bottomRow, int rightCol) {
//右下角 - 左下角 - 右上角 + 左上角，因为pre是比martix多一位的，所以遇到右边界，下边界都要+1
return prefixSum[bottomRow + 1][rightCol + 1] - prefixSum[bottomRow + 1][leftCol] -
prefixSum[topRow][rightCol + 1] + prefixSum[topRow][leftCol];
}
}
N皇后
import java.util.Scanner;
public class Main {
static final int MAX = 22; // 棋盘的最大尺寸
static int[][] chessboard = new int[MAX][MAX]; // 棋盘，用于存储皇后的位置
// 检查在 (row, col) 放置皇后是否安全
static boolean isSafe(int row, int col, int n) {
// 检查同一列
for (int i = 0; i < row; i++) {
if (chessboard[i][col] == 1) {
return false;
}
}
// 检查左上对角线
for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
if (chessboard[i][j] == 1) {
return false;
}
}
// 检查右上对角线
for (int i = row, j = col; i >= 0 && j < n; i--, j++) {
if (chessboard[i][j] == 1) {
return false;
}
}
return true; // 如果没有冲突，返回 true
}
// 递归函数，尝试在第 row 行放置皇后
static boolean solveUtil(int row, int n) {
// 如果所有皇后都成功放置，返回 true
if (row == n) {
return true;
}
// 尝试在当前行的每一列放置皇后
for (int col = 0; col < n; col++) {
if (isSafe(row, col, n)) { // 检查当前位置是否安全
chessboard[row][col] = 1; // 放置皇后
// 递归尝试在下一行放置皇后
if (solveUtil(row + 1, n)) {
return true;
}
chessboard[row][col] = 0; // 回溯：移除皇后
}
}
return false; // 如果在当前行的所有列都不能放置皇后，返回 false
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in); // 创建扫描器对象
int n = scanner.nextInt(); // 读取用户输入的棋盘大小
// 初始化棋盘
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
chessboard[i][j] = 0;
}
}
// 求解 N 皇后问题
if (!solveUtil(0, n)) { // 如果没有找到解决方案，输出提示信息
System.out.println("No solution found");
} else {
// 打印解决方案，每行输出一个皇后所在的列
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (chessboard[i][j] == 1) {
System.out.print((j + 1) + " "); // 输出皇后所在的列
break;
}
}
}
}
scanner.close(); // 关闭扫描器
}
}
主元素
主元素：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt(); // 读取测试用例的数量
while (T-- > 0) {
int n = sc.nextInt(); // 读取集合的元素数量
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt(); // 读取集合中的元素
}
// 调用方法找到主元素
String result = findMajorityElement(arr, n);
// 输出结果
System.out.println(result);
}
sc.close();
}
// 方法：使用摩尔投票算法找到主元素
private static String findMajorityElement(int[] arr, int n) {
int count = 0;
int condidate = -1;
for(int num : arr){
if(count == 0){
count = 1;
condidate = num;
}else if(num == condidate){
count++;
}else{
count--;
}
}
count = 0;
for(int num : arr){
if( num == condidate){
count++;
}
}
if(count > n/2){
return String.valueOf(condidate);
}else{
return "no";
}
}
}
用DFS计算pre和post
import java.util.*;
public class Main {
private static int time;
private static int[] pre;
private static int[] post;
private static List<List<Integer>> graph;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in); // 读取输入
int n = scanner.nextInt(); // 顶点数
int e = scanner.nextInt(); // 边数
pre = new int[n + 1]; // 初始化 pre 数组
post = new int[n + 1]; // 初始化 post 数组
graph = new ArrayList<>(); // 初始化邻接表
for (int i = 0; i <= n; i++) {
graph.add(new ArrayList<>()); // 创建每个顶点的邻接表
}
for (int i = 0; i < e; i++) {
int a = scanner.nextInt(); // 读取边的起点
int b = scanner.nextInt(); // 读取边的终点
graph.get(a).add(b); // 添加边到邻接表
}
for (int i = 1; i <= n; i++) {
Collections.sort(graph.get(i)); // 按顶点编号从小到大排序邻接表
}
time = 1; // 时钟从 1 开始
boolean[] visited = new boolean[n + 1]; // 初始化访问标记数组
dfs(1, visited); // 从 1 号顶点开始 DFS
// 输出 pre 数组
for (int i = 1; i <= n; i++) {
System.out.print(pre[i] + " ");
}
System.out.println();
// 输出 post 数组
for (int i = 1; i <= n; i++) {
System.out.print(post[i] + " ");
}
System.out.println();
scanner.close(); // 关闭扫描器
}
private static void dfs(int v, boolean[] visited) {
visited[v] = true; // 标记顶点 v 为已访问
pre[v] = time++; // 记录 pre 值并增加时间
for (int neighbor : graph.get(v)) { // 遍历邻接顶点
if (!visited[neighbor]) { // 如果邻接顶点未被访问
dfs(neighbor, visited); // 递归调用 DFS
}
}
post[v] = time++; // 记录 post 值并增加时间
}
}
标签：return,
scanner,
int,
DFS,
++,
static,
回溯,
new,
合集
From： https://www.cnblogs.com/hanlinyuan/p/18288247