以下代碼適用于附加輸入。
public class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
return wordBreakMemo(s, new HashSet<>(wordDict), 0, new Boolean[s.length()]);
}
private boolean wordBreakMemo(String s, Set<String> wordDict, int start, Boolean[] memo) {
if (start == s.length()) {
return true;
}
if (memo[start] != null) {
return memo[start];
}
for (int end = start 1; end <= s.length(); end ) {
if (wordDict.contains(s.substring(start, end)) && wordBreakMemo(s, wordDict, end, memo)) {
return memo[start] = true;
}
}
return memo[start] = false;
}
}
但是當我如下將區域變數更改為全域變數時，我的代碼需要更長的時間來執行，導致 LeetCode 上出現“超出時間限制”。
class Solution {
HashSet<String> set;
String s;
Boolean dp[];
public boolean wordBreak(String s, List<String> wordDict) {
set=new HashSet();
set.addAll(wordDict);
this.s=s;
dp=new Boolean[s.length()];
return wordMemo(0);
}
public boolean wordMemo(int start)
{
if(start==s.length())
return true;
if(dp[start]!=null)
return dp[start];
for(int i=start 1; i<=s.length(); i )
{
if(set.contains(s.substring(start, i)) && wordMemo(i))
{
dp[start]=true;
return true;
}
}
return false;
}
}
輸入：
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"
["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]
有人可以解釋一下這里發生了什么嗎？
uj5u.com熱心網友回復：
全域變數沒有較慢的獲取時間，沒有。
每當您在編碼挑戰中超過時間限制時，您應該假設您的演算法或資料結構存在缺陷或錯誤。它絕不是諸如獲取時間或訪問修飾符或您選擇的語言之類的微觀因素。即使您可以通過更好的記憶體訪問模式將程式加速 10%，或者通過從 Python 切換到 C 來加速 100%，您也可能會減少 10,000% 或 10,000,000%，而不是 100%。當挑戰設計者期望 O(n) 時，如果您的程式意外地為 O(n 2 ) 或 O(2 n )，那就是多么糟糕。
在這里，第一個程式有：
return memo[start] = false;
而第二個剛剛：
return false;
它從不記憶false結果。有更多的重復計算，足以殺死演算法的 Big-O 時間復雜度。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/424346.html
下一篇：一些模hijinkery