Sorry, your browser cannot access this site
This page requires browser support (enable) JavaScript
Learn more >

剑指Offer的笔记

发布于：Mar 25, 2020
次浏览

本篇笔记，记录剑指offer中的问题(不只是面试题)。

对某些面试题，同时也指出leetcode对应题目的网址

:dagger:需要对文档进行补充，代码解释等

注意点：

基本素质：基础知识、高质量代码、清晰的思路、优化效率的能力、综合能力

面试问题摘记：

C++中四个与类型转换相关的关键字

背景：在C/C++语言中用 (type) value（在C++还可以采用type(value)）来进行显式类型转换（explicit type conversion），常常又被称为强制转换（cast投射/铸模）。这种转换的正确性完全掌握在程序员手中，传统上强制转换往往被过度使用，成为C++程序犯错的一个主要根源。
为了减少强制转换的副作用，并且在查错时使程序员能够快速定位（总是最值得怀疑的）强制转换，在标准C++中新增加了4个关键字*_cast，用来提倡一种全新的C++显式转换语法：
*_cast (expression)

问：C++中，有哪四个与类型转换相关的关键字？

答：static_cast, const_cast, dynamic_cast, reinterpret_cast

  • static_cast, 运算符完成相关类型之间类型的转换

    • 静态转换，在编译处理期间

    • C++内置基本数据类型之间的转换。但是没有运行时类型的检测来保证转换的安全性。

    • 用法：

      • 子类指针转换为基类是安全的，基类转换为字类就是不安全的。
      • 基本数据类型之间的转换，int->char。
      • 空指针转换为目标类型的空指针。
      • 任何类型的表达式转换成void类型。
    1
    2
    l = static_cast<long>(i);//i是整型，l是长整型。
    f = static_cast<float>(i);//在传统方法下，可以进行隐式转换。
    1
    2
    3
    4
    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_cast

    • 去常转换，编译时执行

    • const_cast操作不能在不同的种类间转换。相反，它仅仅把它作用的表达式转换成常量。它可以使一个本来不是const类型的数据转换成const类型的，或者把const属性去掉。

    • 用法：

      • 常量指针被转化成非常量的指针，并且仍然指向原来的对象
      • 常量引用被转换成非常量的引用，并且仍然指向原来的对象
    1
    2
    3
    4
    5
    6
    7
    8
    const int i = 0;
    int *pi;
    pi = &i; // 错误
    pi = (int *)&i; // 被反对
    pi = const_cast<int *>(&i); // 完美，将常量指针转换成非常量指针
    long *pl = const_cast<long *>(&i); // 错误，要求是同数据类型
    volatile int k = 0;
    int *pk = const_cast<int *>(&k); // 正确

  • dynamic_cast => dynamic_cast (expression)

    • 基类必须有虚函数，即为多态时，可以转换

    • 将一个基类对象指针（或引用）cast到继承类指针，dynamic_cast会根据基类指针是否真正指向继承类指针来做相应处理.

    • 该运算符把expression转换成type-id类型的对象。Type-id 必须是类的指针、类的引用或者void*；

    如果 type-id 是类指针类型，那么expression也必须是一个指针，如果 type-id 是一个引用，那么 expression 也必须是一个引用。

    • dynamic_cast运算符可以在执行期决定真正的类型。如果 downcast 是安全的（也就说，如果基类指针或者引用确实指向一个派生类对象）这个运算符会传回适当转型过的指针。如果 downcast 不安全，这个运算符会传回空指针（也就是说，基类指针或者引用没有指向一个派生类对象）。

    dynamic_cast主要用于类层次间的上行转换和下行转换，还可以用于类之间的交叉转换。

    dynamic_cast（动态转换）：一种安全的向下类型转换（downcast）操作，用于在一个类继承层次上向下移动。

    1
    2
    3
    4
    5
    6
    7
    8
    class Pet {……};
    class Dog : public Pet {……};
    class Cat : public Pet {……};
    ……
    Pet *pPet = new Cat; // 向上的类型转换
    Dog *pDog = dynamic_cast<Dog *>(pPet); // 类型错误，返回0(NULL)
    Cat *pCat = dynamic_cast<Cat *>(pPet); // 类型正确，返回指针
    Cat *pCat = static_cast<Cat *>(pPet); // 正确，减少运行时的开销

  • reinterpret_cast (expression)

    • 使用reinterpret_cast通常是一种不明智且不方便的编程方式。但是在必须使用时，它也是非常有用的。

    • type-id 必须是一个指针、引用、算术类型、函数指针或者成员指针。它可以把一个指针转换成一个整数，也可以把一个整数转换成一个指针（先把一个指针转换成一个整数，再把该整数转换成原类型的指针，还可以得到原先的指针值）。

