2.8143AC字节笔试4.12坑点解析
第一题AC
思路过于简单直接给代码，坑点是，不能把b数组也记录下来（不记录时间复杂度为2n，记录则时间复杂度为3n。。。别问我为什么这么优化，因为没其他地方优化。。。）
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
int[] nums = new int[t];
for (int i = 0; i < t; i++) {
int n = sc.nextInt();
int[] a = new int[n];
for (int j = 0; j < n; j++) {
a[j] = sc.nextInt();
}
boolean res = true;
boolean chan = false;
int k = 0;
int right = 0;
for (int j = 0; j < n; j++) {
int b = sc.nextInt();
if(b == a[j]) continue;
if(a[j] > b){
res = false;
right = n - j - 1;
break;
}
if(a[j] != b){
k = b - a[j];
if(chan){
res = false;
right = n - j - 1;
break;
}else {
while (j < n){
if(a[j] == b){
break;
}
if(a[j] + k != b){
res = false;
break;
}
b = sc.nextInt();
j++;
}
chan = true;
}
}
}
if(res) nums[i] = 1;
else nums[i] = 2;
for (int j = 0; j < right; j++) {
sc.nextInt();
}
}
sc.close();
for (int i = 0; i < t; i++) {
if(nums[i] == 1) System.out.println("YES");
else if(nums[i] == 2)System.out.println("NO");
}
} 第二题0.2
也是很暴力的思路，但是还有一些条件没考虑到，不知道大佬有没有优秀的解法
private static int res = 0;
private static ArrayList<Integer> nums = new ArrayList<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for (int i = 0; i < n; i++) {
nums.add(sc.nextInt());
}
sc.close();
if(n == 1) System.out.println(0);
else {
cut(0);
System.out.println(res);
}
}
private static void cut(int i) {
if(i == nums.size()) return;
if(i == nums.size() - 1){
if(nums.get(i) >= nums.get(i - 1)) return;
cut(i - 1);
}
if(nums.get(i) <= nums.get(i + 1)) cut(i + 1);
else if(i == 0){
int sum = nums.get(i);
int right = nums.get(i + 1);
int curr = sum;
while (curr > right) curr /= 2;
nums.remove(0);
int index = 0;
while (sum > right){
sum -= curr;
nums.add(0, curr);
res++;
index++;
}
nums.add(0, sum);
cut(index);
}else {
int sum = nums.get(i);
int right = nums.get(i + 1);
int left = nums.get(i - 1);
if (sum < left) cut(i - 1);
nums.remove(i);
int index = i;
while (sum > right * 2) {
nums.add(i, right);
res++;
index++;
sum -= right;
}
if (sum > right + left) {
nums.add(i, right);
nums.add(i, sum - right);
res++;
}else {
nums.add(i, left);
nums.add(i, sum - left);
res++;
}
cut(index + 1);
}
} 第三题0.9
也是很暴力的思路。。坑点：1.找优惠券的时候用一下二分查找；2.可能存在没有优惠券可用的情况（所有优惠券面额都大于该价格），对了，不要用数组记录第二个数组，那样会多了m的复杂度
private static int[] cuts;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
cuts = new int[n];
for (int i = 0; i < n; i++) {
cuts[i] = sc.nextInt();
}
Arrays.sort(cuts);
int money = 0;
long res = 0;
for (int i = 0; i < m; i++) {
money = sc.nextInt();
int left = find(money);
while (left >= 0 && cuts[left] > money){
left--;
}
if(left >= 0) res = res + (long) money - (long) cuts[left];
else res = res + (long) money;
}
sc.close();
System.out.println(res);
}
public static int find(int mon){
int left = 0, right = cuts.length - 1;
int mid = (left + right) / 2;
while (left < right){
if(cuts[mid] < mon) left = mid + 1;
else if(cuts[mid] > mon) right = mid - 1;
else return mid;
mid = (left + right) / 2;
}
return left;
} 第四题0.7143
也是暴力。。。。坑点：如果在循环直接输出，ac0.5714，如果记录下结果最后输出0.7143.。。字节今天的题都很简单很暴力，但很烦，而且有很多奇奇怪怪的细节
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
ArrayList<String> ans = new ArrayList<>();
for (int i = 0; i < t; i++) {
int n = sc.nextInt();
int[] nums = new int[n];
for (int j = 0; j < n; j++) {
nums[j] = sc.nextInt();
}
StringBuffer curr = new StringBuffer();
for (int j = 0; j < n; j++) {
int val = nums[j];
int left = j - 1;
int res = 0;
while (left >= 0 && nums[left] <= val){
left--;
res++;
}
int right = j + 1;
while (right < n && nums[right] <= val){
right++;
res++;
}
if(j < n - 1) curr.append(res + " ");
else curr.append(res);
}
ans.add(curr.toString());
}
sc.close();
for (int i = 0; i < ans.size(); i++) {
System.out.println(ans.get(i));
}
} 
腾讯云智研发二面24人在聊