1、字符串重排

时间限制：C/C++ 1秒，其他语言 2s  空间限制：C/C++ 32768K，其他语言 65536K

题目描述

给你一个原始字符串，根据该字符串内每个字符出现的次数，按照ASCII码递增顺序重新调整输出。举例！假设原始字符串为：eeefgghhh

则每种字符串出现的次数分别是：（1）eee  3次；（2）f  1次；（3）gg  2次；（4）hhh  3次；

重排输出后的字符串如下：efghegheh

编写程序实现上述功能。

输入描述：eeefgghhh（原始字符串中仅可能出现数字和字母，请注意区分字母大小写）

输出描述：efghegheh

思路1：通过字典的方式存储字符串每个字符出现的次数，并按ASCII码递增顺序对字典进行排序。然后依次遍历字典，

使用setdefault()方法创建字典，setdefault()方法语法：

dict.setdefault(key, default=None)

　参数：key -- 查找的键值。

　　　　default -- 键不存在时，设置的默认键值。

返回值：如果字典中包含有给定键，则返回该键对应的值，否则返回为该键设置的值。

class Solution:    def rearrange_string(self, string):        if not string:            return None        char_count = {}        for char in string:            char_count.setdefault(char, 0)            char_count[char] += 1        char_count = sorted(char_count.items(), key=lambda x: x[0])        res = ''        while char_count:            index = 0            while index < len(char_count):                val = char_count[index]                if val[1] > 1:                    res += val[0]                    char_count[index] = （val[0], val[1] - 1]）                    index += 1                elif val[1] == 1:                    res += val[0]                    del char_count[index]                else:                    del char_count[index]        return resif __name__ == "__main__":    import sys    while True:        try:            string = sys.stdin.readline().strip()            print(Solution().rearrange_string(string))        except:            break

思路2：(1)将字符串去重并按ASCII码递增顺序进行排序存入char列表;

(2)用count列表存储对应字符出现的次数;

(3)通过zip将两张列表压缩并转为字典；

(4)通过char*maxCount重复遍历char列表，如果对应的count大于0则将该字符存入res，并进行count-1。

class Solution:    def rearrange_string(self,string):        if not string:            return None        char=list(sorted(set(string)))        count=[]        for c in char:            count.append(string.count(c))        char_count=dict(zip(char,count))        maxCount=max(count)        res=''        for i in char*maxCount:            if char_count[i]>0:                res+=i                char_count[i]-=1            else:                continue        return resif __name__=='__main__':    while True:        try:            string=input()            print(Solution().rearrange_string(string))        except:            break

 

　　

 

2、跳跃比赛

时间限制：C/C++1秒，其他语言2秒     空间限制;C/++32768k，其他语言：65536K

题目描述：

给出一组正整数，你从第一个数向最后一个数跳跃，每次至少跳跃一格，每个数的值表示你从这个位置可以跳跃的最大长度。计算如何以最小的跳跃次数跳到最后一个数。

输入描述：第一行表示有多少个数n，第二行开始依次是1到n个数，一个数一行

输出描述：输出一行，表示至少跳跃的次数

示例1：

输入：

7

2

3

2

1

2

1

5

输出：

3

说明：7表示接下来要输入7个正整数，从2开始。数字本身代表可以跳跃的最大步长，此时有2种跳法，为2-2-2-5和2-3-2--5都为3步

思路1;

class Solution:    def min_hops(self, steps):        if not steps or len(steps) == 1:            return 0        cache = [0] * len(steps)        cache[0] = 0        arr_one_hop = [[] for i in range(len(steps))]        for index, val in enumerate(steps):            hop_floor = min(index + val, len(steps) - 1)            for pos in range(index + 1, hop_floor + 1):                arr_one_hop[pos].append(index)        for index in range(1, len(steps)):            all_hops = []            while arr_one_hop[index]:                all_hops.append(1+cache[arr_one_hop[index].pop()])            cache[index] = min(all_hops)        return cache[len(steps) - 1]if __name__=='__main__':    while True:        try:            n = int(input())            steps = [int(input()) for _ in range(n)]            print(Solution().min_hops(steps))        except:            break

 

 

 

3、大数相乘

时间限制：C/C++1秒，其他语言2秒     空间限制;C/++32768k，其他语言：65536K

题目描述：

编写“长整数相乘”程序，实现两个任意长度的长整数（正数）相乘，输出结果

输入描述：第一行输入数字A的字符串，字符范围（0-9），第二行输入数字B的字符串，字符范围（0-9）

输出描述：输出字符A、B两数相乘的结果，结果为字符串。

示例1：

输入：

1234

4321

输出：

5332114

说明

第一排数字*第二排数字