摘要:問題在于如何將問題拆分成多次搜索。然而,乘法如何處理呢這里我們需要用一個變量記錄乘法當前累乘的值,直到累乘完了,遇到下一個加號或減號再將其算入計算結果中。這樣的計算結果就是。注意第一次搜索不添加運算符,只添加數字,就不會出現這種表達式了。
Expression Add Operators
深度優先搜索 復雜度Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value.
Examples:
"123", 6 -> ["1+2+3", "1*2*3"] "232", 8 -> ["2*3+2", "2+3*2"] "105", 5 -> ["1*0+5","10-5"] "00", 0 -> ["0+0", "0-0", "0*0"] "3456237490", 9191 -> []
時間 O(N^2) 空間 O(N)
思路因為要輸出所有可能的情況,必定是用深度優先搜索。問題在于如何將問題拆分成多次搜索。加減法很好處理,每當我們截出一段數字時,將之前計算的結果加上或者減去這個數,就可以將剩余的數字字符串和新的計算結果代入下一次搜索中了,直到我們的計算結果和目標一樣,就完成了一次搜索。然而,乘法如何處理呢?這里我們需要用一個變量記錄乘法當前累乘的值,直到累乘完了,遇到下一個加號或減號再將其算入計算結果中。這里有兩種情況:
乘號之前是加號或減號,例如2+3*4,我們在2那里算出來的結果,到3的時候會加上3,計算結果變為5。在到4的時候,因為4之前我們選擇的是乘號,這里3就應該和4相乘,而不是和2相加,所以在計算結果時,要將5先減去剛才加的3得到2,然后再加上3乘以4,得到2+12=14,這樣14就是到4為止時的計算結果。
另外一種情況是乘號之前也是乘號,如果2+3*4*5,這里我們到4為止計算的結果是14了,然后我們到5的時候又是乘號,這時候我們要把剛才加的3*4給去掉,然后再加上3*4*5,也就是14-3*4+3*4*5=62。這樣5的計算結果就是62。
因為要解決上述幾種情況,我們需要這么幾個變量,一個是記錄上次的計算結果currRes,一個是記錄上次被加或者被減的數prevNum,一個是當前準備處理的數currNum。當下一輪搜索是加減法時,prevNum就是簡單換成currNum,當下一輪搜索是乘法時,prevNum是prevNum乘以currNum。
注意第一次搜索不添加運算符,只添加數字,就不會出現+1+2這種表達式了。
我們截出的數字不能包含0001這種前面有0的數字,但是一個0是可以的。這里一旦截出的數字前導為0,就可以return了,因為說明前面就截的不對,從這之后都是開始為0的,后面也不可能了。
代碼public class Solution { Listres; public List addOperators(String num, int target) { helper(num, target, "", 0, 0); return res; } private void helper(String num, int target, String tmp, long currRes, long prevNum){ // 如果計算結果等于目標值,且所有數都用完了,則是有效結果 if(currRes == target && num.length() == 0){ String exp = new String(tmp); res.add(exp); return; } // 搜索所有可能的拆分情況 for(int i = 1; i <= num.length(); i++){ String currStr = num.substring(0, i); // 對于前導為0的數予以排除 if(currStr.length() > 1 && currStr.charAt(0) == "0"){ // 這里是return不是continue return; } // 得到當前截出的數 long currNum = Long.parseLong(currStr); // 去掉當前的數,得到下一輪搜索用的字符串 String next = num.substring(i); // 如果不是第一個字母時,可以加運算符,否則只加數字 if(tmp.length() != 0){ // 乘法 helper(next, target, tmp+"*"+currNum, (currRes - prevNum) + prevNum * currNum, prevNum * currNum); // 加法 helper(next, target, tmp+"+"+currNum, currRes + currNum, currNum); // 減法 helper(next, target, tmp+"-"+currNum, currRes - currNum, -currNum); } else { // 第一個數 helper(next, target, currStr, currNum, currNum); } } } }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/64601.html
摘要:雙棧法四則運算括號復雜度時間空間思路算符優先算法,核心維護兩個棧,一個操作數棧,一個操作符棧。 Basic Calculator 2 Implement a basic calculator to evaluate a simple expression string. The expression string contains only non-negative integers...
Problem Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value...
摘要:題目鏈接動態規劃問題,最后要求全部滿足條件的。還有個問題是取數字的時候可能超過的范圍,用來處理。的做法,討論切分點從到,本質和做法是一樣的,復雜度也不會降低。關鍵是求值,又變成原來的問題了,所以這題感覺不能加。 282. Expression Add Operators 題目鏈接:https://leetcode.com/problems... 動態規劃問題,最后要求全部滿足條件的pa...
摘要:但是有可能嵌套的語句只是轉移到了工廠類,這違背了我們的目的。這樣可以減少嵌套語句的數量,并將責任委托給單個值。一個評估規則和返回基于輸入的結果。首先,我們將定義一個接口其次,讓我們實現一個所述接受一個表達對象,并返回結果。概述 ifelse是任何編程語言的重要組成部分。但是我們編寫了大量嵌套的if語句,這使得我們的代碼更加復雜和難以維護。 接下來,讓我們探索如何簡化代碼的中的ifelse語句...
摘要:小鹿題目根據逆波蘭表示法,求表達式的值。給定逆波蘭表達式總是有效的。算法思路仔細觀察上述的逆波蘭表達式,可以發現一個規律就是每遇到一個操作符,就將操作符前的兩個操作數進行運算,將結果保存到原位置。 Time:2019/4/14Title: Evaluate Reverse Polish NotationDifficulty: MediumAuthor:小鹿 題目:Evaluate ...
閱讀 2121·2023-04-26 02:19
閱讀 1914·2021-11-19 09:40
閱讀 1704·2021-09-29 09:35
閱讀 3575·2021-09-29 09:34
閱讀 4297·2021-09-07 10:16
閱讀 5530·2021-08-11 11:14
閱讀 3578·2019-08-30 15:54
閱讀 1629·2019-08-30 15:53