282. Expression Add Operators

enda 發(fā)布于2019-08-14 17:35 / 2444人閱讀

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

282. Expression Add Operators

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

動(dòng)態(tài)規(guī)劃問(wèn)題，最后要求全部滿足條件的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，開(kāi)頭的數(shù)字多帶帶處理，因?yàn)榍懊鏇](méi)有符號(hào)，dfs來(lái)解。還有個(gè)問(wèn)題是取數(shù)字的時(shí)候可能超過(guò)int的范圍，用long來(lái)處理。

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)算過(guò)的所有值，也就是說(shuō)把所有s[i+1:]可能的所有值和相應(yīng)的path存在一個(gè)hashmap里面。關(guān)鍵是求suffix值，又變成原來(lái)的問(wèn)題了，所以這題感覺(jué)不能加memo。