1
2
3
4
5
6
7
8
9
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);

参考资料：
C++中，有哪四个与类型转换相关的关键字
C++中，有哪4个与类型转换相关的关键字？

空类型的大小

1问：一个空类型里面没有定义任何成员变量、成员函数，对该类型的求sizeof，得到的结果是什么？

答：为1，但是也根据编译器改变，vs当中是1。

解释：按理应该求得sizeof为0，但是在声明该类型的时候，他在内存中必须有一定的空间，否则无法使用这些实例。

2问：如果添加构造函数和析构函数呢？

答：还是1，调用这两个函数只需要两个函数的地址，而他们只和类型相关，和实例无关。

3问：如果上面的析构函数是虚函数呢？

答：如果是虚析构函数，那么会为该类型生成虚函数表，并在该类型当中添加一个指向虚函数表的指针。32位系统中一个指针占4字节，sizeof=4。64位系统中sizeof的得到的值位8。

拷贝构造函数

拷贝构造函数的传入参数必须是A(const&A a), 参数必须当成常量引用

赋值运算符函数

题目：为类型CMyString的声明添加赋值运算符函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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;
}

单例 C++ 几种实现

  • 实现一：线程不安全

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Singleton{
    public: 
        static Singleton* getInstance(){
            if(m_instance == nullptr){
                m_instance = new Singleton();
            }
            return m_instance;
        }
    private:
        Singleton();
        Singleton(const Singleton& other);
        static Singleton* m_instance;
    };
    Singleton* Singleton::m_instance=nullptr;
    /*
    	正常情况下，如果线程A调用getInstance()时，将m_instance 初始化了，那么线程B再调用getInstance()时，就不会再执行new了，直接返回之前构造好的对象。然而存在这种情况，线程A执行m_instance = new Singleton()还没完成，这个时候m_instance仍然为nullptr，线程B也正在执行m_instance = new Singleton()，这是就会产生两个对象，线程A和B可能使用的是同一个对象，也可能是两个对象，这样就可能导致程序错误，同时，还会发生内存泄漏。
    */

  • 实现二：线程安全，锁代价高

    1
    2
    3
    4
    5
    6
    7
    Singleton* Singleton:getInstance(){
       	Lock(); //每次都会lock锁代价高
        if(m_instance == nullptr);
        	m_instance = new Singleton;
        Unlock();
       	return m_instance;
    }

  • 实现三：线程安全，低锁代价

    1
    2
    3
    4
    5
    6
    7
    8
    9
    Singleton* Singleton:getInstance(){
        if(m_instance == nullptr){
            Lock();
            if(m_instance == nullptr);
                m_instance = new Singleton;
            Unlock();
        }
       	return m_instance;
    }

  • 实现四：解决方案三的bug，java/C#提出volatile，也就是把m_instanced用volatile声明，避免reorder。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    /*
    这个方法没有进行深入研究
    */
    //C++ 11版本之后的跨平台实现 
    // atomic c++11中提供的原子操作
    std::atomic<Singleton*> Singleton::m_instance;
    std::mutex Singleton::m_mutex;

    /*
    * std::atomic_thread_fence(std::memory_order_acquire); 
    * std::atomic_thread_fence(std::memory_order_release);
    * 这两句话可以保证他们之间的语句不会发生乱序执行。
    */
    Singleton* Singleton::getInstance() {
        Singleton* tmp = m_instance.load(std::memory_order_relaxed);
        std::atomic_thread_fence(std::memory_order_acquire);//获取内存fence
        if (tmp == nullptr) {
            std::lock_guard<std::mutex> lock(m_mutex);
            tmp = m_instance.load(std::memory_order_relaxed);
            if (tmp == nullptr) {
                tmp = new Singleton;
                std::atomic_thread_fence(std::memory_order_release);//释放内存fence
                m_instance.store(tmp, std::memory_order_relaxed);
            }
        }
        return tmp;
    }

  • 实现五：pthread_once函数

    • 在linux中，pthread_once()函数可以保证某个函数只执行一次。

    • 声明: int pthread_once(pthread_once_t once_control, void (init_routine) (void))；

      功能: 本函数使用初值为PTHREAD_ONCE_INIT的once_control变量保证init_routine()函数在本进程执行序列中仅执行一次。 

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      class Singleton{
      public:
          static Singleton* getInstance(){
              // init函数只会执行一次
              pthread_once(&ponce_, &Singleton::init);
              return m_instance;
          }
      private:
          Singleton(); //私有构造函数，不允许使用者自己生成对象
          Singleton(const Singleton& other);
          //要写成静态方法的原因：类成员函数隐含传递this指针（第一个参数）
          static void init() {
              m_instance = new Singleton();
            }
          static pthread_once_t ponce_;
          static Singleton* m_instance; //静态成员变量 
      };
      pthread_once_t Singleton::ponce_ = PTHREAD_ONCE_INIT;
      Singleton* Singleton::m_instance=nullptr; //静态成员需要先初始化

  • 实现六：C++11版最简洁跨平台方案

    • 使用局部静态变量

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      class Singleton{
      public：
          // 注意返回的是引用
          static Singleton& getInstance(){
          	static Singleton m_instance; //局部静态变量
          	return m_instance;
      	}
      private:
          Singleton();
          Singleton(const Singleton& other);
      }；

      //模板类
      template<typename T>
      class Singleton
      {
      public:
          static T& getInstance() {
              static T value_; //静态局部变量
              return value_;
          }

      private:
          Singleton();
          ~Singleton();
          Singleton(const Singleton&); //拷贝构造函数
          Singleton& operator=(const Singleton&); // =运算符重载
      };

      sizeof获取数组大小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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);
    //判断输出的结果？
}

