快手2020秋招笔试真题

1、字母组合

【题目描述】给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合，按照字典序升序排序,如果有重复的结果需要去重给出数字到字母的映射如下（与电话按键相同）。注意1不对应任何字母。

输入描述

输入2-9数字组合，字符串长度 1<=length<=20

输出描述

输出所有组合

示例1

输入

输出

[ad, ae, af, bd, be, bf, cd, ce, cf]

示例2

输入

输出

[wa, wb, wc, xa, xb, xc, ya, yb, yc, za, zb, zc]

示例3

输入

输出

[gjt, gju, gjv, gkt, gku, gkv, glt, glu, glv, hjt, hju, hjv, hkt, hku, hkv, hlt, hlu, hlv, ijt, iju, ijv, ikt, iku, ikv, ilt, ilu, ilv]

【解题思路】

直接深搜递归暴力枚举所有情况。

【参考代码】

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        TreeSet<String> s = new TreeSet<>(letterCombinations(str));
        System.out.println(s);
    }
 
    // 定义每个数字对应的字符
    static String[] a = new String[] { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
    static StringBuffer sb = new StringBuffer();
 
    public static List<String> letterCombinations(String digits) {
        if (digits.length() == 0) {
            return null;
        }
        List<String> answer = new ArrayList<String>();
 
        // 开始回溯
        zuhe(digits, 0, answer);
        return answer;
    }
 
    private static void zuhe(String digits, int n, List<String> answer) {
        if (n == digits.length()) {
            answer.add(sb.toString());
            return;
        }
        for (int i = 0; i < a[digits.charAt(n) - '0'].length(); i++) {
            sb.append(a[digits.charAt(n) - '0'].charAt(i));
            zuhe(digits, n + 1, answer);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
 
}

2、字符统计

【题目描述】统计字符串（字符串最大长度<=100000）中字符出现的次数，并按出现次数降序输出。

输入描述

Ababca

输出描述

a:3,b:2,c:1

示例1

输入

Ababca

输出

a:3,b:2,c:1

【解题思路】

直接使用计数排序统计。

【参考代码】

# coding=utf-8
s = input()
 
d = {i: 0 for i in set(s)}
for n in s:
    d[n] += 1
r = [{'k': k, 'v': v} for k, v in d.items()]
r = sorted(r, key=lambda x: x['v'], reverse=True)
print(','.join([str(x["k"])+":"+str(x["v"]) for x in r]))

3、石头碰撞

【题目描述】给定一组石头，每个石头有一个正数的重量。每一轮开始的时候，选择两个石头一起碰撞，假定两个石头的重量为x，y，x<=y,碰撞结果为：
1. 如果x==y，碰撞结果为两个石头消失。
2. 如果x != y，碰撞结果两个石头消失，生成一个新的石头，新石头重量为y-x。
最终最多剩下一个石头为结束。求解最小的剩余石头质量的可能性是多少。

输入描述

第一行输入石头个数(<=100)
第二行输入石头质量，以空格分割，石头质量总和<=10000

输出描述

最终的石头质量

示例1

输入