剑指Offer的笔记

 l = static_cast<long>(i);//i是整型，l是长整型。
 f = static_cast<float>(i);//在传统方法下，可以进行隐式转换。

 i = static_cast<int>(l);//i是整型，l是长整型，f是浮点型，c是char。
 i = static_cast<int>(f);// i = l，i = f会告警，且会丢失数据。
 c = static_cast<char>(i);//i = （int）l，不会告警，但是程序debug困难。
 

    const int sz = 100; // 定义数组大小，标准C++提倡用常型变量（而不是常数或
    // 符号常量宏）
    struct X {int a[sz];}; // 只包含一个整数数组的结构
    X x; // 定义结构变量，此时结构中的数组元素的值无意义（需要初始化）
    int *px = reinterpret_cast<int *> (&x); // 为了初始化，先把结构转化为int数组
    for (int *i = px; i < px + sz; i++) *i = 0; // 将每个数组元素的值初始化为0
    print(reinterpret_cast<X *> (px)); // 重新转换成结构指针，以便使用
    // 也可以直接使用原来的标识符x
    // 此语句相当于print(&x);

    class CMyString
    {
    public:
        CMyString(char* pData=nullptr);
        CMyString(const CMyString& str);
        /*	 常规正确写法
        CMyString& CMyString：：operator == (const CMyString& str) //注意返回当前类型以支持连续赋值
        {
            if(this == &str) //注意判断输入的与当前的是不是同一个对象
                return *this;
            delete [] this; //注意删除当前空间之后在进行赋值
            m_pData = nullptr;
            
            m_pData = new char[strlen(str.m_pData) + 1];
            strcpy(m_pData,str.m_pData);  //学会使用strcpy
            
            return *this; //记得返回当前 	
        }    
        */
        
        /*  
        1. 较好的方法是，先申请内存再删除当前空间的内存，这样可以避免内存不足异常。
        2. 或者，先创建临时实例，在交换临时实例和原来的实例。
        */
        ~CMyString(void);
    private:
        char* m_pData;
    }

int GetSize(arr[] a){
    return sizeof(a);
}

int main(){
    int data1[] ={1,2,3,4,5};
    int size1 = sizeof(data1);
    
    int * data2 = data1;
    int size2 = sizeof(data2);
    
    int size3 = GetSize(data1);
    
    printf("%d, %d, %d",size1,size2,size3);
    //判断输出的结果？
}

class Solution {

public:
    vector<int> findDuplicates(vector<int>& nums) {

    #if 0 //方法一：时间复杂度空间复杂度比较差
    /**
     * 采用排序遍历的方法
     * 执行用时 :152 ms, 在所有 C++ 提交中击败了30.36%的用户
     * 内存消耗 :16.3 MB, 在所有 C++ 提交中击败了13.75%的用户
     */

    vector<int> dup;
    if(nums.size()<2){
        return dup;
    }
    sort(nums.begin(),nums.end());

    vector<int>::iterator it;
    for(it = nums.begin() + 1;it != nums.end();++it){
        if((*it) == (*(it - 1))){
            dup.push_back((*it));
        }
    }
    return dup;
    #endif

    #if 1
    /**
     * 采用hashtable的方法
     *
     * 28/28 cases passed (92 ms)
	 * Your runtime beats 84.69 % of cpp submissions
     * Your memory usage beats 13.88 % of cpp submissions (16.3 MB)
     */

    vector<int> dup;
    if(nums.size()<2){
        return dup;
    }

    /**
     * 解释：
     *   需要一个辅助输出数组。
     *	 遍历元素，该元素-1下标位置数据修改为当前值的负数，如果便利到该元素对应下标的数据已经是负数了，说
     *	 明已经找到过一次了，便把他添加到输出数组当中
     *      
     *
    */
    vector<int> res;
    for(int v:nums){ 
        v = abs(v);
        if(nums[v-1] < 0) 
            res.push_back(v);
        else 
            nums[v-1] = -nums[v-1];
    }
    return res;



    return dup;
    #endif



    }
};

#include <vector>
#include <iostream>
using namespace std;

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        /**
         * 思路：从右上角开始查找，逐次排除某行某列。
         *      如果大于target则剔除这一列，如果小于target则剔除这一行。
         * 
         * [
         *   [1,   4,  7, 11, 15],
         *   [2,   5,  8, 12, 19],
         *   [3,   6,  9, 16, 22],
         *   [10, 13, 14, 17, 24],
         *   [18, 21, 23, 26, 30]
         *  ]
         * 
         * 
         */
        if(matrix.empty()){
            return false;
        }

        size_t col = matrix.at(0).size();
        size_t row = matrix.size();
        //cout <<"row:"<< row <<"col:"<<col<<endl;

        int colptr = col -1;
        int rowptr = 0;

        bool found = false;
        if(col > 0 && row > 0 ){
            while (rowptr < row && colptr >= 0)
            {
                /* code */
                if(target == matrix[rowptr][colptr]){
                    found = true;
                    break;
                } 
                if(target > matrix[rowptr][colptr]){
                    rowptr++;
                }else
                {
                    colptr--;
                }
            }
        }
        return found;
    }
};

