Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.
Mündəricat
Problem bəyanat
The Mötərizələr əlavə etməyin müxtəlif yolları LeetCode Həlli – “Mötərizələr əlavə etməyin müxtəlif yolları” rəqəmlərin və operatorların sətir ifadəsi verildiyini bildirir. Nömrələri və operatorları qruplaşdırmaq üçün müxtəlif mümkün yolların hesablanmasından bütün mümkün nəticələri qaytarmalıyıq.
Cavabı istənilən qaydada qaytarın.
Misal:
Input: expression = "2-1-1"
Output: [0,2]
Explanation:
- ((2-1)-1) = 0, mümkün nəticələrdən biridir.
- (2-(1-1)) = 2, həm də mümkün nəticələrdən biridir.
Input: expression = "2*3-4*5"
Output: [-34,-14,-10,-10,10]
Explanation:
- (2*(3-(4*5))) = -34
- ((2*3)-(4*5)) = -14
- ((2*(3-4))*5) = -10
- (2*((3-4)*5)) = -10
- (((2*3)-4)*5) = 10
- Deməli, [-34, -14, -10, -10, 10] mümkün nəticələrdir.
Yanaşma
Idea:
- Bu problemi həll etmək üçün əsas fikir istifadə etməkdir Recursion.
- Rekursiyanın hər addımında üzərində işləməli olduğumuz ifadənin sol və sağ ucları var.
- Hər bir i indeksi üçün təkrarlayın diapazon [l,r] və yenidən, [l,i-1] və [i+1,r] üçün rekurs bir şərtlə ki, cari simvol operator olsun və qaytarılan cavablar toplusunu müvafiq olaraq adlandırılmış sol və sağ vektorda saxlayın.
- İndi, müvafiq olaraq sol və sağ vektorlarda qiymətləndirilən hər bir ifadə üçün nəticəni tətbiq etdikdən sonra bütün yeni dəyərləri tapın. a op b, burada a solda operand, b sağda operand və op operatordur.
- Cari vəziyyət üçün cavabı qaytarın {l,r};
- Biz də istifadə edərək nəticəni yadda saxlaya bilərik dinamik proqramlaşdırma.
Kodu
Mötərizələr əlavə etməyin müxtəlif yolları Leetcode C++ Həlli:
class Solution {
public:
map<pair<int,int>,vector<int>> dp;
vector<int> solve(int l,int r,string expression){
if(dp.count({l,r})){
return dp[{l,r}];
}
vector<int> ans;
for(int i=l;i<=r;i++){
if(expression[i]=='+' or expression[i]=='-' or expression[i]=='*'){
vector<int> left = solve(l,i-1,expression);
vector<int> right = solve(i+1,r,expression);
for(auto& num1:left){
for(auto& num2:right){
if(expression[i]=='+'){
ans.push_back(num1+num2);
}
else if(expression[i]=='-'){
ans.push_back(num1-num2);
}
else{
ans.push_back(num1*num2);
}
}
}
}
}
if(ans.empty()){
ans.push_back(stoi(expression.substr(l,r-l+1)));
}
return dp[{l,r}] = ans;
}
vector<int> diffWaysToCompute(string expression) {
return solve(0,expression.length()-1,expression);
}
};
Mötərizələr əlavə etməyin müxtəlif yolları Leetcode Java Həlli:
public class Solution {
public List<Integer> diffWaysToCompute(String input) {
List<Integer> ret = new LinkedList<Integer>();
for (int i=0; i<input.length(); i++) {
if (input.charAt(i) == '-' ||
input.charAt(i) == '*' ||
input.charAt(i) == '+' ) {
String part1 = input.substring(0, i);
String part2 = input.substring(i+1);
List<Integer> part1Ret = diffWaysToCompute(part1);
List<Integer> part2Ret = diffWaysToCompute(part2);
for (Integer p1 : part1Ret) {
for (Integer p2 : part2Ret) {
int c = 0;
switch (input.charAt(i)) {
case '+': c = p1+p2;
break;
case '-': c = p1-p2;
break;
case '*': c = p1*p2;
break;
}
ret.add(c);
}
}
}
}
if (ret.size() == 0) {
ret.add(Integer.valueOf(input));
}
return ret;
}
}
Mötərizələr əlavə etməyin müxtəlif yolları üçün mürəkkəblik təhlili Leetcode həlli
Zamanın mürəkkəbliyi
Yuxarıdakı kodun zaman mürəkkəbliyi Katalan nömrəsi. Hər bir vəziyyət üçün [l,r], biz [l,r] diapazonunda iterasiya edirik və onu iki dəstə [l,i-1] və [i+1,r] bölürük ki, bu da Katalan nömrəsinin hesablanmasına tərs bərabərdir. Beləliklə, zaman mürəkkəbliyi Katalan rəqəmləri ilə eynidir.
Kosmik Mürəkkəblik
Yuxarıdakı kodun kosmik mürəkkəbliyi O (cavab ölçüsü).
