科大讯飞/奇安信/大疆测试工程师8.15-16在线笔试编程题

- 科大讯飞
1、一只铁杆顶端，有一只蜗牛。第一天先滑落当前距离的一半，再滑落3米，第二天先滑落当前距离的一半，再滑落3米，第三天先滑落当前距离的一半，再滑落6米，第四天先滑落当前距离的一半，再滑落9米，第五天先滑落当前距离的一半，再滑落15米。以此内推，直至滑落到地面。给定滑落到地面的天数，求铁杆的最大高度（不会大于4G）。
输入描述：一个数字，表明滑落至地面的天数，小于36
输出描述：一个数字，表明铁杆最大的高度

#include<iostream>
#include<vector>
unsing namespace std;
int main(){
    int n;
    cin>>n;
    vector<int> day_h(n+1, 0);
    day_h[1] = 3;
    for(int i = 2; i < n+1; i++)
        day_h[i] = day_h[i - 1] + day_h[i - 2];
    double ans = day_h[n];
    for(int i = n; i > 0; i++){
        ans *= 2;
        ans += day_h[i-1];
    }
    cout<<ans;
}

2、为了节约存储容量，需要压缩字符串，请编写一段程序，可以将字符串（任意长度）按照如下规则压缩并输出。
压缩规则为：相同字符连续，则压缩为“数字个数+字符”，如“aaabb”压缩为“3a2b”
输入描述：随机字符串
输出描述：按照规则压缩之后的字符串
- 奇安信
1、老板一共需要给某个员工发奖金n元，可以选择一次发1元，也可以选择一次发2元……老板也可以选择一次发n元（必须以元为整数单位发放）。请问老板给这位员工发放完n元奖金共有多少种方法？
示例1：一共有2元奖金，有两种发放方法，第一种：分别每次发放1元，两次发放完，第二种：一次全部发放完
输入：2
输出：2
示例2：一共有3元奖金，有4种发放方法，第一种：分别每次发放一元，3次发放完，第二种先第一次发2元，第二次发1元，第三种第一次发1元，第二次发2元，第四种：一次全部发放完
输入：3
输出：4
注：输入参数为一个整数数字，输出为一个整数数字

def CalulateMethod(num_money):
    #
    # @param num_money int整型 奖金的总数,单位为元
    # @return int整型
    #
    # write code here
    if num_money == 0:
        print(0, end="")
    else:
        dp = [0 for i in range(max(num_money + 1, 3))]
        dp[0] = 0
        dp[1] = 1
        dp[2] = 2
        i = 3
        while i <= num_money:
            sum = 0
            j = i - 1
            while j >= 0:
                sum += dp[j]
                j -= 1
            dp[i] = sum + 1
            i += 1
        print(dp[num_money])


if __name__ == "__main__":
    num_money = int(input())
    CalulateMethod(num_money)

2、撤销/恢复操作具有广泛的用途，比如word文档中插入一个单词，可以点撤销，然后可以恢复。编程实现如下功能：从标准输入读取到一个字符串，字符串可包含0个或多个单词，单词以空格或者tab分隔；如果遇到“undo”字符串，表示“撤销”操作，前一个字符串被撤销掉；如果遇到“redo”字符串，表示恢复刚才撤销掉的字符串。
例如：输入字符串“hello undo redo word”，对字符串中的undo和redo处理后，最终输出的结果为“hello word”
输入描述：一行字符串：包含0个或多个单词，单词以空格或者tab分隔
输出描述：一行字符串：由0个或多个单词组成，单词以空格分隔
示例1：
输入：hello undo redo world.
输出：hello world.
- 大疆
1、比较两个字符串（str1，str2），如果str1中的字母经过排列组合后，可以组合成str2，则返回True，否则返回False
注意：1、当前方法仅考虑小写字母；2、需要考虑方法的执行效率
例如：
（'rkqodlw','world'）——True
（'katas','steak'）——False

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class checkSame{
    public static boolean judge(String str1, String str2){
        if(str1 == null || str2 == null){
            return false;
        }
        Map<Character, Integer> charCount = new HashMap<>();
        for(char ch : str1.toCharArray()){
            Integer count = charCount.getOrDefault(ch,0);
            charCount.put(ch, count + 1);
        }
        for(char ch : str2.toCharArray()){
            Integer count = charCount.getOrDefault(ch, 0);
            if(count < 1){
                return false;
            }
            charCount.put(ch, count - 1);
        }
        return true;
    }
    public static void main(String[]args){
        Scanner s = new Scanner(System.in);
        while(s.hasNextLine()){
            String str1 = s.nextLine();
            String str2 = s.nextLine();
            System.out.println(judge(str1, str2)?"True":"False");
        }
        s.close();
    }
}