void SortAges(int ages[],int lengh){
    if(ages == nullptr || length <=0)
        return;
    const int olestAge = 99;
    int timesOfAge[oldestAge + 1];
    
    for(int i=0;i< length;++i){
        timesOfAge[i] = 0;
    }
    
    for(int i=0;i<length;++i){
        int age = ages[i];
 		if(age < 0 || age > oldestAge)
            throw new std::exception("age out of range.");
        
        ++ timesOfAge[age];
    }
    
    int index = 0;
    for(int i=0;i<=oldestAge; ++i){
        for(int j=0;j<timesOfAges[i];++j){
            ages[index] = i;
            ++ index;
        }
    }
}

#include <vector>
#include <iostream>
using namespace std;

class Solution {
public:
    /**
     * 用两个指针减少遍历的次数
    */
    int findMin(vector<int>& nums) {
        size_t leftPtr = 0;
        size_t rightPtr = nums.size() -1;
        size_t destinyPtr = 0;
        //cout << "debug:: in the findMin function!"<<endl;
        if(nums.size() < 1)
            cerr << "Invalid Input arry" << endl;
        if(nums.size()==1)
            return nums[0];    
        while (nums[leftPtr] >= nums[rightPtr])
        {
            //cout << "debug:: still in the while!"<<endl;
            /* code */
            if(rightPtr - leftPtr == 1){
                //如果两个指针之差为1则说明已经找到了最小值
                destinyPtr = rightPtr;
                break;
            }
            size_t mid = (rightPtr + leftPtr) / 2;
            if(nums[mid]==nums[leftPtr] && nums[mid] == nums[rightPtr]){
                //如果三个相等没法判断的情况
                //采用顺序查找的方式
                int min = nums[0];
                for(size_t i=0;i<nums.size();++i){
                    if(min > nums[i]){
                        min = nums[i];
                    }
                }
                return min;
            }
            if(nums[mid] > nums[leftPtr]){
                leftPtr = mid;
            }
            if(nums[mid] < nums[rightPtr]){
                rightPtr = mid;
            }
        }
        return nums[destinyPtr];
    }
};

/*
 * @lc app=leetcode.cn id=79 lang=cpp
 *
 * [79] 单词搜索
 */

// @lc code=start

#include <vector>
#include <string>
using namespace std;

/**
 * 思路：回溯法。
 * 87/87 cases passed (456 ms)
 * Your runtime beats 9.21 % of cpp submissions
 * Your memory usage beats 6.3 % of cpp submissions (160.1 MB)
 * 
*/

/*

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.

*/
class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        
        size_t index = 0;
        size_t row = board.size();
        size_t col = board[0].size();

        // 初始化visited矩阵
        vector<bool> init_visited(col,false);
        vector<vector<bool>> visited(row,init_visited);

        bool haspath = false;

        for(int i =0; i < row; ++i){

            for(int j =0;j < col; ++j){
                haspath = findWordCore(board,visited,row,col,word,0,i,j);
                if(haspath){
                    return true;
                }
            }
        }
        return haspath;
    }

    bool findWordCore(
        vector<vector<char>>& board,
        vector<vector<bool>>& visited, 
        size_t rowtotal,
        size_t coltotal,
        string word,
        size_t next_IndexInWord,
        size_t next_row,
        size_t next_col){
        
        if(next_IndexInWord == word.size()){
            return true;
        }

        bool hasPath = false;
        if(
            next_row < rowtotal && 
            next_col < coltotal && 
            board[next_row][next_col] == word[next_IndexInWord] &&
            !visited[next_row][next_col]){
                ++ next_IndexInWord;

                visited[next_row][next_col] = true;

                hasPath = findWordCore(//网上搜索
                    board,
                    visited,
                    rowtotal,
                    coltotal,
                    word,
                    next_IndexInWord,
                    next_row,
                    next_col - 1
                ) || findWordCore(
                    board,
                    visited,
                    rowtotal,
                    coltotal,
                    word,
                    next_IndexInWord,
                    next_row,
                    next_col + 1
                ) || findWordCore(
                    board,
                    visited,
                    rowtotal,
                    coltotal,
                    word,
                    next_IndexInWord,
                    next_row - 1,
                    next_col
                ) ||findWordCore(
                    board,
                    visited,
                    rowtotal,
                    coltotal,
                    word,
                    next_IndexInWord,
                    next_row + 1,
                    next_col
                );

                if (!hasPath)
                {
                    /* code */
                    --next_IndexInWord;
                    visited[next_row][next_col] = false;
                }
            }
        // 放回当前子节点往后是否存在路径
        return hasPath;
    }
};
// @lc code=end

