leetcode383. Ransom Note

KevinYan 发布于2019-08-16 13:48 / 2718人阅读

摘要：思路一使用索引为字母的数组来存储该字母还剩下几个没有从杂志中找到。每从杂志中找到一个字母，对应字母位置上的数字减一，每遇到一个字母则该字母位置上的数字加一。如果没有多余的字母，则说明可以找到足够多的字母拼接。如果找不到，则说明无法完成拼接。

题目

Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.

Each letter in the magazine string can only be used once in your ransom note.

Note:
You may assume that both strings contain only lowercase letters.

canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true

假设有一组字母和一组从杂志中获取的字母，问是否能够用从杂志中获取的字母构成想要的那组字母，要求每个单词只能使用一次。

思路一

使用索引为字母的数组来存储该字母还剩下几个没有从杂志中找到。每从杂志中找到一个字母，对应字母位置上的数字减一，每遇到一个字母则该字母位置上的数字加一。如果没有多余的字母，则说明可以找到足够多的字母拼接。

    public boolean canConstruct(String ransomNote, String magazine) {
        if(ransomNote.isEmpty()) return true;
        if(ransomNote.length() > magazine.length()) return false;
        int p1 = 0, p2 = 0;
        int[] count = new int[26];
        int wordCount = 0;
        while(p1 < ransomNote.length() && p2 < ransomNote.length()) {
            char c1 = ransomNote.charAt(p1);
            char c2 = magazine.charAt(p2);
            if(++count[c1-"a"] == 1) {
                wordCount++;
            }
            if(--count[c2-"a"] == 0) {
                wordCount--;
            }
            
            p1++;
            p2++;
        }
        
        while(p2 < magazine.length()) {
            if(wordCount == 0) break;
            char c = magazine.charAt(p2);
            count[c-"a"]--;
            if(count[c-"a"] == 0) {
                wordCount--;
            }
            p2++;
        }
        return wordCount == 0;
    }

思路二：找不到字母就结束

思路二利用java的API来查找magazine中从上一个找到的字母开始，下一个字母所在的位置。如果找不到，则说明无法完成拼接。

    public boolean canConstruct(String ransomNote, String magazine) {
        int len=ransomNote.length();
        int[] index = new int[128];
        for(int i = 0; i < len; i++){
            char cu=ransomNote.charAt(i);
            int result=magazine.indexOf(cu,index[cu]);
            if(result == -1){
                return false;
            }
            else{
                index[cu]=result + 1;   
            }   
        }
        return true;
    }

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

GPU云服务器云服务器 Ransom Leetcod LeetCode note

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/72354.html

[LeetCode] 383. Ransom Note

Problem Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazi...

AlanKeene 2019-08-19 11:17 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0
小程序自定义导航栏（适配所有手机）

摘要：背景在做小程序时，关于默认导航栏，我们遇到了以下的问题手机对于页面的展示不一致，安卓的显示不居中页面的只支持纯文本级别的样式控制，不能够做更丰富的效果左上角的事件无法监听定制路由导航单一，只能够返回上一页，深层级页面的返回不够友好探索小程序背景在做小程序时，关于默认导航栏，我们遇到了以下的问题： Android、IOS手机对于页面title的展示不一致，安卓title的显示不居中...

jayzou 2019-08-30 15:44 评论0 收藏0
小程序自定义导航栏（适配所有手机）

摘要：背景在做小程序时，关于默认导航栏，我们遇到了以下的问题手机对于页面的展示不一致，安卓的显示不居中页面的只支持纯文本级别的样式控制，不能够做更丰富的效果左上角的事件无法监听定制路由导航单一，只能够返回上一页，深层级页面的返回不够友好探索小程序背景在做小程序时，关于默认导航栏，我们遇到了以下的问题： Android、IOS手机对于页面title的展示不一致，安卓title的显示不居中...

Yu_Huang 2019-08-26 10:49 评论0 收藏0