成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[Leetcode] Expression Add Operators 添加運算符

sumory / 1387人閱讀

摘要：問題在于如何將問題拆分成多次搜索。然而，乘法如何處理呢這里我們需要用一個變量記錄乘法當(dāng)前累乘的值，直到累乘完了，遇到下一個加號或減號再將其算入計算結(jié)果中。這樣的計算結(jié)果就是。注意第一次搜索不添加運算符，只添加數(shù)字，就不會出現(xiàn)這種表達(dá)式了。

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 -> []
深度優(yōu)先搜索 復(fù)雜度

時間 O(N^2) 空間 O(N)

思路

因為要輸出所有可能的情況，必定是用深度優(yōu)先搜索。問題在于如何將問題拆分成多次搜索。加減法很好處理，每當(dāng)我們截出一段數(shù)字時，將之前計算的結(jié)果加上或者減去這個數(shù)，就可以將剩余的數(shù)字字符串和新的計算結(jié)果代入下一次搜索中了，直到我們的計算結(jié)果和目標(biāo)一樣，就完成了一次搜索。然而，乘法如何處理呢？這里我們需要用一個變量記錄乘法當(dāng)前累乘的值，直到累乘完了，遇到下一個加號或減號再將其算入計算結(jié)果中。這里有兩種情況:

乘號之前是加號或減號，例如2+3*4，我們在2那里算出來的結(jié)果，到3的時候會加上3，計算結(jié)果變?yōu)?。在到4的時候，因為4之前我們選擇的是乘號，這里3就應(yīng)該和4相乘，而不是和2相加，所以在計算結(jié)果時，要將5先減去剛才加的3得到2，然后再加上3乘以4，得到2+12=14，這樣14就是到4為止時的計算結(jié)果。

另外一種情況是乘號之前也是乘號，如果2+3*4*5，這里我們到4為止計算的結(jié)果是14了，然后我們到5的時候又是乘號，這時候我們要把剛才加的3*4給去掉，然后再加上3*4*5，也就是14-3*4+3*4*5=62。這樣5的計算結(jié)果就是62。

因為要解決上述幾種情況，我們需要這么幾個變量，一個是記錄上次的計算結(jié)果currRes，一個是記錄上次被加或者被減的數(shù)prevNum，一個是當(dāng)前準(zhǔn)備處理的數(shù)currNum。當(dāng)下一輪搜索是加減法時，prevNum就是簡單換成currNum，當(dāng)下一輪搜索是乘法時，prevNum是prevNum乘以currNum。

注意

第一次搜索不添加運算符，只添加數(shù)字，就不會出現(xiàn)+1+2這種表達(dá)式了。

我們截出的數(shù)字不能包含0001這種前面有0的數(shù)字，但是一個0是可以的。這里一旦截出的數(shù)字前導(dǎo)為0，就可以return了，因為說明前面就截的不對，從這之后都是開始為0的，后面也不可能了。

代碼 
public class Solution {
    
    List res;
    
    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){
        // 如果計算結(jié)果等于目標(biāo)值，且所有數(shù)都用完了，則是有效結(jié)果
        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);
            // 對于前導(dǎo)為0的數(shù)予以排除
            if(currStr.length() > 1 && currStr.charAt(0) == "0"){
                // 這里是return不是continue
                return;
            }
            // 得到當(dāng)前截出的數(shù)
            long currNum = Long.parseLong(currStr);
            // 去掉當(dāng)前的數(shù)，得到下一輪搜索用的字符串
            String next = num.substring(i);
            // 如果不是第一個字母時，可以加運算符，否則只加數(shù)字
            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 {
                // 第一個數(shù)
                helper(next, target, currStr, currNum, currNum);
            }

        }
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/64601.html

相關(guān)文章

  • [Leetcode] Basic Calculator/Evaluate Expression 設(shè)

    摘要：雙棧法四則運算括號復(fù)雜度時間空間思路算符優(yōu)先算法，核心維護(hù)兩個棧，一個操作數(shù)棧，一個操作符棧。 Basic Calculator 2 Implement a basic calculator to evaluate a simple expression string. The expression string contains only non-negative integers...

    starsfun 評論0 收藏0

  • [LeetCode] 282. Expression Add Operators

    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...

    wangjuntytl 評論0 收藏0

  • 282. Expression Add Operators

    摘要：題目鏈接動態(tài)規(guī)劃問題，最后要求全部滿足條件的。還有個問題是取數(shù)字的時候可能超過的范圍，用來處理。的做法，討論切分點從到，本質(zhì)和做法是一樣的，復(fù)雜度也不會降低。關(guān)鍵是求值，又變成原來的問題了，所以這題感覺不能加。 282. Expression Add Operators 題目鏈接：https://leetcode.com/problems... 動態(tài)規(guī)劃問題，最后要求全部滿足條件的pa...

    enda 評論0 收藏0

  • Java中多個ifelse語句的替代設(shè)計

    摘要：但是有可能嵌套的語句只是轉(zhuǎn)移到了工廠類，這違背了我們的目的。這樣可以減少嵌套語句的數(shù)量，并將責(zé)任委托給單個值。一個評估規(guī)則和返回基于輸入的結(jié)果。首先，我們將定義一個接口其次，讓我們實現(xiàn)一個所述接受一個表達(dá)對象，并返回結(jié)果。概述 ifelse是任何編程語言的重要組成部分。但是我們編寫了大量嵌套的if語句，這使得我們的代碼更加復(fù)雜和難以維護(hù)。 接下來，讓我們探索如何簡化代碼的中的ifelse語句...

    izhuhaodev 評論0 收藏0

  • LeetCode 之 JavaScript 解答第150題 —— 逆波蘭表達(dá)式求值

    摘要：小鹿題目根據(jù)逆波蘭表示法，求表達(dá)式的值。給定逆波蘭表達(dá)式總是有效的。算法思路仔細(xì)觀察上述的逆波蘭表達(dá)式，可以發(fā)現(xiàn)一個規(guī)律就是每遇到一個操作符，就將操作符前的兩個操作數(shù)進(jìn)行運算，將結(jié)果保存到原位置。 Time：2019/4/14Title: Evaluate Reverse Polish NotationDifficulty: MediumAuthor:小鹿 題目：Evaluate ...

    104828720 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<