//#define ROBOTMOVERANGE

#ifdef ROBOTMOVERANGE

#include <iostream>
#include <vector>
#include <string>
using namespace std;
/**
 * 当前代码没有经过测试
 * 
 * 
*/

class Solution
{

public:
    size_t rangOfMove(
        size_t threahold,
        size_t rows,
        size_t cols)
    {
        
        vector<bool> init_visit(cols,false);
        vector<vector<bool>> visited (rows,init_visit);

        int count = rangOfMoveCore(threahold,rows,cols,0,0,visited);

        return count;
    }
private:
    /* data */
    size_t rangOfMoveCore(
        size_t threshold,
        size_t rowstotal,
        size_t colstotal,
        size_t row,
        size_t col,
        vector<vector<bool>> &visited

    ){
        int count = 0;
        if(/*在可运动范围之内*/true)
        {
            visited[row][col] = true;

            count = 1 + rangOfMoveCore(
                threshold,rowstotal,colstotal,
                row,col - 1,visited
            ) + rangOfMoveCore(
                threshold,rowstotal,colstotal,
                row,col + 1,visited
            ) + rangOfMoveCore(
                threshold,rowstotal,colstotal,
                row - 1,col,visited
            ) + rangOfMoveCore(
                threshold,rowstotal,colstotal,
                row + 1,col,visited
            );
        }
        return count;

    }


    bool check(
        size_t threshold,size_t rowstotal,
        size_t colstotal,size_t row,size_t col,
        vector<vector<bool>> visited){
            if(row>=0 && col >= 0 &&
                row < rowstotal && col < colstotal && 
                getDigitSum(row) + getDigitSum(col) <= threshold &&
                 !visited[row][col])
                 {
                     return true;
                 }
            return false;
        }
    int getDigitSum(int number){
        int sum = 0;
        while (number > 0)
        {
            /* code */
            sum += number % 10;
            number /= 10;
        }
        return sum;
    }
};

#define CUT_ROPE
#ifdef CUT_ROPE

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

class Solution
{
public:
    int cut_ropeByBP(int n)
    {
        if (2 > n)
        {
            return 0;
        }
        else if (2 == n)
        {
            return 1;
        }
        else if (3 == n)
        {
            return 2;
        }
        // 开始做动规

        vector<int> pd(n + 1, 0);
        pd[0] = 0;
        pd[1] = 1;
        pd[2] = 2;
        pd[3] = 3; //切3为一段的时候，切下来的是3。

        int max = 0;

        for (int i = 4; i <= n; ++i)
        {
            max = 0;
            for(int j=0;j <= i/2 ;++j){
                int p = pd[j] * pd[i-j];
                if (max < p)
                {
                    /* code */
                    max = p;
                }
                //cout<<"debug: max=" << max << "  index=" << i << endl;
                pd[i] = max;
            }   
        }
        //cout<<"debug: " << n << endl;
        max = pd[n];
        return max;

    }

    int cut_ropeByGreedy(int length)
    {
        if (2 > length)
        {
            return 0;
        }
        else if (2 == length)
        {
            return 1;
        }
        else if (3 == length)
        {
            return 2;
        }

        int timesOf3 = length / 3;

        if(length - timesOf3 * 3 == 1){
            timesOf3 -=1;
        }
        int timesOf2 = (length - timesOf3 * 3) / 2;

        return (int)pow(3,timesOf3) * (int)(pow(2,timesOf2));

    }
};

/*
 * @lc app=leetcode.cn id=191 lang=cpp
 *
 * [191] 位1的个数
 */

// @lc code=start

#include <cstdint>
#include <iostream>
using namespace std;
/**
 * 
 * 601/601 cases passed (0 ms)
 * Your runtime beats 100 % of cpp submissions
 * Your memory usage beats 58.53 % of cpp submissions (8.2 MB)
 * 
*/
class Solution {
public:
    int hammingWeight(uint32_t n) {
        
        /**
         * n-1， 把所有该为右边的1都变为零。这个过程能剔除一个一。
         * 右边都变成0，可以用n&(n-1) 做到
        */
       int count = 0;
       while (n)
       {
           /* code */
           ++ count;
           n = (n-1) & n;
       }
       return count;
    }
};
// @lc code=end

