首页 > 其他 > 详细

lc 0227

时间:2020-02-27 21:41:53      阅读:27      评论:0      收藏:0      [点我收藏+]

标签:imp   提交   得到   分享   image   index   

? 1189. “气球” 的最大数量

描述

给你一个字符串?text,你需要使用 text 中的字母来拼凑尽可能多的单词?"balloon"(气球)。

字符串?text 中的每个字母最多只能被使用一次。请你返回最多可以拼凑出多少个单词?"balloon"。

?

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

技术分享图片

解答

思路:
bucket 数组,(或者用map/py 字典实现更好)
统计 ballon 这个字典里的最小数

cpp

todo watch

int maxNumberOfBalloons(char * text){
    int* hashSet=(int*)malloc(sizeof(int)*128);
    memset(hashSet,0,sizeof(int)*128);
    int textLength = 0;
    while(text[textLength]){
        hashSet[text[textLength]]++;
        textLength++;
    }
    
    int wordQty = textLength;
    wordQty = (wordQty>hashSet['a'])?hashSet['a']:wordQty;
    wordQty = (wordQty>hashSet['b'])?hashSet['b']:wordQty;
    wordQty = (wordQty>hashSet['n'])?hashSet['n']:wordQty;
    wordQty = (wordQty>(hashSet['o']>>1))?(hashSet['o']>>1):wordQty;
    wordQty = (wordQty>(hashSet['l']>>1))?(hashSet['l']>>1):wordQty;

    free(hashSet);
    return wordQty;
}

py

class Solution:
    def maxNumberOfBalloons(self, text: str) -> int:
        mydict = {}
        tgt = ['b','a','l','o','n']
        for i in tgt:
            mydict[i] = 0
        for c in text:
            if c in tgt:
                mydict[c] = mydict[c] + 1 # # 这里是否需要初始化mydict的key value(=0)呢?
        counter = mydict['a']
        for k in mydict:
            tmp1 = mydict[k]
            if k == 'l' or k == 'o':
                tmp = tmp1 // 2
                if tmp < counter:
                    counter = tmp
            else:
                if tmp1 < counter:
                    counter = tmp1
        return counter
'''执行用时 :
44 ms
, 在所有 Python3 提交中击败了
37.20%
的用户
内存消耗 :
13.5 MB
, 在所有 Python3 提交中击败了
35.66%
的用户'''

improved py

