《剑指Offer》笔记

发表于 | 分类于 | |

剑指Offer

  1. Chapter 1：面试的流程

    1. 一定要在代码开头处考虑边界条件，特殊输入（空指针，空字符串），错误处理等意外情况。

  2. Chapter 2：面试需要的基础知识

    1. sizeof(空类型) ==1 而非0，因为空类型也需要占用一定的空间，否则无法使用该实例。

    2. 如果上述空类型加了构造函数和虚构函数，再求sizeof还是1。因为构造函数和虚构函数只需要知道函数地址就可以了。

    3. 如果上述构造函数和虚构函数是虚函数，则编译器会为该类型生成虚函数表，并在该类型的每一个实例中添加一个指向虚函数表的指针。在32位机器，一个指针占4个字节，即sizeof得到4，在64位上则得到8。

    4. c++不允许复制构造函数传值参数：A(A other) => A(const A& other)

    5. vector每次扩容时，新的容量都是前一次的两倍，使用动态数组要尽量减少改变数组容量大小的次数。

    6. 1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      int GetSize(int data[])
      {
        return sizeof(data);
      }

      int main()
      {
      	int data1[]={1,2,3,4,5};
        	int size1=sizeof(data1);//5*4=20
        	int* data2 = data1;
        	int size2 = sizeof(data2);//4 data2虽然指向数组第一个，但本质仍为指针
        	int size3 = GetSize(data1);//4 退化为指针
      }
    7. 1
      2
      3
      4
      5
      6
      7
      8
      9
      int main()
      {
        	char str1 [] = "Hello world!";
        	char str2 [] = "Hello world!";
        	// str1 != str2 不同的指针
        	char* str3 = "Hello world!";
        	char* str4 = "Hello world!";
        	//str3==str4 都指向"Hello world!"这个常量地址
      }

    8. 使用辅助空间实现O(n)排序 => timesOfAges[age] ++;

    ​

  • 整数中1出现的次数（从1到n整数中1出现的次数）

    ​ 统计n这个数每一位上数字恰好为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
    class Solution {
    public:
        int NumberOf1Between1AndN_Solution(int n)
        {
        	int factor = 1;
            int left, right;//left的最后一位是1的可能数
            int ans = 0, count;
            int leftRight;//left的最后一位
            left = n / factor;
            right = n % factor;
            while (left > 0)
            {
                leftRight = left % 10;
                if (leftRight > 1)
                {
                    count = (left / 10 + 1) * factor;
                } else if (leftRight == 1)
                {
                    count = left / 10 * factor + (right + 1);
                } else
                {
                    count = left / 10 * factor;
                }
                ans += count;
              
                factor *= 10;
                left = n / factor;
                right = n % factor;
            }
            return ans;
        }
    };

    ​

  • 把数组排成最小的数

    自定义排序的compare，到底是s1放前面比较小还是s2放前面比较小。注意比较函数得用static。因为需要给全局得sort调用。

    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
    //
    // Created by cpz on 2018/1/24.
    //
    #include "head.h"

    class Solution {
    public:
        string PrintMinNumber(vector<int> numbers)
        {
            vector<string> strs;
            string ans = "";
            for (auto i:numbers)
            {
                strs.push_back(to_string(i));
            }
            sort(strs.begin(), strs.end(), compare);
            for (auto i:strs)
                ans += i;
            return ans;
        }

        static bool compare(string str1, string str2)
        {
            string s1 = str1 + str2, s2 = str2 + str1;
            if (s1 < s2)
                return true;
            else
                return false;
        }
    };

    ​

  • 丑数

    把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

    vector新加进来的数一定是前面的某个数*2，或者*3，或者*5得来的！

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    class Solution {
    public:
        int GetUglyNumber_Solution(int index)
        {
            if (index < 1)
                return 0;
            vector<int> v;
            v.push_back(1);
            int i = 0, j = 0, k = 0;
            while (v.size() < index)
            {
                v.push_back(Min(v[i] * 2, v[j] * 3, v[k] * 5));
                if (v.back() == v[i] * 2) i++;
                if (v.back() == v[j] * 3) j++;
                if (v.back() == v[k] * 5) k++;
            }
            return v.back();
        }

        int Min(int i, int j, int k)
        {
            return min(i, min(j, k));
        }
    };

    ​

  • 数组中的逆序对

    在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

    ​ 比较难的一道题了，想了好久！O（N^2）肯定过不了，没想到是归并排序的变种。把原数组分为左右两部分，那么总的逆序对会等于，左边数组的逆序数对+右边数组的逆序数对+一个数在左一个数在右的逆序数对，即inv = inv(left) + inv(right) + inv(merge)。因为在归并的时候，左右数组已经有序了，所以一个数在左边（记为a[i]），一个数在右边（记为a[j]）的可能数为：(mid - i + 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
    38
    39
    40
    41
    //
    // Created by cpz on 2018/1/24.
    //
    #include "head.h"

    class Solution {
    public:
        void mergeSort(vector<int> &data, int start, int end)
        {
            int mid = (start + end) / 2;
            if (end > start)
            {
               mergeSort(data, start, mid);
               mergeSort(data, mid + 1, end);
               merge(data, start, mid, end);
            }
        }
        void merge(vector<int> &data, int start, int mid, int end)
        {
            vector<int> temp;
            int i = start, j = mid + 1;
            int count = end - start + 1;
            while (count)
            {
                if (i > mid)
                    temp.push_back(data[j++]);
                else if (j > end)
                    temp.push_back(data[i++]);
                else if (data[i] < data[j])
                    temp.push_back(data[i++]);
                else//data[i] > data[j]
                    temp.push_back(data[j++]);
               
                count--;
            }
            for (int k = start; k <= end; ++k)
            {
                data[k] = temp[k - start];
            }
        }
    };

    ​

    ​

    ​ 再看可以统计逆序数对的归并排序，改变的代码行用diff注释。

    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
    //
    // Created by cpz on 2018/1/24.
    //
    #include "head.h"

    class Solution {
    public:
        int InversePairs(vector<int> data)
        {
            return mergeSort(data, 0, data.size() - 1);
        }

        int mergeSort(vector<int> &data, int start, int end)
        {
            int inv = 0;//diff
            int mid = (start + end) / 2;
            if (end > start)
            {
                inv += mergeSort(data, start, mid);//diff
                inv += mergeSort(data, mid + 1, end);//diff
                inv += merge(data, start, mid, end);//diff
            }
            return inv;//diff
        }

        int merge(vector<int> &data, int start, int mid, int end)
        {
            int inv = 0;//diff
            vector<int> temp;
            int i = start, j = mid + 1;
            int count = end - start + 1;
            while (count)
            {
                if (i > mid)
                    temp.push_back(data[j++]);
                else if (j > end)
                    temp.push_back(data[i++]);
                else if (data[i] < data[j])
                    temp.push_back(data[i++]);
                else//data[i] > data[j]
                {
                    inv += (mid - i + 1) ;//diff
                    temp.push_back(data[j++]);
                }
                count--;
            }
            for (int k = start; k <= end; ++k)
            {
                data[k] = temp[k - start];
            }
            return inv;//diff
        }
    };

    ​