剣指offer-アルゴリズムとデータ操作-動的計画、貪欲なアルゴリズムとビット演算

春招刷題ノート-剣指offer-アルゴリズムとデータ操作

アルゴリズムとデータ操作——動的計画、貪欲アルゴリズムとビット演算

動的計画と貪欲アルゴリズム

ロープを切る

ビット演算

バイナリの1の個数を計算する

は、1つの数が2の整数次数であるか否かを判断する

である.

整数mを計算するバイナリは、整数nのバイナリ

を得るために何ビットを変更する必要があるかを計算する.
アルゴリズムとデータ操作——動的計画、貪欲なアルゴリズムとビット演算
ダイナミックプランニングと欲張りアルゴリズム
動的計画には以下のいくつかの特徴がある:一、最大値や最小値などの問題の最適解を求める場合、問題はより小さな重複するサブ問題に分解して解決することができる.
二、全体の問題の最適解はサブ問題の最適解に依存する問題であり、一般的に動的計画を用いて解決する.
三、大きな問題をいくつかの小さな問題に分解し、これらの小さな問題の間には互いに重なり合うより小さなサブ問題がある.
四、サブ問題は大きな問題を分解する過程で繰り返されるため、サブ問題を繰り返し計算することを避けるために、下から上への順序でサブ問題の最適解を先に計算して保存し、それをもとに大きな問題の最適解を求めることができる.上から問題を分析し、下から上へ問題を解く.
縄を切る
長さnのロープを1本あげます.ロープをmセグメントに切ってください(m、nは整数で、n>1で、m≧1).各段の紐の長さをk[0]、k[1]、......、k[m]と記す.k[0]k[1]…*k[m]可能な最大積はいくらですか?例えば、ロープの長さが8の場合、私たちはそれを長さがそれぞれ2、3、3の3段に切って、この時最大の積18を得ます.

//          
#include 
#include 
using namespace std;

// ===================    =====================
int maxProductAfterCutting_solution1(int length) {
    //               ，            
    //                ，          。
    if (length < 2) 
        return 0;
    if (length == 2)
        return 1;
    if (length == 3)
        return 2;

    int* maxpro = new int[length + 1];
    for (int i = 0; i < length + 1; i++)
        maxpro[i] = 0;
    
    //     maxPro[2] = 2,   
    maxpro[0] = 0;
    maxpro[1] = 1;
    maxpro[2] = 2;
    maxpro[3] = 3;

    int max = 0;
    for (int i = 4; i <= length; i++) {
        max = 0;
        for (int j = 1; j <= i / 2; j++) {
            int temp = maxpro[j] * maxpro[i - j];
            if (max < temp)
                max = temp;
        }
        maxpro[i] = max;
    }

    int res = maxpro[length];

    delete[] maxpro;
    return res;
}

// ==================    =====================
int maxProductAfterCutting_solution2(int length) {
    if (length < 2) 
        return 0;
    if (length == 2)
        return 1;
    if (length == 3)
        return 2;
    
    int timesof3 = length / 3;

    if (length - 3 * timesof3 == 1)
        timesof3 -= 1;

    int timesof2 = (length - 3 * timesof3) / 2;

    return (int) (pow(3, timesof3)) * (int)(pow(2, timesof2));
}

// ====================    ====================
void test(const char* testName, int length, int expected)
{
    int result1 = maxProductAfterCutting_solution1(length);
    if(result1 == expected)
        std::cout << "Solution1 for " << testName << " passed." << std::endl;
    else {
        std::cout << "Solution1 for " << testName << " FAILED. ";
        cout << "length: " << length << " expected: " << expected << " result: " << result1 << std::endl;
    }

    int result2 = maxProductAfterCutting_solution2(length);
    if(result2 == expected)
        std::cout << "Solution2 for " << testName << " passed." << std::endl;
    else
        std::cout << "Solution2 for " << testName << " FAILED." << std::endl;
}

void test1()
{
    int length = 1;
    int expected = 0;
    test("test1", length, expected);
}

void test2()
{
    int length = 2;
    int expected = 1;
    test("test2", length, expected);
}

void test3()
{
    int length = 3;
    int expected = 2;
    test("test3", length, expected);
}

void test4()
{
    int length = 4;
    int expected = 4;
    test("test4", length, expected);
}

void test5()
{
    int length = 5;
    int expected = 6;
    test("test5", length, expected);
}

void test6()
{
    int length = 6;
    int expected = 9;
    test("test6", length, expected);
}

void test7()
{
    int length = 7;
    int expected = 12;
    test("test7", length, expected);
}

void test8()
{
    int length = 8;
    int expected = 18;
    test("test8", length, expected);
}

void test9()
{
    int length = 9;
    int expected = 27;
    test("test9", length, expected);
}

void test10()
{
    int length = 10;
    int expected = 36;
    test("test10", length, expected);
}

void test11()
{
    int length = 50;
    int expected = 86093442;
    test("test11", length, expected);
}

int main(int agrc, char* argv[])
{
    test1();
    test2();
    test3();
    test4();
    test5();
    test6();
    test7();
    test8();
    test9();
    test10();
    test11();

    return 0;
}

ビット演算
バイナリの1の個数を計算する
タイトル説明:整数を入力し、その数をバイナリで表す1の数を出力します.ここで負数は補数で表される.

class Solution {
public:
    int  NumberOf1(int n) {
        //     N 1          n        1，   
        //  1       ，  n     ，    n         1，
        //      2      4，  n         1，      ，
        //                    1。          ，
        //           。
        int countof1 = 0;
        unsigned int flag = 1;
        while (flag) {
            if (n & flag)
                ++countof1;
            flag = flag << 1;
        }
        return countof1;
    }
};

//             
class Solution {
public:
    int  NumberOf1(int n) {
        /*
                  ，        1，  ，       
            1，   0，    1   0，    1     0  
          1，1         。     12     1100，  1100
          1   1011,，  ，   1100 1011      1100&1011=1000
            1100     1   0，             1   ，
                 1，                        
         1.        ：
        */
       int countof1 = 0;
       while (n) {
           countof1++;
           n = (n - 1) & n;
       }
       return countof1;
    }
};

1つの数が2の整数次数であるか否かを判断する

bool PowerOf2(int n) {
    /*
              ，        1，  ，       
        1，   0，    1   0，    1     0  
      1，1         。     12     1100，  1100
      1   1011,，  ，   1100 1011      1100&1011=1000
        1100     1   0，             1   ，
             1，                        
     1.
               2     ，                    1 1
                    ，        2     ，      1  
        ，         2     。
    */
    if (n <= 0) return false;
    n = (n - 1) & n;
    if (n == 0)
        return true;
    return false;
}

整数mのバイナリを計算して何ビットを変えなければ整数nのバイナリを得ることができません
構想分析:まずmとnの異或演算を行い、異或演算で得られた1の個数を統計し、すなわちmのバイナリに一定の桁数を変更してnのバイナリを得る.

int NumberNeededChannged(int m, int n) {
    int temp = m ^ n;
    int countof1 = 0;
    while (temp) {
        //    temp 1   
        ++countof1;
        temp = (temp - 1) & temp;
    }

    return countof1;
}