LeetCode 周赛-291

第一题1 问题描述 给你一个表示某个正整数的字符串 number 和一个字符 digit 。 从 number 中 恰好 移除 一个 等于 digit 的字符后,找出并返回按 十进制 表示 最大 的结果字符串。生成的测试用例满足 digit 在 number 中出现至少一次。 示例1: 输入:number = "123", digit = "3" 输出:"12" 解释:"123" 中只有一个 '3' ,在移除 '3' 之后,结果为 "12" 。 示例2: 输入:number = "1231", digit = "1" 输出:"231" 解释:可以移除第一个 '1' 得到 "231" 或者移除第二个 '1' 得到 "123" 。 由于 231 > 123 ,返回 "231" 。 示例3: 输入:number = "551", digit = "5" 输出:"51" 解释:可以从 "551" 中移除第一个或者第二个 '5' 。 两种方案的结果都是 "51" 。 提示:...

May 1, 2022 · Huo Haodong

阿拉伯数字转中文

初步想法 下面是一些将阿拉伯数字转为中文的例子: 0 = 零 10 = 十 1000 = 一千 9527 = 九千五百二十七 10051 = 一万零五十一 111111111 = 一亿一千一百一十一万一千一百一十一 一个最直观的想法就是按照从最低位到最高位的顺序,依次将数字映射为相应的中文字符并加上单位,比如: 0 = 零 10 = 一十零 1000 = 一千零百零十零 10051 = 一万零千零百五十一 110010 = 一十一万零千零百一十零 210010 = 二十一万零千零百一十零 但是这样的转换方法对于“零”的处理并不理想,我们中文的习惯一般是将连续出现的多个“零”合为一个,并去除末尾的“零”。因此我们需要对“零”进行单独处理。 此外,对于数字 110010 最高位的 11 而言,我们一般是读成“十一万”而不是“一十一万”,所以还应对位于开头的 10 ~ 19 之间的数字进行处理。 观察上面的例子也很容易注意到,按照这种朴素的处理方法,添加“万”、“亿”等特殊数位的时机也是一个棘手的问题。 通过上述分析可以看到,阿拉伯数字转中文并没有一个统一的规则,且因为中文的阅读习惯比较特殊,还应进行许多特殊处理。 算法设计与实现 以数字 123456789 为例,我们可以将数字从右到左按照每 4 位为一段进行单独处理,之后对每段处理后的结果进行拼接: 将 123456789 分为 1、2345、6789 三段,每段单独处理; 6789 = 六千 七百 八十 九,2345 = 二千 三百 四十 五,1 = 一; 对结果进行拼接,注意拼接的时候带上每段相应的数位,比如“万”和“亿”,拼接后为:一 亿 二千三百四十五 万 六千七百八十九。 按照这样的规则处理就可以解决“万”、“亿”等特殊单位的添加问题。...

March 13, 2022 · Huo Haodong

LeetCode 周赛-215

第一题-设计有序流 问题 有 n 个 (id, value) 对,其中 id 是 1 到 n 之间的一个整数,value 是一个字符串。不存在 id 相同的两个 (id, value) 对。 设计一个流,以 任意 顺序获取 n 个 (id, value) 对,并在多次调用时按id递增的顺序返回一些值。 实现 OrderedStream 类: OrderedStream(int n) 构造一个能接收 n 个值的流,并将当前指针ptr设为 1 。 String[] insert(int id, String value) 向流中存储新的 (id, value)对。存储后: 如果流存储有 id = ptr的(id, value) 对,则找出从id = ptr开始的 最长id连续递增序列 ,并按顺序返回与这些id关联的值的列表。然后,将 ptr 更新为最后那个 id + 1 。 否则,返回一个空列表。 示例 输入...

November 15, 2020 · Huo Haodong

异或在算法中的应用

二进制运算中,异或无处不在。由于其各种不错的性质在计算机中应用很广。由于日常中很少接触到需要应用到异或的算法,对异或的印象也只停留在各种计算机底层设计中,终归是纸上谈兵。最近接触到了一个使用异或的巧妙算法,便发现自己对异或的理解过于肤浅。 异或简介 交换律 结合律 $x;XOR;0 = x$ | $x;XOR;x = 0$ $A;XOR;\underline{B;XOR;B} = A;XOR;\underline{0} = A $ 使用异或的如上性质,在交换两个变量的值时,可以直接通过异或实现而不用使用额外空间: A = A ^ B; B = B ^ A;//B = B ^ A ^ B = B ^ B ^ A = A A = A ^ B;//A = A ^ B ^ A = B 引子 **问题:**在一个数组中,如果只有一个数重复出现了奇数次而其余数出现了偶数次,设计一个算法来找出这个出现奇数次的数。要求算法满足时间复杂度$O(n)$,空间复杂度$O(1)$。 传统解法 按照传统的思路来的话,可以使用一个HashSet,每次读入一个数据,如果在HashSet中则去掉这个数,反之则将该数字加入HashSet。而这个问题要求$O(1)$的空间复杂度,只能另辟蹊径。 异或解法 可以注意到,这个问题如果使用异或的思想来解决的话便很方便。 假设原数组 nums = {1, 2, 2, 3, 3, 4, 4}所求数字便为 1。初始化Mask = 0,对每个元素都进行运算Mask ^= num[i]。运算后得Mask = 1。即得到了所求的数字。...

April 28, 2020 · Huo Haodong