資訊專欄INFORMATION COLUMN
摘要：思路一使用索引為字母的數(shù)組來(lái)存儲(chǔ)該字母還剩下幾個(gè)沒有從雜志中找到。每從雜志中找到一個(gè)字母，對(duì)應(yīng)字母位置上的數(shù)字減一，每遇到一個(gè)字母則該字母位置上的數(shù)字加一。如果沒有多余的字母，則說(shuō)明可以找到足夠多的字母拼接。如果找不到，則說(shuō)明無(wú)法完成拼接。
題目
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
假設(shè)有一組字母和一組從雜志中獲取的字母，問是否能夠用從雜志中獲取的字母構(gòu)成想要的那組字母，要求每個(gè)單詞只能使用一次。
思路一使用索引為字母的數(shù)組來(lái)存儲(chǔ)該字母還剩下幾個(gè)沒有從雜志中找到。每從雜志中找到一個(gè)字母，對(duì)應(yīng)字母位置上的數(shù)字減一，每遇到一個(gè)字母則該字母位置上的數(shù)字加一。如果沒有多余的字母，則說(shuō)明可以找到足夠多的字母拼接。
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;
}
思路二：找不到字母就結(jié)束
思路二利用java的API來(lái)查找magazine中從上一個(gè)找到的字母開始，下一個(gè)字母所在的位置。如果找不到，則說(shuō)明無(wú)法完成拼接。
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;
}
想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/72354.html
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...
摘要：月下半旬攻略道題，目前已攻略題。目前簡(jiǎn)單難度攻略已經(jīng)到題，所以后面會(huì)調(diào)整自己，在刷算法與數(shù)據(jù)結(jié)構(gòu)的同時(shí)，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。 一 目錄 不折騰的前端，和咸魚有什么區(qū)別...
摘要：在線網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語(yǔ)言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號(hào)： showImg(htt...
摘要：背景在做小程序時(shí)，關(guān)于默認(rèn)導(dǎo)航欄，我們遇到了以下的問題手機(jī)對(duì)于頁(yè)面的展示不一致，安卓的顯示不居中頁(yè)面的只支持純文本級(jí)別的樣式控制，不能夠做更豐富的效果左上角的事件無(wú)法監(jiān)聽定制路由導(dǎo)航單一，只能夠返回上一頁(yè)，深層級(jí)頁(yè)面的返回不夠友好探索小程序 背景 在做小程序時(shí)，關(guān)于默認(rèn)導(dǎo)航欄，我們遇到了以下的問題： Android、IOS手機(jī)對(duì)于頁(yè)面title的展示不一致，安卓title的顯示不居中...
摘要：背景在做小程序時(shí)，關(guān)于默認(rèn)導(dǎo)航欄，我們遇到了以下的問題手機(jī)對(duì)于頁(yè)面的展示不一致，安卓的顯示不居中頁(yè)面的只支持純文本級(jí)別的樣式控制，不能夠做更豐富的效果左上角的事件無(wú)法監(jiān)聽定制路由導(dǎo)航單一，只能夠返回上一頁(yè)，深層級(jí)頁(yè)面的返回不夠友好探索小程序 背景 在做小程序時(shí)，關(guān)于默認(rèn)導(dǎo)航欄，我們遇到了以下的問題： Android、IOS手機(jī)對(duì)于頁(yè)面title的展示不一致，安卓title的顯示不居中...
閱讀 2313·2023-04-25 16:42
閱讀 1210·2021-11-22 14:45
閱讀 2348·2021-10-19 13:10
閱讀 2833·2021-09-29 09:34
閱讀 3418·2021-09-23 11:21
閱讀 2110·2021-08-12 13:25
閱讀 2201·2021-07-30 15:15
閱讀 3500·2019-08-30 15:54
