leetcode383. Ransom Note

KevinYan 發布于2019-08-16 13:48 / 2807人閱讀

摘要：思路一使用索引為字母的數組來存儲該字母還剩下幾個沒有從雜志中找到。每從雜志中找到一個字母，對應字母位置上的數字減一，每遇到一個字母則該字母位置上的數字加一。如果沒有多余的字母，則說明可以找到足夠多的字母拼接。如果找不到，則說明無法完成拼接。

題目

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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