C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

C++でのパッチ配列

配列番号と1つの番号があるとします。配列内のいくつかの要素の合計によって範囲[1、n]（両方を含む）の任意の数を形成できるように、配列内に要素を追加できます。必要なパッチの最小数を見つける必要があります。したがって、配列が[1,4]のようで、指定された数値がn =7の場合、出力は1になります。これは、最初の数値が[1]、[4]、および[1,4] =5であるため、次のように追加すると2を配列に入れると、数値は[1]、[2]、[4]、[1,2]、[1,4]、[2,4]、[1,2,4]になるため、合計は値はそれぞれ1、2、4、3、5、6、7になります。

これを解決するには、次の手順に従います-

  • req：=1、i：=0、ret：=0

  • req <=nの場合、do −

    • i

      • req =req + nums [i]

      • iを1増やします

    • それ以外の場合

      • req =req + req

      • retを1増やします

  • retを返す

例

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int minPatches(vector<int>& nums, int n) {
      long long int req = 1;
      int i = 0;
      int ret = 0;
      while(req <= n){
         if(i < nums.size() && nums[i] <= req){
            req += nums[i];
            i++;
         } else {
            req += req;
            ret++;
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,4};
   cout << (ob.minPatches(v, 7));
}

入力

{1,4}

出力

1

  1. 文字列のC++配列

    このセクションでは、C++で文字列の配列を定義する方法を説明します。私たちが知っているように、Cには文字列がありませんでした。文字配列を使用して文字列を作成する必要があります。したがって、文字列の配列を作成するには、文字の2次元配列を作成する必要があります。各行は、その行列に異なる文字列を保持しています。 C ++には、stringというクラスがあります。このクラスオブジェクトを使用すると、文字列型データを格納し、それらを非常に効率的に使用できます。オブジェクトの配列を作成できるので、文字列の配列を簡単に作成できます。 その後、文字列型のベクトルオブジェクトを作成し、それらを配列として使用

  2. C++での並べ替え

    このセクションでは、C++で並べ替えアルゴリズムを実行する方法を説明します。並べ替えられた配列は、各要素が数値、アルファベット順などの順序で並べ替えられた配列です。バブルソート、挿入ソート、選択ソート、マージソート、クイックソート、ヒープソートなど、数値配列をソートするための多くのアルゴリズムがあります。選択ソートを使用した配列のソートの詳細については、以下を参照してください。 選択ソートは、ソートされた配列を生成するソート方法です。これは、配列内の最小の要素を繰り返し見つけて、ソートされていない部分の先頭にある要素と交換することによって行われます。 選択ソートを使用してソートされた配列を