程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> leetcode筆記:Patching Array

leetcode筆記:Patching Array

編輯:關於C++

一. 題目描述

Given a sorted positive integer array nums and an integer n, add/patch elements to the array such that any number in range [1, n] inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.

Example 1:
nums = [1, 3], n = 6
Return 1.

二. 題目分析

題目的大意是,給定一個數組nums和一個數n,求添加最少的數使得區間[1, n]中的每個數都可以由數組nums中元素累加組成。

由於數組已經排序,因此基本的思路是,定義一個整形變量currSum,假設數組nums目前可以累加的數的范圍為[1, currSum),如果此時向數組中添加一個元素kk <= currSum)可以將累加的數的范圍擴充為[1, currSum + k),而題目中要求向數組nums添加元素的次數最少,因此當且僅當k = currSum時,累加數的范圍可以取到上限[1, 2 * currSum)。在遍歷數組nums時,有以下兩種操作:

當數組中有小於等於currSum的元素nums[index]時,則利用數組中的元素,同時currSum += nums[index]; 若沒有,則添加新元素currSum入數組,此時范圍擴展至最大,同時令currSum <<= 1

三. 示例代碼

#include 
#include 

using namespace std;

class Solution {
public:
    int minPatches(vector& nums, int n) {
        int result = 0, index = 0;
        // currSum標記了當前數組nums可累加到的最大范圍[1, currSum)
        for (int currSum = 1; currSum <= n; )
        {
            // 數組內元素小於currSum時,可累加的sum上限增加為
            // currSum + nums[index],然後數組索引值加1
            if (index < nums.size() && nums[index] <= currSum)
                currSum += nums[index++];
            else
            {   
                currSum <<= 1; // 添入元素後,可累加的sum范圍加倍
                ++result;
            }
        }
        return result;
    }
};

四. 小結

這種方法並不容易馬上想到,對於這一類型的問題,特別需要在紙面上多列舉例子,慢慢從中找出規律。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved