亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

282. Expression Add Operators

enda / 2532人閱讀

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

282. Expression Add Operators

題目鏈接：https://leetcode.com/problems...

動(dòng)態(tài)規(guī)劃問題，最后要求全部滿足條件的path。subproblem是：dp[i]: possible sum of s[0, i+1]，function是：dp[i] = dp[i-k] + (-prev + prev*cur, +cur, -cur)
注意s[i-k+1]如果等于0，那么k只能等于1，如果有除的時(shí)候也不能是0，開頭的數(shù)字多帶帶處理，因?yàn)榍懊鏇]有符號(hào)，dfs來解。還有個(gè)問題是取數(shù)字的時(shí)候可能 超過int的范圍，用long來處理。

public class Solution {
    public List addOperators(String num, int target) {
        List res = new ArrayList();
        dfs(res, num, "", 0, 0, target, 0);
        return res;
    }
    
    private void dfs(List res, String num, String path, int dep, long sum, int target, long prev) {
        if(dep == num.length()) {
            if(sum == target) res.add(path);
            return;
        }
        
        for(int i = dep; i< num.length(); i++) {
            // 0 can not be the start of number if more than 2 digits
            if(num.charAt(dep) == "0" && i > dep) break;
            long cur = Long.parseLong(num.substring(dep, i+1));
            if(dep == 0) dfs(res, num, path+cur, i+1, cur, target, cur);
            else {
                dfs(res, num, path + "+" + cur, i+1, sum+cur, target, cur);
                dfs(res, num, path + "-" + cur, i+1, sum-cur, target, -cur);
                dfs(res, num, path + "*" + cur, i+1, sum-prev+prev*cur, target, prev*cur);
                // if(cur != 0) dfs(res, num, path + "/" + cur, i+1, sum-prev+prev/cur, target, prev/cur);
            }
        }
    }
}

divide and conquer的做法，討論切分點(diǎn)從left+1到right，本質(zhì)和dfs做法是一樣的，復(fù)雜度也不會(huì)降低。參考：
http://bookshadow.com/weblog/...

關(guān)于memo的，這里應(yīng)該記的是suffix已經(jīng)算過的所有值，也就是說把所有s[i+1:]可能的所有值和相應(yīng)的path存在一個(gè)hashmap里面。關(guān)鍵是求suffix值，又變成原來的問題了，所以這題感覺不能加memo。

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/66679.html

相關(guān)文章

  • 282. Expression Add Operators

    摘要：唯一需要注意的就是乘法的情況，產(chǎn)生出，到達(dá)的時(shí)候，算出不包含的值，這里是，是乘號(hào)以前的算式值，算乘法部分。 Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * be...

    Caicloud 評(píng)論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 評(píng)論0 收藏0

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

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

    starsfun 評(píng)論0 收藏0

  • [Leetcode] Expression Add Operators 添加運(yùn)算符

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

    sumory 評(píng)論0 收藏0

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

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

    izhuhaodev 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<