链家2018春招Java工程师编程题题解.md

武培轩 2020年02月06日 53次浏览

Light

题目描述

在小红家里面,有n组开关,触摸每个开关,可以使得一组灯泡点亮。现在问你,使用这n组开关,最多能够使得多少个灯泡点亮呢?

输入

第一行一个n,表示有n组开关。接下来n行,每行第一个整数为k,表示这个开关控制k个灯泡,接下来k个整数,表示控制的灯泡序号。

满足:1<=n<=1000 、1<=k<=1000 、序号是在int范围内正整数。

输出

输出最多多少个灯泡点亮。

样例输入

3

1 1

1 2

2 1 2

样例输出

2

思路

这道题是一个去重的问题,即多个开关可能按下都使同一个开关亮,那么可以利用HashSet去重。

代码实现

package lianjia.demo1;

import java.util.HashSet;
import java.util.Scanner;

/**
 * 题目描述:
 * 在小红家里面,有n组开关,触摸每个开关,可以使得一组灯泡点亮。
 * 现在问你,使用这n组开关,最多能够使得多少个灯泡点亮呢?
 * 输入
 * 第一行一个n,表示有n组开关。
 * 接下来n行,每行第一个整数为k,表示这个开关控制k个灯泡,接下来k个整数,表示控制的灯泡序号。
 * 满足:
 * 1<=n<=1000
 * 1<=k<=1000
 * 序号是在int范围内正整数。
 * 输出
 * 输出最多多少个灯泡点亮。
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k;
        int x;
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < n; i++) {
            k = sc.nextInt();
            for (int j = 0; j < k; j++) {
                x = sc.nextInt();
                set.add(x);
            }
        }
        System.out.println(set.size());
    }
}

triangle

题目描述

在迷迷糊糊的大草原上,小红捡到了n根木棍,第i根木棍的长度为i,小红现在很开心。她想选出其中的三根木棍组成美丽的三角形。但是小明想捉弄小红,想去掉一些木棍,使得小红任意选三根木棍都不能组成三角形。请问小明最少去掉多少根木棍呢?

输入

本题包含若干组测试数据。对于每一组测试数据。第一行一个n,表示木棍的数量。满足 1<=n<=100000

输出

输出最少数量

样例输入

4

样例输出

1

思路

如果两边和大于第三边,那么要去掉的木棍数加1,否则都加1,继续判断

代码实现

package lianjia.demo2;

import java.util.Scanner;

/**
 * 题目描述:
 * 在迷迷糊糊的大草原上,小红捡到了n根木棍,第i根木棍的长度为i,小红现在很开心。
 * 她想选出其中的三根木棍组成美丽的三角形。
 * 但是小明想捉弄小红,想去掉一些木棍,使得小红任意选三根木棍都不能组成三角形。
 * 请问小明最少去掉多少根木棍呢?
 * 输入
 * 本题包含若干组测试数据。
 * 对于每一组测试数据。
 * 第一行一个n,表示木棍的数量。
 * 满足 1<=n<=100000
 * 输出
 * 输出最少数量
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int i, n;
        int count = 0;
        int a = 2;
        int b = 3;
        while (sc.hasNext()) {
            n = sc.nextInt();
            for (i = 4; i <= n; i++) {
                if (a + b > i) {
                    count++;
                } else {
                    a = b;
                    b = i;
                }
            }
            System.out.println(count);
            count = 0;
            a = 2;
            b = 3;
        }
    }
}