0014數位成本和為目标值的最大數字

數位成本和為目标值的最大數字

編号：0014

試題來源：leetcode

文章目錄

• 題目描述
• 解答算法
• • 算法思路
  • 代碼實作
  • 複雜度分析

題目描述

給定整數數組

cost

和一個整數

target

。傳回滿足如下規則的可以得到的最大整數：

• 給目前結果添加一個數位

  i+1

  的成本為

  cost[i]

  (

  cost

  數組的下标從0開始)
• 總成本必須恰好等于

  target

• 添加的位數中沒有數字0

傳回類型

string

如果無法得到任何整數，那麼傳回

。

解答算法

算法思路

很顯然這是一個0-1完全背包問題。

我用的是暴力做法，時間複雜度太高，失敗了

參考代碼

target

是目标的花費，顯然，

cost

數組中的每一個值都是正數，因為一旦存在

，那麼可以無窮添加，就沒有最大值了。是以 c o s t [ i ] ≥ 1 cost[i]\geq 1 cost[i]≥1。是以可以設定一個temp數組，其中元素是

string

類型，

temp[i]

存儲當總花費為

i

的時候産生的最大

string

。

顯然有如下遞推公式

temp[target] = max{temp[target - cost[i]]+cost[i],cost[i] + temp[target - cost[i]]}

，如果 t a r g e t − c o s t [ i ] = = 0 target - cost[i] == 0 target−cost[i]==0說明這是第一個添加的元素。如果 t a r g e t − c o s t [ i ] < 0 target - cost[i] < 0 target−cost[i]<0說明，該

target

沒有滿足條件的

string

；如果

temp[target - cost[i]]

對應的

string

為空，說明它不存在，那麼自然不能在一個不存在的字元串上加數位是以也不存在。

通過遞推公式，一個個周遊

temp[i]

，最後就能夠解決問題

代碼實作

class Solution {
public:
    string largestNumber(vector<int>& cost, int target) {
        int len = cost.size();
        unordered_map<int, int> cost2num;  //key存放的是花費，對應得是下标
        for(int i = 0; i < len; i++) {   //更新花費map
            if(cost2num.find(cost[i]) == cost2num.end() || cost2num[cost[i]] < i + 1) {
                cost2num[cost[i]] = i + 1;
            }
        }   
        vector<string> temp(target + 1, "");  //vector數組得長度為target+1,初始值均為空字元串
        for(int i = 1; i <= target; i++) {  //從1開始，逐漸提升target的值
            for(const auto& [cost, num]: cost2num) {
                int index = i - cost;       //如果添加了目前數位，是在temp[i-cost]的基礎上添加的
                if(index == 0 || index > 0 && temp[index] != "") { //如果index == 0說明目前添加的i是第一個數位;如果index>0，那麼需要temp[i-cost]有合适的取值，才能添加新的數位
                    string second = to_string(num);
                    string new_str = temp[index] > second? temp[index] + second: second + temp[index];  //産生添加數位之後的string
                    if(new_str.size() > temp[i].size() || new_str.size() == temp[i].size() && new_str > temp[i]) {  //和目前temp[i]進行對比，誰大選誰
                        temp[i] = new_str;
                    }
                }
            }
        }
        return temp[target] == ""? "0": temp[target];  //非空傳回string，否則傳回0
    }
};
           

複雜度分析

• 時間複雜度：整個過程中周遊了 O ( t a r g e t ) O(target) O(target)的時間，同時每一次都進行了比較操作以及對9個可以添加的數位的比較，最終的時間複雜度為 O ( n ) O(n) O(n)
• 空間複雜度：申請了 O ( t a r g e t ) O(target) O(target)的額外空間，時間複雜度為 O ( n ) O(n) O(n)