logo头像
Snippet 博客主题

笔试/面试中遇到的题

字节跳动 5.21

1 反转字符串

Problem

String str = “A retupmoc si a enihcam taht nac eb detcurtsni ot yrrac tuo secneuqes fo citemhtira ro lacigol snoitarepo yllacitamotua aiv retupmoc gnimmargorp”
输出正确的顺序:
A computer is a machine that can be instructed to carry out sequences of arithmetic or logical operations automatically via computer programming

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import java.util.Scanner;
import java.util.Scanner;
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
String str = "A retupmoc si a enihcam taht nac eb detcurtsni ot yrrac tuo secneuqes fo citemhtira ro lacigol snoitarepo yllacitamotua aiv retupmoc gnimmargorp";

String [] arr = str.split(" ");
StringBuilder sb = new StringBuilder();

int len = arr.length;
for(int i=0; i<len-1; i++){

String temp = reverse(arr[i]);

sb.append(temp);
sb.append(" ");

}
sb.append(reverse(arr[len-1]));


System.out.println(sb.toString());

}

public static String reverse(String s){
char [] arr = s.toCharArray();
int len = arr.length;
int l=0;
int r = len-1;
while(l<r){
char temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
l++;
r--;
}
String re = new String(arr,0, len);
return re;


}
}

2 峰值下标

Problem

写一个函数,参数是前升后降的数组,返回值是数组峰值对应的下标,例子[1, 2, 4, 5, 7, 9, 8, 6, 3]

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
//Scanner in = new Scanner(System.in);
//int a = in.nextInt();
//System.out.println(a);
System.out.println("Hello World!");
int[] arr = {1,2,4,5,7,9,8,6,3};
int re = solution(arr);
System.out.println(re);

}
public static int solution(int[] arr){
int l = 0;
int r = arr.length-1;
int m=0;
while(l<=r){
m= l +(r-l)/2;
if(arr[m-1]<arr[m] && arr[m]>arr[m+1]){
break;
}else if(arr[m-1]<arr[m]&& arr[m]<arr[m+1]){
l=m;
}else{
r=m;
}
}
return m;
}
}

3 大于前面最大值,小于后面最小值

Problem

4 3 1 2 7 9 8 10
前面所有的数都比其小,
后面所有的数都比其大

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
//Scanner in = new Scanner(System.in);
//int a = in.nextInt();
//System.out.println(a);
System.out.println("Hello World!");
int [] arr = {4,3,1,2,7,9,8,10};
int count = solution(arr);
System.out.println(count);
}
public static int solution(int [] arr){
int len =arr.length;
int[] min = new int[len];
int[] max = new int[len];
max[0] = arr[0];

for(int i=1; i<len; i++){
max[i] = Math.max(max[i-1], arr[i]);
}
min[len-1] = arr[len-1];
for(int i=len-2; i>=0; i--){
min[i] = Math.min(min[i+1], arr[i]);
}
int count = 0;
if(arr[0]<min[1]){
//System.out.println(arr[0]);
count++;
}
if(arr[len-1]>max[len-2]){
count++;
//System.out.println(arr[len-1]);
}
for(int j =1; j< len-1; j++){
if(arr[j]>max[j-1] && arr[j]<min[j+1]){
count++;
// System.out.println(arr[j]);
}
}
return count;


}
}

拼多多5.6

1

2 火柴拼正方形

3

4

打乱数组

Problem

使用最熟悉的编程语言,实现函数:
数组array,存放着不同的数字,要求:
a) 尽量打乱数组array
b) 数字不能在原位置重复

按照指定步长反转链表

Problem

实现一个函数,给定步长m,每m个节点一组反转单链表,写出函数。

逛街

Problem

小Q在周末的时候和他的小伙伴来到大城市逛街,一条步行街上有很多高楼,共有n座高楼排成一行。
小Q从第一栋一直走到了最后一栋,小Q从来都没有见到这么多的楼,所以他想知道他在每栋楼的位置处能看到多少栋楼呢?(当前面的楼的高度大于等于后面的楼时,后面的楼将被挡住)

例如:m=2,a->b->c->d->e->f 变成 b->a->d->c->f->e

差值数组的最大公约数

Problem

题目描述:
牛牛有一个长度为n的数组a,你要找一个最大的正整数d,使得对于所有i(1≤i≤n),ai+1-ai是
d的倍数,即ai+1-ai=kd(k>1)
输入:
第一行一个正整数n(取值[2,2
100000])
第二行n个正整数a1-an(1≤ai≤10^18)
输出:
若d不存在,输出-1,否则输出最大的d

Solution

  1. 用一个Scanner 来接受第一个数,new 数组,大小为n
  2. 计算差值
    判断每个差值:
    <0: 输出 -1.return
  3. 计算完差值后,判断size大小
    size == 0 : 原数组只有一个数,没有差值,-1 return
    size == 1 : 原数组只有两个数,差值只有一个,那这个值就是最大公约数 return
  4. 普遍情况是由大于等于两个差值
    那就用辗转相除法找其最大公约数(先找两个的,这个结果再与第三个,。。。以此类推);
    注意:10^18超过int(-2^31-1~2^31)范围,用 long

两/多个数字的最大公约数求法:辗转相除法

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;

public class Chazhishuzu {
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long [] input = new long[n];
ArrayList<Long> list = new ArrayList<>();
for(int i =0; i< n; i ++){
input[i] = sc.nextLong();
if(i>=1){
long temp = input[i] - input[0];
if(temp<=0){
System.out.println(-1);
return;
}
list.add(temp);
}
}
if(list.size()==0){
System.out.println(-1);
return;
}
if(list.size()==1){
System.out.println(list.get(0));
}
long res = list.get(0);
for(int i=1; i<list.size(); i++){
res = gcd(res, list.get(i));
}
System.out.println(res);
}
public static long gcd(long a, long b){//辗转相除法
if(b==0){
return a;
}
return gcd(b,a%b);
}
}

找aj减ai的最大值

Problem

有一个数组a,找aj减ai的最大值,且满足j大于i?返回该最大值,以及对应的i,j下标。要求是时间复杂度O(n),空间复杂度O(1)。

Solution

题目的要求是时间复杂度O(n),空间复杂度O(1)。

两个错误的思路要避免,一是数组排序,最好的排序算法时间复杂度也是nlogn,明显达不到要求。另外一个是遍历数组求得最大值和最小值,然后相减,但照顾不到i<=j的条件。

正确的思路是对上述第二个算法的改进,将数组第一个元素设置为最大和最小值(i=j=0),最大差值的初始值max就是0,然后移动j,每次移动都计算a[j]-a[i],如果结果大于max就替换max,小于的话什么都不做,而如果结果小于0,则将i赋值为j,继续上面的操作。最终得到的结果就是正确答案。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class Main {
public static void main(String[] args) {
System.out.println("Hello World!");
int a[] = {6,18,3,98,67,24,0,43,17,17,67,81,49,-15,9};
int[] maxArr = max(a);
System.out.println(maxArr[0]);
System.out.println(maxArr[1]);
System.out.println(maxArr[2]);


}
public static int[] max(int[] arr){
int result = arr[0] - arr[0];
int[] resultArr = new int[3];
int i = 0;
int j = 0;
int resultI = 0;
int resultJ = 0;
for(j=1; j< arr.length;j++){
if(arr[j]- arr[i]>result){
result = arr[j]- arr[i];
resultI = i;
resultJ = j;
}else if(arr[j]- arr[i] < 0){
i = j;
}
}
resultArr[0] = result;
resultArr[1] = resultI;
resultArr[2] = resultJ;
return resultArr;

}
}