算法合集
读入输出
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
public class Main {
public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
public static PrintWriter out = new PrintWriter(System.out);
public static StringTokenizer st = new StringTokenizer("");
public static void main(String[] args) throws Exception {
String line;
while ((line = in.readLine()) != null) {
st = new StringTokenizer(line);
}
out.close();
}
}
递归和分治
-
class Solution { public List<List<Integer>> subsets(int[] nums) { ans = new ArrayList<List<Integer>>(); set = new ArrayList<Integer>(); findSubsets(nums,0); return ans; } private void findSubsets(int []nums,int index){ //退出条件 if(index == nums.length){ ans.add(new ArrayList<Integer>(set)); return ; } //不选 findSubsets(nums,index+1); //选 set.add(nums[index]); findSubsets(nums,index+1); //还原 set.remove(set.size()-1); } private ArrayList<List<Integer>> ans; private List<Integer> set; } -
class Solution { public List<List<Integer>> combine(int n, int k) { ans = new ArrayList<List<Integer>>(); set = new ArrayList<Integer>(); this.n = n; this.k = k; findSubsets(1); return ans; } private void findSubsets(int index){ //剪枝 /* 选的数已经超过了k个 或者，把剩下的数全选也不够k个 就可以退出 */ if(set.size() > k || set.size() + n - index + 1 < k){ return; } //终止条件 if(index == n+1){ if(set.size() == k){ ans.add(new ArrayList<Integer>(set));// 复制List } return ; } // 不选 findSubsets(index+1); //选 set.add(index); findSubsets(index+1); //复原 set.remove(set.size()-1); } private List<List<Integer>> ans; private List<Integer> set; private int n; private int k; } -
class Solution { public List<List<Integer>> permute(int[] nums) { List<List<Integer>> res = new ArrayList<>(); int[] visited = new int[nums.length]; backtrack(res, nums, new ArrayList<Integer>(), visited); return res; } private void backtrack(List<List<Integer>> res, int[] nums, ArrayList<Integer> tmp, int[] visited) { if (tmp.size() == nums.length) { res.add(new ArrayList<>(tmp)); return; } for (int i = 0; i < nums.length; i++) { if (visited[i] == 1) continue; visited[i] = 1; tmp.add(nums[i]); backtrack(res, nums, tmp, visited); visited[i] = 0; tmp.remove(tmp.size() - 1); } } } -
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode invertTree(TreeNode root) { if(root == null) return null; invertTree(root.left); invertTree(root.right); TreeNode tmp = root.left; root.left = root.right; root.right = tmp; return root; } }
7-6 汉诺塔问题
题意和思路:
有三根柱子，第一根柱子上有 n 个按照从大到小排列的圆盘，要求将这些圆盘移动到第三根柱子上，其中每次只能移动一个圆盘，并且较大的圆盘不能放在较小的圆盘上面。要求输出移动步骤。
代码解释：
move()函数：递归地移动圆盘的过程。函数参数说明如下：
- n：要移动的圆盘数量。
- a、b、c：三个柱子的名称，用于输出移动步骤。
- 如果只有一个圆盘需要移动，直接从起始柱子 a 移动到目标柱子 c。
- 如果有多个圆盘需要移动，先将 n-1 个圆盘从起始柱子 a 移动到辅助柱子 b，然后将最后一个圆盘从 a 移动到 c，最后再将 n-1 个圆盘从辅助柱子 b 移动到目标柱子 c。
main()函数：读入圆盘数量和三个柱子的名称，调用move()函数进行圆盘移动。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// 移动圆盘的函数
// 参数说明：
// n：要移动的圆盘数量。
// a、b、c：三个柱子的名称，用于输出移动步骤。
void move(int n, string a, string b, string c) {
// 如果只有一个圆盘需要移动，直接从起始柱子 a 移动到目标柱子 c。
if (n == 1) {
cout << a << "->" << c << endl;
return;
}
// 如果有多个圆盘需要移动
// 先将 n-1 个圆盘从起始柱子 a 移动到辅助柱子 b，
move(n - 1, a, c, b);
// 然后将最后一个圆盘从 a 移动到 c，
cout << a << "->" << c << endl;
// 最后再将 n-1 个圆盘从辅助柱子 b 移动到目标柱子 c。
move(n - 1, b, a, c);
}
int main() {
int n; // 圆盘数量
string a, b, c; // 三个柱子的名称
cin >> n >> a >> b >> c; // 读入圆盘数量和三个柱子的名称
move(n, a, b, c); // 移动圆盘
return 0;
}
快速幂
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
public class Main {
public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
public static PrintWriter out = new PrintWriter(System.out);
public static long quick_pow(long a, long b, long p) {
long ans = 1;
for (; b != 0; b >>= 1) {
if ((b & 1) == 1) {
ans *= a;
ans %= p;
}
a *= a;
a %= p;
}
return ans;
}
public static void main(String[] args) throws Exception {
int n = Integer.parseInt(in.readLine());
while (n-- > 0) {
StringTokenizer st = new StringTokenizer(in.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int p = Integer.parseInt(st.nextToken());
out.println(quick_pow((long)a, (long)b, (long)p));
}
out.close();
}
}
回溯算法
46. 全排列 - 力扣（LeetCode）
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
最大数字 - 蓝桥云课 (lanqiao.cn)
一个数的大小是从左到右依次判断，所以我们从最左边开始枚举，我们无需关注后面的数，要利用自己的1号操作和2号操作保证当前这个数位的数一定要尽可能最大
然后分别考虑两种操作，首先两种操作不可能混用，因为它们是抵消的效果，所以要么对这个数全使用1操作，要么2操作。假设某个数位的值为x,首先考虑1号操作，使用后可以让该数位变大，出于贪心考虑，我们想让它变成9，那么需要进行9-x次1号操作，当然可能此时1号操作并不足以让我们将x变成9，但我们还是使用剩余的全部的次数将其变大，所以每次考虑1号操作应该使用的操作数t应该为t=min(n,9-x),此时x将变为x+t，然后进行下一位的判断。
其次我们考虑2号操作，这个的判断比较简单，它是让某个值减小，唯一能让某个数变大的机会就是将其减到0后再减就会变成9。那么这样操作需要的次数就是x+1，如果操作次数不够，那我们宁愿不使用，因为这只会让这个数位变得更小。
在深搜dfs的过程中，参数记录遍历到第几个数位以及此时累计的和，当搜索完所有数位后，将此时的和与答案进行一个取max，最后的值则为答案。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
public class Main {
public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
public static PrintWriter out = new PrintWriter(System.out);
public static StringTokenizer st = new StringTokenizer("");
public static int a;
public static int b;
public static long ans = 0l;
public static void dfs(int i, StringBuilder n) {
// 如果已经遍历完n的每一位数字，则更新答案为n的值并返回
if (i == n.length()) {
ans = Math.max(ans, Long.parseLong(n.toString()));
return;
} else {
// 获取当前位的数字
int x = (int) (n.charAt(i) - '0');
// 将当前位数字加1的操作次数
int t = Math.min(a, 9 - x);
// 执行加1操作，并更新a和x的值
a -= t;
x += t;
char yuan = n.charAt(i);
char ch = (char) (x + '0');
n.setCharAt(i, ch);
// 继续递归处理下一位数字
dfs(i + 1, n);
// 回溯，恢复之前的值
// 因为n(StringBuilder)是引用传递，
//当从一个分支跳到另一个分支的时候，
//如果不把前一个分支的数据给移除掉，
//那么n(StringBuilder)就会把前一个分支的数据带到下一个分支去，造成结果错误。
n.setCharAt(i, yuan);
//这a是因为设置的全局变量,x是因为前面改过
a += t;
x -= t;
// 如果剩余的b足够进行减1操作
if (b >= (x + 1)) {
// 执行减1操作，并更新b和x的值
b -= (x + 1);
char yuan2 = n.charAt(i);
n.setCharAt(i, '9');
// 继续递归处理下一位数字
dfs(i + 1, n);
// 回溯，恢复之前的值
b += (x + 1);
n.setCharAt(i, yuan2);
}
}
}
public static void main(String[] args) throws Exception {
st = new StringTokenizer(in.readLine());
// 输入正整数N、操作1次数A、操作2次数B
long n = Long.parseLong(st.nextToken());
a = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());
StringBuilder sb = new StringBuilder(String.valueOf(n));
// 从第0位开始递归处理
dfs(0, sb);
// 输出答案
out.print(ans);
out.close();
}
}
动态规划
1. 674. 最长连续递增序列 - 力扣（LeetCode）
题意：
寻找一个连续的最长递增子串
题解
法一：
-
count 为当前元素峰值，ans为最大峰值
-
初始化 count = 1
-
从 0 位置开始遍历，遍历时根据前后元素状态判断是否递增，
-
递增则 count++，递减则 count=1
-
如果 count>ans，则更新 ans
-
直到循环结束
-
时间复杂度：O(N)
class Solution { public int findLengthOfLCIS(int[] nums) { if(nums.length <= 1){ return nums.length; } int ans = -1; int tot = 1; for(int i = 1; i < nums.length; i++){ if(nums[i] > nums[i-1]){ tot++; }else{ tot = 1; } ans = Math.max(ans,tot); } return ans; } }
法二：动态规划
-
数组dp[i]：以下标 i 为结尾的数组的连续递增的子序列长度为 dp[i]。
注意这里的定义，一定是以下标 i 为结尾，并不是说一定以下标 00 为起始位置。 -
当 nums[i] > nums[i-1]时： nums[i] 可以接在 nums[i-1]] 之后（此题要求严格连续递增），此情况下最长上升子序列长度为 dp[i-1] + 1 ；
-
当 nums[i] <= nums[i-1] 时：nums[i]无法接在 nums[i-1]之后，此情况上升子序列不成立，跳过。
上述所有 -
情况 下计算出的 dp[i-1]+1 的最大值，为直到 i 的最长上升子序列长度（即 dp[i] ）。
-
转移方程： dp[i] = dp[i-1] + 1。
class Solution { public int findLengthOfLCIS(int[] nums) { if(nums.length == 0){ return nums.length; } int arr[] = new int[10005]; Arrays.fill(arr,1); int ans = 1; for(int i = 1; i < nums.length; i++){ if(nums[i] > nums[i - 1]){ arr[i] = arr[i - 1] + 1; } ans = Math.max(ans,arr[i]); } return ans; } }
01背包
2022 - 蓝桥云课 (lanqiao.cn)
有2022个物品，它们的编号分别是1到2022，它们的体积分别等于它们的编号。也就是说，有2022种物品，物品体积等于物品编号。
从2022个物品种选取10个物品，满足10个物品的体积之和为2022 用f[i][j][k]表示前i个物品里选择j个物品，体积之和为k的方案数 则对于前i种物品，有两种选择，选或者不选 f[i][j][k]=f[i-1][j][k] 不选 f[i][j][k]=f[i-1][j-1][k-i] 选 (为什么是k-i，因为第i个物品的体积就是i)
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
public class Main {
public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
public static PrintWriter out = new PrintWriter(System.out);
public static StringTokenizer st = new StringTokenizer("");
public static void main(String[] args) throws Exception {
// 表示前2022个物品选择10个物品，体积总和为2022的方案个数 ,,数组下标为1开始，所以使2023，11，2023
long[][][] f = new long[2023 + 10][10 + 10][2023 + 10];
// 初始化当选择物品数量为0时的方案数
for (int i = 0; i <= 2022; i++) {
f[i][0][0] = 1;
}
// 动态规划计算方案数
for (int i = 1; i <= 2022; i++) {
for (int j = 1; j <= 10; j++) {
for (int k = 1; k <= 2022; k++) {
// 不选第i个物品的情况，方案数等于上一个状态的方案数
f[i][j][k] = f[i - 1][j][k];
if (k >= i) {
// 选第i个物品的情况，方案数等于上一个状态的方案数加上剩余体积的方案数
f[i][j][k] += f[i - 1][j - 1][k - i];
}
}
}
}
// 输出符合条件的方案数
out.print(f[2022][10][2022]);
out.close();
// System.out.println("379187662194355221");
}
}
278. 数字组合 - AcWing题库
方案数板子
将 M 看作背包容量，每个数看成一个物品，Ai 看成是体积。本题即转化为：求出总体积恰好是 M 的方案数。
思路：
-
状态表示：
f[i,j]：所有只从前i个物品中选，且总体积不超过j的方案的数量
-
状态计算：
-
和 01 背包一致，根据最后一步第
i个物品选还是不选分类 -
不包含物品i的所有选法：
f[i][j] = f[i-1][j]
-
包含物品i的所有选法
f[i][j] = f[i-1][j-vi]
状态转移方程：
f[i][j] = f[i-1][j]+f[i-1][j-vi]
-
-
状态初始化及答案：
f[0]=1，初始M为 0 时，一个不选也是一种方案，其它均为 0- 答案即为
f[m]
一维代码：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10005;
int n, m;
int f[N];
int main() {
cin >> n >> m;
f[0] = 1;
for (int i = 0; i < n; ++i) {
int v;
cin >> v;
for (int j = m; j >= v; --j)
f[j] += f[j - v];
}
cout << f[m] << endl;
return 0;
}
二维代码：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10005;
int n, m;
int v[N];
int f[N][N];
int main() {
cin >> n >> m;
f[0][0] = 1;
for (int i = 1; i <= n; ++i) cin >> v[i];
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= m; ++j) {
f[i][j] = f[i - 1][j];
if (j >= v[i]) f[i][j] += f[i - 1][j - v[i]];
}
}
cout << f[n][m] << endl;
return 0;
}
416. 分割等和子集 - 力扣（LeetCode）
动态规划（转换为 0-1 背包问题） - 分割等和子集 - 力扣（LeetCode）
class Solution {
public boolean canPartition(int[] nums) {
int len = nums.length;
int sum = 0;
for (int num : nums) {
sum += num;
}
if ((sum & 1) == 1) {
return false;
}
int target = sum / 2;
// 状态定义：dp[i][j] 表示从数组的 [0, i] 这个子区间内挑选一些正整数，每个数只能用一次，使得这些数的和恰好等于 j
boolean[][] dp = new boolean[len][target + 1];
if (nums[0] <= target) {
dp[0][nums[0]] = true;
}
for (int i = 1; i < len; i++) {
for (int j = 0; j <= target; j++) {
dp[i][j] = dp[i - 1][j];
if (nums[i] == j) {
dp[i][j] = true;
}
if (nums[i] < j) {
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
}
}
}
return dp[len - 1][target];
}
}
线段树
P3374 【模板】树状数组 1
题意
线段树模板
算法训练营的详细说明：
#include <bits/stdc++.h>
using namespace std;
#define lc k << 1 //左孩子存储下标为2*k
#define rc k << 1 | 1 //右孩子下表为2*k+1
const int maxn = 10005;
int n, a[maxn];
struct node {
// l，r表示区间左右端点，mx表示区间[l,r]的最大值
int l, r, mx;
} tree[maxn * 4];
/**
* @brief 构造线段树
*
* @param k 下标
* @param l 区间左值
* @param r 区间右值
*/
void build(int k, int l, int r) {
//创建左子树
//创建右子树
tree[k].l = l;
tree[k].r = r;
//到了根节点赋值
if (l == r) {
tree[k].mx = a[l];
return;
}
//如果没有到达的话就递归创建左子树和右子树
int mid = (l + r) / 2;
build(lc, l, mid);
build(rc, mid + 1, r);
//回归的时候更新最大值
tree[k].mx = max(tree[lc].mx, tree[rc].mx);
}
/**
* @brief 线段树的点更新操作
* 将i -> v
*
* @param k 下标
* @param i 原来的值
* @param v 修改后的值
*/
void update(int k, int i, int v) {
if (tree[k].l == tree[k].r && tree[k].l == i) {
tree[k].mx = v;
return;
}
int mid = (tree[k].l == tree[k].r) / 2;
if (i <= mid) {
update(lc, i, v);
} else {
update(rc, i, v);
}
tree[k].mx = max(tree[lc].mx, tree[rc].mx);
}
/**
* @brief 区间覆盖查询
*
* @param k 下标
* @param l 区间左值
* @param r 区间右值
* @return int
*/
int query1(int k, int l, int r) {
//刚好区间覆盖，
if (tree[k].l >= l && tree[k].r <= r) {
return tree[k].mx;
}
int mid = (tree[k].l == tree[k].r) / 2;
int maxv = -INT_MAX;
if (l <= mid) {
maxv = max(maxv, query1(lc, l, r));
}
if (r >= mid) {
maxv = max(maxv, query1(rc, l, r));
}
return maxv;
}
int main() {
return 0;
}
题解
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int n, m, a[500001], f[2000001];
/**
* @brief 建树
*
* @param k 下标
* @param l 左端点
* @param r 右端点
*/
inline void buildtree(int k, int l, int r) {
if (l == r) {
f[k] = a[l];
return;
}
int mid = (l + r) >> 1;
buildtree(k + k, l, mid);
buildtree(k + k + 1, mid + 1, r);
f[k] = f[k + k] + f[k + k + 1];
}
/**
* @brief 添加数
*
* @param k 下标
* @param l 区间左值
* @param r 区间右值
* @param x 需要添加数的下标，包含在[l, r]之间
* @param y 添加数的值
*/
inline void add(int k, int l, int r, int x, int y) {
f[k] += y;
if (l == r) {
return;
}
int mid = (l + r) >> 1;
if (x <= mid) {
add(k + k, l, mid, x, y);
} else {
add(k + k + 1, mid + 1, r, x, y);
}
}
/**
* @brief 计算子段和
*
* @param k 下标
* @param l 左区间
* @param r 右区间
* @param s 子区间的左区间
* @param t 子区间的右区间
* @return int
*/
int calc(int k, int l, int r, int s, int t) {
if (l == s && r == t) {
return f[k];
}
int m = (l + r) >> 1;
if (t <= m) {
return calc(k + k, l, m, s, t);
} else if (s > m) {
return calc(k + k + 1, m + 1, r, s, t);
} else{
return calc(k + k, l, m, s, m) + calc(k + k + 1, m + 1, r, m + 1, t);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
buildtree(1, 1, n);
for (int i = 1; i <= m; i++) {
int t, x, y;
cin >> t >> x >> y;
if (t == 1) {
add(1, 1, n, x, y);
} else {
cout << calc(1, 1, n, x, y)<<endl;
}
}
return 0;
}
平衡树
知识教学
二叉树
模板
顺序存储的二叉树 转 二叉树
- 设根结点的存储位置下标为1，最后一个点的下标为n。存储的时候按照完全二叉树的形式进行存储，如果对应位置没有结点，则数据记为0。设某双亲结点的下标为i，则若2i（左孩子结点下标）或2i+1（右孩子结点下标）存在且数据不为0，说明该结点存在左孩子或右孩子结点。
public static TreeNode build_tree(int[] arr, int i, int n) {
TreeNode root = new TreeNode();
if (arr[i] == 0) {
return null;
}
root.val = arr[i];
root.left = null;
root.right = null;
if (2 * i <= n && arr[i] != 0) {
root.left = build_tree(arr, 2 * i, n);
}
if (2 * i + 1 <= n && arr[2 * i + 1] != 0) {
root.right = build_tree(arr, 2 * i + 1, n);
}
return root;
}
中序和前序建二叉树
public static Node build(int pre_start, int pre_end, int order_start, int order_end) {
if (pre_start > pre_end) {
return null;
}
//pre = [3,9,20,15,7], order = [9,3,15,20,7]
Node tree_root = new Node(pre[pre_start]);
int root = 0;
for (int i = order_start; i <= order_end; i++) {
if (order[i] == pre[pre_start]) {
root = i;
break;
}
}
int left_len = root - order_start;
tree_root.left = build(pre_start + 1, pre_start + left_len, order_start, root - 1);
tree_root.right = build(pre_start + left_len + 1, pre_end, root + 1, order_end);
return tree_root;
}
数组构建二叉树
class TreeNode {
public TreeNode left;
public TreeNode right;
public Integer val;
public TreeNode() {
}
}
public class Main {
public static TreeNode createTree(int index, int[] arr) {
if (index >= arr.length) {
return null;
}
TreeNode root = new TreeNode();
root.val = arr[index];
root.left = createTree(index * 2, arr);
root.right = createTree(index * 2 + 1, arr);
return root;
}
public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
public static PrintWriter out = new PrintWriter(System.out);
public static StringTokenizer st = new StringTokenizer("");
public static void main(String[] args) throws Exception {
int[] arr = new int[]{0, 1, 2, 3, 4, 5, 6};
TreeNode tree = createTree(1, arr);
out.close();
}
}
当下标从0开始构建
public static TreeNode createTree(int index,int[] arr){
if(index>=arr.length){
return null;
}
TreeNode root = new TreeNode();
root.val = arr[index];
root.left = createTree(index*2+1,arr);
root.right = createTree(index*2+2,arr);
return root;
}
static class TreeNode{
public TreeNode left;
public TreeNode right;
public Integer val;
public TreeNode(){
}
}
镜面反转
public static Node mirrorTree(Node root) {
if (root == null) return null;
Node tmp = root.left;
root.left = mirrorTree(root.right);
root.right = mirrorTree(tmp);
return root;
}
层序遍历
public static List<Node> bfs(Node root) {
Queue<Node> queue = new ArrayDeque<>();
queue.add(root);
List<Node> ans = new ArrayList<>();
while (!queue.isEmpty()) {
Node cur = queue.poll();
ans.add(cur);
if (cur.left != null) {
queue.add(cur.left);
}
if (cur.right != null) {
queue.add(cur.right);
}
}
return ans;
}
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null) {
return new ArrayList();
}
Deque<TreeNode> queue = new ArrayDeque<>();
List<List<Integer>> ans = new ArrayList<>();
queue.addLast(root);
while (!queue.isEmpty()) {
int n = queue.size();
List<Integer> tmp = new ArrayList<>();
while (n-- > 0) {
TreeNode cur = queue.pollFirst();
tmp.add(cur.val);
if (cur.left != null) {
queue.addLast(cur.left);
}
if (cur.right != null) {
queue.addLast(cur.right);
}
}
ans.add(tmp);
}
return ans;
}
}
堆
/**
* @Classname Main
* @Description TODO
* @Date 2023/2/5 19:55
* @Created by LeiXin
*/
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;
/**
* @Classname Main
* @Description TODO
* @Date 2022/12/6 21:15
* @Created by LeiXin
*/
public class Main {
public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
public static PrintWriter out = new PrintWriter(System.out);
public static void main(String[] args) throws Exception {
StringTokenizer st = new StringTokenizer(in.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
PriorityQueue<Integer> q = new PriorityQueue<>();
st = new StringTokenizer(in.readLine());
for (int i = 1; i <= n; i++) {
int x = Integer.parseInt(st.nextToken());
q.add(x);
}
Integer[] qq = new Integer[q.size()];
Object[] objects = q.toArray();
qq = Arrays.copyOf(objects, q.size(), Integer[].class);
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < qq.length; i++) {
map.put(qq[i], i);
}
for (int i = 1; i <= m; i++) {
st = new StringTokenizer(in.readLine());
String[] ss = new String[100];
int tot = 0;
while (st.hasMoreTokens()) {
ss[tot++] = st.nextToken();
}
if (ss[3].equals("root")) {
int r = Integer.parseInt(ss[0]);
if (qq[0] == r) {
out.println("T");
} else {
out.println("F");
}
} else if (ss[4].equals("siblings")) {
int left = Integer.parseInt(ss[0]);
int right = Integer.parseInt(ss[2]);
Integer l = map.get(left);
Integer r = map.get(right);
boolean is_f = false;
int min = Math.min(l, r);
int max = Math.max(l, r);
double min_d = 1.0 * (min - 1) / 2.0;
int min_i = (int) min_d;
double max_d = 1.0 * (max - 2) / 2.0;
int max_i = (int) max_d;
if (min_d % 1 == 0 && max_d % 1 == 0 && min_d - max_d <= 0.0000001) {
is_f = true;
}
if (is_f) {
out.println("T");
} else {
out.println("F");
}
} else if (ss[3].equals("parent")) {
int fa = Integer.parseInt(ss[0]);
fa = map.get(fa);
int child = Integer.parseInt(ss[5]);
child = map.get(child);
if (fa * 2 + 1 == child || fa * 2 + 2 == child) {
out.println("T");
} else {
out.println("F");
}
} else {
int child = Integer.parseInt(ss[0]);
int fa = Integer.parseInt(ss[5]);
fa = map.get(fa);
child = map.get(child);
if (fa * 2 + 1 == child || fa * 2 + 2 == child) {
out.println("T");
} else {
out.println("F");
}
}
}
/*
5 4
-46 -23 -26 -24 -10
-24 is the root
-26 and -23 are siblings
-46 is the parent of -23
-23 is a child of -10
*/
out.close();
}
}
经典题目
玩转二叉树
包括前序+中序建树,然后镜面反转,然后层序遍历
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;
/**
* @Classname Main
* @Description TODO
* @Date 2023/1/4 20:01
* @Created by LeiXin
*/
class Node {
int val;
Node left;
Node right;
public Node() {
}
public Node(int val, Node left, Node right) {
this.val = val;
this.left = left;
this.right = right;
}
public Node(int val) {
this.val = val;
}
}
public class Main {
public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
public static PrintWriter out = new PrintWriter(System.out);
public static int[] order = new int[35];
public static int[] pre = new int[35];
public static Node build(int pre_start, int pre_end, int order_start, int order_end) {
if (pre_start > pre_end) {
return null;
}
//pre = [3,9,20,15,7], order = [9,3,15,20,7]
Node tree_root = new Node(pre[pre_start]);
int root = 0;
for (int i = order_start; i <= order_end; i++) {
if (order[i] == pre[pre_start]) {
root = i;
break;
}
}
int left_len = root - order_start;
tree_root.left = build(pre_start + 1, pre_start + left_len, order_start, root - 1);
tree_root.right = build(pre_start + left_len + 1, pre_end, root + 1, order_end);
return tree_root;
}
public static Node mirrorTree(Node root) {
if (root == null) return null;
Node tmp = root.left;
root.left = mirrorTree(root.right);
root.right = mirrorTree(tmp);
return root;
}
public static List<Node> bfs(Node root) {
Queue<Node> queue = new ArrayDeque<>();
queue.add(root);
List<Node> ans = new ArrayList<>();
while (!queue.isEmpty()) {
Node cur = queue.poll();
ans.add(cur);
if (cur.left != null) {
queue.add(cur.left);
}
if (cur.right != null) {
queue.add(cur.right);
}
}
return ans;
}
public static void main(String[] args) throws Exception {
StringTokenizer st = new StringTokenizer(in.readLine());
int n = Integer.parseInt(st.nextToken());
st = new StringTokenizer(in.readLine());
for (int i = 1; i <= n; i++) {
order[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(in.readLine());
for (int i = 1; i <= n; i++) {
pre[i] = Integer.parseInt(st.nextToken());
}
//preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
//构造树
Node root = build(1, n, 1, n);
root = mirrorTree(root);
List<Node> nodes = bfs(root);
for (int i = 0; i < nodes.size(); i++) {
if (i == 0) {
out.print(nodes.get(i).val);
} else {
out.print(" " + nodes.get(i).val);
}
}
out.close();
}
}
顺序存储的二叉树的最近的公共祖先问题
236. 二叉树的最近公共祖先
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
/**
* @Classname Main
* @Description TODO
* @Date 2023/2/13 18:48
* @Created by LeiXin
*/
public class Main {
public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
public static PrintWriter out = new PrintWriter(System.out);
public static TreeNode build_tree(int[] arr, int i, int n) {
TreeNode root = new TreeNode();
if (arr[i] == 0) {
return null;
}
root.val = arr[i];
root.left = null;
root.right = null;
if (2 * i <= n && arr[i] != 0) {
root.left = build_tree(arr, 2 * i, n);
}
if (2 * i + 1 <= n && arr[2 * i + 1] != 0) {
root.right = build_tree(arr, 2 * i + 1, n);
}
return root;
}
public static TreeNode lca(TreeNode root, TreeNode p, TreeNode q) {
//根是q或p或null
if (root == null) {
return null;
}
if (root.val == p.val || root.val == q.val) {
return root;
}
TreeNode left = lca(root.left, p, q);
TreeNode right = lca(root.right, p, q);
if (left != null && right != null) {
return root;
} else if (left == null && right == null) {
return null;
} else if (left == null && right != null) {
return right;
} else {
return left;
}
}
public static void main(String[] args) throws Exception {
StringTokenizer stringTokenizer = new StringTokenizer(in.readLine());
int n = Integer.parseInt(stringTokenizer.nextToken());
int[] arr = new int[n + 1];
stringTokenizer = new StringTokenizer(in.readLine());
for (int i = 1; i <= n; i++) {
arr[i] = Integer.parseInt(stringTokenizer.nextToken());
}
TreeNode root = build_tree(arr, 1, n);
stringTokenizer = new StringTokenizer(in.readLine());
int a = Integer.parseInt(stringTokenizer.nextToken());
int flag = 0;
if (!(1 <= a && a <= n) || arr[a] == 0) {
out.println("ERROR: T[" + a + "] is NULL");
flag = 1;
}
int b = Integer.parseInt(stringTokenizer.nextToken());
if (flag == 0 && (!(1 <= b && b <= n) || arr[b] == 0)) {
out.println("ERROR: T[" + b + "] is NULL");
flag = 1;
}
if (flag == 0) {
TreeNode lca = lca(root, new TreeNode(arr[a]), new TreeNode(arr[b]));
for (int i = 1; i <= n; i++) {
if (arr[i] == lca.val) {
out.print(i + " ");
}
}
out.print(lca.val);
}
out.close();
}
}
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
public TreeNode() {
}
}
二叉树的层序遍历
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null) {
return new ArrayList();
}
Deque<TreeNode> queue = new ArrayDeque<>();
List<List<Integer>> ans = new ArrayList<>();
queue.addLast(root);
while (!queue.isEmpty()) {
int n = queue.size();
List<Integer> tmp = new ArrayList<>();
while (n-- > 0) {
TreeNode cur = queue.pollFirst();
tmp.add(cur.val);
if (cur.left != null) {
queue.addLast(cur.left);
}
if (cur.right != null) {
queue.addLast(cur.right);
}
}
ans.add(tmp);
}
return ans;
}
}
图
模板
dfs遍历最远距离:
void dfs(int x, int depth) {
if (depth > ans_depth) { // 如果当前深度大于最大深度，则更新最大深度和最大深度对应的节点编号
ans_depth = depth;
ans_d = x;
}
vis[x] = 1; // 标记该节点已经被访问过
for (int i = head[x]; i; i = e[i].next) { // 遍历与该节点相邻的所有节点
int v = e[i].to;
if (!vis[v]) { // 如果该节点还没有被访问过，则递归访问它
dfs(v, depth + 1);
}
}
}
求从 u 到 v 的路径条路:
//求从 u 到 v 的路径条路
int dfs(int u, int v) {
if (u == v) {
return 1; // 找到了一条从u到v的路径
}
int cnt = 0;
vis[u] = 1; // 将u标记为已访问
for (int i = head[u]; i; i = e[i].next) {
int nxt = e[i].to;
if (!vis[nxt]) {
cnt += dfs(nxt, v); // 递归地从nxt开始搜索到v的路径
}
}
vis[u] = 0; // 将u标记为未访问
return cnt;
}
dfs记录路径:
void dfs(int x) {
vis[x] = 1;
ans.push_back(x);
vector<int> ve;
for (int i = head[x]; i; i = e[i].next) {
ve.push_back(e[i].to);
}
sort(ve.begin(), ve.end());
for (int i = 0; i < ve.size(); i++) {
int to = ve[i];
if (!vis[to]) {
dfs(to);
//下面代码记录回溯路径
// ans.push_back(x);
}
}
}
经典题目
病毒溯源
- 这里边需要排序后插入，而且链式前向星是头插法
- 需要自己找起点
- dfs需要自己规划终点
#include <bits/stdc++.h>
#define mp(x, y) make_pair(x, y)
using namespace std;
typedef long long ll;
int n, m;
const int maxn = 10000 + 10;
const int maxm = maxn * 4;
struct node {
int to;
int next;
} e[maxm];
// end数组用于记录该点的是否为终点
// maxlen当前已知最长路长度
// ru数组记录每个点的入度，用于查找源点
int head[maxn], tot = 0, vis[maxn], ru[maxn], endss[maxn], maxlen = 0;
vector<int> ans;
vector<int> ve;
void add_edge(int u, int v) {
e[++tot].to = v;
e[tot].next = head[u];
head[u] = tot;
}
// 递归搜索每条道路
void dfs(int i, int len) {
if (endss[i] == 1) {
if (len > maxlen) {
maxlen = len;
ans = ve;
}
return;
}
for (int j = head[i]; j; j = e[j].next) {
ve.push_back(e[j].to);
dfs(e[j].to, len + 1);
ve.pop_back();
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int k;
cin >> k;
int arr[k];
// k为0说明该病毒不能变异成别的什么了，即为路径终点
if (k == 0) {
endss[i] = 1;
}
for (int j = 0; j < k; j++) {
int x;
cin >> x;
arr[j] = x;
ru[arr[j]]++;
}
// 由于是前向星建图所以要先将结点从大到小排序后建图才能做到先搜结点小的边
// greater<int>()让sort可以从大到小排序而非从小到大
sort(arr, arr + k, greater<>());
for (int j = 0; j < k; j++) {
add_edge(i, arr[j]);
}
}
int start = 0;
// 由于题目说了只有一个源点，所以找到一个源点即可跳出循环
for (int i = 0; i < n; i++) {
if (ru[i] == 0) {
start = i;
break;
}
}
ve.push_back(start);
dfs(start, 1);
cout << maxlen << endl;
for (int i = 0; i < ans.size(); i++) {
if (i == 0) {
cout << ans[i];
} else {
cout << " " << ans[i];
}
}
return 0;
}
L2-020 功夫传人
这里就图的bfs
#include <bits/stdc++.h>
using namespace std;
int n;
double z, r;
double res = 0;
const int maxn = 100000 + 10;
const int maxm = 2 * (maxn);
struct node {
int to;
int next;
int val;
} e[maxn];
int head[maxn], vis[maxn], tot;
double dedao[maxn];
double gong[maxn];
void add_edge(int u, int v) {
e[++tot].to = v;
e[tot].next = head[u];
head[u] = tot;
}
void bfs() {
queue<int> q;
q.push(0);
while (!q.empty()) {
// 循环n次没有起任何作用
int n = q.size();
for (int ii = 1; ii <= n; ii++) {
int cur = q.front();
q.pop();
if (vis[cur] == 1) {
continue;
}
vis[cur] = 1;
for (int i = head[cur]; i; i = e[i].next) {
int v = e[i].to;
// 不得道
if (dedao[v] - 0 < 0.00000000001) {
gong[v] = gong[cur] - (gong[cur] * 0.01 * r);
} else {
gong[v] = gong[cur] - (gong[cur] * 0.01 * r);
gong[v] *= dedao[v];
}
q.push(v);
}
}
}
}
int main() {
// ios::sync_with_stdio(false);
// cin.tie(0);
cin >> n >> z >> r;
for (int i = 0; i < n; i++) {
int k;
cin >> k;
if (k != 0) {
for (int j = 0; j < k; j++) {
int x;
cin >> x;
add_edge(i, x);
}
} else {
double x;
cin >> x;
dedao[i] = x;
}
}
gong[0] = z;
// 祖师也可以得道
if (!(dedao[0] - 0 < 0.00000000001)) {
gong[0] *= dedao[0];
}
bfs();
double ans = 0;
for (int i = 0; i < n; i++) {
if (!(dedao[i] - 0 < 0.00000000001)) {
ans += gong[i];
}
}
int q = ans;
cout << q;
// printf("%.0f", floor(ans));
return 0;
}
L2-031 深入虎穴
思路:
这是一个求有向图中距离起点最远的点的算法，采用深度优先搜索（DFS）实现。
算法思路：
1.先用 add_edge() 函数将图中所有点的关系存储到 e[] 数组中，实现建图。
2.找到入度为 0 的点，作为 DFS 的起点，存储到 start 变量中。
3.用 DFS 搜索整个图，记录搜索到每个点的深度（depth），如果 depth 大于当前的最大深度（ans_depth），更新最大深度和深度最大的点（ans_d）。
4.最终输出距离入口最远的那扇门的编号（ans_d）。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100000 + 10;
const int maxm = 2 * (maxn); // 因为是有向图，每个点最多有两个度，分别为入度和出度，所以边的数量最多是点数的两倍
struct node {
int to; // 表示边的另一个端点
int next; // 表示与该点相邻的下一条边的编号
int val; // 该边的边权，题目中并没有给出边权，所以该变量没有用到
} e[maxm];
int head[maxn], vis[maxn], tot; // head 数组是邻接表的头指针数组，vis 数组标记是否被访问过，tot 表示边的编号
void add_edge(int u, int v) { // 添加一条边，注意是有向边，即从 u 指向 v
e[++tot].to = v;
e[tot].next = head[u];
head[u] = tot;
}
int ans_depth = 0, ans_d = 0; // ans_depth 表示最大深度，ans_d 表示最大深度对应的节点编号
void dfs(int x, int depth) {
if (depth > ans_depth) { // 如果当前深度大于最大深度，则更新最大深度和最大深度对应的节点编号
ans_depth = depth;
ans_d = x;
}
vis[x] = 1; // 标记该节点已经被访问过
for (int i = head[x]; i; i = e[i].next) { // 遍历与该节点相邻的所有节点
int v = e[i].to;
if (!vis[v]) { // 如果该节点还没有被访问过，则递归访问它
dfs(v, depth + 1);
}
}
}
int ru[maxn]; // 记录每个节点的入度
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for (int ii = 1; ii <= n; ii++) {
int k;
cin >> k;
for (int i = 1; i <= k; i++) {
int x;
cin >> x;
add_edge(ii, x); // 添加一条边，从 ii 指向 x
ru[x]++; // x 的入度加一
}
}
int start = 0;
for (int i = 1; i <= n; i++) {
if (ru[i] == 0) { // 找到入度为 0 的节点作为起点
start = i;
break;
}
}
dfs(start, 1); // 从起点开始 DFS
cout << ans_d; // 输出最大深度对应的节点编号
return 0;
}
7-33 地下迷宫探索 (pintia.cn)
给定一个地下迷宫，迷宫的通道是直的，所有的交叉点（包括通道的端点）都有一盏灯和一个开关。要求从某个起点开始在迷宫中点亮所有的灯并回到起点。输入中给出了地下迷宫的节点数、边数和起始点编号，随后给出了每条边的两个端点编号。
思路：
本题可以通过深度优先遍历（DFS）来求解。具体思路如下：
1.从起点开始，进行深度优先遍历，把遍历到的点记录下来，同时点亮灯。
2.每次遍历到一个节点时，把与该节点相邻的所有节点按编号从小到大排序后，依次递归遍历。
3.遍历完成后，再从遍历序列的末尾开始回溯，即可回到起点，并保证灯都点亮了。
4.最后统计已遍历节点的数量，如果与总节点数相等，则说明迷宫是一个连通图，输出遍历序列，否则输出0。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1005;
const int maxm = 2 * 3000;
int fa[maxn];
int n, m;
struct node {
int to, next;
} e[maxm];
int head[maxn], vis[maxn], tot;
void add_edge(int u, int v) {
e[++tot].to = v;
e[tot].next = head[u];
head[u] = tot;
}
vector<int> ans;
void dfs(int x) {
vis[x] = 1;
ans.push_back(x); // 将遍历到的节点加入答案序列中
vector<int> ve;
for (int i = head[x]; i; i = e[i].next) { // 枚举与当前节点相邻的所有节点
ve.push_back(e[i].to); // 将节点加入到可达节点列表中
}
sort(ve.begin(), ve.end()); // 对可达节点进行排序，方便后续的操作
for (int i = 0; i < ve.size(); i++) {
int to = ve[i];
if (!vis[to]) { // 如果可达节点没有被访问过
dfs(to); // 递归访问该可达节点
ans.push_back(x); // 将当前节点加入到答案序列中
}
}
}
int main() {
int n, m, s;
cin >> n >> m >> s;
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
add_edge(u, v); // 添加无向边
add_edge(v, u);
}
dfs(s); // 从起点开始深度优先遍历
for (int i = 0; i < ans.size(); i++) { // 输出答案序列
if (i == 0) {
cout << ans[i];
} else {
cout << " " << ans[i];
}
}
int tot = 0;
for (int i = 1; i <= n; i++) { // 统计已经访问过的节点数
if (vis[i] == 1) {
tot++;
}
}
if (tot != n) { // 如果访问的节点数不等于总节点数，则说明存在未访问过的节点，输出 0
cout << " " << 0;
}
return 0;
}
7-9 旅游规划
两条边的最短路,即u->v要考虑一个距离,还要考虑一个费用.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 505;
const int maxm = (maxn * (maxn - 1) / 2);
struct node {
int to, next, val, fee;
} e[2 * maxm];
int head[maxn], vis[maxn], tot, dist[maxn];
int fee[maxn];
// 添加边的函数，u,v为边的两个端点，w为边的长度，fee为过路费
void add_edge(int u, int v, int w, int fee) {
e[++tot].to = v;
e[tot].val = w;
e[tot].fee = fee;
e[tot].next = head[u];
head[u] = tot;
}
// 定义小根堆结构体，包含当前节点cur，到该节点的距离dis，到该节点的过路费fee
struct heap {
int cur;
int dis;
int fee;
bool operator<(const heap &b) const {
if (dis == b.dis) {
return fee > b.fee;
} else {
return dis > b.dis;
}
}
};
int n, m, s, d;
// dijkstra算法实现
void dijkstra() {
priority_queue<heap> q; // 定义小根堆q
q.push({s, 0, 0}); // 初始将出发点s加入堆中
memset(dist, 0x3f3f3f3f, sizeof(dist)); // 将距离数组dist初始化为极大值
memset(fee, 0x3f3f3f3f, sizeof(fee)); // 将过路费数组fee初始化为极大值
dist[s] = 0; // 初始将出发点到出发点的距离设为0
fee[s] = 0; // 初始将出发点到出发点的过路费设为0
while (!q.empty()) { // 只要堆不为空就一直循环
heap cur_q = q.top(); // 取出堆顶元素，即距离最短的点
q.pop(); // 弹出堆顶元素
int u = cur_q.cur; // 获取当前节点
if (vis[u] == 1) { // 如果当前节点已经访问过，就跳过该节点，继续取下一个节点
continue;
}
vis[u] = 1; // 将当前节点标记为已访问
for (int i = head[u]; i; i = e[i].next) { // 遍历与当前节点相邻的所有节点
int v = e[i].to; // 获取相邻节点的编号
int w = e[i].val; // 获取相邻节点与当前节点的距离
int f = e[i].fee; // 获取通过该边需要收取的过路费
// 如果从源点到 u 的距离 dist[u] 加上从 u 到 v 的距离 w，
// 比目前已经计算出来的从源点到 v 的距离 dist[v] 更短
if (dist[u] + w < dist[v]) {
// 更新从源点到 v 的最短距离为 dist[u] + w
dist[v] = dist[u] + w;
// 更新从源点到 v 的最小收费为 fee[u] + f
fee[v] = fee[u] + f;
// 把 v 加入到优先队列中，以便对其它的点进行松弛操作
q.push({v, dist[v], fee[v]});
}
// 如果从源点到 u 的距离 dist[u] 加上从 u 到 v 的距离 w，
// 和目前已经计算出来的从源点到 v 的距离 dist[v] 一样
else if (dist[u] + w == dist[v]) {
// 如果从源点到 v 的最小收费 fee[v] 大于从源点到 u 的最小收费 fee[u] 加上从 u 到 v 的收费 f
if (fee[u] + f < fee[v]) {
// 更新从源点到 v 的最小收费为 fee[u] + f
fee[v] = fee[u] + f;
// 把 v 加入到优先队列中，以便对其它的点进行松弛操作
q.push({v, dist[v], fee[v]});
}
}
}
}
cout << dist[d] << " " << fee[d];
}
int main() {
cin >> n >> m >> s >> d;
for (int i = 1; i <= m; i++) {
int u, v, w, f;
cin >> u >> v >> w >> f;
// 去重，避免出现重边
if (u != v) {
add_edge(u, v, w, f);
add_edge(v, u, w, f);
}
}
dijkstra();
return 0;
}
并查集
模板
题目
红色警报
#include <bits/stdc++.h>
#define mp(x, y) make_pair(x, y)
using namespace std;
typedef long long ll;
int n, m;
const int maxn = 510;
const int maxm = 5010;
int fa[maxn], vis[maxn];
void init() {
for (int i = 0; i < n; i++) {
fa[i] = i;
}
}
int find(int x) {
if (x != fa[x]) {
fa[x] = find(fa[x]);
}
return fa[x];
}
int count() {
int tot = 0;
for (int i = 0; i < n; i++) {
if (i == fa[i] && vis[i] == 0) {
tot++;
}
}
return tot;
}
void merge(int x, int y) {
int a = find(x), b = find(y);
if (a != b) {
fa[a] = b;
}
}
struct node {
int u, v;
} e[maxm];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
init();
for (int i = 0; i < m; i++) {
cin >> e[i].u >> e[i].v;
merge(e[i].u, e[i].v);
}
int count1 = count();
int k;
cin >> k;
// 重新建立并查集
for (int i = 0; i < k; i++) {
int x;
cin >> x;
init();
vis[x] = 1;
for (int j = 0; j < m; j++) {
if (vis[e[j].u] == 1 || vis[e[j].v] == 1) {
continue;
}
merge(e[j].u, e[j].v);
}
int count2 = count();
// cout<<count1<<" "<<count2<<endl;
if (count1 == count2 || count1 - 1 == count2) {
cout << "City " << x << " is lost." << endl;
} else {
cout << "Red Alert: City " << x << " is lost!" << endl;
}
count1 = count2;
}
if (k == n) {
cout << "Game Over." << endl;
}
return 0;
}
部落
#include <bits/stdc++.h>
using namespace std;
const int maxn = 10000 + 10;
int fa[maxn];
int sum[maxn];
// 查找x所在集合的祖先
int find(int x) {
// 如果x是自己的祖先，则返回x
if (x == fa[x]) {
return x;
}
// 否则递归查找x的祖先，并压缩路径
return fa[x] = find(fa[x]);
}
// 合并x和y所在的两个集合
void merge(int x, int y) {
// 找到x所在集合的祖先fx和y所在集合的祖先fy
int fx = find(x), fy = find(y);
// 如果x和y不在同一个集合中，则将fx的父节点设为fy，合并两个集合
if (fx != fy) {
fa[fx] = fy;
}
}
int n;
void init() {
// 初始化每个元素所在的集合为它自己
for (int i = 1; i <= maxn; i++) {
fa[i] = i;
}
}
int main() {
cin >> n;
init();
set<int> se;
for (int ii = 1; ii <= n; ii++) {
int k;
cin >> k;
int first = 0;
for (int i = 1; i <= k; i++) {
int tmp;
cin >> tmp;
se.insert(tmp); // 将所有出现过的人员编号加入set中，统计社区总人数
if (i == 1) {
first = tmp;
continue;
}
// 将第一个人与后面的每一个人合并
merge(first, tmp);
}
}
cout << se.size() << " "; // 输出社区总人数
int tot = 0;
for (int i = 1; i <= se.size(); i++) {
// 如果i是祖先节点，则说明i所在的集合是一个互不相交的部落，统计部落数量
if (fa[i] == i) {
tot++;
}
}
cout << tot << endl; // 输出部落数量
int q;
cin >> q;
for (int ii = 1; ii <= q; ii++) {
int x, y;
cin >> x >> y;
if (find(x) == find(y)) {
cout << "Y" << endl; // x和y在同一个集合中，输出Y
} else {
cout << "N" << endl; // x和y不在同一个集合中，输出N
}
}
return 0;
}
分而治之
大意:
这是一道关于图论算法的题目。题目描述了一个战争中攻打敌方城市的策略，要求先攻下部分城市，使得剩余的城市成为孤立无援的状态，然后再分别攻打。输入给定敌方城市个数、连接两个城市的通路条数以及各个城市之间的连接关系，还有一系列攻打方案，每个方案给出攻打的城市数量和城市编号，要求判断这些方案是否可行。输出结果为每个方案的可行性，YES表示可行，NO表示不可行。
具体思路如下：
- 先读入图的信息，并使用邻接表存储图。在添加边的时候要注意是无向图，所以需要同时加入两个方向的边。
- 对于每个攻击方案，读入攻击城市的编号，将其标记为已攻下，其他城市标记为未攻下。
- 对于每个未攻下的城市，遍历其相邻的城市，如果相邻的城市中有未攻下的城市，说明该攻击方案不可行，直接跳出循环，否则继续判断下一个未攻下的城市。
#include <bits/stdc++.h> // 引入万能头文件
using namespace std;
const int maxn = 10000 + 10; // 定义常量
const int maxm = 2 * maxn;
int head[maxn], tot, vis[maxn]; // 定义头节点、计数器和标记数组
struct node {
int to, next; // 存储边的信息
} e[maxm];
void add_edge(int u, int v) { // 添加边
e[++tot].to = v;
e[tot].next = head[u];
head[u] = tot;
}
int main() {
int n, m;
cin >> n >> m; // 输入城市数量和道路数量
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y; // 输入道路连接的两个城市
add_edge(x, y); // 添加双向边
add_edge(y, x);
}
int k;
cin >> k; // 输入方案数量
for (int ii = 1; ii <= k; ii++) {
memset(vis, 0, sizeof(vis)); // 清空标记数组
int kk;
cin >> kk; // 输入方案中攻占的城市数量
for (int j = 1; j <= kk; j++) {
int x;
cin >> x; // 输入方案中攻占的城市编号
vis[x] = 1; // 标记为已攻占
}
int is_ok = 1; // 定义是否可行的标志
for (int t = 1; t <= n; t++) { // 遍历每一个城市
if (vis[t] == 1) { // 如果已经攻占了，直接跳过
continue;
}
for (int i = head[t]; i; i = e[i].next) { // 遍历与该城市相邻的城市
if (vis[e[i].to] == 0) { // 如果相邻城市没有被攻占，方案不可行
is_ok = 0;
}
}
}
if (is_ok == 1) { // 输出方案可行性结果
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
}
return 0; // 结束程序
}
栈和队列
L2-032 彩虹瓶
题意和思路:
这是一道非常好的模拟题目，可以使用堆栈模拟装填的过程。
首先根据题意，每次拿到货物后需要进行判断，如果是可以直接装填的颜色，就直接装填；否则就将其码放在一个临时货架上。同时，需要记录下来已经装填的颜色编号，以便后续判断。
码放时，由于可能会有多个箱子需要码放，因此需要使用一个栈来记录每个颜色的箱子数量。具体地，如果当前的货物不是下一个需要装填的颜色，就将其放到栈顶的箱子上，即将其入栈。如果当前的货物是下一个需要装填的颜色，那么就将栈顶的箱子取下来进行装填。如果栈空，说明没有可以取的箱子，无法完成任务，应该退出循环。
另外，还需要记录下来临时货架的容量，如果超过容量，也无法完成任务，应该退出循环。
最终，如果所有的颜色都已经装填完成，就输出 YES；否则输出 NO。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100000 + 10; // 最大颜色数量+10
const int maxm = 2 * (maxn); // 堆栈最大容量
int main() {
ios::sync_with_stdio(false); // 关闭流同步，提高cin、cout的输入输出效率
cin.tie(0); // 不关联任何流，防止输入输出操作时被阻塞
int n, m, k;
cin >> n >> m >> k; // 读入n,m,k
while (k--) { // 处理k组数据
int tot = 1; // 当前需要填充的颜色编号
stack<int> st; // 定义一个堆栈st
int flag = 1; // 是否能完成任务的标志，初始化为1
for (int i = 1; i <= n; i++) { // 处理每种颜色的小球
int x;
cin >> x; // 读入当前小球的颜色编号x
if (x == tot) { // 如果当前小球颜色编号等于当前需要填充的颜色编号
tot++; // 更新当前需要填充的颜色编号
while (!st.empty() && tot == st.top()) { // 如果堆栈非空，且堆栈顶部的颜色编号等于当前需要填充的颜色编号
st.pop(); // 弹出堆栈顶部的颜色编号
tot++; // 更新当前需要填充的颜色编号
}
} else { // 如果当前小球颜色编号不等于当前需要填充的颜色编号
st.push(x); // 将当前小球颜色编号压入堆栈
}
if (st.size() > m) { // 如果堆栈大小大于堆栈最大容量m
flag = 0; // 无法完成任务，将标志设为0
}
}
if (st.size() > 0) { // 如果堆栈非空
flag = 0; // 无法完成任务，将标志设为0
}
cout << (flag ? "YES\n" : "NO\n"); // 输出是否能完成任务的结果
}
return 0;
}
二分
模板
public int search(int[] nums, int target) {
int l = 0;
int r = nums.length - 1;
while(l < r){
int mid = (l+r)/2;
if(nums[mid] >= target){
r = mid;
}else{
l = mid + 1;
}
}
if(nums[r] != target){
return -1;
}else{
return r;
}
}
模板2
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型一维数组
* @param target int整型
* @return int整型
*/
public int search (int[] nums, int target) {
if(nums.length == 0){
return -1;
}
if(nums[0] == target){
return 0;
}
int l = 0,r = nums.length;
while(l + 1 < r){
int mid = (l + r) / 2;
if(nums[mid] == target){
return mid;
}else if (nums[mid] > target){
r = mid;
}else{
l = mid;
}
}
return -1;
// write code here
}
}
模板3
class Solution {
public int maximumCandies(int[] candies, long k) {
long sum = 0;
for(int val : candies)
sum += val;
if(sum < k){
return 0;
}
long left = 1,right = sum;
long ans = 0;
while(left <= right){
long mid = left + (right - left) / 2;
if(check(candies,mid,k)){
ans = mid;
left = mid + 1;
}else{
right = mid - 1;
}
}
return (int)ans;
}
boolean check(int[] candies, long limit, long k) {
for (int val : candies) {
if (val < limit) continue;
else if (val == limit) k--;
else {
k -= val / limit;
}
}
return k <= 0;
}
}
以上三种模板的不同的介绍:
二分查找不同模板分析与比较-腾讯云开发者社区-腾讯云 (tencent.com)
题目
二分查找-I_
- 模板题目,查找一个数,没有这个数就返回-1.
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型一维数组
* @param target int整型
* @return int整型
*/
public int search (int[] nums, int target) {
if(nums.length == 0){
return -1;
}
if(nums[0] == target){
return 0;
}
int l = 0,r = nums.length;
while(l + 1 < r){
int mid = (l + r) / 2;
if(nums[mid] == target){
return mid;
}else if (nums[mid] > target){
r = mid;
}else{
l = mid;
}
}
return -1;
// write code here
}
}
二分查找
class Solution {
public int search(int[] nums, int target) {
int l = 0;
int r = nums.length - 1;
while(l < r){
int mid = (l+r)/2;
if(nums[mid] >= target){
r = mid;
}else{
l = mid + 1;
}
}
if(nums[r] != target){
return -1;
}else{
return r;
}
}
}
列车调度
#include <bits/stdc++.h>
#define mp(x, y) make_pair(x, y)
using namespace std;
typedef long long ll;
const int maxn = 100005;
int arr[maxn];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
int ans = 0;
set<int> se;
for (int i = 1; i <= n; i++) {
int x;
cin>>x;
if (se.size() == 0) {
ans++;
se.insert(x);
} else {
if (se.lower_bound(x + 1) != se.end()) {
auto t = se.lower_bound(x + 1);
se.erase(t);
} else {
ans++;
}
se.insert(x);
}
}
cout << ans;
return 0;
}
2226. 每个小孩最多能分到多少糖果 - 力扣（LeetCode）
二分答案的板子
class Solution {
public int maximumCandies(int[] candies, long k) {
long sum = 0;
for(int val : candies)
sum += val;
if(sum < k){
return 0;
}
long left = 1,right = sum;
long ans = 0;
while(left <= right){
long mid = left + (right - left) / 2;
if(check(candies,mid,k)){
ans = mid;
left = mid + 1;
}else{
right = mid - 1;
}
}
return (int)ans;
}
boolean check(int[] candies, long limit, long k) {
for (int val : candies) {
if (val < limit) continue;
else if (val == limit) k--;
else {
k -= val / limit;
}
}
return k <= 0;
}
}
875. 爱吃香蕉的珂珂 - 力扣（LeetCode）
二分答案板子
class Solution {
public int minEatingSpeed(int[] piles, int h) {
int l = 1;
int r = -1;
for(int val : piles){
r = Math.max(r,val);
}
int ans = 1;
System.out.println("l:" + l + "r:" + r);
while(l <= r){
int mid = l + (r - l) / 2;
if(check(piles,mid,h)){
System.out.println("mid:"+ mid );
ans = mid;
r = mid - 1;
}else{
l = mid + 1;
}
}
return ans;
}
boolean check(int [] piles, int k, int h){
int tot_hour = 0;
for(int val : piles){
tot_hour += Math.ceil(1.0 * val / k);
}
if(tot_hour <= h){
return true;
}else{
return false;
}
}
}
堆
互评成绩
#include <bits/stdc++.h>
#define mp(x, y) make_pair(x, y)
using namespace std;
typedef long long ll;
vector<double> ve;
priority_queue<double> q;
int main() {
// ios::sync_with_stdio(false);
// cin.tie(0);
int n, k, m;
cin >> n >> k >> m;
for (int i = 1; i <= n; i++) {
ve.clear();
for (int j = 1; j <= k; j++) {
double x;
cin >> x;
ve.push_back(x);
}
sort(ve.begin(), ve.end());
double tot = 0;
for (int i = 1; i < ve.size() - 1; i++) {
tot += ve[i];
}
q.push(1.0 * tot / (k - 2));
}
vector<double> ans;
for (int i = 0; i < m; i++) {
double cur = q.top();
ans.push_back(cur);
q.pop();
}
sort(ans.begin(), ans.end());
for (int i = 0; i < ans.size(); i++) {
double cur = ans[i];
if (i == 0) {
printf("%.3f", cur);
} else {
printf(" %.3f", cur);
}
}
return 0;
}
模拟
数字或者数学模拟
特立独行的幸福
题意:
本题需要实现一个算法，用于寻找一个区间内的所有特立独行的幸福数，并计算它们的独立性。幸福数的定义为：对一个十进制数的各位数字做一次平方和，称作一次迭代。如果一个十进制数能通过若干次迭代得到 1，就称该数为幸福数。特立独行的幸福数，是在一个有限的区间内不依附于任何其它数字的；其独立性就是依附于它的幸福数的个数。如果这个数还是个素数，则其独立性加倍。另一方面，如果一个大于1的数字经过数次迭代后进入了死循环，那这个数就不幸福。
思路:
这道题目要求给定一个区间 [A,B]，找到所有在这个区间内的特立独行的幸福数和它的独立性。
算法思路：
首先，需要写一个函数 is_prime 判断一个数是否为素数。若一个数是特立独行的幸福数，则它需要满足以下两个条件：
- 在 [A,B] 范围内；
- 该数能通过若干次迭代得到 1，且在迭代过程中没有出现过已知的幸福数。
对于第二个条件，可以使用一个 vector 容器来记录幸福数出现的次数，如果一个数字在迭代过程中已经出现过一次，则可以判断它不是特立独行的幸福数。
最后，输出满足条件的幸福数和它的独立性。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 10000 + 10;
int vis[maxn]; // 标记数组，记录数字是否被访问过
// 判断x是否为质数，返回值为0表示x为1，返回值为1表示x不是质数，返回值为2表示x是质数
int is_prime(int x) {
if (x == 1) {
return 0;
}
for (int i = 2; i * i <= x; i++) {
if (x % i == 0) {
return 1;
}
}
return 2;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int left, right;
cin >> left >> right;
map<int, int> mp; // 记录幸福数和独立性的映射
for (int tt = left; tt <= right; tt++) { // 枚举区间[left, right]中的每个数字
int x = tt;
vector<int> ve; // 记录经过的数字序列
while (x != 1) { // 如果当前数字不为1，继续进行迭代
int sum = 0;
while (x) { // 计算平方和
sum += (x % 10) * (x % 10);
x /= 10;
}
x = sum;
if (find(ve.begin(), ve.end(), x) != ve.end()) { // 如果已经出现过这个数字，说明进入了死循环
break;
}
ve.push_back(x);
vis[x] = 1; // 标记数字x已被访问
}
if (x == 1) { // 如果当前数字为1，说明是一个幸福数
mp[tt] = ve.size(); // 将幸福数和独立性存储到映射中
}
}
int flag_out = 0; // 标记是否输出了幸福数
for (auto it : mp) { // 遍历映射，输出独立的幸福数和独立性
if (vis[it.first] == 0) { // 如果该幸福数独立，则输出
flag_out = 1;
cout << it.first << " " << it.second * is_prime(it.first) << endl;
}
}
if (!flag_out) { // 如果没有输出幸福数，则输出SAD
cout << "SAD" << endl;
}
return 0;
}
字符串模拟
L2-030 冰岛人 (pintia.cn)
题意:
这是一道关于维京人姓氏制度的算法题目，题目要求实现一个 App，可以查询两个人的祖宗关系，并判断是否存在五代以内的公共祖先。如果两个人为异性且五代以内无公共祖先，则输出 "Yes"；如果两个人为异性但五代以内有公共祖先，则输出 "No"；如果两个人为同性，则输出 "Whatever"；如果有一人不在名单内，则输出 "NA"。
#include <bits/stdc++.h>
using namespace std;
struct node {
char sex; // 性别
string fa; // 父亲的名字
};
map<string, node> people; // 存储所有人的信息
// check函数用于判断两个人的祖先关系
bool check(string a, string b) {
int i = 1;
for (string cura = a; cura.size() != 0; cura = people[cura].fa, i++) {
int j = 1;
for (string curb = b; curb.size() != 0; curb = people[curb].fa, j++) {
if (i >= 5 && j >= 5) { // 如果超过五代则直接返回true
return true;
}
if (cura == curb) { // 如果找到了公共祖先则直接返回false
return false;
}
}
}
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
string a, b;
cin >> a >> b;
// 根据姓氏的最后一个字母来确定性别
if (b[b.size() - 1] == 'n') {
people[a] = {'m', b.substr(0, b.size() - 4)};
} else if (b[b.size() - 1] == 'r') {
people[a] = {'f', b.substr(0, b.size() - 7)};
} else {
people[a].sex = b[b.size() - 1];
}
}
int m;
cin >> m;
string str;
for (int i = 1; i <= m; i++) {
string a, b;
cin >> a >> str >> b >> str;
// 判断两个人是否在人名单内
if (people.find(a) == people.end() || people.find(b) == people.end()) {
cout << "NA" << endl;
} else if (people[a].sex == people[b].sex) { // 如果两个人性别相同则输出 "Whatever"
cout << "Whatever" << endl;
} else {
if (check(a, b) == 1) { // 如果五代以内没有公共祖先则输出 "Yes"
cout << "Yes" << endl;
} else { // 如果五代以内有公共祖先则输出 "No"
cout << "No" << endl;
}
}
}
return 0;
}
STL大法
L2-039 清点代码库
- 首先，使用
map数据结构统计每个功能模块对应的输出，每个输出作为一个长度为 M 的向量存储。 - 然后，将所有向量按照出现次数从大到小排序，若次数相同，则按照向量大小和字典序从小到大排序。
- 最后，输出向量的总数以及每个向量出现的次数和向量本身。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100000 + 10;
const int maxm = 2 * (maxn);
// 建立vector<int>到int的映射，mp存储每个vector出现的次数
map<vector<int>, int> mp;
// 自定义比较函数，按照出现次数从大到小排序，次数相同时按vector大小和字典序从小到大排序
bool cmp(pair<vector<int>, int> a, pair<vector<int>, int> b) {
if (b.second == a.second) {
vector<int> x = a.first;
vector<int> y = b.first;
for (int i = 0; i < x.size(); i++) {
if (x[i] < y[i]) {
return true;
} else if (x[i] > y[i]) {
return false;
}
}
} else {
return a.second > b.second;
}
}
int main() {
ios::sync_with_stdio(false); // 关闭同步流，提高cin输入效率
cin.tie(0); // 解除cin与cout的绑定，提高cin输入效率
int n, m;
cin >> n >> m;
// 对于每个输入的vector，统计它的出现次数
for (int i = 1; i <= n; i++) {
vector<int> ve;
for (int j = 1; j <= m; j++) {
int x;
cin >> x;
ve.push_back(x);
}
mp[ve]++;
}
// 存储答案的vector，ans存储所有的vector及其出现次数
vector<pair<vector<int>, int>> ans;
for (auto it : mp) {
ans.push_back({it.first, it.second});
}
// 按照题目要求排序
sort(ans.begin(), ans.end(), cmp);
// 输出答案
cout << ans.size() << endl;
for (auto it : ans) {
cout << it.second << " ";
vector<int> tmp = it.first;
for (int i = 0; i < tmp.size(); i++) {
if (i == 0) {
cout << tmp[i];
} else {
cout << " " << tmp[i];
}
}
cout << endl;
}
return 0;
}
拓扑排序
模板
题目
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 110;
const int maxm = 2 * 110;
vector<int> ve[maxn]; // 存储每个子任务依赖的子任务
int ru[maxn]; // 存储每个子任务的入度
int vis[maxn]; // 标记每个子任务是否被访问过
int main() {
int n;
cin >> n;
// 处理每个子任务的依赖集合
for (int i = 1; i <= n; i++) {
int k;
cin >> k;
for (int j = 1; j <= k; j++) {
int x;
cin >> x;
ve[x].push_back(i); // 存储依赖关系
ru[i]++; // 增加入度
}
}
queue<int> q;
// 将所有入度为0的子任务加入队列
for (int i = 1; i <= n; i++) {
if (ru[i] == 0) {
q.push(i);
}
}
int tot = q.size(); // 记录加入队列的子任务数量
while (!q.empty()) {
int cur = q.front();
q.pop();
if (vis[cur]) {
continue; // 如果当前子任务已经被访问过，则跳过
}
vis[cur] = 1; // 标记当前子任务为已访问
// 处理当前子任务依赖的子任务
for (int i = 0; i < ve[cur].size(); i++) {
int to = ve[cur][i];
ru[to]--; // 将依赖的子任务入度减一
if (ru[to] == 0) { // 如果依赖的子任务入度为0，则加入队列
q.push(to);
tot++; // 记录加入队列的子任务数量
}
}
}
// 如果所有子任务都被访问过，则方案可行，输出1，否则输出0
if (tot == n) {
cout << "1" << endl;
} else {
cout << "0" << endl;
}
return 0;
}
日期
题目
跑步锻炼 - 蓝桥云课 (lanqiao.cn)
/**
* @Classname Main
* @Description TODO
* @Date 2023/2/5 19:55
* @Created by LeiXin
*/
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.time.LocalDate;
import java.time.temporal.ChronoUnit;
/**
* @Classname Main
* @Description TODO
* @Date 2022/12/6 21:15
* @Created by LeiXin
*/
public class Main {
public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
public static PrintWriter out = new PrintWriter(System.out);
public static void main(String[] args) throws Exception {
LocalDate start = LocalDate.of(2000, 1, 1);
LocalDate end = LocalDate.of(2020, 10, 1);
int tot = 0;
while (!start.isAfter(end)) {
int week = start.getDayOfWeek().getValue();
int month = start.getDayOfMonth();
if (week == 1 || start.getDayOfMonth() == 1) {
tot += 2;
} else {
tot++;
}
start = start.plus(1L, ChronoUnit.DAYS);
}
out.println(tot);
out.close();
}
}
回文日期 - 蓝桥云课 (lanqiao.cn)
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.time.LocalDate;
import java.time.format.DateTimeFormatter;
import java.time.temporal.ChronoUnit;
public class Main {
// 创建一个BufferedReader对象，用于读取输入
public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
// 创建一个PrintWriter对象，用于输出结果
public static PrintWriter out = new PrintWriter(System.out);
// 创建一个DateTimeFormatter对象，用于格式化日期
public static DateTimeFormatter formatter = DateTimeFormatter.ofPattern("yyyyMMdd");
// 判断一个日期是否为回文日期
public static boolean ishui(LocalDate date) {
// 格式化日期并获取年份和月日部分
String cur = date.format(formatter);
String a = cur.substring(0, 4);
String b = cur.substring(4);
// 将月日部分反转
String re_b = new StringBuilder(b).reverse().toString();
// 判断是否相等
if (a.equals(re_b)) {
return true;
} else {
return false;
}
}
// 判断一个日期是否为全同号日期
public static boolean isab(LocalDate date) {
// 格式化日期并将其转换为字符数组
String cur = date.format(formatter);
char[] charArray = cur.toCharArray();
// 判断字符数组中每个元素是否相等
if (charArray[0] == charArray[2] && charArray[2] == charArray[5] && charArray[5] == charArray[7]
&& charArray[1] == charArray[3] && charArray[3] == charArray[4] && charArray[4] == charArray[6]) {
return true;
} else {
return false;
}
}
public static void main(String[] args) throws Exception {
// 读取输入并将其转换为LocalDate对象，然后加1天
String s = in.readLine();
LocalDate date = LocalDate.parse(s, formatter).plus(1, ChronoUnit.DAYS);
// 用两个变量来记录是否已经找到回文日期和全同号日期
int is_hui = 0;
int is_ab = 0;
while (true) {
// 如果找到了回文日期并且之前没有找到，输出该日期
if (ishui(date) && is_hui == 0) {
out.println(date.format(formatter));
is_hui = 1;
}
// 如果找到了全同号日期并且之前没有找到，输出该日期
if (isab(date) && is_ab == 0) {
out.println(date.format(formatter));
is_ab = 1;
}
// 如果回文日期和全同号日期都找到了，退出循环
if (is_ab == 1 && is_hui == 1) {
break;
}
// 将日期加1天
date = date.plus(1, ChronoUnit.DAYS);
}
// 关闭输出流
out.close();
}
}
特殊日期 - 蓝桥云课 (lanqiao.cn)
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.time.LocalDate;
import java.time.temporal.ChronoUnit;
public class Main {
public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
public static PrintWriter out = new PrintWriter(System.out);
// 定义一个函数用于计算给定数字字符串中各位数字的总和
public static int sum(String num) {
int tot = 0;
char[] charArray = num.toCharArray();
for (int i = 0; i < charArray.length; i++) {
tot += (charArray[i] - '0');
}
return tot;
}
public static void main(String[] args) throws Exception {
// 定义开始日期和结束日期
LocalDate date1 = LocalDate.of(1900, 1, 1);
LocalDate date2 = LocalDate.of(9999, 12, 31);
// 定义答案计数器
int ans = 0;
// 遍历所有日期并检查每个日期是否符合要求
while (date1.isBefore(date2)) {
// 计算年份、月份和日期中各位数字的总和
int year = sum(String.valueOf(date1.getYear()));
int month = sum(String.valueOf(date1.getMonthValue()));
int day = sum(String.valueOf(date1.getDayOfMonth()));
// 如果年份等于月份和日期中各位数字的总和，则增加答案计数器
if (year == month + day) {
ans++;
}
// 将日期加1天
date1 = date1.plus(1, ChronoUnit.DAYS);
}
// 输出答案
out.print(ans);
// 关闭输出流
out.close();
}
}
进制
题目
寻找一个十进制数，使得其十六进制表示中的每个字符都是小写字母a-f
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
public class Main {
public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); // 读取输入
public static PrintWriter out = new PrintWriter(System.out); // 输出结果
public static void main(String[] args) throws Exception {
int cur = 2023; // 初始化 cur 为 2023，作为起始值
while (true) { // 进入一个循环，用于寻找符合要求的整数
String s = Integer.toString(cur, 16); // 将当前的整数 cur 转换成 16 进制字符串
char[] charArray = s.toCharArray(); // 将字符串转换成字符数组
int flag = 1; // 初始化 flag 为 1，用于表示当前的整数 cur 是否符合要求
for (int i = 0; i < charArray.length; i++) { // 遍历字符数组中的每一个字符
if (!('a' <= charArray[i] && charArray[i] <= 'f')) { // 如果当前字符不在 a~f 之间
flag = 0; // 将 flag 设为 0，表示当前的整数 cur 不符合要求
break; // 跳出循环，不再判断剩余的字符
}
}
if (flag == 1) { // 如果整个字符数组中的字符都在 a~f 之间
out.println(cur); // 输出当前的整数 cur
break; // 跳出循环，结束程序
}
cur++; // 将 cur 的值加一，继续寻找符合要求的整数
}
out.close(); // 关闭输出流
}
}