suanfabiji

 

1 差分练习

1 模板题

代码实现:

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();int num = sc.nextInt();long[][] arr = new long[n + 2][m + 2];for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {insert(arr, i, j, i, j, sc.nextInt());}}while (num > 0) {int x1 = sc.nextInt();int y1 = sc.nextInt();int x2 = sc.nextInt();int y2 = sc.nextInt();int zz = sc.nextInt();insert(arr, x1, y1, x2, y2, zz);num--;}for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {arr[i][j] = arr[i][j] + arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1];}}for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {System.out.print(arr[i][j] + " ");}System.out.println();}}public static void insert(long[][] arr, int x1, int y1, int x2, int y2, int num) {arr[x1][y1]+=num;arr[x1][y2+1]-=num;arr[x2+1][y1]-=num;arr[x2+1][y2+1]+=num;}
}

2 干草堆2041. 干草堆 - AcWing题库

代码实现:

import java.util.Arrays;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner input = new Scanner(System.in);int N = input.nextInt();int K = input.nextInt();long []arr1 = new long[N+2];while(K>0){int x = input.nextInt();int y = input.nextInt();arr1[x] += 1;arr1[y+1] -= 1;K--;}for (int i = 2; i <= N; i++) {arr1[i] =arr1[i-1]+arr1[i];}Arrays.sort(arr1);System.out.println(arr1[N / 2 + 2]);}
}

3 最高的牛101. 最高的牛 - AcWing题库

代码实现:

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner input = new Scanner(System.in);int N = input.nextInt();//牛的数量int P = input.nextInt();//最高牛的位置int H = input.nextInt();//最高牛的身高int M = input.nextInt();//对数boolean[][] exist = new boolean[N + 1][N + 1];int[] arr = new int[N + 1];arr[0] = H;//给第一个元素初始化为H间接使每一个数都初始化为H,在过程中不断的相减从而达到题目的要求for (int i = 1; i <= M; i++) {int A = input.nextInt();int B = input.nextInt();if (A > B) {int temp = A;//大小A = B;B = temp;}if (!exist[A][B]) {//去重arr[A + 1]--;arr[B]++;exist[A][B] = true;}}for (int i = 1; i <= N; i++) {arr[i] = arr[i - 1] + arr[i];System.out.println(arr[i]);}}
}

4 棋盘5396. 棋盘 - AcWing题库

代码实现:

import java.io.*;
import java.util.Scanner;public class Main {static int N=2010;static int[][] b=new int[N][N];public static void main(String[] args) throws IOException {Scanner scanner=new Scanner(new BufferedInputStream(System.in));BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));int n=scanner.nextInt(),m=scanner.nextInt();while(m-->0) {int x1=scanner.nextInt(),y1=scanner.nextInt(),x2=scanner.nextInt(),y2=scanner.nextInt();insert(x1,y1,x2,y2,1);}for(int i=1;i<=n;i++) {for(int j=1;j<=n;j++) {b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];writer.write(Integer.toString(b[i][j] % 2));}writer.write('\n');}writer.flush();scanner.close();}public static void insert(int x1, int y1, int x2, int y2,int c) {b[x1][y1]+=c;b[x2+1][y1]-=c;b[x1][y2+1]-=c;b[x2+1][y2+1]+=c;}
}

5 桶列表1715. 桶列表 - AcWing题库

代码实现:


import java.util.Arrays;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner input = new Scanner(System.in);int N = input.nextInt();int[] arr = new int[10100];int max = 0;for (int i = 0; i < N; i++) {int si = input.nextInt();max = Math.max(max, si);int ti = input.nextInt();max = Math.max(max, ti);int bi = input.nextInt();arr[si] += bi;arr[ti + 1] -= bi;}for (int i = 1; i <= max; i++) {arr[i] += arr[i - 1];//System.out.println(arr[i]);}Arrays.sort(arr);System.out.println(arr[arr.length - 1]);}
}

