Fork me on GitHub

笔经整理2

题目来源:牛客网

1. [编程题] 连续最大和

时间限制:1秒
空间限制:32768K

一个数组有 N 个元素,求连续子数组的最大和。 例如:[-1,2,1],和最大的连续子数组为[2,1],其和为 3

输入描述:
输入为两行。 第一行一个整数n(1 <= n <= 100000),表示一共有n个元素 第二行为n个数,即每个元素,每个整数都在32位int范围内。以空格分隔。

输出描述:
所有连续子数组中和最大的值。

输入例子1:

3 -1 2 1

输出例子1:

3

思路:

  1. 维护一个长度为 n 的 num 数组,数组含义:以该元素为末尾的连续子集的最大和;
  2. 判断条件,如果 i-1 处的”最大和”加上num[i] 会使”最大和”有所增加,则更新”最大和”。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.Scanner;

public class Main{
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int max = -0x3ffffff;
int[] num = new int[n];
for (int i = 0; i < n; ++i) {
int t = input.nextInt();
num[i] = t;
if (i > 0) {
if (num[i] + num[i - 1] > num[i]) {
num[i] = num[i] + num[i - 1];
}
}
if (num[i] > max) {
max = num[i];
}
}
System.out.println(max);
}
}

2. [编程题]餐馆

某餐馆有n张桌子,每张桌子有一个参数:a 可容纳的最大人数; 有m批客人,每批客人有两个参数:b人数,c预计消费金额。 在不允许拼桌的情况下,请实现一个算法选择其中一部分客人,使得总预计消费金额最大
输入描述:

输入包括m+2行。 第一行两个整数n(1 <= n <= 50000),m(1 <= m <= 50000) 第二行为n个参数a,即每个桌子可容纳的最大人数,以空格分隔,范围均在32位int范围内。 接下来m行,每行两个参数b,c。分别表示第i批客人的人数和预计消费金额,以空格分隔,范围均在32位int范围内。

输出描述:

输出一个整数,表示最大的总预计消费金额
示例1

输入

3 5 2 4 2 1 3 3 5 3 7 5 9 1 10

输出

20

思路关键点:

  1. 二维数组的 sort 方法(使用 Comparator);
  2. 有序数组的二分查找
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
package org.written.program;


import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Test {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
while(input.hasNext()) {
int n = input.nextInt();
int m = input.nextInt();
int[] desk = new int[n];
for (int i = 0; i < n; ++i) {
desk[i] = input.nextInt();
}
Arrays.sort(desk);
int maxDesk = desk[n - 1];

int[][] cus = new int[m][2];
for (int j = 0; j < m; ++j) {
cus[j][0] = input.nextInt();
cus[j][1] = input.nextInt();
}
Arrays.sort(cus, new Comparator<int[]>() {
@Override
public int compare(int[] a, int[] b) {
return b[1] - a[1];
}
});

// 计算最大金额
Long sum = 0l;
int index;
boolean[] tableNum = new boolean[n];
for (int i = 0; i < m; ++i) {
if (cus[i][0] > maxDesk) {
continue; // 超过桌子容纳数量,跳过
}

index = bs(desk, cus[i][0]);
while (index < n && tableNum[index] == true) {
index++;
}

if (index < n) {
sum += cus[i][1];
tableNum[index] = true; // 去重
}
}

System.out.println(sum);
}
input.close();
}

// 二分查找
private static int bs(int[] num, int tar) {
int low = 0;
int high = num.length - 1;
int mid;
while (low <= high) {
mid = (high + low) >> 1;
if (num[mid] >= tar)
high = mid - 1;
else
low = mid + 1;
}

return low;
}

}

3. 最大乘积

给定一个无序数组,包含正数、负数和0,要求从中找出3个数的乘积,使得乘积最大,要求时间复杂度:O(n),空间复杂度:O(1)

输入描述:
无序整数数组A[n]

输出描述:
满足条件的最大乘积

输入例子1:
3 4 1 2

输出例子1:
24

思路:听说用long就能解决,我这里用BigInteger算牛刀杀鸡了。

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


import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String str = sc.nextLine();
String[] strings = str.split("\\s+");
if (strings == null) {
continue;
}
if (strings.length < 3) {
continue;
}
BigInteger[] arg = new BigInteger[strings.length];
for (int i = 0; i < arg.length; ++i) {
arg[i] = BigInteger.valueOf(new Long(strings[i]));
}
Arrays.sort(arg);
BigInteger max = BigInteger.valueOf(0);
max = arg[0].multiply(arg[1]).multiply(arg[2]).max(max);
max = arg[0].multiply(arg[1]).multiply(arg[arg.length - 1]).max(max);
max = arg[0].multiply(arg[arg.length - 2]).multiply(arg[arg.length - 1]).max(max);
max = arg[arg.length - 3].multiply(arg[arg.length - 2]).multiply(arg[arg.length - 1]).max(max);

System.out.println(max);
}
}


}

私下练习(蛮好的题目):

1. 试题一

