package 第4讲枚举模拟与排序;
import java.util.Scanner;
public class 例题_787归并排序 {
static Scanner in = new Scanner(System.in);
static int N = 100010;
static int n;
static int[] a = new int[N];
static int[] t = new int[N];
public static void main(String[] args) {
n = in.nextInt();
for (int i = 0; i < n; i ++) a[i] = in.nextInt();
mergeSort(0, n - 1);
for (int i = 0; i < n; i ++) System.out.print(a[i] + " ");
}
public static void mergeSort(int l, int r) {
if (l >= r) return ;
int mid = l + r >> 1;
mergeSort(l, mid);
mergeSort(mid + 1, r);
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r) t[k ++] = a[i] <= a[j] ? a[i ++] : a[j ++];
while (i <= mid) t[k ++] = a[i ++];
while (j <= r) t[k ++] = a[j ++];
for (k = 0, i = l; i <= r; k ++, i ++) a[i] = t[k];
}
}
活动打卡代码
AcWing 787. 归并排序
活动打卡代码
AcWing 466. 回文日期
package 第4讲枚举模拟与排序;
import java.util.Scanner;
public class 例题_466回文日期 {
/**
* 枚举
* 如果前4位已经确定，那么后4位也确定了，所以枚举前4位。
* 思路：1、枚举前4位回文数。
* 2、判断日期是否在规定范围内。
* 3、判断日期是否合法。
*/
static Scanner in = new Scanner(System.in);
static int date1, date2;
static int[] days = new int[] {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
// 检查当前时间是否合法
public static boolean check(int date) {
int y = date / 10000; // 年
int m = date % 10000 / 100; // 月
int d = date % 100; // 日
if (m < 1 || m > 12) return false;
if (m != 2) { // 不是2月
return d <= days[m];
} else { // 是2月
// 四年一闰，百年不闰，四百年又一闰。
boolean flag = ((y % 4 == 0 && y % 100 != 0) || y % 400 == 0);
if (flag) return d <= days[m] + 1;
else return d <= days[m];
}
}
public static void main(String[] args) {
date1 = in.nextInt();
date2 = in.nextInt();
int ans = 0;
for (int i = 1000; i < 10000; i ++) {
int x = i;
int date = i;
for (int j = 0; j < 4; j ++) {
date = date * 10 + (x % 10);
x /= 10;
}
if (date1 <= date && date <= date2 && check(date)) ans ++;
}
System.out.println(ans);
}
}
活动打卡代码
AcWing 1204. 错误票据
package 第4讲枚举模拟与排序;
import java.util.Scanner;
public class 例题_1204错误票据 {
static Scanner in = new Scanner(System.in);
static int N = 100010;
static int n;
static int[] cnt = new int[N];
public static void main(String[] args) {
// min记录开始值，max记录结束值
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
int n = in.nextInt();
while (in.hasNextInt()) {
int t = in.nextInt();
cnt[t] ++;
min = Math.min(min, t);
max = Math.max(max, t);
}
int ans1 = 0, ans2 = 0;
for (int i = min; i <= max; i ++) {
if (cnt[i] == 0) ans1 = i;
if (cnt[i] == 2) ans2 = i;
}
System.out.println(ans1 + " " + ans2);
}
}
活动打卡代码
AcWing 1245. 特别数的和
package 第4讲枚举模拟与排序;
import java.util.Scanner;
public class 例题_1245特别数的和 {
// 模拟，如果数位中有2019就加上
static Scanner in = new Scanner(System.in);
static int n;
public static void main(String[] args) {
n = in.nextInt();
long ans = 0;
for (int i = 1; i <= n; i ++) {
int x = i;
while (x != 0) {
int t = x % 10;
x /= 10;
if (t == 2 || t == 0 || t == 1 || t == 9) {
ans += i;
break;
}
}
}
System.out.println(ans);
}
}
活动打卡代码
AcWing 1236. 递增三元组
package 第4讲枚举模拟与排序;
import java.util.Arrays;
import java.util.Scanner;
public class 例题_1236递增三元组 {
/**
* 数据范围在10^5，时间复杂度在O(nlogn)以内，所以最多只能枚举1个数组。
* 而AC两个数组在两端，枚举A时，只能限制B，但不能限制C，所以我们枚举B数组。
*
* 主要思想：枚举B数组，再分别求出A数组中小于当前Bi和C数组中大于当前Bi的个数，相乘累加即是答案。
* 求个数有两种方法：1、前缀和
* 2、二分
* （这里用二分吧，简单一些，hh，注意边界问题0或者n-1时个数可能不存在）
*/
static Scanner in = new Scanner(System.in);
static int N = 10010;
static int n;
public static void main(String[] args) {
int n = in.nextInt();
int[] a = new int[n];
int[] b = new int[n];
int[] c = new int[n];
for (int i = 0; i < n; i ++) a[i] = in.nextInt();
for (int i = 0; i < n; i ++) b[i] = in.nextInt();
for (int i = 0; i < n; i ++) c[i] = in.nextInt();
Arrays.sort(a);
Arrays.sort(b);
Arrays.sort(c);
long ans = 0;
for (int i = 0; i < n; i ++) {
// 二分A数组中比Bi小的个数
int al = 0;
int ar = n - 1;
while (al < ar) {
int mid = al + ar + 1 >> 1;
if (a[mid] < b[i]) al = mid;
else ar = mid - 1;
}
long cnta;
if (al == 0 && a[al] >= b[i]) cnta = 0; // 个数不存
else cnta = (al - 0) + 1;
// 二分C数组中比Bi大的数
int cl = 0;
int cr = n - 1;
while (cl < cr) {
int mid = cl + cr >> 1;
if (c[mid] > b[i]) cr = mid;
else cl = mid + 1;
}
long cntc;
if (cl == n - 1 && c[cl] <= b[i]) cntc = 0; //个数不存在
else cntc = ((n - 1) - cl) + 1;
ans += cnta * cntc;
}
System.out.println(ans);
}
}
活动打卡代码
AcWing 1210. 连号区间数
package 第4讲枚举模拟与排序;
import java.util.Scanner;
public class 例题_1210连号区间数 {
/**
* 注意给出的数据就包含1~n的所有数，并且每个数字只出现一次。
* 两重循环，第一重循环固定左端点，第二重循环固定右端点
* 思路：在区间l~r中找到最大值max和最小值min，如果max - min == r - l，
* 说明当前区间是递增且连续的
* 例如：一个区间[4,6,7,5] max = 7, min = 4, 7 - 4 == 3 - 0, 所以是连续的
* 一个区间[5,3,2,6] max = 6, min = 2, 6 - 2 != 3 - 0, 所以不是连续的
*/
static Scanner in = new Scanner(System.in);
static int N = 10010;
static int n;
static int[] a = new int[N];
public static void main(String[] args) {
n = in.nextInt();
for (int i = 0; i < n; i ++) a[i] = in.nextInt();
int ans = 0;
for (int i = 0; i < n; i ++) {
// 由于区间不断一直变大，max和min只会不断变大和变小
// 所以不需要对每一个新区间都遍历一次
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int j = i; j < n; j ++) {
min = Math.min(min, a[j]);
max = Math.max(max, a[j]);
if (max - min == j - i) ans ++;
}
}
System.out.println(ans);
}
}
活动打卡代码
AcWing 3578. 最大中位数
package acwing.race;
import java.util.Arrays;
import java.util.Scanner;
public class 最大中位数3578 {
/**
* 这居然是一个二分！！！
* 二分最大中位数答案，再将中位数右边的数补齐至当前中位数，判断操作次数是否小于k。
*/
static Scanner in = new Scanner(System.in);
static int n, k;
public static void main(String[] args) {
n = in.nextInt();
k = in.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i ++) a[i] = in.nextInt();
Arrays.sort(a);
long l = 0, r = Integer.MAX_VALUE;
while (l < r) {
long mid = l + r + 1 >> 1;
if (check(a, mid)) l = mid;
else r = mid - 1;
}
System.out.println(l);
}
// 检查当前中位数为x时，操作次数是否足够
public static boolean check(int[] a, long x) {
long sum = 0;
for (int i = n / 2; i < n; i ++) {
if (x > a[i]) sum += x - a[i];
}
return sum <= k;
}
}
活动打卡代码
AcWing 3579. 数字移动
package acwing.race;
import java.util.Scanner;
public class 数字移动3579 {
/**
* 这题首要任务就是把题目看懂!!!
* 把题目看懂了，分析题目就明白是用并查集求连通块大小
*/
static Scanner in = new Scanner(System.in);
static int N = 200010;
static int[] p = new int[N];
static int[] s = new int[N];
public static void main(String[] args) {
int t = in.nextInt();
while (t -- > 0) {
int n = in.nextInt();
for (int i = 1; i <= n; i ++) {
p[i] = i;
s[i] = 1;
}
for (int i = 1; i <= n; i ++) {
int j = in.nextInt();
if (find(i) != find(j)) {
s[find(i)] += s[find(j)];
p[find(j)] = find(i);
}
}
for (int i = 1; i <= n; i ++) System.out.print(s[find(i)] + " ");
System.out.println();
}
}
public static int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
}
活动打卡代码
AcWing 3549. 最长非递减子序列
package acwing.lanqiaobei;
import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class 最长非递减子序列3549 {
/**
* y总思想题解，新数字序列a的最长非递减子序列，翻转之前状态肯定是
* 有4段：111...222...111...222，其中中间的两段是需要翻转，且每段长度允许为0。
*
* 这个是y总的简单化代码，非常简洁。
*/
static In in = new In(System.in);
public static void main(String[] args) throws Exception {
int n = in.nextInt();
// 注意：s1是前1段最大长度，s2是前2段的最大长度，以此类推！！
int s1 = 0, s2 = 0, s3 = 0, s4 = 0;
while (n -- > 0) {
int x = in.nextInt();
if (x == 1) {
s1 = s1 + 1; // 直接加在第1段后面。
s3 = Math.max(s2 + 1, s3 + 1); // 接在第2段后面或者在第3段后面加。
} else {
s2 = Math.max(s1 + 1, s2 + 1); // 接在第1段后面或者在第2段后面加。
s4 = Math.max(s3 + 1, s4 + 1); // 接在第3段后面或者在第3段后面加。
}
}
// 输出最长的一段，1中s3最长，2中s4最长
System.out.println(Math.max(s3, s4));
}
}
class In{
BufferedReader reader;
StringTokenizer tokenizer;
In(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream));
tokenizer = null;
}
public String next() throws Exception {
if (tokenizer == null || !tokenizer.hasMoreTokens()) {
tokenizer = new StringTokenizer(reader.readLine());
}
return tokenizer.nextToken();
}
public int nextInt() throws Exception {
return Integer.parseInt(next());
}
}
活动打卡代码
AcWing 3548. 双端队列
package acwing.lanqiaobei;
import java.util.Scanner;
public class 双端队列3548 {
/**
* 注意数据范围在2×10^5，而且队列中一定不会存在重复数字
*
* 直接用一个数组记录数字所在的下标，每次查询输出距离左右端点的最小值即可。
* y总的方法甚至不需要保存数据，只保存下标。
*/
static Scanner in = new Scanner(System.in);
static int N = 200010;
static int q, x;
static int[] a = new int[N]; // 模拟队列（该数组可以直接删除）
static int[] sign = new int[N]; // 纪录下标
public static void main(String[] args) {
q = in.nextInt();
int l = N / 2, r = N / 2 + 1;
while (q -- > 0) {
String s = in.next();
x = in.nextInt();
if (s.equals("L")) {
a[l] = x;
sign[x] = l;
l --;
} else if (s.equals("R")) {
a[r] = x;
sign[x] = r;
r ++;
} else {
int ans = Math.min(sign[x] - (l + 1), (r - 1) - sign[x]);
System.out.println(ans);
}
}
}
}