面试题3：数组中重复的数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
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



    }
};

面试题4：二维数组中查找

解决该问题的关键是，从右上角开始找，因为右上角的数据!=目标数据的时候，大于target和小于target可以分成不同情况进行排除某行某列，从而不断进一步找到目标数，但是从左上角就无法分成两种情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#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;
    }
};

面试题5：替换空格

题目：请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

知识：从前往后替换的话，时间效率低（n2），需要重复遍历后面的字符。所以可以考虑从后面向前替换新增字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <string.h>
#include <stdio.h>


class Solution {
public:
	void replaceSpace(char *str,int length) {

        if(str == nullptr || length < 0) // 错误输入处理
            return;
            
        size_t count_space = 0;
        for (size_t i = 0; i < length; i++)
        {
            /* code */
            if(*(str+i) == ' ')
                count_space++;
        }
        // info :printf("%d\n",count_space);
        char* retstr = new char[length + count_space * 2];
        retstr[length + count_space * 2] = '\0';

        /**
         *  执行从后替换逻辑 
         * 
         */
        // debug :length = 14
        unsigned ptr = length + count_space * 2 - 1;
        for (size_t i = length -1 ; i <= ptr; i--)
        {
            // debug :printf("%s \n",str+i);
            /* code */
            if( *(str + i) == ' ' ){
                *(retstr + ptr) = '0'; ptr--;
                *(retstr + ptr) = '2'; ptr--;
                *(retstr + ptr) = '%'; ptr--;
            }
            else
            {
                /* code */
                
                *(retstr + ptr) = *(str +i);
                ptr--;
            }
        }
        printf(" retstr is :%s \n",retstr);
	}
};

面试题6、7、8、9、10

快速排序

O(n)的排序算法（有条件）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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;
        }
    }
}

面试题11：旋转数组的最小数字

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

你可以假设数组中不存在重复元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#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];
    }
};

面试题12：回溯法-矩阵中的路径

Leetcode中对应：单词搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
/*
 * @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

面试题13：回溯法-机器人的运动范围

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
//#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;
    }
};

面试题14：贪婪-剪绳子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#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));

    }
};

面试题15: 一个数字中某一位为1的个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/*
 * @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

面试题16：一个数的整数次方

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
/*
 * @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

面试题17：打印1-n位数的最大整数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#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;
    }
};

面试题18：删除链表的节点

补充学习

链表

hash表实现

二叉树

红黑树

B+ tree

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://hexoblog.maplestory.work/2020/03/25/2020-03-25-%E5%89%91%E6%8C%87offer/

本页文档最后更新于：Dec 5, 2021

Interviews

Coding

评论