精华内容
下载资源
问答
  • 给定一个只包含大写英文字母的字符串S,要求你给出对S重新排列的所有不相同的排列数。 如:S为ABA,则不同的排列有ABA、AAB、BAA三种。 解题思路 先把每个字符当成唯一出现过一次,计算所有排列数;再统计重复出现的...

    题目描述
    给定一个只包含大写英文字母的字符串S,要求你给出对S重新排列的所有不相同的排列数。
    如:S为ABA,则不同的排列有ABA、AAB、BAA三种。

    解题思路
    先把每个字符当成唯一出现过一次,计算所有排列数;再统计重复出现的字母,除去每个字母的排列次数

    例如
    对于ABA,当成三个不同字符则排列数为: S 总 = A 3 3 S_总=A_3^3 S=A33,其中A出现两次,排列数为: S A = A 2 2 S_A=A_2^2 SA=A22,B出现两次,排列数为: S B = A 1 1 S_B=A_1^1 SB=A11,最终计算得: S = S 总 / ( S A ∗ S B ) = 3 ∗ 2 ∗ 1 / ( 2 ∗ 1 ∗ 1 ) = 3 S=S_总/(S_A*S_B)=3*2*1/(2*1*1)=3 S=S/(SASB)=321/(211)=3

    代码:

    import java.util.HashMap;
    import java.util.Map;
    import java.util.Scanner;
    
    /**
     * 题目描述
     * 给定一个只包含大写英文字母的字符串S,要求你给出对S重新排列的所有不相同的排列数。
     * 如:S为ABA,则不同的排列有ABA、AAB、BAA三种
     *
     * 解题思路:先把每个字符当做唯一出现,再除去相同字母的排列次数
     */
    public class ReSortChars {
    	public static void main(String[] args) {
    		Scanner s = new Scanner(System.in);
    		char[] chars = s.nextLine().toCharArray();
    		Map<Character, Integer> map = new HashMap<Character, Integer>();
    		int num = 0;
    		for (char ch:chars) {
    			if(null == map.get(ch)) {
    				num = 0;
    			} else {
    				num = map.get(ch);
    			}
    			map.put(ch,num + 1);
    		}
    		int allSort = SortOne(chars.length);
    		for (char key : map.keySet()) {
    			allSort = allSort/SortOne(map.get(key));
    		}
    		System.out.println(allSort);
    	}
    
    	static int SortOne (int charsnum) {
    		if (charsnum == 1) {
    			return 1;
    		}
    		return charsnum * SortOne(charsnum - 1);
    	}
    }
    
    展开全文
  • 给定一个任意一个字符串s,求重新排列的所有不同的排列数,包含该输入的字符串本身。 import java.util.*; /** * @PackageName: PACKAGE_NAME * @ClassName: Test10 * @Author: * @Date: 2020/4/16 20:20 * ...

    给定一个任意一个字符串s,求重新排列的所有不同的排列数,包含该输入的字符串本身。
    给定一个字符串s,求重新排列的所有不同的排列数,包含该输入的字符串本身

    
    import java.util.*;
    /**
     * @PackageName: PACKAGE_NAME
     * @ClassName: Test10
     * @Author: 
     * @Date: 2020/4/16 20:20
     * @Description: //TODO
     */
    public class Test10 {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            while (sc.hasNext()) {
                String s = sc.nextLine().toUpperCase();
                if (!s.isEmpty()) {
                    int length = s.length();
                    char[] chars = s.toCharArray();
                    Arrays.sort(chars);
                    Map<Character, Integer> map = new HashMap<>();
                    for (int i = 0; i < chars.length; i++) {
                        boolean flag = true;
                        int num = 1;//该字母的个数;
                        while (flag) {
                            if (i+1<chars.length &&chars[i] == chars[i + 1]) {
                                if (!(i+1< chars.length)){
                                    break;
                                }
                                i++;
                                num++;
                            } else {
                                flag = false;
                                map.put(chars[i], num);
                            }
                        }
                    }
                    Collection<Integer> values = map.values();
                    long pailieshu = getJieChen(length);
                    for (int chushu : values) {
                        pailieshu = pailieshu / getJieChen(chushu);
                    }
                    System.out.println(pailieshu);
                }
            }
        }
    
        public static long getJieChen(int num) {
            long result = 1;
            for (int i = 0; i < num; i++) {
                result = result * (num-i) ;
            }
            return result;
        }
    }
    
    

    测试结果:

    D:\developer\Java\jdk1.8.0_231\bin\java.exe -agentlib:jdwp=transport=dt_socket,address=127.0.0.1:56798,suspend=y,server=n -javaagent:C:\Users\changlei\.IntelliJIdea2019.1\system\captureAgent\debugger-agent.jar -Dfile.encoding=UTF-8 -classpath "D:\developer\Java\jdk1.8.0_231\jre\lib\charsets.jar;D:\developer\Java\jdk1.8.0_231\jre\lib\deploy.jar;D:\developer\Java\jdk1.8.0_231\jre\lib\ext\access-bridge-64.jar;D:\developer\Java\jdk1.8.0_231\jre\lib\ext\cldrdata.jar;D:\developer\Java\jdk1.8.0_231\jre\lib\ext\dnsns.jar;D:\developer\Java\jdk1.8.0_231\jre\lib\ext\jaccess.jar;D:\developer\Java\jdk1.8.0_231\jre\lib\ext\jfxrt.jar;D:\developer\Java\jdk1.8.0_231\jre\lib\ext\localedata.jar;D:\developer\Java\jdk1.8.0_231\jre\lib\ext\nashorn.jar;D:\developer\Java\jdk1.8.0_231\jre\lib\ext\sunec.jar;D:\developer\Java\jdk1.8.0_231\jre\lib\ext\sunjce_provider.jar;D:\developer\Java\jdk1.8.0_231\jre\lib\ext\sunmscapi.jar;D:\developer\Java\jdk1.8.0_231\jre\lib\ext\sunpkcs11.jar;D:\developer\Java\jdk1.8.0_231\jre\lib\ext\zipfs.jar;D:\developer\Java\jdk1.8.0_231\jre\lib\javaws.jar;D:\developer\Java\jdk1.8.0_231\jre\lib\jce.jar;D:\developer\Java\jdk1.8.0_231\jre\lib\jfr.jar;D:\developer\Java\jdk1.8.0_231\jre\lib\jfxswt.jar;D:\developer\Java\jdk1.8.0_231\jre\lib\jsse.jar;D:\developer\Java\jdk1.8.0_231\jre\lib\management-agent.jar;D:\developer\Java\jdk1.8.0_231\jre\lib\plugin.jar;D:\developer\Java\jdk1.8.0_231\jre\lib\resources.jar;D:\developer\Java\jdk1.8.0_231\jre\lib\rt.jar;D:\developer\IdeaProjects\offer\out\production\fuxi;D:\developer\JetBrains\IntelliJ IDEA 2019.1\lib\idea_rt.jar" Test10
    Connected to the target VM, address: '127.0.0.1:56798', transport: 'socket'
    ABCDEFGHHA
    907200
    ABA
    3
    A
    1
    AA
    1
    AAAAAA
    1
    AAAAAB
    6
    ABC
    6
    ABCD
    24
    

    我写的代码对任意一个字符串求所有不同的排列数都适用吧?

    展开全文
  • 给出一组非负整数,重新排列他们的顺序把他们组成一个最大的整数。 例 给出 [1, 20, 23, 4, 8],返回组合最大的整数应为 8423201 给出 [1, 201, 20, 9, 8],返回组合最大的整数应为 98202011 给出 [...
    文章为原创首发地址: https://hooyes.net/p/python-l...

    描述

    给出一组非负整数,重新排列他们的顺序把他们组成一个最大的整数。

    例
    给出 [1, 20, 23, 4, 8],返回组合最大的整数应为 8423201
    给出 [1, 201, 20, 9, 8],返回组合最大的整数应为 98202011
    给出 [1, 203, 20, 9, 8],返回组合最大的整数应为 98203201
    

    算法

    我给简单好理解的两个排序算法:

    算法1:

    先把对比的数字转成字符,拼接后再转成整数进行大小对比,即 int(a+b) 与 int(b+a) 进行降序排列。代码1。

    算法2:

    每个元素逐个字符进行对比。代码2。

    代码1

    # Python2
    
    class Solution:
        def largestNumber(self, nums):
            scmp = lambda a,b: int(b+a)-int(a+b)
            res = ''.join(sorted(map(str, nums), cmp=scmp)).lstrip('0')
            return res or '0'
    # Python3 
    
    from functools import cmp_to_key
    class Solution:
        def largestNumber(self, nums):
            key = cmp_to_key(lambda a,b: int(b+a)-int(a+b))
            res = ''.join(sorted(map(str, nums), key=key)).lstrip('0')
            return res or '0'

    代码2

    
    # Python2 
    
    class Solution:
        def largestNumber(self,nums):
            def cxx(x,y):
                i = 0 
                sx= str(x)
                sy= str(y)
                while i< len(str(min(x,y))):
                    if sx[i] > sy[i]:
                        return 1
                    elif sx[i] < sy[i]:
                        return -1
                    elif x == y:
                        return 0
                    i+=1
                if i == len(sx):
                    return -1 if sy[i]>sy[0] else 1
                if i == len(sy):
                    return 1 if sx[i]>sx[0] else -1
            nx = sorted(nums,cmp=lambda x,y:cxx(x,y),reverse=True)        
            res = ''.join(map(str, nx)).lstrip('0')
            return res or '0'     
    

    测试

    t = Solution()
    print(t.largestNumber([1, 20, 23, 4, 8]))
    // 8423201

    以上代码已放到Hooyes的Github上开源,欢迎Fork或提建议。

    largest-number.py

    运行 python largest-number.py 即可以测试。

    展开全文
  • 排序——希尔排序(Shell's sort)

    千次阅读 2020-02-08 23:21:06
    希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。该方法因D.L.Shell于1959年提出而得名。 希尔排序是把记录按下标的一定...

    希尔排序概况

    希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。该方法因D.L.Shell于1959年提出而得名。

    希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至 1 时,整个文件恰被分成一组,算法便终止。

    希尔排序是基于插入排序的以下两点性质而提出改进方法的:

    1. 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率。

    2. 但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位。

    算法思路

    先取一个小于 n 的整数 d_1 作为第一个增量,把文件的全部记录分组。所有距离为 d_1 的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量 d_{2}<d_{1} 重复上述的分组和排序,直至所取的增量d_{t}=1(d_{t}<d_{t-1}<\cdots <d_{2}<d_{1}),即所有记录放在同一组中进行直接插入排序为止。

    该方法实质上是一种分组插入方法。

    图解算法

    假设,我们有一个数列,初始状态为\left \{ 5,7,8,3,1,2,4,6 \right \},一共 8 个元素。

    第一轮

    我们按下标相隔距离为 4 进行分组,这样a[0]与a[4]是一组、a[1]与a[5]是一组、...。如下图所示。

    每个分组进行插入排序后,各个分组就变成了有序的,注意整体不一定有序。如下图所示。

    第二轮

    小增量为上个增量的一半 2,继续划分分组。此时,每个分组元素个数多了,但是,数组变的部分有序了,插入排序效率同样比高。此时的分组情况如下图所示。

    对每个分组进行插入排序,使其每个分组各自有序。如下图所示。

    第三轮

    最后设置增量为上一个增量的一半 1,则整个数组被分为一组,此时,整个数组已经接近有序了,插入排序效率高。如下图所示。

    再对分组进行插入排序,使其每个分组各自有序。这样排序完成。

    动画展示

    我们借用五分钟学算法的gif动图,感谢五分钟学算法。

    算法性能

    时间复杂度

    希尔排序的复杂度和增量序列是相关的。为了保证分组粗调没有盲区,每一轮的增量需要彼此“互质”,也就是没有除1之外的公约数。

    \left \{ 1,2,4,8,\cdots \right \}这种序列并不是很好的增量序列,使用这个增量序列的时间复杂度(最坏情形)是O(n^{2})

    Hibbard 提出了另一个增量序列\left \{ 1,3,7,\cdots,2^{k}-1 \right \},通项公式 2^{k}-1,这种序列的时间复杂度(最坏情形)为O(n^{1.5})

    Sedgewick 提出了几种增量序列,其最坏情形运行时间为O(n^{1.3}),其中最好的一个序列是\left \{ 1,5,9,41,109,\cdots \right \},通项公式 9*4^{k}-9*2^{k}+1 或者 4^{k}-3*2^{k}+1

    所以我们认为希尔排序的平均时间复杂度为O(nlogn)

    空间复杂度

    由于希尔排序使用了插入排序的方法,所以空间复杂度和插入排序相同,O(1)

    稳定性

    不稳定。由于多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以希尔排序是不稳定的。

    代码实现

    C和C++

    void shellSort(int arr[], int len) {
        //计算的序列为1, 4, 13, 40, 121, 364, 1093...
        int gap = 1;
        while (gap < len/3) {
            gap = 3*gap+1;
        }
        
        while (gap >= 1) {
            for (int i=gap; i<len; i++) {
                //对arr[i], arr[i-h], arr[i-2h], ... 使用插入排序
                int e = arr[i];
                int j;
                for (j=i; j>=gap; e<arr[j-gap]; j-=gap) {
                    arr[j] = arr[j-gap];
                }
                arr[j] = e;
            }
            gap /= 3;
        }
    }

    Java

    public class ShellSort implements IArraySort {
    
        @Override
        public int[] sort(int[] sourceArray) throws Exception {
            // 对 arr 进行拷贝,不改变参数内容
            int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
    
            int gap = 1;
            while (gap < arr.length/3) {
                gap = gap * 3 + 1;
            }
    
            while (gap > 0) {
                for (int i = gap; i < arr.length; i++) {
                    int tmp = arr[i];
                    int j = i - gap;
                    while (j >= 0 && arr[j] > tmp) {
                        arr[j + gap] = arr[j];
                        j -= gap;
                    }
                    arr[j + gap] = tmp;
                }
                gap = (int) Math.floor(gap / 3);
            }
    
            return arr;
        }
    }

    Python

    def shellSort(arr):
        import math
        gap=1
        while(gap < len(arr)/3):
            gap = gap*3+1
        while gap > 0:
            for i in range(gap,len(arr)):
                temp = arr[i]
                j = i-gap
                while j >=0 and arr[j] > temp:
                    arr[j+gap]=arr[j]
                    j-=gap
                arr[j+gap] = temp
            gap = math.floor(gap/3)
        return arr

     

    展开全文
  • package lianxi.Demo; import java.util.ArrayList; import java.util.List;... * (字母进行排序,如:s,a,g,d,b; 控制台输入 a b d g s) */ public class DemoSort { public static void main(St...
  • 由于字符串S可以重新排列,因此,这个题目不是求字符串的匹配问题,而是查找和统计的问题。只需统计Bulbasaur这个单词中每个字符出现的次数,最少出现次数就是答案。需要注意的是,字母a和字母u均出现两次,在最后...
  • 【Java】编写程序,确定一个字符串s的字符重新排列后能否变成另一个字符串t 在编写之前,应先核实字符集的大小,是否区分大小写,空白字符是否需要考虑 首先考虑两个字符串长度是否相等,如果不相等那么肯定不能...
  • 给出一组关键字序列{29,18,25,47,58,12,51,10},分别给出用希尔排序、直接选择排序算法从小到大排序的结果。 参考施老师等编著的《数据结构》,本代码参考了赵同学的报告。 算法思想: 选择排序的基本思想是依次从待...
  • leetcode1528. 重新排列字符串

    千次阅读 多人点赞 2021-03-08 15:52:11
    你一个字符串 s 和一个 长度相同 的整数数组 indices 。 请你重新排列字符串 s ,其中第 i 个字符需要移动到 indices[i] 指示的位置。 返回重新排列后的字符串。 示例 1: 输入:s = "codeleet", indices = ...
  • 查询的数据进行排序和分组

    千次阅读 2018-03-20 10:32:10
    一、信息进行排序 通过orderby关键字,LINQ可以实现升序和降序排列。LINQ还支持次要排序(也可以按升序和降序排列),只要将需要排序的项用逗号隔开即可。 在一个集合上调用Reverse扩展方法即可翻转该集合中的...
  • 在主程序中输入5字符串,调用sort(s,n)函数n个字符串s进行排序,然后输出排序后的结果。例如:输入字符串Li Xiao Wang Zhang Yu,输出:Zhang Yu Xiao Wang Li。 代码如下 #include <stdio.h> #include <...
  • 重新排列字符串(Java实现)

    万次阅读 2020-10-24 15:18:06
    请你重新排列字符串 s ,其中第 i 个字符需要移动到 indices[i] 指示的位置。 返回重新排列后的字符串。 提示: s.length == indices.length == n 1 <= n <= 100 s 仅包含小写英文字母。 0 <= indices[i] &...
  • sort/qsort字符串排序

    千次阅读 2015-03-30 18:22:56
    转自:http://blog.sina.com.cn/s/blog_9159c90501016xer.html 按照字典序排序: c++版: string s[21];  for(int i=0;...但这只是按照字典序排序的,按长度排序如下: 按长度排序: c++版: #in
  • 给出一个字符串 S,考虑其所有重复子串(S 的连续子串,出现两次或多次,可能会有重叠)。 返回任何具有最长可能长度的重复子串。(如果 S 不含重复子串,那么答案为 ""。) 方法1:后缀数组法 // 后缀数组法 ...
  • C/C++描述 LeetCode 周赛 5472. 重新排列字符串

    千次阅读 多人点赞 2020-07-26 12:23:50
    你一个字符串 `s` 和一个 **长度相同** 的整数数组 `indices` 。 请你重新排列字符串 `s` ,其中第 `i` 个字符需要移动到 `indices[i]` 指示的位置。 返回重新排列后的字符串。
  • 字符串重新排列

    千次阅读 2017-04-05 19:25:29
    一个字符串重新排列,字母排在前面,数字排在后面,并不改变原来字母之间以及数字之间的字符顺序。 如:wjhg1451wet030 ——wjhgwet1451030 我们暂不考虑这些字符串中有其他非法字符,只考虑该字符串只有字母...
  • 给出班里某门课程的成绩单,请你按成绩从高到低成绩单排序输出,如果有相同分数则名字字典序小的在前。 格式 输入格式 第一行为n (n大于0不超过20),表示班里的学生数目; 接下来的n行,每行为每个学生的名字和他...
  • 深入理解B/S与C/S架构

    万次阅读 多人点赞 2018-07-24 16:44:19
    深入理解B/S与C/S架构 阅读目录: 什么是C/S架构 什么是B/S架构 B/S架构的几种形式 发展前景 一、什么是C/S架构 C/S架构是第一种比较早的软件架构,主要用于局域网内。也叫 客户机/服务器...
  • 运行结果:分析:先选定第一个数字,然后将后面的数字依次遍历求和,并与需要的数字...下面将一种简单的方法:先看题目要求:输入一个递增排序的数组和一个数字S,在数组中查找两个数,是的他们的和正好是S,如果...
  • Java 第十一届 蓝桥杯 省模拟赛 字母重新排列

    万次阅读 多人点赞 2020-04-13 16:14:01
    字母重新排列 题目 问题描述 将LANQIAO中的字母重新排列,可以得到不同的单词,如LANQIAO、AAILNOQ等,注意这7个字母都要被用上,单词不一定有具体的英文意义。  请问,总共能排列如多少个不同的单词。 答案提交 这...
  • Lua中table进行排序

    万次阅读 2018-01-20 23:41:54
    lua的table中实现了table.sort()方法,可以table进行排序。这种情况适用于直接以table存储的元素为依据进行的排序。 local tbl = {1,2,4,5,3} function sortGT(a, b) return a > b end print('before sort.') ...
  • 程序分析:首先输入一组数据,然后其进行排序,每次选取一个元素放在其最终位置。上图是按从小到大的顺序排列,从大到小以此类推。 import java.util.Scanner; public class Prog35 { public static void main...
  • #找出来各个元素在字符串中重复个数 s='eeeyyyccceeeeejjjj' ...#倒叙排序字典 dic = sorted(di.items(),key=lambda key:key[1],reverse=True) print(dic) #dic现在是列表形式,转为字典格式, 访问这...
  • 目录 ...请你重新排列字符串 s ,其中第 i 个字符需要移动到 indices[i] 指示的位置。 返回重新排列后的字符串。 示例 1: 输入:s = "codeleet", indices = [4,5,6,7,0,2,1,3] 输出:"lee..
  • ♣题目部分(原文见公众号:python宝) 题目描述 给定一个只包含大写英文字母的字符串S,要求你给出对S重新排列的所有不相同的排列数(包括自己本身)。 如:S为ABA,则不同的...
  • java输入数字排序

    千次阅读 2018-08-04 08:34:25
    输出:输入的数字排序 package scannerDemo; import java.util.Scanner; public class ScannerDemo { public static void main(String[] args) { Scanner s = new Scanner(System.in); String s...
  • 请你重新排列字符串 s ,其中第 i 个字符需要移动到 indices[i] 指示的位置。 返回重新排列后的字符串。 示例 1: 输入:s = “codeleet”, indices = [4,5,6,7,0,2,1,3] 输出:“leetcode” 解释:如图所示,...
  • for(s=file.readLine();s!=null;s=file.readLine()){ //System.out.println(s); list.add(s);//文件内容增加到数组中 } file.close(); Collections.sort(list, new Comparator() { public ...
  •  给定两个字符串,请编写程序,确定其中一个字符串的字符重新排列后,能否变成另一个字符串。这里规定大小写为不同字符,且考虑字符串重点空格。  给定一个string stringA和一个string  stringB,请返回一个...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,035,527
精华内容 414,210
关键字:

给出对s重新排列