2 双指针练习

1 判断源字符串是否可以通过删除字符从而变成目标字符串

import java.util.Scanner;public class abc_2 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String SS = sc.next();String TS = sc.next();sc.close();if (en(SS, TS)) {System.out.println("YES");} else {System.out.println("NO");}}private static boolean en(String SS, String TS) {int sIndex = 0, tIndex = 0;while (sIndex < SS.length() && tIndex < TS.length()) {if (SS.charAt(sIndex) == TS.charAt(tIndex)) {tIndex++; // 移动目标字符串的索引}sIndex++; // 移动源字符串的索引}// 如果目标字符串已经完全匹配,则返回YESreturn tIndex == TS.length();}
}

2 数组的逆置

import java.util.Scanner;public class abc_1 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int len = sc.nextInt();int [] arr = new int[len];for (int i = 0; i < len; i++) {arr[i] = sc.nextInt();}for(int i=0,j=len-1;i<j;i++,j--) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}for(int i=0;i<len;i++) {System.out.print(arr[i]+" ");}}
}

3 完美序列(未ac)

代码实现

1 暴力for

import java.util.Arrays;
import java.util.Scanner;public class abc_6 {public static void main(String[] args) {Scanner input = new Scanner(System.in);int N = input.nextInt();int p = input.nextInt();int[] arr = new int[N];for (int i = 0; i < N; i++) {arr[i] = input.nextInt();}Arrays.sort(arr);int count = 0;for (int i = 0; i < N - 1; i++) {for (int j = arr.length - 1; j > 0; j--) {if (arr[i] * p >= arr[j] && i < j) {count = Math.max(count, j - i + 1);}}}System.out.println(count);}
}

双指针算法改进

import java.util.Arrays;
import java.util.Scanner;public class abc_7 {public static void main(String[] args) {Scanner input = new Scanner(System.in);int N = input.nextInt();int p = input.nextInt();int[] arr = new int[N];for (int i = 0; i < N; i++) {arr[i] = input.nextInt();}Arrays.sort(arr);int count = 0;int j = 0;for (int i = 0; i < N; i++) {while (j < N && arr[i] * p >= arr[j]) {j++;}if (i < j) {count = Math.max(count, j - i);}}System.out.println(count);}
}

4 最长连续递增序列

