删除最小字母（第四范式算法一面）

删除最小字母（第四范式算法一面）

一、题目描述

给定一个长度为n的小写字符数组，一次操作是删除一个最小字母，如有多个删除最靠左的。要求输出操作k次后的字符串。

输入：abcdabcd k = 3输出：cdbcd

二、解题思路 & 代码

由于都是小写字母，字符类型比较简单，故而可以用简便的方法

采用哈希表将字符串进行计数将键值从小到大排序，而后从前往后删除，当删除的数量 == k 时停止

from collections import Counterdef delMinAlpha(s, k): n = len(s) dic = Counter(s) print("dic:", dic) sum_ = 0 del_dic = {} key_list = sorted(list(dic.keys())) print("key_list:", key_list) for stop_ind, key in enumerate(key_list): sum_ = sum_ + dic[key] del_dic[key] = dic[key] if sum_ >= k: break print("ind:", stop_ind) print("sum_:", sum_) stop_key = key_list[stop_ind] print("stop_key:", stop_key) del_dic[stop_key] = dic[stop_key] - (sum_ - k) print("del_dic:", del_dic) new_list = '' for j in range(n): if s[j] not in del_dic: # 要删除的键值 不存在 new_list += s[j] elif s[j] in del_dic and del_dic[s[j]] > 0: # 要删除的键值 存在，且还没删光 del_dic[s[j]] -= 1 continue elif s[j] in del_dic and del_dic[s[j]] <= 0: # 即使要删除的键值 存在，但是已经删光了 new_list += s[j] return new_listif __name__ == '__main__': # ASCII_num = ord('a') # 返回 ASCII 码 s = 'abcdabcdabcdabcd' k = 14 res = delMinAlpha(s, k) print("res:", res)

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。