当前位置: 首页 > news >正文

【华为OD题库-106】全排列-java

题目

给定一个只包含大写英文字母的字符串S,要求你给出对S重新排列的所有不相同的排列数。如:S为ABA,则不同的排列有ABA、AAB、BAA三种。
解答要求
时间限制:5000ms,内存限制:100MB
输入描述
输入一个长度不超过10的字符串S,确保都是大写的。
输出描述
输出S重新排列的所有不相同的排列数(包含自己本身)。
示例1:
输入
ABA
输出
3
示例2:
输入
ABCDEFGHHA
输出
907200

思路

求含重复元素的排列总数,两种方法(数学法效率远高于dfs):

  1. dfs列举所有排列,得到总数,只需要总数,不需要具体组合,具体思路详见:【JAVA-排列组合】一个套路速解排列组合题
  2. 数学公式法

比如输入数据为:ABCDDDA
不考虑重复数据,总的排列数为:res=7!
统计重复元素出现次数:A出现2次,D出现3次,其他出现1次
所以最后结果为:res=7!/(2!*3!)=420

备注:数学法可以这样理解,不考虑重复,那么n个元素的排列方法为n!,再去重,比如某个元素有3个,在不去重时,它重复了3!次,去重时直接除掉它就可以了

题解

package hwod;import java.util.*;public class ArrangeInOrder {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String str = sc.nextLine();System.out.println(arrangeInOrder(str));System.out.println(arrangeInOrder2(str));}private static int res;private static int arrangeInOrder(String str) {final char[] chars = str.toCharArray();Arrays.sort(chars);int[] used = new int[chars.length];dfs(chars, used, 0);return res;}private static void dfs(char[] chars, int[] used, int len) {if (len == chars.length - 1) {//确定到倒数第二位即可res++;return;}for (int i = 0; i < chars.length; i++) {if (i > 0 && chars[i] == chars[i - 1] && used[i - 1] == 0) continue;if (used[i] == 1) continue;used[i] = 1;dfs(chars, used, len + 1);used[i] = 0;}}//方案二:数学法private static int arrangeInOrder2(String str) {Map<Character, Integer> map = statisticsCnt(str);int size = str.length();long res = getFactorialNum(size);int divide = 1;for (Character key : map.keySet()) {divide *= getFactorialNum(map.get(key));}return (int) (res / divide);}private static Map<Character, Integer> statisticsCnt(String string) {Map<Character, Integer> map = new HashMap<>();for (int i = 0; i < string.length(); i++) {map.put(string.charAt(i), map.getOrDefault(string.charAt(i), 0) + 1);}return map;}/*** @param n* @return 计算阶乘*/private static long getFactorialNum(long n) {if (n == 1) return 1;return n * getFactorialNum(n - 1);}
}

推荐

如果你对本系列的其他题目感兴趣,可以参考华为OD机试真题及题解(JAVA),查看当前专栏更新的所有题目。

说明

本专栏所有文章均为原创,欢迎转载,请注明文章出处:https://blog.csdn.net/qq_31076523/article/details/134176793。百度和各类采集站皆不可信,搜索请谨慎鉴别。技术类文章一般都有时效性,本人习惯不定期对自己的博文进行修正和更新,因此请访问出处以查看本文的最新版本。

相关文章:

【华为OD题库-106】全排列-java

题目 给定一个只包含大写英文字母的字符串S&#xff0c;要求你给出对S重新排列的所有不相同的排列数。如:S为ABA&#xff0c;则不同的排列有ABA、AAB、BAA三种。 解答要求 时间限制:5000ms,内存限制:100MB 输入描述 输入一个长度不超过10的字符串S&#xff0c;确保都是大写的。…...

Three.js 详细解析(持续更新)

1、简介&#xff1b; Three.js依赖一些要素&#xff0c;第一是scene&#xff0c;第二是render&#xff0c;第三是carmea npm install --save three import * as THREE from "three"; import { GLTFLoader } from "three/examples/jsm/loaders/GLTFLoader.js&quo…...

Unity中Shader平移矩阵

文章目录 前言方式一&#xff1a;对顶点本地空间下的坐标进行相加平移1、在属性面板定义一个四维变量记录在 xyz 上平移多少。2、在常量缓冲区进行申明3、在顶点着色器中&#xff0c;在进行其他坐标转化之前&#xff0c;对模型顶点本地空间下的坐标进行转化4、我们来看看效果 方…...

python dash 的学习笔记1

dash 用python开发web界面 https://dash.plotly.com/ 官方上支持jula F# python一类。当然我只会python只学习python中使用dash. 要做一个APP&#xff0c;用php,java以及.net都可以写&#xff0c;只所有选择python是因为最近在用这一个。同时也发现python除了慢全是优点。 资料…...

SQLITE如何同时查询出第一条和最后一条两条记录

一个时间记录表&#xff0c;需要同时得到整个表或一段时间内第一条和最后一条两条记录&#xff0c;按如下方法会提示错误&#xff1a;ORDER BY clause should come after UNION not before select * from sdayXX order by op_date asc limit 1 union select * from sday…...

四、ensp配置ftp服务器实验

文章目录 实验内容实验拓扑操作步骤配置路由器为ftp server 实验内容 本实验模拟企业网络。PC-1为FTP 用户端设备&#xff0c;需要访问FTP Server&#xff0c;从服务器上下载或上传文件。出于安全角度考虑&#xff0c;为防止服务器被病毒文件感染&#xff0c;不允许用户端直接…...

VS2020使用MFC开发一个贪吃蛇游戏

背景&#xff1a; 贪吃蛇游戏 按照如下步骤实现:。初始化地图 。通过键盘控制蛇运动方向&#xff0c;注意重新设置运动方向操作。 。制造食物。 。让蛇移动&#xff0c;如果吃掉食物就重新生成一个食物&#xff0c;如果会死亡就break。用蛇的坐标将地图中的空格替换为 #和”将…...

【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集:括号生成、岛屿问题、扫雷游戏

《博主简介》 小伙伴们好&#xff0c;我是阿旭。专注于人工智能AI、python、计算机视觉相关分享研究。 ✌更多学习资源&#xff0c;可关注公-仲-hao:【阿旭算法与机器学习】&#xff0c;共同学习交流~ &#x1f44d;感谢小伙伴们点赞、关注&#xff01; 《------往期经典推荐--…...

字符设备驱动开发-注册-设备文件创建

一、字符设备驱动 linux系统中一切皆文件 1、应用层&#xff1a; APP1 APP2 ... fd open("led驱动的文件"&#xff0c;O_RDWR); read(fd); write(); close(); 2、内核层&#xff1a; 对灯写一个驱动 led_driver.c driver_open(); driver_read(); driver_write(…...

TrustZone之可信操作系统

有许多可信内核&#xff0c;包括商业和开源的。一个例子是OP-TEE&#xff0c;最初由ST-Ericsson开发&#xff0c;但现在是由Linaro托管的开源项目。OP-TEE提供了一个功能齐全的可信执行环境&#xff0c;您可以在OP-TEE项目网站上找到详细的描述。 OP-TEE的结构如下图所示&…...

java定义三套场景接口方案

一、背景 在前后端分离开发的背景下&#xff0c;后端java开发人员现在只需要编写接口接口。特别是使用微服务开发的接口。resful风格接口。那么一般后端接口被调用有下面三种场景。一、不需要用户登录的接口调用&#xff0c;第二、后端管理系统接口调用&#xff08;需要账号密…...

idea连接数据库,idea连接MySQL,数据库驱动下载与安装

文章目录 普通Java工程先创建JAVA工程JDBC连接数据库测试连接 可视化连接数据库数据库驱动下载与安装常用的数据库驱动下载MySQL数据库Oracle数据库SQL Server 数据库PostgreSQL数据库 下载MySQL数据库驱动JDBC连接各种数据库的连接语句MySQL数据库Oracle数据库DB2数据库sybase…...

Redis-实践知识

转自极客时间Redis 亚风 原文视频&#xff1a;https://u.geekbang.org/lesson/535?article681062 Redis最佳实践 普通KEY Redis 的key虽然可以自定义&#xff0c;但是最好遵循下面几个实践的约定&#xff1a; 格式&#xff1a;[业务名称]:[数据名]:[id] 长度不超过44字节 不…...

多维时序 | MATLAB实现SSA-CNN-SVM麻雀算法优化卷积神经网络-支持向量机多变量时间序列预测

多维时序 | MATLAB实现SSA-CNN-SVM麻雀算法优化卷积神经网络-支持向量机多变量时间序列预测 目录 多维时序 | MATLAB实现SSA-CNN-SVM麻雀算法优化卷积神经网络-支持向量机多变量时间序列预测预测效果基本介绍模型描述程序设计参考资料 预测效果 基本介绍 多维时序 | MATLAB实现…...

leetcode160相交链表思路解析

分别让tmp1以及tmp2的结点分别先指向headA以及headB&#xff0c;当遍历完成后&#xff0c;再让tmp1以及tmp2分别指向haedB和headA反转 此处有个问题&#xff1a;为什么if判断句中写tmp1&#xff01;&#xff1d;nullptr&#xff0c;能够编译通过&#xff0c;但是写tmp1->ne…...

在线分析工具-日志优化

一、概述 针对于大日志文件&#xff0c;统计分析出日志文件的相关指标&#xff0c;帮助开发测试人员&#xff0c;优化日志打印。减少存储成本 二、日志分析指标 重复打印日志&#xff1a;统一请求reqId的重复打印日志打印最多的方法&#xff1a;检测出打印日志最多的方法…...

硬核实战!mysql 错误操作整个表全部数据后如何恢复?附解决过程、思路(百万行SQL,通过binlog日志恢复)

mysql 错误操作整个表全部数据后如何恢复&#xff1f;&#xff08;百万行SQL&#xff0c;通过binlog日志恢复&#xff09; 事件起因 事情起因&#xff1a;以为某个表里的数据都是系统配置的数据&#xff0c;没有用户数据&#xff0c;一个字段需要覆盖替换为新的url链接&#x…...

【什么是反射机制?为什么反射慢?】

✅ 什么是反射机制&#xff1f;为什么反射慢&#xff1f; ✅典型解析✅拓展知识仓✅反射常见的应用场景✅反射和Class的关系 ✅典型解析 反射机制指的是程序在运行时能够获取自身的信息。在iava中&#xff0c;只要给定类的名字&#xff0c;那么就可以通过反射机制来获得类的所有…...

PostGreSQL:货币类型

货币类型&#xff1a;money money类型存储固定小数精度的货币数字&#xff0c;小数的精度由数据库的lc_monetary设置决定。windows系统下&#xff0c;该配置项位于/data/postgresql.conf文件中&#xff0c;默认配置如下&#xff0c; lc_monetary Chinese (Simplified)_Chi…...

ESP8266网络相框采用TFT_eSPI库TJpg_Decoder库mixly库UDP库实现图片传送

用ESP8266和TFT_ESPI模块来显示图片数据。具体来说&#xff0c;我们将使用ILI9431显示器作为显示设备&#xff0c;并通过UDP协议将图片数据从发送端传输到ESP8266。最后&#xff0c;我们将解析这些数据并在TFT屏幕上显示出来。在这个过程中&#xff0c;我们将面临一些编程挑战&…...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心

当仓库学会“思考”&#xff0c;物流的终极形态正在诞生 想象这样的场景&#xff1a; 凌晨3点&#xff0c;某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径&#xff1b;AI视觉系统在0.1秒内扫描包裹信息&#xff1b;数字孪生平台正模拟次日峰值流量压力…...

什么是Ansible Jinja2

理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具&#xff0c;可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板&#xff0c;允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板&#xff0c;并通…...

嵌入式学习笔记DAY33(网络编程——TCP)

一、网络架构 C/S &#xff08;client/server 客户端/服务器&#xff09;&#xff1a;由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序&#xff0c;负责提供用户界面和交互逻辑 &#xff0c;接收用户输入&#xff0c;向服务器发送请求&#xff0c;并展示服务…...

基于Springboot+Vue的办公管理系统

角色&#xff1a; 管理员、员工 技术&#xff1a; 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能&#xff1a; 该办公管理系统是一个综合性的企业内部管理平台&#xff0c;旨在提升企业运营效率和员工管理水…...

Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐&#xff1a;「storms…...

elementUI点击浏览table所选行数据查看文档

项目场景&#xff1a; table按照要求特定的数据变成按钮可以点击 解决方案&#xff1a; <el-table-columnprop"mlname"label"名称"align"center"width"180"><template slot-scope"scope"><el-buttonv-if&qu…...