Fork me on GitHub

笔经整理2

Posted on | Edited on | In | Views:

题目来源：牛客网

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
37
38
39


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

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
68
69
70

// 题目二：

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
70
71
72
// 题目三：

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-------------