当前位置: 首页 > 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;我们将面临一些编程挑战&…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

在Ubuntu24上采用Wine打开SourceInsight

1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...

scikit-learn机器学习

# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...

HubSpot推出与ChatGPT的深度集成引发兴奋与担忧

上周三&#xff0c;HubSpot宣布已构建与ChatGPT的深度集成&#xff0c;这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋&#xff0c;但同时也存在一些关于数据安全的担忧。 许多网络声音声称&#xff0c;这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...

离线语音识别方案分析

随着人工智能技术的不断发展&#xff0c;语音识别技术也得到了广泛的应用&#xff0c;从智能家居到车载系统&#xff0c;语音识别正在改变我们与设备的交互方式。尤其是离线语音识别&#xff0c;由于其在没有网络连接的情况下仍然能提供稳定、准确的语音处理能力&#xff0c;广…...

React从基础入门到高级实战:React 实战项目 - 项目五:微前端与模块化架构

React 实战项目&#xff1a;微前端与模块化架构 欢迎来到 React 开发教程专栏 的第 30 篇&#xff01;在前 29 篇文章中&#xff0c;我们从 React 的基础概念逐步深入到高级技巧&#xff0c;涵盖了组件设计、状态管理、路由配置、性能优化和企业级应用等核心内容。这一次&…...

Canal环境搭建并实现和ES数据同步

作者&#xff1a;田超凡 日期&#xff1a;2025年6月7日 Canal安装&#xff0c;启动端口11111、8082&#xff1a; 安装canal-deployer服务端&#xff1a; https://github.com/alibaba/canal/releases/1.1.7/canal.deployer-1.1.7.tar.gz cd /opt/homebrew/etc mkdir canal…...

JS的传统写法 vs 简写形式

一、条件判断与逻辑操作 三元运算符简化条件判断 // 传统写法 let result; if (someCondition) {result yes; } else {result no; }// 简写方式 const result someCondition ? yes : no;短路求值 // 传统写法 if (condition) {doSomething(); }// 简写方式 condition &…...

SpringCloud——Nacos

1、核心功能&#xff1a; 服务注册与发现&#xff1a; 服务实例可动态注入到Nacos中&#xff0c;消费者通过服务名发现可用实例。 // 启用EnableDiscoveryClient注解启用Nacos SpringBootApplication EnableDiscoveryClient public class UserServiceApplication {public st…...