笔试合集1

数组中的逆序对 例如： 7564 75 64 7 5 6 4 57 46 count=2 (5<7, 4<6) 4567 count=5 (5>4, 7>4,6)

public class Solution { int cnt; public int InversePairs(int[] array) { cnt = 0; if (array != null) mergeSortUp2Down(array, 0, array.length - 1); return cnt; } /* * 归并排序(从上往下) */ public void mergeSortUp2Down(int[] a, int start, int end) { if (start >= end) return; int mid = (start + end) >> 1; mergeSortUp2Down(a, start, mid); mergeSortUp2Down(a, mid + 1, end); merge(a, start, mid, end); } /* * 将一个数组中的两个相邻有序区间合并成一个 */ public void merge(int[] a, int start, int mid, int end) { int[] tmp = new int[end - start + 1]; int i = start, j = mid + 1, k = 0; while (i <= mid && j <= end) { if (a[i] <= a[j]) tmp[k++] = a[i++]; else { tmp[k++] = a[j++]; cnt += mid - i + 1; // core code, calculate InversePairs............ } } while (i <= mid) tmp[k++] = a[i++]; while (j <= end) tmp[k++] = a[j++]; for (k = 0; k < tmp.length; k++) a[start + k] = tmp[k]; } }

视野争夺 Input:

4 6 3 6 2 4 0 2 4 7

4个range, 范围是0到6。 [[0,2], [2,4], [3,6], [4,7]] range只有两种关系，包含，和不包含。 L=0 count =0 [0,2] count=1 L=2 [2,4] count =2 (2<=L) L=4 [3,6] count = 3 (3, 4 <= L) [4,7] count =3 L=7

Output:

3

import java.util.Arrays; import java.util.Comparator; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in=new Scanner(System.in); int n=in.nextInt(); int L=in.nextInt(); int[][] temp=new int[n][2]; for(int i=0;i<n;i++) { for(int j=0;j<2;j++) { temp[i][j]=in.nextInt(); } } //。获得了数组，进行排序 Arrays.sort(temp,new Comparator<int[]>() { public int compare(int[] o1, int[] o2) { return o1[0]==o2[0]?o1[1]-o2[1]:o1[0]-o2[0]; } }); int index=0; int count=0; int pre=0; //右边界 while(pre<L) { if(temp[index][0]>pre) { //没有从0开始的range System.out.println(-1); } int max=0; while(index<n&&temp[index][0]<=pre) { max=Math.max(max, temp[index][1]); index++; } count++; pre=max; if(pre>=L) { System.out.println(count); return; } if(index>=n) { System.out.println(-1); return; } } } }

假期 动态规划 如果今天可以工作，比较昨天的健身和休息。 如果今天可以健身，比较昨天的工作和休息。 如果今天可以休息，比较昨天的工作，健身和休息。

import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); String day_str = in.nextLine(); String [] work_str = in.nextLine().split(" "); String [] gym_str = in.nextLine().split(" "); int day = Integer.parseInt(day_str); //日期 int [] works = new int[day+1]; int [] gyms = new int[day+1]; for(int i = 1;i < day+1;i++) { works[i] = Integer.parseInt(work_str[i - 1]); gyms[i] = Integer.parseInt(gym_str[i-1]); } int res = holiday(day, works, gyms); System.out.println(res); } public static int holiday(int day, int [] works, int [] gyms){ int res; int [][] dp = new int[day+1][3]; dp[0][0] = dp[0][1] = dp[0][2] = 0; for (int i = 1; i < day+1; i++) { if(works[i] == 1){ //第i天可以选择工作 dp[i][1] = Math.max(dp[i-1][0], dp[i-1][2]) + 1; } if(gyms[i] == 1){ //第i天可以选择健身 dp[i][2] = Math.max(dp[i-1][0], dp[i-1][1]) + 1; } dp[i][0] = Math.max(dp[i-1][0], Math.max(dp[i-1][1], dp[i-1][2])); } res = day - Math.max(dp[day][0], Math.max(dp[day][1], dp[day][2])); return res; } }

逛街 Input

6 5 3 8 3 2 5

Output

3 3 5 4 4 4

i = 5, right[5]=1 i=4, right[4] =2 i=3, right[3] = 2 (3>2, stack.pop()) i=2, right[2] =1 (8>2, 3, 5, stack.pop()) i=1, right[1] = 2 i=0, right[0] = 3

import java.util.*; public class Main { 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(); } // stack中要保存的是 能看见的楼的 index int[] rightLook = new int[len]; Stack<Integer> stack = new Stack<>(); for(int i = len - 1 ; i >= 0 ; i--){ rightLook[i] = stack.size(); while((!stack.isEmpty()) && (arr[i] >= arr[stack.peek()])){ stack.pop(); } stack.push(i); } stack.clear(); for(int i = 0 ; i < len ; i++){ int total = rightLook[i] + 1 + stack.size(); while((!stack.isEmpty()) && (arr[i] >= arr[stack.peek()])){ stack.pop(); } System.out.print(total + " "); stack.push(i); } } }

压缩算法

import java.util.*; public class Main{ public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String next = scanner.next(); scanner.close(); System.out.println(decode(next)); } public static String decode(String words){ while (words.contains("]")){ int right = words.indexOf("]"); int left = words.lastIndexOf("[", right); String repeatStr = words.substring(left+1, right); String[] split = repeatStr.split("\\|"); words = words.replace("["+repeatStr+"]", String.join("", Collections.nCopies(Integer.parseInt(split[0]), split[1]))); } return words; } }

逆序对 Input:

2 2 1 4 3 4 1 2 0 2

Output:

0 6 6 0

https://blog.csdn.net/qq_43517189/article/details/105313349