自定义函数,实现求解任意整数的幂运算,例如2^9, 3^(-5).

最佳要求:时间复杂度log N.

2. 试题二

给定一个m位的正整数n,2≤m≤15,可以通过交换任意两个数位上数字的位置使其尽可能比原来数字大。求k次交换后,可以获得最大的数字。

注意:每次交换时,不能使第一个数位上的数字为0.

例如:输入1374,2 输出为7413,表示1374经过两次数位交换,可以获得的最大数字为7413。

3. 试题三

给定任意一维数组,如{1, 4, 3, 5, 9, 12, 11, 14, 17}。该数组可能是有序的,也可能是无序的。请写一个函数,求出将该数组变成有序数组时,最少需要重新排序的元素个数。例如{1, 4, 3, 5, 9, 12, 11, 14, 17},输出结果为:6,需要对{4, 3, 5, 9, 12, 11}重新排序。

最佳要求:时间复杂度O(N),空间复杂度O(1)。

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
45
// 题目一

import java.util.Scanner;

/**
* 自定义函数,实现求解任意整数的幂运算,例如2^9, 3^(-5).
* <p>
* 最佳要求:时间复杂度log N.
*/
public class Question1 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
long a = sc.nextInt();
long b = sc.nextInt();
boolean flag = true; // true 表示 b 为正数
if (b < 0) {
flag = false;
b = -b;
}
long result = getPower(a, b);
if (flag == false) {
System.out.println(1.0 / result);
} else {
System.out.println(result);
}
}
}

// 快速降幂
public static long getPower(long a, long b) {
long result = 1;

while (b > 0) {
if ((b & 1) == 1) {
result = a * result;
}
a = a * a;
b = b >> 1;
}
return result;
}


}

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

// 题目二:

import java.util.Scanner;

/**
* 给定一个m位的正整数n,2≤m≤15,可以通过交换任意两个数位上数字的位置使其尽可能比原来数字大。求k次交换后,可以获得最大的数字。
* <p>
* 注意:每次交换时,不能使第一个数位上的数字为0.
* <p>
* 例如:输入1374,2 输出为7413,表示1374经过两次数位交换,可以获得的最大数字为7413。
*/
public class Question2 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int m = sc.nextInt();
int n = sc.nextInt();
int length = String.valueOf(m).length();
int[] num = new int[length];
// 转换为数组
for (int i = length - 1; i >= 0; --i) {
num[i] = m % 10;
m /= 10;
}
int count = 0;// 交换计数
int index = 0;// 遍历索引
while (true) {
if (count >= n || index >= length) {
break;
}

// 找到最大数及角标
int max = 0;
int maxIndex = -1;
for (int i = index + 1; i < length; ++i) {
if (num[i] > max) {
max = num[i];
maxIndex = i;
}
}
if (maxIndex != -1) {
// 交换
exchange(num, index, maxIndex);
++count;
}

++index;
}

for (int i = 0; i < length; ++i) {
System.out.print(num[i]);
}
System.out.println();
}
}

public static void exchange(int[] num, int index, int maxIndex) {
if (index == maxIndex) {
return;
}
int temp = num[index];
num[index] = num[maxIndex];
num[maxIndex] = temp;
}

}

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
// 题目三:

import java.util.Scanner;

import static java.lang.Math.abs;

/**
* 给定任意一维数组,如{1, 4, 3, 5, 9, 12, 11, 14, 17}。
* 该数组可能是有序的,也可能是无序的。请写一个函数,求出将该数组变成有序数组时,最少需要重新排序的元素个数。
* 例如{1, 4, 3, 5, 9, 12, 11, 14, 17},输出结果为:6,需要对{4, 3, 5, 9, 12, 11}重新排序。
* <p>
* 最佳要求:时间复杂度O(N),空间复杂度O(1)。
*/
public class Question3 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String input = sc.nextLine();
String[] strs = input.split(" ");
int[] nums = new int[strs.length];
for (int i = 0; i < strs.length; ++i) {
nums[i] = Integer.parseInt(strs[i]);
}

boolean flag = true; // 默认增序
if (nums[0] > nums[nums.length - 1]) {
// 降序
flag = false;
}

int maxIndex = flag ? 0 : nums.length - 1;
int minIndex = flag ? nums.length - 1 : 0;

int max = nums[maxIndex];
int min = nums[minIndex];

if (flag) {
for (int i = 0; i < nums.length; ++i) {
int j = nums.length - i - 1;
if (nums[i] >= max) {
max = nums[i];
} else {
maxIndex = i;
}
if (nums[j] < min) {
min = nums[j];
} else {
minIndex = j;
}
}
} else {
for (int i = 0; i < nums.length; ++i) {
int j = nums.length - i - 1;
if (nums[j] >= max) {
max = nums[j];
} else {
maxIndex = j;
}
if (nums[i] < min) {
min = nums[i];
} else {
minIndex = i;
}
}
}
int result = abs(maxIndex - minIndex) + 1;
System.out.println(result);

}
}
-------------The End-------------