首页 > 其他分享 >1079. 活字印刷

1079. 活字印刷

时间:2023-05-19 15:46:36浏览次数:55  
标签:tiles return 1079 int length 活字印刷 cntMap new

你有一套活字字模 tiles,其中每个字模上都刻有一个字母 tiles[i]。返回你可以印出的非空字母序列的数目。

注意:本题中,每个活字字模只能使用一次。

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/letter-tile-possibilities
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

回溯

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

class Solution {

    private int solve(Map<Character, Integer> cntMap, Set<Character> characterSet, int n) {
        if (n == 0) {
            return 1;
        }
        int result = 1;
        for (Character character : characterSet) {
            if (cntMap.get(character) > 0) {
                cntMap.merge(character, -1, Integer::sum);
                result += solve(cntMap, characterSet, n - 1);
                cntMap.merge(character, 1, Integer::sum);
            }
        }
        return result;
    }

    public int numTilePossibilities(String tiles) {
        if (tiles == null || tiles.length() == 0) {
            return 0;
        }
        Map<Character, Integer> cntMap = new HashMap<>();
        for (int i = 0; i < tiles.length(); i++) {
            cntMap.merge(tiles.charAt(i), 1, Integer::sum);
        }
        Set<Character> characterSet = cntMap.keySet();
        return solve(cntMap, characterSet, tiles.length()) - 1;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            System.out.println(new Solution().numTilePossibilities(in.next()));
        }
    }
}

DP

class Solution {

    private static final int[][] c = new int[8][8];

    static {
        for (int i = 0; i < 8; i++) {
            c[i][0] = c[i][i] = 1;
            for (int j = 1; j < i; ++j) {
                c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
            }
        }
    }

    public int numTilePossibilities(String tiles) {
        if (tiles == null || tiles.length() == 0) {
            return 0;
        }
        Map<Character, Integer> cntMap = new HashMap<>();
        for (int i = 0; i < tiles.length(); i++) {
            cntMap.merge(tiles.charAt(i), 1, Integer::sum);
        }
        int m = cntMap.size();
        int n = tiles.length();

        int[][] f = new int[m + 1][n + 1];
        f[0][0] = 1;
        int i = 0;
        for (int cnt : cntMap.values()) {
            i++;
            for (int j = 0; j <= n; j++) {
                for (int k = 0; k <= cnt && k <= j; k++) {
                    f[i][j] += f[i - 1][j - k] * c[j][k];
                }
            }
        }
        return Arrays.stream(f[m]).sum() - f[m][0];
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            System.out.println(new Solution().numTilePossibilities(in.next()));
        }
    }
}

标签:tiles,return,1079,int,length,活字印刷,cntMap,new
From: https://www.cnblogs.com/tianyiya/p/17415322.html

相关文章

  • [LeetCode] 1079. Letter Tile Possibilities
    Youhave n  tiles,whereeachtilehasoneletter tiles[i] printedonit.Return thenumberofpossiblenon-emptysequencesofletters youcanmakeusingthelettersprintedonthose tiles.Example1:Input:tiles="AAB"Output:8Explanation:......
  • PAT Basic 1079. 延迟的回文数
    PATBasic1079.延迟的回文数1.题目描述:给定一个\(k+1\)位的正整数\(N\),写成\(a_k⋯a_1a_0\)的形式,其中对所有\(i\)有\(0≤a_i<10\)且\(a_k>0\)。\(N\)被称为一个回文数,当且仅当对所有\(i\)有\(a_i=a_{k−i}\)。零也被定义为一个回文数。非回文数也可以通过一......
  • 【codevs1079】回家
    problemsolutioncodes//标程Dijkstra#include<iostream>#include<algorithm>#include<vector>usingnamespacestd;//Tintn=60,m,vis[1010];//GraphstructEdge{in......
  • 『题解』UVA 10795 A Different Task
    题目传送门双倍经验:LuoguP1242分析汉诺塔相信每一个合格的OIer都听说过并且实现过。这是一个递归的程序。汉诺塔本来就有两个规则:一次只能移动最上面的一个盘......
  • 51nod1079 中国剩余定理
    1079中国剩余定理基准时间限制:1秒空间限制:131072KB分值:0难度:基础题收藏 关注一个正整数K,给出KMod一些质数的结果,求符合条件的最小的......
  • 活字印刷
    rt,用以下胶泥块进行造句(一个不剩的粘过来了)整理档案我很拿手呀!啊……这些表格和理论分析好难读……和浪漫小说不一样。博士,您也读过维多利亚的文学作品吗?悄悄告诉您,我最......
  • 1079. 活字印刷
    你有一套活字字模 tiles,其中每个字模上都刻有一个字母 tiles[i]。返回你可以印出的非空字母序列的数目。注意:本题中,每个活字字模只能使用一次。案例:输入:"AAB"输出:8......
  • 题解 UVA10791
    前言:数学符号约定:\(p\):任意一个质数\(n\)或\(m\):任意一个正整数\(a_i\):唯一分解时质数的指数\(A\):集合若无特殊说明,本篇题解的数学符号将会严格按照上......
  • 1079 延迟的回文数——20分
    给定一个k+1位的正整数N,写成ak…a1a0的形式,其中对所有i有0<=ai<10且ak>0。N被称为一个回文数,当且仅当对所有i有ai=ak-i。零也被定义为一个回文数。......