/*
 * @lc app=leetcode.cn id=50 lang=cpp
 *
 * [50] Pow(x, n)
 */

 // @lc code=start


 /**
  * 采用 >> 1 的方式，减少运行时间
  * 304/304 cases passed (4 ms)
  * Your runtime beats 71.5 % of cpp submissions
  * Your memory usage beats 93.42 % of cpp submissions (8.2 MB)
 */

#include <iostream>
using namespace std;

class DivZeroException {

	const char* what() {
		return "Math Error, /0";
	}
};


class Solution {
public:
	double myPow(double x, int n) {

		double result = 1.0;
		if (n < 0 && x - 0.0 < 0.0005f && x - 0.0 > -0.0000f) {
			throw DivZeroException();
		}

		if (n == INT_MIN) {
			//避免 INT_MIN 的相反数越界的问题

			++n;// 不越界
			n = -n;//算正数

			// 后边又乘了两个x是因为上边的abs(n) 本来应该是偶数的，但是自己做了处理后相当于少了2个x
			// result = myPow(x * x, abs(n) / 2);
            result = this->unsignedPow(x * x * x * x, n /  4) ;

			return 1.0 / result;
		}

		if (n < 0) {
			//需要算倒数
			unsigned int absEx = (unsigned int)(-n);
			result = this->unsignedPow(x, absEx);
			result = 1 / result;
		}
		else if (n > 0)
		{
			/* code */
			unsigned int absEx = (unsigned int)n;
			result = this->unsignedPow(x, absEx);
		}
		else
		{
			/* code */
			return 1.0f;
		}

		return result;
	}


	double unsignedPow(double x, unsigned int n) {

		if (n == 0)
			return 0;
		else if (n == 1) {
			return x;
		}

		double result = unsignedPow(x, n >> 1);
		result *= result; // 计算二次方
		if ((n & 0x01) == 1) { // 如果次方为奇数，则再最后输出的时候需要 * x;
			result *= x;
		}

		return result;
	}
};
// @lc code=end

#define PRINTONE2NBIT_NUMBER
#ifdef PRINTONE2NBIT_NUMBER

#include <iostream>
#include "stdio.h"
#include <cstring>
using namespace std;

class Solution
{

    /* data */
    /**
     * 用string实现大数的输出。
    */
public:
    void print1ToMaxOfNDigits(int n){
        if(n <= 0){
            return;
        }
        // printf("get into main function\n");

        char* number = new char[n +1];
        
        // printf("start init\n");
        memset(number,'0',n);//每一位复制数字零
        number[n]='\0';//最后一位赋值结束符
        // printf("init finished\n");

        int calcount = 0;
        while (!incrementNumber(number) )
        {

            /* code */
            printf("now the number is:");
            printf("%s\n",number);

            printf("standard output: ");
            printNumberWithout0(number);
            printf("\n");
            // calcount ++;//只是为了防止越界
            // if(calcount > 100000000){
            //     break;
            // }
        }
        // printf("whole function finished");
        return;
    }

private:

    void printNumberWithout0(char* n){
        
        size_t strLength = strlen(n);

        bool isThefirstZero = true;

        for(size_t i=0; i <= strLength; ++i){
            
            if(isThefirstZero){

                if( n[i] != '0'){
                    isThefirstZero = false;
                    printf("%c",n[i]);
                }
            
            }else{
                printf("%s",n + i);
                break;
            }
        }
    }

    bool incrementNumber(char * incrementNumber){
        // printf("start increase function...\n");
        size_t strLength = strlen(incrementNumber);
        //int bitNumber = 0;
        bool overflow = false;
        int takeover = 0;

        int afterAdd = 0;

        // printf("start loop for add & check takeover\n");
        for (int i = strLength -1 ; i >= 0; --i)
        {
            // printf("loop i = %d\n",i);
            afterAdd = incrementNumber[i] - '0' + takeover;
            takeover = 0;
            /* code */
            if(i == strLength -1){//如果是第一位则要+1
                afterAdd++;
            }

            if(afterAdd == 10){

                if (i ==0){ // 如果在最高位的时候进位的话，说明溢出了
                    overflow = true;
                }
                else{
                    takeover = 1;
                    incrementNumber[i] = '0';
                    afterAdd = 0;
                }
            }
            else if (afterAdd <= 9){
                incrementNumber[i] = '0' + afterAdd;
            }
        }
        // printf("ending increase function...");
        return overflow;
    }
};