百度2017春招筆試真題編程題集合
買帽子 數(shù)據(jù)結(jié)構(gòu)
度度熊想去商場(chǎng)買一頂帽子挟纱，商場(chǎng)里有N頂帽子，有些帽子的價(jià)格可能相同吟策。度度熊想買一頂價(jià)格第三便宜的帽子棠绘，問(wèn)第三便宜的帽子價(jià)格是多少？
輸入描述:
首先輸入一個(gè)正整數(shù)N（N <= 50）叽躯，接下來(lái)輸入N個(gè)數(shù)表示每頂帽子的價(jià)格（價(jià)格均是正整數(shù)财边，且小于等于1000）
輸出描述:
如果存在第三便宜的帽子，請(qǐng)輸出這個(gè)價(jià)格是多少点骑，否則輸出-1
輸入例子1:
10
10 10 10 10 20 20 30 30 40 40
輸出例子1:
30
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.TreeSet;
/**
* 思路：利用數(shù)據(jù)結(jié)構(gòu)酣难，找出第三大的數(shù)即可
*/
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
int inputCount;
Integer result;
TreeSet<Integer> set = new TreeSet();
while (in.nextToken() != StreamTokenizer.TT_EOF) {
inputCount = (int) in.nval;
while (inputCount-- != 0) {
in.nextToken();
set.add((int) in.nval);
}
set.pollFirst();
set.pollFirst();
result = set.pollFirst();
out.println(result == null ? -1 : result);
}
out.flush();
}
}
度度熊回家 貪心
一個(gè)數(shù)軸上共有N個(gè)點(diǎn)，第一個(gè)點(diǎn)的坐標(biāo)是度度熊現(xiàn)在位置黑滴，第N-1個(gè)點(diǎn)是度度熊的家『┠迹現(xiàn)在他需要依次的從0號(hào)坐標(biāo)走到N-1號(hào)坐標(biāo)。
但是除了0號(hào)坐標(biāo)和N-1號(hào)坐標(biāo)袁辈，他可以在其余的N-2個(gè)坐標(biāo)中選出一個(gè)點(diǎn)菜谣，并直接將這個(gè)點(diǎn)忽略掉，問(wèn)度度熊回家至少走多少距離晚缩？
輸入描述:
輸入一個(gè)正整數(shù)N, N <= 50尾膊。
接下來(lái)N個(gè)整數(shù)表示坐標(biāo)，正數(shù)表示X軸的正方向橡羞，負(fù)數(shù)表示X軸的負(fù)方向眯停。絕對(duì)值小于等于100
輸出描述:
輸出一個(gè)整數(shù)表示度度熊最少需要走的距離。
輸入例子:
4
1 4 -1 3
輸出例子:
4
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
/**
* 貪心思想
*
* 問(wèn)：忽略一個(gè)點(diǎn)卿泽，回家至少多少距離（至少多少距離 = 總距離 - 最大縮短距離）莺债？
* 縮短距離 = 三點(diǎn)之間的間隔和 - 忽略中間點(diǎn)之后的間隔和
*
* 答：忽略一個(gè)點(diǎn)之后，總距離必須是縮短的最多签夭。
*/
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
int inputN;
int arr[] = new int[55];
while (in.nextToken() != StreamTokenizer.TT_EOF) {
inputN = (int) in.nval;
for (int index = 0; index < inputN; index++) {
in.nextToken();
arr[index] = (int) in.nval;
}
int sum = Math.abs(arr[inputN - 1] - arr[inputN - 2]);
// 最大的縮短距離
int maxReduceLength = 0;
for (int index = 1; index < inputN - 1; index++) {
// 求各兩點(diǎn)之間距離之和
sum += Math.abs(arr[index] - arr[index - 1]);
// 求出三點(diǎn)之間齐邦，若忽略中間的點(diǎn)，計(jì)算出縮短距離
int temp = Math.abs(arr[index] - arr[index - 1]) + Math.abs(arr[index + 1] - arr[index]) - Math.abs(arr[index + 1] - arr[index - 1]);
// 記錄最大的縮短距離是多少
maxReduceLength = maxReduceLength > temp ? maxReduceLength : temp;
}
// 至少需要走的距離 = 總距離 - 最大縮短距離
out.println(sum - maxReduceLength);
}
out.flush();
}
}
尋找三角形 暴力
三維空間中有N個(gè)點(diǎn)第租，每個(gè)點(diǎn)可能是三種顏色的其中之一措拇，三種顏色分別是紅綠藍(lán)，分別用'R', 'G', 'B'表示慎宾。
現(xiàn)在要找出三個(gè)點(diǎn)丐吓，并組成一個(gè)三角形，使得這個(gè)三角形的面積最大趟据。
但是三角形必須滿足：三個(gè)點(diǎn)的顏色要么全部相同券犁，要么全部不同。
輸入描述:
首先輸入一個(gè)正整數(shù)N三維坐標(biāo)系內(nèi)的點(diǎn)的個(gè)數(shù).(N <= 50)
接下來(lái)N行汹碱，每一行輸入 c x y z粘衬，c為'R', 'G', 'B' 的其中一個(gè)。x，y稚新，z是該點(diǎn)的坐標(biāo)勘伺。(坐標(biāo)均是0到999之間的整數(shù))
輸出描述:
輸出一個(gè)數(shù)表示最大的三角形面積，保留5位小數(shù)褂删。
輸入例子:
5
R 0 0 0
R 0 4 0
R 0 0 3
G 92 14 7
G 12 16 8
輸出例子:
6.00000
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Scanner;
/**
* 思路：暴力遍歷所有的點(diǎn)飞醉，看其是否匹配條件，然后再利用海倫公式計(jì)算其面積
*/
public class Main {
static class Point {
// 注意：此處最好設(shè)為 private屯阀，并使用 set & get
String color;
Integer x;
Integer y;
Integer z;
}
private static boolean isMatch(String color1, String color2, String color3) {
if (color1.equals(color2) && color1.equals(color3) || !color1.equals(color2) && !color1.equals(color3) && !color2.equals(color3)) {
return true;
}
return false;
}
/**
* 海倫公式求面積:s = sqrt(p* (p-a) * (p-b) * (p-c)) 其中 p=(a+b+c) / 2
*/
private static double heron(Point pointA, Point pointB, Point pointC) {
double a = distance(pointA, pointB);
double b = distance(pointA, pointC);
double c = distance(pointB, pointC);
double p = (a + b + c) / 2;
return Math.sqrt(p * (p - a) * (p - b) * (p - c));
}
private static double distance(Point pointA, Point pointB) {
return Math.sqrt((pointA.x - pointB.x) * (pointA.x - pointB.x) + (pointA.y - pointB.y) * (pointA.y - pointB.y) + (pointA.z - pointB.z) * (pointA.z - pointB.z));
}
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
int inputN;
Point[] points = new Point[55];
double result;
while (in.hasNext()) {
inputN = in.nextInt();
result = 0;
for (int index = 0; index < inputN; index++) {
points[index] = new Point();
points[index].color = in.next();
points[index].x = in.nextInt();
points[index].y = in.nextInt();
points[index].z = in.nextInt();
}
for (int indexI = 0; indexI < inputN - 2; indexI++) {
for (int indexJ = indexI + 1; indexJ < inputN - 1; indexJ++) {
for (int indexK = indexJ + 1; indexK < inputN; indexK++) {
if (isMatch(points[indexI].color, points[indexJ].color, points[indexK].color)) {
double temp = heron(points[indexI], points[indexJ], points[indexK]);
if (result < temp) {
result = temp;
}
}
}
}
}
out.printf("%.5f",result);
out.println();
}
out.flush();
}
}
有趣的排序 貪心 逆向思維
度度熊有一個(gè)N個(gè)數(shù)的數(shù)組冒掌，他想將數(shù)組從大到小排好序，但是萌萌的度度熊只會(huì)下面這個(gè)操作：
任取數(shù)組中的一個(gè)數(shù)然后將它放置在數(shù)組的最后一個(gè)位置蹲盘。
問(wèn)最少操作多少次可以使得數(shù)組從小到大有序股毫？
度度熊有一個(gè)N個(gè)數(shù)的數(shù)組，他想將數(shù)組從大到小排好序召衔，但是萌萌的度度熊只會(huì)下面這個(gè)操作：
任取數(shù)組中的一個(gè)數(shù)然后將它放置在數(shù)組的最后一個(gè)位置铃诬。
問(wèn)最少操作多少次可以使得數(shù)組從小到大有序？
輸入描述:
首先輸入一個(gè)正整數(shù)N苍凛，接下來(lái)的一行輸入N個(gè)整數(shù)趣席。(N <= 50, 每個(gè)數(shù)的絕對(duì)值小于等于1000)
輸出描述:
輸出一個(gè)整數(shù)表示最少的操作次數(shù)。
輸入例子:
4
19 7 8 25
輸出例子:
2
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;
/**
* 貪心思路 + 逆向思維
*
* 貪心的思路：移動(dòng)的方式醇蝴，選擇最優(yōu)的思路宣肚，那么移動(dòng)的次數(shù)肯定是最少的。
*
* 最優(yōu)的思路：對(duì)于數(shù)組中的第 i 個(gè)元素悠栓，如果它后面有比它小的元素霉涨，這就說(shuō)明第 i 個(gè)元素理應(yīng)被移動(dòng)到末尾去。
* 另外惭适，應(yīng)該優(yōu)先移動(dòng)較小的元素笙瑟，這樣才能夠保證較小元素最后排在最前面。
*
* 步驟：①癞志、用一個(gè)備份數(shù)組 b往枷，把 a 中元素放到b中，對(duì) b 數(shù)組進(jìn)行排序凄杯。
* ②错洁、用備份數(shù)組 b 中（排好序的）第 j 個(gè)依次與原數(shù)組 a （輸入順序）中的第 i++ 個(gè)元素比較
* i、若 a[i] == b[j]戒突，則 count++;j++
* ③屯碴、統(tǒng)計(jì)出一共有 count 個(gè)，這些元素是不需要移動(dòng)的元素妖谴，一共有 n 個(gè)元素窿锉，所以需要移動(dòng) n - count 次
*
* 偽代碼：
* b = copy a
* sort b
* for i = 0 to n & j < n do
* if a[i] == b[j] then
* j++;
* count++;
* endif
* end
*/
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
int inputN;
int[] arr = new int[55];
int[] aux = new int[55];
while (in.nextToken() != StreamTokenizer.TT_EOF) {
inputN = (int) in.nval;
for (int index = 0; index < inputN; index++) {
in.nextToken();
arr[index] = (int) in.nval;
aux[index] = arr[index];
}
Arrays.sort(arr, 0, inputN);
int indexJ = 0;
int count = 0;
for (int indexI = 0; indexI < inputN && indexJ < inputN; indexI++) {
if (aux[indexI] == arr[indexJ]) {
indexJ++;
count++;
}
}
out.println(inputN - count);
}
out.flush();
}
}
不等式數(shù)列 動(dòng)態(tài)規(guī)劃
度度熊最近對(duì)全排列特別感興趣,對(duì)于1到n的一個(gè)排列,度度熊發(fā)現(xiàn)可以在中間根據(jù)大小關(guān)系插入合適的大于和小于符號(hào)(即 '>' 和 '<' )使其成為一個(gè)合法的不等式數(shù)列。但是現(xiàn)在度度熊手中只有k個(gè)小于符號(hào)即('<'')和n-k-1個(gè)大于符號(hào)(即'>'),度度熊想知道對(duì)于1至n任意的排列中有多少個(gè)排列可以使用這些符號(hào)使其為合法的不等式數(shù)列膝舅。
輸入描述:
輸入包括一行,包含兩個(gè)整數(shù)n和k(k < n ≤ 1000)
輸出描述:
輸出滿足條件的排列數(shù),答案對(duì)2017取模嗡载。
輸入例子:
5 2
輸出例子:
66
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
/**
* 動(dòng)態(tài)規(guī)劃
*
* dp[i][j] 表示有 i 個(gè)數(shù)字及 j 個(gè)小于號(hào)所能組成的數(shù)量。
*
* 當(dāng)加入第 i 個(gè)數(shù)字時(shí)：
* ①仍稀、加在不等式開(kāi)頭：即 1 < 2 ==> 3 > 1 < 2 此時(shí)就等同于加入了一個(gè)大于號(hào)
* ②洼滚、加在不等式末尾：即 1 < 2 ==> 1 < 2 < 3 此時(shí)就等同于加入了一個(gè)小于號(hào)
* ③、加在不等式中間：
* i技潘、不等號(hào)為小于號(hào)：即 1 < 2 ==> 1 < 3 > 2 此時(shí)就等同于加入了一個(gè)大于號(hào)遥巴，但對(duì)于中間的每個(gè)小于號(hào)，都可以執(zhí)行這樣一次插入享幽。
* ii铲掐、不等號(hào)為大于號(hào)：即 1 > 2 ==> 1 < 3 > 2 此時(shí)就等同于加入了一個(gè)小于號(hào)，但對(duì)于中間的每個(gè)大于號(hào)值桩，都可以執(zhí)行這樣一次插入摆霉。
*
* 綜上所述，dp[i][j] 等于以上四種情況之和：
* dp[i][0] = 1; 沒(méi)有不等號(hào)時(shí)奔坟，只有一種不等式組合携栋。
* dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + dp[i-1][j] * j + dp[i-1][j-1] * (i-j+1)
* = dp[i-1][j] * (j+1) + dp[i-1][j-1] * (i-j)
*
* 結(jié)果記得 mod 2017
*/
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
int inputN;
int inputK;
// 表示有 i 個(gè)數(shù)字及 j 個(gè)小于號(hào)所能組成不等式的數(shù)量
int[][] dp = new int[1005][1005];
while (in.nextToken() != StreamTokenizer.TT_EOF) {
inputN = (int) in.nval;
in.nextToken();
inputK = (int) in.nval;
dp[1][0] = 1;
// 從 dp[2][1] 開(kāi)始
for (int indexI = 2; indexI <= inputN; indexI++) {
dp[indexI][0] = 1;
for (int indexJ = 1; indexJ <= inputK; indexJ++) {
dp[indexI][indexJ] = (dp[indexI - 1][indexJ - 1] * (indexI - indexJ) + dp[indexI - 1][indexJ] * (indexJ + 1)) % 2017;
}
}
out.println(dp[inputN][inputK] % 2017);
}
out.flush();
}
}
