import java.util.Scanner; public class Main{ public static int getUpMedian2(int[] arr1, int s1, int e1, int[] arr2, int s2, int e2) { if (arr1 == null || arr2 == null) { return -1; } int mid1 = 0; int mid2 = 0; int offset = 0; while (s1 < e1) { mid1 = (s1 + e1) / 2; mid2 = (s2 + e2) / 2; offset =...

import java.util.Scanner; public class Main { public static String getString(char[]chs,int n){ if(chs==null||chs.length==0||n<1){ return ""; } int cur=1; int base= chs.length; int len=0; while (n>=cur){ len++; n-=cur; cur*=base; } char[] res=new char[len]; int index=0; int nCur=0; do...

public class h9a14 { static public int[] p;//根节点 static public int[] rank;//秩 public static void init(int n) { //初始化p[i]：第i个集合的根节点[第1个——第N个集合] p = new int[n + 1]; for (int i = 0; i < p.length; i++) { p[i] = i; } //ran[i]：第i个集合一共有多少个元素 rank = new int[n + 1]; for (int i = 0; i < rank.length; i++...

/*方法1 时间复杂度O(N^2) i位置上方的水= max{min{i左侧最大值，i右侧最大值}-arr[i],0} * */ public static int getWater1(int[] arr) { if (arr == null || arr.length < 3) { return 0; } int res = 0; for (int i = 1; i < arr.length - 1; i++) { int leftMax = 0; int rightMax = 0; for (int j = 0; j < i; j++) { leftMax = Math....

import java.util.Comparator; import java.util.PriorityQueue; import java.util.Scanner; public class Main { public static class Program { public int cost; public int profit; public Program(int cost, int profit) { this.cost = cost; this.profit = profit; } } //定义小根堆如何比较大小 public static class costMinCom...

import java.util.Scanner; public class Main { public static int maxGap(int[] nums) { if (nums == null || nums.length < 2) { return 0; } int len = nums.length; int min = Integer.MAX_VALUE; int max = Integer.MIN_VALUE; for (int i = 0; i < len; i++) { min = Math.min(min, nums[i]); max = Math.max(...

import java.util.*; public class Main { public static int minPathValue(int[][] m) { if (m == null || m.length == 0 || m[0].length == 0 || m[0][0] != 1 || m[m.length - 1][m[0].length - 1] != 1) { return -1; } int res = -1; int[][] map = new int[m.length][m[0].length]; map[0][0] = 1; Queue<Integer&...

import java.util.Scanner; public class Main { /*1、一共N*N个位置，复杂度O(N^2) 2、对于每一个位置，检测是否有边长为1---N的正方形 复杂度O(N) 3、如何检测，复杂度O(1) 时间复杂度为O(n^3) 空间复杂度为O(n^2) * */ public static int getMaxSize(int[][] m) { int[][] right = new int[m.length][m[0].length]; int[][] down = new int[m.length][m[0].length]; setBorderMap...

import java.util.*; public class Main{ public static int maxLen1(int[] arr, int k) { if (arr == null || arr.length == 0) { return 0; } int[] minSums = new int[arr.length]; int[] minSumEnds = new int[arr.length]; minSums[arr.length - 1] = arr[arr.length - 1]; minSumEnds[arr.length - 1] = arr.length -...

import java.util.Scanner; public class Main { /*方法1：a^a=0 a^0=a 异或满***换律 * */ public static int printOdd1(int[] arr) { int e0 = 0; for (int cur : arr) { e0 ^= cur; } return e0; } public static void main(String[] args) { Scanner in=new Scanner(System.in); int n=in.nextInt(); int[] arr=new int[n]; for...

import java.util.Scanner; import java.io.*; public class Main { public static void main(String[] args){ Scanner in=new Scanner(System.in); int a=in.nextInt(); int b=in.nextInt(); // a=a^b; // b=a^b; // a=a^b; a=a+b; b=a-b; a=a-b; System.out.println(a+" "+b); } }

/*方法3：快速幂 时间复杂度O(logN) 取模的话在乘法除加上即可 * */ public static int getNum3(int n) { if (n < 1) { return 0; } if (n == 1 || n == 2) { return n; } int[][] base = {{1, 1}, {1, 0}}; int[][] res = matrixPower(base, n - 2); return 2 * res[0][0] + res[1][0]; } //求矩阵m的p次方 public static int[][] matrixPower(int[][...

import java.util.Scanner; public class Main { /*1、基础： dp[i][j]：表示str[i...j]最少添加几个字符使得str[i...j]是回文串 时间复杂度O(N^2),空间复杂度O(N^2) * */ public static int[][] getDP(char[] str) { int[][] dp = new int[str.length][str.length]; for (int j = 1; j < str.length; j++) { dp[j - 1][j] = str[j - 1] == str[j] ? 0 :...

import java.util.Scanner; public class Main { public static void reverse(char[] chas, int start, int end) { char tmp = 0; while (start < end) { tmp = chas[start]; chas[start] = chas[end]; chas[end] = tmp; start++; end--; } } /*补充 字符数组chas和一个整数size，把大小为size的坐班去整体移动到右半区 ABCDE size=3 DEABC 1.[0,size...