Go Java算法之从英文中重建数字示例详解

2024-02-18 00:54:25

从英文中重建数字

给你一个字符串 s ，其中包含字母顺序打乱的用英文单词表示的若干数字（0-9）。按升序返回原始的数字。

示例 1：

输入：s = "owoztneoer" 输出："012" 示例 2：

输入：s = "fviefuro" 输出："45"

提示：

1 <= s.length <= 105

s[i] 为 ["e","g","f","i","h","o","n","s","r","u","t","w","v","x","z"] 这些字符之一

s 保证是一个符合题目要求的字符串

Java实现

先对 s 进行词频统计，然后根据「英文单词中的字符唯一性」确定构建的顺序，最后再对答案进行排序即可。

zero 中的 z 在其余所有单词中都没出现过，可以先统计 zero 的出现次数，并构建 00；然后观察剩余数字，其中 eight 中的 g 具有唯一性，构建 88；
再发现 six 中的 x 具有唯一性，构建 66；
发现 three 中的 h 具有唯一性（利用在此之前 eight 已经被删除干净，词频中仅存在 three 对应的 h)，构建 33 ...

最终可以确定一个可行的构建序列为 0, 8, 6, 3, 2, 7, 5, 9, 4, 1。

class Solution {
    static String[] ss = new String[]{"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
    static int[] priority = new int[]{0, 8, 6, 3, 2, 7, 5, 9, 4, 1};
    public String originalDigits(String s) {
        int n = s.length();
        int[] cnts = new int[26];
        for (int i = 0; i < n; i++) cnts[s.charAt(i) - 'a']++;
        StringBuilder sb = new StringBuilder();
        for (int i : priority) {
            int k = Integer.MAX_VALUE;
            for (char c : ss[i].toCharArray()) k = Math.min(k, cnts[c - 'a']);
            for (char c : ss[i].toCharArray()) cnts[c - 'a'] -= k;
            while (k-- > 0) sb.append(i);
        }
        char[] cs = sb.toString().toCharArray();
        Arrays.sort(cs);
        return String.valueOf(cs);
    }
}

时间复杂度：O(mlogm)

空间复杂度：O(L+m)

Go实现

输入中各个字母的个数，可以知道一些数字的个数了，比如只有零用了z，只有六用了x等等，

在将一些可以求得的个数求了后，将它们占用的其他字母的个数排除掉，经过排除后，剩下的有用到别人用过的字母的数字的个数也可以得到了。比如在四的个数通过u得到后，五的个数就可以通过剩下的f的个数得到了。

func originalDigits(s string) string {
    cnts, a := make([]int, 26), byte('a')
    for i := range s {
        cnts[s[i] - a]++
    }
    zeros, twos, fours, sixs, eights := cnts[byte('z') - a], cnts[byte('w') - a], cnts[byte('u') - a], cnts[byte('x') - a], cnts[byte('g') - a]
    fives, sevens, ones, threes := cnts[byte('f') - a] - fours, cnts[byte('s') - a] - sixs, cnts[byte('o') - a] - zeros - twos - fours, cnts[byte('h') - a] - eights
    nines := cnts[byte('i') - a] - fives - sixs - eights
    return strings.Repeat("0", zeros) + strings.Repeat("1", ones) + strings.Repeat("2", twos) + strings.Repeat("3", threes) + strings.Repeat("4", fours) + strings.Repeat("5", fives) + strings.Repeat("6", sixs) + strings.Repeat("7", sevens) + strings.Repeat("8", eights) + strings.Repeat("9", nines)
}

时间复杂度：O(mlogm)

空间复杂度：O(L+m)

以上就是Go Java算法之从英文中重建数字示例详解的详细内容，更多关于Go Java算法英文重建数字的资料请关注我们其它相关文章！

详解Java中Dijkstra(迪杰斯特拉)算法的图解与实现

目录简介工作过程总体思路实现小根堆 Dijsktra 测试简介 Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径.主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止.Dijkstra算法是很有代表性的最短路径算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等.注意该算法要求图中不存在负权边.对应问题:在无向图G=(V,E)中,假设每条边E(i)的长度W(i),求由顶点V0到各节点的最短路径. 工作过
Go实现分布式唯一ID的生成之雪花算法

目录背景: 特性: 雪花算法: 分布式唯一ID的生成背景: 在分布式架构下,唯一序列号生成是我们在设计一个尤其是数据库使用分库分表的时候会常见的一个问题特性: 全局唯一,这是基本要求,不能出现重复数字类型,趋势递增,后面的ID必须比前面的大长度短,能够提高查询效率,这也是从MySQL数据库规范出发的,尤其是ID作为主键时**信息安全,**如果ID连续生成,势必会泄露业务信息,所以需要无规则不规则高可用低延时,ID生成快,能够扛住高并发,延时足够低不至于成为业务瓶颈. 雪花算法: sno
Go 加密解密算法小结

目录前言 md5 hmac sha1 AES ECB模式 CBC模式 CRT模式 CFB模式 OFB模式 RSA加密参考: 前言加密解密在实际开发中应用比较广泛,常用加解密分为:“对称式”.“非对称式”和”数字签名“. 对称式:对称加密(也叫私钥加密)指加密和解密使用相同密钥的加密算法.具体算法主要有DES算法,3DES算法,TDEA算法,Blowfish算法,RC5算法,IDEA算法. 非对称加密(公钥加密):指加密和解密使用不同密钥的加密算法,也称为公私钥加密.具体算法主要有RSA.E
详解Java如何实现数值校验的算法

给定一个字符串如何判断它是否为数值类型?例如:字符串+100.5e2.-123.3.1416以及-1E-16都表示数值,为数值类型,但12e.1a3.14.1.2.3.+-5以及12e+5.4都不是. 本文将带着大家实现这个判断算法,欢迎各位感兴趣的开发者阅读本文. 实现思路我们先来看一下数值的定义规则:表示数值的字符串遵循模式A[.[B]][e|EC]或者.B[e|EC],其中: A为数值的整数部分 B紧跟着小数点为数值的小数部分 C紧跟着e或者E为数值的指数部分在小数里可能没有数值的整数
golang常用加密解密算法总结(AES、DES、RSA、Sha1、MD5)

目录关于加密解密 AES DES RSA MD5 Sha1 Base64 在项目开发过程中,当操作一些用户的隐私信息,诸如密码.帐户密钥等数据时,往往需要加密后可以在网上传输.这时,需要一些高效地.简单易用的加密算法加密数据,然后把加密后的数据存入数据库或进行其他操作:当需要读取数据时,把加密后的数据取出来,再通过算法解密. 关于加密解密当前我们项目中常用的加解密的方式无非三种. 对称加密, 加解密都使用的是同一个密钥, 其中的代表就是AES.DES 非对加解密, 加解密使用不同的密钥, 其
Java 常见的限流算法详细分析并实现

目录为什么要限流限流算法计数器限流漏桶限流令牌桶限流为什么要限流在保证可用的情况下尽可能多增加进入的人数,其余的人在排队等待,或者返回友好提示,保证里面的进行系统的用户可以正常使用,防止系统雪崩. 限流算法限流算法很多,常见的有三类,分别是计数器算法 .漏桶算法.令牌桶算法 . (1)计数器: 在一段时间间隔内,处理请求的最大数量固定,超过部分不做处理. (2)漏桶: 漏桶大小固定,处理速度固定,但请求进入速度不固定(在突发情况请求过多时
Go Java算法之从英文中重建数字示例详解

目录从英文中重建数字 Java实现 Go实现从英文中重建数字给你一个字符串 s ,其中包含字母顺序打乱的用英文单词表示的若干数字(0-9).按升序返回原始的数字. 示例 1: 输入:s = "owoztneoer" 输出:"012" 示例 2: 输入:s = "fviefuro" 输出:"45" 提示: 1 <= s.length <= 105 s[i] 为 ["e","g&
C++ Leetcode实现从英文中重建数字

目录题目分析代码题目分析首先我们先分析每个字母的组成,然后发现一些字符只在一个单词中出现,我们先去统计一下这些单词个数. z,w,u,x,g都只出现在一个数字中,也就是0,2,4,6,8,我们用哈希表统计一下s字符串中各个字符的数量,就可以知道0,2,4,6,8的数量,然后我们注意一下只在两个数字中出现的字符. h 只在 3,8 中出现.由于我们已经知道了 8 出现的次数,因此可以计算出 3 出现的次数. f 只在 4,5 中出现.由于我们已经知道了 4 出现的次数,因此可以计算出
Java结构型设计模式中代理模式示例详解

目录代理模式分类主要角色作用静态代理与动态代理的区别静态代理的基本使用创建抽象主题创建真实主题创建代理主题客户端调用 JDK动态代理的基本使用创建抽象主题创建真实主题创建代理主题客户端调用小优化 CGLIB动态代理的基本使用创建抽象主题创建真实主题创建代理主题客户端调用小优化 CGLIB与JDK动态代理区别 1.执行条件 2.实现机制 3.性能代理模式代理模式(Proxy Pattern)属于结构型模式. 它是指为其他对象提供一种代理以控制对这个对象的
Java结构型设计模式中建造者模式示例详解

目录建造者模式概述角色优缺点应用场景基本使用创建产品类创建建造者类使用链式写法创建产品类与建造者类使用建造者模式概述建造者模式(Builder Pattern)属于创建型模式. 它是将一个复杂的构建与其表示相分离,使得同样的构建过程可以创建不同的表示. 简而言之:建造者模式就是使用多个简单的对象一步一步构建成一个复杂的对象. 建造者模式适用于创建对象需要很多步骤,但是步骤的顺序不一定固定.如果一个对象有非常复杂的内部结构(很多属性),可以将复杂对象的创建和使用进行分
Java中泛型的示例详解

目录泛型概述使用泛型的好处泛型的定义与使用定义和使用含有泛型的类含有泛型的方法含有泛型的接口泛型通配符通配符基本使用通配符高级使用----受限泛型泛型概述我们都知道集合中是可以存放任意对象的,只要把对象存储集合后,那么这时他们都会被提升成Object类型.当我们在取出每一个对象,并且进行相应的操作,这时必须采用类型转换. 大家观察下面代码: public class GenericDemo { public static void main(String[] args) {
java面向对象设计原则之里氏替换原则示例详解

目录概念实现拓展概念里氏替换原则是任何基类出现的地方,子类一定可以替换它:是建立在基于抽象.多态.继承的基础复用的基石,该原则能够保证系统具有良好的拓展性,同时实现基于多态的抽象机制,能够减少代码冗余. 实现里氏替换原则要求我们在编码时使用基类或接口去定义对象变量,使用时可以由具体实现对象进行赋值,实现变化的多样性,完成代码对修改的封闭,扩展的开放.如:商城商品结算中,定义结算接口Istrategy,该接口有三个具体实现类,分别为PromotionalStrategy (满减活动,两
java面向对象设计原则之接口隔离原则示例详解

目录概念实现拓展概念小接口原则,即每个接口中不存在子类用不到却必须实现的方法,如果不然,就要将接口拆分.如下图所示定义了一个接口,包含了5个方法,实现类A用到了3个方法.实现类B用到了3个方法,类图如下: 类A没有方法4.方法5,却要实现它:类B没有方法2.方法3,但还是要实现这两个方法,不符合接口隔离原则.改造为将其拆分为三个接口,实现方式改为下图所示,符合接口隔离原则: 实现面向对象机制中一个类可以实现多个接口,通过多重继承分离,通过接口多继承(实现)来实现客户的需求,代码更加清
java面向对象设计原则之合成复用原则示例详解

目录概念示例拓展概念尽量使用合成/聚合,而不是使用继承实现复用.所谓的合成/聚合是指一个对象里持有另外一个类的对象,通过调用这些对象的方法得到复用已有功能的目的.如:报文解译程序中,按照继承复用可以设计为: 子类调用父类的方法即可完成水文报文解译.气象解译中通用方法:子类中一定包含了父类的方法,这个叫继承复用. 按照合成/聚合原则设计为: 水文协议和气象协议中,持有编码和位制转换对象,通过调用对象方法即可完成复用. 示例数据库连接的复用:首先看通过集成关系复用数据连接代码如下 pub
java设计模式七大原则之开闭原则示例详解

目录 1.什么是开闭原则? 2.违反Ocp代码案例 3.遵守Ocp代码案例 1.什么是开闭原则? 开闭原则(Open Closed Principle)是编程中最基础.最重要的设计原则.一个软件实体如类,模块和函数应该对扩展开放(对提供方),对修改关闭(对使用方).用抽象构建框架,用实现扩展细节.当软件需要变化时,尽量通过扩展软件实体的行为来实现变化,而不是通过修改已有的代码来实现变化.编程中遵循其它原则,以及使用设计模式的目的就是遵循开闭原则. 2.违反Ocp代码案例 package com.
java编程创建型设计模式工厂方法模式示例详解

目录 1.什么是工厂方法模式? 2.案例实现 3.JDK中的工厂方法模式 1.什么是工厂方法模式? 工厂方法模式设计方案: 将披萨项目的实例化功能抽象成抽象方法,在不同的口味点餐子类中具体实现. 工厂方法模式: 定义了一个创建对象的抽象方法,由子类决定要实例化的类.工厂方法模式将对象的实例化推迟到子类. 何时使用? 不同条件下创建不用实例时.方法是让子类实现工厂接口. 2.案例实现假如说,我们现在有这样一个需求:客户在点披萨时,可以点不同口味的披萨,比如北京的奶酪pizza.北京的胡椒p

Go Java算法之从英文中重建数字示例详解

目录

从英文中重建数字

Java实现

Go实现

相关推荐

随机推荐