class Solution:
    def maxNumberOfBalloons(self, text: str) -> int:
        d = collections.Counter(text)
        return min(d['b'], d['a'], d['l'] // 2, d['o'] // 2, d['n'])

? 784. 字母大小写全排列

https://leetcode-cn.com/problems/letter-case-permutation

描述

给定一个字符串S,通过将字符串S中的每个字母转变大小写,我们可以获得一个新的字符串。返回所有可能得到的字符串集合。

示例:
输入: S = "a1b2"
输出: ["a1b2", "a1B2", "A1b2", "A1B2"]

输入: S = "3z4"
输出: ["3z4", "3Z4"]

输入: S = "12345"
输出: ["12345"]

S 的长度不超过12。
S 仅由数字和字母组成。

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

解答

思路:我们统计字母的数量 i,然后2的次方 之 : i^2,这是数量
为了构造i^2 个:howto todo

c: backTrace !! powerful: backTrace; rev me; todo

//C语言实现,递归回溯 todo

#define MAX_SIZE 10240//tt do we really need so big space for g_re??
#define STR_SIZE 15

struct StrRecord {
    char str[STR_SIZE];
    int pos;
};

struct StrRecord g_str;
int g_num = 0;
char **g_re;//tt why double ptr here?: a ptr point other bunch of ptrs;

void backTrace(char *S, int len, int start)
{
    //tt when the recursive goto the end (of the S)
    //tt we can add the recursive result to the g_re.
    if (g_str.pos == len) {
        g_re[g_num++] = strdup(g_str.str);
    }
    //tt otherwise: we start from `start` to traverse
    //tt all the left char in S(using S[i]);
    //tt to set each alpha char to lower / upper
    //tt each alpha has two possible output: lower / upper
    for (int i = start; i < len; i++) {
        if (isalpha(S[i])) {
            int tmpLower = tolower(S[i]);
            g_str.str[g_str.pos++] = tmpLower;
            //tt backTrace always go to next
            backTrace(S, len, i + 1);
            //tt here we see: `g_str.pos--`
            //tt which jst represent: BACKTrace
            g_str.str[g_str.pos--];
            int tmpUpper = toupper(S[i]);
            g_str.str[g_str.pos++] = tmpUpper;
        } else {
            //tt when it's not alpha(aka num)
            //tt all we need to do is give num to g_str.str
            g_str.str[g_str.pos++] = S[i];
        }
        //tt watch this: two lines: are also the keys of backTrace!!
        backTrace(S, len, i + 1);
        g_str.str[g_str.pos--];
    }
}

char **letterCasePermutation(char *S, int *returnSize)
{
    g_re = malloc(sizeof(char *) * MAX_SIZE);
    g_num = 0;
    memset(&g_str, 0, sizeof(g_str));
    int len = strlen(S);
    backTrace(S, len, 0);
    *returnSize = g_num;
    return g_re;
}

py todo watch me; three me

本题跟78 很像

DFS 回溯 看到题目要求组合或者集合,马上想到可以用回溯法:回溯法本来是说对于每个元素都先考虑放它的情况,再考虑不放它的情况;放在这道题的背景里就是,对于每个字母,先考虑放它,再考虑放它的另一种大小写形式。
用dfs实现回溯,start代表目前从扫描到第几位,

如果是digit,就直接加进去,然后下一层递归

如果是alpha,就先加进去,然后下一层递归;再加对立大小写形式, 然后下一层递归。

class Solution:
    def letterCasePermutation(self, S: str) -> List[str]:
        ret = list()
        l = len(S)
        if l == 0:
            return ['']# is the same as [""]? seems yes
        def dfs(start, tmp):
            if (start >= l or len(tmp) >= l):
                # we already find one ans, so add it to ret
                ret.append(tmp)
                return 
            if S[start].isdigit():
                dfs(start + 1, tmp + S[start])
            elif S[start].islower():
                dfs(start + 1, tmp + S[start])
                dfs(start + 1, tmp + S[start].upper())
            elif S[start].isupper():
                dfs(start + 1, tmp + S[start])
                dfs(start + 1, tmp + S[start].lower())

        dfs(0, "")
        return ret
'''
执行用时 :
116 ms
, 在所有 Python3 提交中击败了
17.12%
的用户
内存消耗 :
14.8 MB
, 在所有 Python3 提交中击败了
17.43%
的用户
'''

todo watch ??

BFS 除了用DFS回溯实现,我们也可以用BFS来解题

线性扫描S,
对于扫描到的每个元素, 都把它的大小写形式分别加到,目前的res里的所有结果里,这样可以得到temp,

然后用temp覆盖res。

比如对于S = "a1b2",

扫描到a时, res = [a, A]

扫描到b时, res = [a1, A1], temp = [a1b, a1B, A1b, A1B]

class Solution(object):
    def letterCasePermutation(self, S):
        """
        :type S: str
        :rtype: List[str]
        """
        import copy
        res = [""]
        
        for i, x in enumerate(S):
            # if len(res) == 0:
            #     res.append(x)
            if x.isdigit():#数字就每个答案都加进去
                for index, item in enumerate(res):
                    res[index] += (x)
            elif x.isupper():#字母就每个答案先放自己再放对立面
                temp = list()
                for index, item in enumerate(res):
                    # print item
                    temp.append(item + (x))
                    temp.append(item + (x.lower()))
                res = copy.deepcopy(temp[:])
            elif x.islower():
                temp = list()
                for index, item in enumerate(res):
                    temp.append(item + (x))
                    temp.append(item + (x.upper()))       
                res = copy.deepcopy(temp[:])
            # print temp
        return res

BitMap

Bitmap法,字符串S的长度为l, 则总共会有 2** l种结果,换成二进制就是0 ~ 2 **l - 1个数,
对于每个数,如果某个位上是0, 就放小写;是1, 就放大写。

class Solution(object):
    def letterCasePermutation(self, S):
        l = len(S)
        n = 2 ** l
        res = list()
        if l == 0:
            res.append("")
        for i in range(0, n): #得到0 ~ 2 ** l 的每个数
            temp = ""

            for j in range(0, l):
                if ((2 ** j) &i) == 0:#当前位是0, 放小写
                    temp += S[j].lower()
                else: #放大写
                    temp += S[j].upper()
            if temp not in res:
                res.append(temp)
        return res

lc 0227

标签:imp   提交   得到   分享   image   index   

原文:https://www.cnblogs.com/paulkg12/p/12374211.html

(0)
(0)
   
举报
评论 一句话评论(0
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号