import java.util.Scanner;public class acb_4 {public static void main(String[] args) {Scanner input = new Scanner(System.in);int n = input.nextInt();//数组长度int[] arr = new int[n];for (int i = 0; i < n; i++) {arr[i] = input.nextInt();}int len_max = 0;for (int i = 0; i < n; i++) {int j = i;//这里需要将索引位置拉到倒数第二个数while (j < n - 1 && check(arr, j)) {//j-i+1是两个位置的距离差,+1是因为index+1位置开始len_max = Math.max(len_max, j - i + 1 + 1);j++;}}System.out.println(len_max);}public static boolean check(int[] arr, int index) {return arr[index + 1] - arr[index] > 0;}
}

5 --3. 无重复字符的最长子串 - 力扣(LeetCode)

代码实现:

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;class abc_8 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String s = sc.nextLine();int len = len(s);System.out.println(len);}public static int len(String s) {if (s == null || s.isEmpty()) return 0;Set<Character> set = new HashSet<>();int i = 0, j = 0, res = 0;while (j < s.length()) {//枚举以第j个字符结尾的最长不重复子串,j从0到s.length()-1if (!set.contains(s.charAt(j))) {//set不包含s.charAt(j),说明不重复,放心加入,j继续后移,更新最大长度set.add(s.charAt(j++));res = Math.max(res, j - i);} else {set.remove(s.charAt(i++));//由于j直到调用set.add(s.charAt(j++))那里才会更新,//故!set.contains(s.charAt[j])会连续为false很多次,//直到set.remove(s.charAt(i++))连续执行很多次,这里的i是从0索引位置开始出发一直删到重复那个元素//eg:pwwkew  此时的s.charAt(j)为w,要将set集合里面的从头开始删除到w - (pw)//把s.charAt[j]删除为止}}return res;}
}

3 滑动窗口练习

//外层循环扩展右边界,内层循环扩展左边界
for (int l = 0, r = 0 ; r < n ; r++) {//当前考虑的元素while (l <= r && check()) {//区间[left,right]不符合题意//扩展左边界}//区间[left,right]符合题意,统计相关信息
}

1-- 3. 无重复字符的最长子串 - 力扣(LeetCode)

代码实现:

class abc_9 {public int lengthOfLongestSubstring(String s) {//滑动窗口char[] ss = s.toCharArray();Set<Character> set = new HashSet<>();//去重int res = 0;//结果for(int left = 0, right = 0; right < s.length(); right++) {//每一轮右端点都扩一个。char ch = ss[right];//right指向的元素,也是当前要考虑的元素while(set.contains(ch)) {//set中有ch,则缩短左边界,同时从set集合出元素set.remove(ss[left]);left++;}set.add(ss[right]);//别忘。将当前元素加入。res = Math.max(res, right - left + 1);//计算当前不重复子串的长度。}return res;}
}

4 DFS深度优先搜索

1全排列问题:输入一个数实现1到这个数的全排列

代码实现:

import java.util.Scanner;public class abc_2_2 {static boolean[] v = new boolean[20];//判断数值是否访问static int n;//1-n的全排列static int[] a = new int[20];//保存方案public static void main(String[] args) {Scanner scanner = new Scanner(System.in);n = scanner.nextInt();dfs(0);}private static void dfs(int x) {//x表示第几个数了if (x == n) {for (int i = 0; i < n; i++) {System.out.print(a[i] + " ");}System.out.println();return;}for (int i = 1; i <= n; i++) {if (!v[i]) {//v[i]boolean数组中不存在a[x] = i;v[i] = true;dfs(x + 1);v[i] = false;}}}
}

分析

//123举例:123遍历
//dfs(0) 调用for循环,v[1]为false,1可以赋值给a[0] ,v[1]=true
//dfs(1) 调用for循环,v[1]为true已经被使用,v[2]为false,2可以被赋值给a[1] ,v[2]=true
//dfs(2) 调用for循环,v[1]为true已经被使用,v[2]为true已经被使用,v[3]为false,3可以赋值a[2] //,v[3]=true
//dfs(3) 直接执行if语句遍历输出数组(v[2]=false)
//123
//后来123遍历结束,执行回溯算法
//回溯dfs(1) for循环执行到3,v[1]为true v[2]=false,3赋值给a[1],v[2]=true
//dfs(2),v[1]为true,v[2]为true,v[3]为false,2可以赋值a[2],v[3]=true
//dfs(3)直接执行if语句遍历输出数组
//132
//dfs(2)到3已经执行完毕回溯dfs(0)

拓展题:实现一个数组的元素全排列

代码实现

import java.util.Scanner;public class TTrain {static int n;static char[] arr_P = new char[26];static char[] arr_p = new char[26];static Scanner input = new Scanner(System.in);static boolean[] emp = new boolean[200];public static void main(String[] args) {n = input.nextInt();for (int i = 0; i < n; i++) {arr_P[i] = input.next().charAt(0);}ddfs(0);}private static void ddfs(int row) {if (row == n) {for (int i = 0; i < n; i++) {System.out.print(arr_p[i] + " ");}System.out.println();}for (int i = 0; i < n; i++) {if (!emp[arr_P[i]]) {emp[arr_P[i]] = true;arr_p[row] = arr_P[i];ddfs(row + 1);emp[arr_P[i]] = false;}}}
}

2 n-皇后问题

代码实现:

import java.util.Scanner;public class abc_2_3 {//首先我们需要一个全局变量nstatic int n;//还需要三个boolean数组判断行列两条斜线static boolean[] arr1 = new boolean[30];static boolean[] arr2 = new boolean[30];static boolean[] arr3 = new boolean[30];//需要输入的Scanner对象static Scanner input = new Scanner(System.in);//需要一个二维数组存放棋盘static char[][] arr_s = new char[30][30];public static void main(String[] args) {n = input.nextInt();//二维数组初始化for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {arr_s[i][j] = '.';}}dfs_s(0);}private static void dfs_s(int row) {if (row == n) {//递归出口for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {System.out.print(arr_s[i][j] + " ");}System.out.println();}System.out.println();return;}for (int i = 0; i < n; i++) {if (!arr1[i] && !arr2[i + row] && !arr3[-row + i + n]) {arr1[i] = arr2[row + i] = arr3[-row + i + n] = true;arr_s[row][i] = 'Q';dfs_s(row + 1);arr1[i] = arr2[row + i] = arr3[-row + i + n] = false;arr_s[row][i] = '.';}}}
}
补充:
// exist_1 列 i--(x) dfs(num)相当于树的一层一层的遍历
// exist_2 左斜线/ i+num--(x+b)
// exist_3 右斜线\ i-num--(-x+b)

2

import java.util.Scanner;public class abc_2_8 {static Scanner sc = new Scanner(System.in);static int n;static char[][] arrss = new char[30][30];static boolean[] a = new boolean[30];static boolean[] b = new boolean[30];static boolean[] c = new boolean[30];static boolean[] d = new boolean[30];public static void main(String[] args) {n = sc.nextInt();for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {arrss[i][j] = '.';}}dfs_8(0, 0, 0);}private static void dfs_8(int x, int y, int s) {if (y == n) {y = 0;x++;}if (x == n) {if (s == n) {for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {System.out.print(arrss[i][j] + " ");}System.out.println();}System.out.println();}return;}//不放dfs_8(x, y + 1, s);//放if (!a[x] && !b[y] && !c[x + y] && !d[x - y + n]) {arrss[x][y] = 'Q';a[x] = b[y] = c[x + y] = d[x - y + n] = true;dfs_8(x, y + 1, s + 1);a[x] = b[y] = c[x + y] = d[x - y + n] = false;arrss[x][y] = '.';}}
}

5 数学知识模板

1 质数模板

    private static boolean isPrime(int n) {if (n < 2) {return false;}for (int i = 2; i <= n / i; i++) {if (n % i == 0) {return false;}}return true;}

2 分解质因数

    private static void input_s(int n) {for (int i = 2; i <= n / i; i++) {//先判断质数,再在质数范围内判断因数if (n % i == 0) {while (n % i == 0) {n /= i;System.out.println(i);}}}if (n > 1) {System.out.println(n);}}

3 最小公倍数最大公因数

最大公因数(GCD)

最大公因数可以通过欧几里得算法来计算。欧几里得算法的基本思想是:两个数的最大公因数等于其中较小的数和两数相除余数的最大公因数。

最小公倍数(LCM)

最小公倍数可以通过最大公因数来计算。两个数的乘积等于它们的最大公因数和最小公倍数的乘积。即:

    //最大公因数    public static int gcd(int a, int b) {if (b == 0) {return a;}return gcd(b, a % b);}// 计算最小公倍数public static int lcm(int a, int b) {return a*b/gcd(a,b);}

4 java内置库进制转换

    // 将整数转换为二进制字符串public static String toBinary(int num) {return Integer.toBinaryString(num);}// 将整数转换为四进制字符串public static String toQuaternary(int num) {StringBuilder result = new StringBuilder();while (num > 0) {result.insert(0, num % 4);num /= 4;}return result.toString();}// 将整数转换为八进制字符串public static String toOctal(int num) {return Integer.toOctalString(num);}// 将整数转换为十六进制字符串public static String toHexadecimal(int num) {return Integer.toHexString(num);}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/465833.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

WPS单元格重复值提示设置

选中要检查的所有的单元格 设置提示效果 当出现单元格值重复时&#xff0c;重复的单元格就会自动变化 要修改或删除&#xff0c;点击

一.Linux文件基本属性

前言&#xff1a;Linux系统是一个多用户系统&#xff0c;不同的用户处于不同的地位&#xff0c;也就是说具有不同的权限。为了安全&#xff0c;对于不同用户访问同一个文件&#xff0c;设置不同权限是很有必要的。 一.文件的基本属性理解 在Linux中&#xff0c;通常是这两个命…

【学习记录】使用CARLA录制双目摄像头SLAM数据

一、数据录制 数据录制的部分参考了网上的部分代码&#xff0c;代码本身并不复杂&#xff0c;基本都是简单的CARLA语法&#xff0c;关键的一点在于&#xff0c;CARLA内部本身并没有预设的双目摄像头&#xff0c;需要我们添加两个朝向相同的摄像头来组成双目系统&#xff0c;这…

算法的基础知识

算法的定义 算法是为了解决某类问题而规定的一个有限长的操作序列。 算法的特性 1. 有穷性&#xff08;Finiteness&#xff09; 含义&#xff1a;一个算法必须总是在执行有穷步后结束&#xff0c;且每一步都必须在有穷时间内完成。重要性&#xff1a;确保算法能够在合理的时…

城镇保障性住房管理:SpringBoot技术应用

2相关技术 2.1 MYSQL数据库 MySQL是一个真正的多用户、多线程SQL数据库服务器。 是基于SQL的客户/服务器模式的关系数据库管理系统&#xff0c;它的有点有有功能强大、使用简单、管理方便、安全可靠性高、运行速度快、多线程、跨平台性、完全网络化、稳定性等&#xff0c;非常…

【ComfyUI】flux人像摄影风格迁移的最优解?这个效果应该暂时无敌了吧?效果不好你打我!

大家好&#xff0c;这期我们主要讨论如何使用stable diffusion comfyUI 制作基于flux的人像摄影&#xff0c;主要实现风格迁移的功能。 我们都知道flux的生态目前不太完善&#xff0c;flux的controlnet和flux ipadapter虽然有&#xff0c;但效果不太好&#xff0c;可控性不强。…

基于微信的追星小程序+ssm(lw+演示+源码+运行)

摘 要 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;追星小程序被用户普遍使用&#xff0c;为方便用户能够可以…

esp32cam+Arduino IDE在编译时提示找不到 esp_camera.h 的解决办法

多半是因为你的ESP32库升级了&#xff0c;不再是 1.02版本&#xff0c;或者根本就没有 ESp32 库。如果被升级了&#xff0c;还原为1.02版本就可以了。如果没有&#xff0c;按照下述方法添加&#xff1a; 首先&#xff0c;在"文件"->"首选项"->"…

基于物联网设计的地下煤矿安全监测与预警

文章目录 一、前言1.1 项目介绍【1】项目开发背景【2】设计实现的功能【3】项目硬件模块组成 1.2 设计思路1.3 系统功能总结1.4 开发工具的选择【1】设备端开发【2】上位机开发 1.5 模块的技术详情介绍【1】NBIOT-BC26模块【2】MQ5传感器【4】DHT11传感器【5】红外热释电人体检…

第8章 利用CSS制作导航菜单作业

1.利用CSS技术&#xff0c;结合链接和列表&#xff0c;设计并实现“山水之间”页面。 浏览效果如下&#xff1a; HTML代码如下&#xff1a; <!DOCTYPE html> <html><head><meta charset"utf-8" /><title>山水之间</title><…

32单片机HAL库的引脚初始化

在使用HAL库时&#xff0c;GPIO初始化函数定义在stm32f4xx_hal_gpio.c文件中&#xff0c;如下&#xff1a; void HAL_GPIO_Init(GPIO_TypeDef *GPIOx, GPIO_InitTypeDef *GPIO_Init); 由这个函数可以看出&#xff0c;在初始化GPIO时&#xff0c;需要向函数传入2个结构体&…

Django安装

在终端创建django项目 1.查看自己的python版本 输入对应自己本机python的版本&#xff0c;列如我的是3.11.8 先再全局安装django依赖包 2.在控制窗口输入安装命令&#xff1a; pip3.11 install django 看到Successflully 说明我们就安装成功了 python的Scripts文件用于存…

网络层5——IPV6

目录 一、IPv6 vs IPv4 1、对IPv6主要变化 2、IPv4 vs IPv6 二、IPv6基本首部 1、版本——4位 2、通信量类——8位 3、流标号——20位 4、有效载荷长度——16位 5、下一个首部——8位 6、跳数限制——8位 7、源 、 目的地址——128位 8、扩展首部 三、IPv6地址 1…

怎么样鉴定疾病相关稀有细胞群?二值化精细模型标签,这个刚发的顶刊单细胞算法值得一学!

生信碱移 HiDDEN&#xff1a;抽丝剥茧 在具有病例和对照单细胞RNA测序研究中&#xff0c;样本级标签通常被直接赋予单个细胞&#xff0c;假设所有病例细胞都受影响。这种传统方法在受影响细胞比例较小或扰动强度较弱时&#xff0c;难以有效识别关键细胞及其标记基因&#xff…

三周精通FastAPI:33 在编辑器中调试

官方文档&#xff1a;https://fastapi.tiangolo.com/zh/tutorial/debugging/ 调试 你可以在编辑器中连接调试器&#xff0c;例如使用 Visual Studio Code 或 PyCharm。 调用 uvicorn 在你的 FastAPI 应用中直接导入 uvicorn 并运行&#xff1a; import uvicorn from fast…

Spring Boot关闭时,如何确保内存里面的mq消息被消费完?

1.背景 之前写一篇文章Spring Boot集成disruptor快速入门demo&#xff0c;有网友留言如下图&#xff1a; 针对网友的留言&#xff0c;那么我们如何解决这个问题呢 Spring-Boot应用停机时&#xff0c;如何保证其内存消息都处理完成&#xff1f; 2.解决方法 方法其实挺简单的&…

vue3+vite搭建脚手架项目使用eletron打包成桌面应用+可以热更新

当前Node版本&#xff1a;18.12.0&#xff0c;npm版本&#xff1a;8.19.2 1.搭建脚手架项目 搭建Vue3ViteTs脚手架-CSDN博客 可删掉index.html文件的title标签 2.配置package.json {"name": "my-vite-project","private": true,"versi…

【Golang】validator库的使用

package mainimport ("fmt""github.com/go-playground/validator" )// MyStruct .. validate:"is-awesome"是一个结构体标签&#xff0c;它告诉验证器使用名为is-awesome的验证规则来验证String字段。 type MyStruct struct {String string vali…

Linux(CentOS)安装 MySQL

CentOS版本&#xff1a;CentOS 7 MySQL版本&#xff1a;MySQL Community Server 8.4.3 LTS 1、下载 MySQL 打开MySQL官网&#xff1a;https://www.mysql.com/ 直接下载网址&#xff1a;https://dev.mysql.com/downloads/mysql/ 其他版本 2、上传 MySQL 文件到 CentOS 使用F…

Pytorch实现transformer语言模型

转载自&#xff1a;| 03_language_model/02_Transformer语言模型.ipynb | 从头训练Transformer语言模型 |Open In Colab | Transformer语言模型 本节训练一个 sequence-to-sequence 模型&#xff0c;使用pytorch的 nn.Transformer <https://pytorch.org/docs/master/nn.ht…