剑指offer学习笔记：5.1 面试官谈效率 && 5.2 时间

面试题29：数组中出现次数超过一半的数字（解法巨多的一道题，leetcode官方就给了5个解法）

数组中有一个数字出现次数超过数组长度的一半，请找出这个数字
leetcode链接 https://leetcode-cn.com/problems/majority-element/

class Solution {
public:
   int majorityElement(vector<int>& nums) {
      //  这里写的是投票法，思路见下面解法二
       int candidate = nums[0];
       int n = 1;
       for(int i = 1; i < nums.size(); i++)
       {
           if (nums[i] == candidate)
           {
               n++;
           }
           else
           {
               n--;
               if (n == 0)
               {
                   candidate = nums[i];
                   n = 1;
               }
           }
       }
       int num = 0;
       for(int i = 0; i < nums.size(); i++)
       {
           if (nums[i] == candidate)
           {
               num++;
           }
       }
       if (num > nums.size() / 2)
       {
           return candidate;
       }
       else{
           return 0;
       }
   }
};

解题思路：只写了剑指offer书上的两种方法，排序法和投票法。但是投票法我感觉只在众数一定存在的情况下适用，没有兼容异常的能力。
最简单直观的方法：简历hash表存数字和数字出现次数，当某个数字出现次数大于n/2,则return。
解法1：因为数组中超过一半的数字一定是数组中位数，同找数组中第k大元素算法。算法启蒙是快速排序。随机选择一个数，将比他小的数都调整到其左面，比他大的数都调整到其右面。当当前选中数据下标为n/2, 为中位数，当下标小于n/2,在他的右数组中查找，当大于，在左数组中查找。知道找到n/2位置元素。
注意考虑输入是null和没有超过一半数字的情况。
leetcode上用这种算法会超出时间限制，改为在牛客链接上写https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163?tpId=13&&tqId=11181&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

class Solution {
public:
        void swap(int &a, int &b)
    {
        int tmp = a;
        a = b;
        b = tmp;
    }
    int partation(vector<int>& num, int begin, int end)
    {
        if (begin >= end)
        {
            return begin;
        }
        int target = num[begin];
        while(begin < end)
        {
            while(begin < end && num[end] >= target)
            {
                end--;
            }
            swap(num[begin], num[end]);
            while(begin < end && num[begin] <= target)
            {
                begin++;
            }
            swap(num[begin], num[end]);
        }
        return begin;
    }
    int quickSort(vector<int>& nums, int begin, int end)
    {
        if (begin >= end)
        {
            return nums[begin];
        }
        int pivot = partation(nums, begin, end);
        // cout << pivot << endl;
        if (pivot == -1)
        {
            return -1;
        }
        else if (pivot == nums.size() / 2)
        {
            return nums[pivot];
        }
        else if (pivot > nums.size() / 2)
        {
            return quickSort(nums, begin, pivot - 1);
        }
        return quickSort(nums, pivot + 1, end);
    }
    int MoreThanHalfNum_Solution(vector<int> numbers) {
                if (numbers.size() == 0)
        {
            return -1;
        }
        // 先写个快排，然后找中位数
        int mid = quickSort(numbers, 0, numbers.size() - 1);
        int num = 0;
        for(int i = 0; i < numbers.size(); i++)
        {
            if (numbers[i] == mid)
            {
                num++;
            }
        }
        if (num > numbers.size() / 2)
        {
            return mid;
        }
        else{ return 0;}
    }
};

解法2：考虑数组中出现次数超过一半的数，其出现次数一定大于其余所有数字出现次数之后。因此，进行操作，用result记录当前数字，num=1。当当前数字与result相同num+1，当当前数字与result不同，result-1。num减为0后result更换为当前数字，并且num重新置1。最后result就是要得到的数字。
模拟23324522225

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate = nums[0];
        int n = 1;
        for(int i = 1; i < nums.size(); i++)
        {
            if (nums[i] == candidate)
            {
                n++;
            }
            else
            {
                n--;
                if (n == 0)
                {
                    candidate = nums[i];
                    n = 1;
                }
            }
        }
        return candidate;
    }
};

面试题30：最小的k个数

输入n个整数，找到其中最小的k个数
leetcode链接 https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/

class Solution {
public:
   int partition(vector<int>& arr, int begin, int end)
   {
       int target = arr[begin];
       end--;
       while(begin < end)
       {
           // cout << "begin: " << begin << " end: " << end << endl;
           while(begin < end && arr[end] >= target)
           {
               end--;
           }
           int tmp = arr[end];
           arr[end] = arr[begin];
           arr[begin] = tmp;
           while(begin < end && arr[begin] <= target)
           {
               begin++;
           }
           tmp = arr[end];
           arr[end] = arr[begin];
           arr[begin] = tmp;
       }
       return begin;
   }
   void quickSort(vector<int>& arr, int begin, int end, int k)
   {
       if (begin >= end)
       {
           return;
       }
       int pivot = partition(arr, begin, end);
       if (pivot == k)
       {
           return;
       }
       if (pivot > k)
       {
           quickSort(arr, begin, pivot, k);
       }
       else
       {
           quickSort(arr, pivot + 1, end, k);
       }
       return;
   }
   vector<int> getLeastNumbers(vector<int>& arr, int k) {
       // 快排思想，对应下文中第二种思路
       if (arr.size() < k)
       {
           return arr;
       }
       quickSort(arr, 0, arr.size(), k);
       vector<int> result;
       for(int i = 0; i < k; i++)
       {
           result.push_back(arr[i]);
       }
       return result;
   }
};

解题思路：1）最直观的思路，排序，取前k个，注意数组长度。2）与上题中解法一思想类似，用快排中partiton函数找到位于第k位的元素，在数组左面的部分就是最先的k个数。但是利用这种思想的问题就是需要改变原始数组。3）维护一个大小为k的数据结构，每次新增数据和当前最大值比，如果大于最大值，则不变。小于最大值，则替换。因为需要获得每次的最大值，第一想到的是大顶堆。但是因为大顶堆不好写，可以退而求其次选择查找复杂度为logk的红黑树。stl中set和multiset都是红黑树实现的，因此可以直接拿来用。

性能上来看第二种算法最好，但是因为要读进来全部数据并会对原始数组进行更改，某些场景尤其是数据量级很大时不适用。第三种算法只需维护k的数据结构就好，更适合海量数据取前k。
解法一：快排，取k

class Solution {
public:
    int partition(vector<int>& arr, int begin, int end)
    {
        int target = arr[begin];
        end--;
        while(begin < end)
        {
            // cout << "begin: " << begin << " end: " << end << endl;
            while(begin < end && arr[end] >= target)
            {
                end--;
            }
            int tmp = arr[end];
            arr[end] = arr[begin];
            arr[begin] = tmp;
            while(begin < end && arr[begin] <= target)
            {
                begin++;
            }
            tmp = arr[end];
            arr[end] = arr[begin];
            arr[begin] = tmp;
        }
        return begin;
    }
    void quickSort(vector<int>& arr, int begin, int end)
    {
        if (begin >= end)
        {
            return;
        }
        int pivot = partition(arr, begin, end);
        quickSort(arr, begin, pivot);
        quickSort(arr, pivot + 1, end);
        return;
    }
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        // 快排，之后取前k个数
        if (arr.size() < k)
        {
            return arr;
        }
        quickSort(arr, 0, arr.size());
        vector<int> result;
        for(int i = 0; i < k; i++)
        {
            result.push_back(arr[i]);
        }
        return result;
    }
};

解法二：用快排的partition

class Solution {
public:
    int partition(vector<int>& arr, int begin, int end)
    {
        int target = arr[begin];
        end--;
        while(begin < end)
        {
            // cout << "begin: " << begin << " end: " << end << endl;
            while(begin < end && arr[end] >= target)
            {
                end--;
            }
            int tmp = arr[end];
            arr[end] = arr[begin];
            arr[begin] = tmp;
            while(begin < end && arr[begin] <= target)
            {
                begin++;
            }
            tmp = arr[end];
            arr[end] = arr[begin];
            arr[begin] = tmp;
        }
        return begin;
    }
    void quickSort(vector<int>& arr, int begin, int end, int k)
    {
        if (begin >= end)
        {
            return;
        }
        int pivot = partition(arr, begin, end);
        if (pivot == k)
        {
            return;
        }
        if (pivot > k)
        {
            quickSort(arr, begin, pivot, k);
        }
        else
        {
            quickSort(arr, pivot + 1, end, k);
        }
        return;
    }
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        // 快排，之后取前k个数
        if (arr.size() < k)
        {
            return arr;
        }
        quickSort(arr, 0, arr.size(), k);
        vector<int> result;
        for(int i = 0; i < k; i++)
        {
            result.push_back(arr[i]);
        }
        return result;
    }
};

解法三：利用set的红黑树结构，实现每次获取最大值的操作。注意用multiset不是set，不然会被去重。这种方法更适合大数据，时间上比前两种要耗时。

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        if (arr.size() < k)
        {
            return arr;
        }
        // 红黑树，我来了
        // c++中set的底层实现为红黑树
        multiset<int, greater<int>> tmp;
        int i = 0;
        while(i < k)
        {
            tmp.insert(arr[i]);
            i++;
        }
        while(i < arr.size())
        {
            if (arr[i] < *tmp.begin())
            {
                tmp.erase(tmp.begin());
                tmp.insert(arr[i]);
            }
            i++;
        }
        vector<int> result;
        set<int>::iterator it;
        for(it = tmp.begin(); it != tmp.end(); it++)
        {
            result.push_back(*it);
        }
        return result;
    }
};

【c++拾遗】set与红黑树
参考链接：https://www.cnblogs.com/caiyishuai/p/8646345.html
C++ STL中标准关联容器set, multiset, map, multimap内部采用的就是一种非常高效的平衡检索二叉树：红黑树，也成为RB树(Red-Black Tree)。
set关联式容器。set作为一个容器也是用来存储同一数据类型的数据类型，并且能从一个数据集合中取出数据，在set中每个元素的值都唯一，而且系统能根据元素的值自动进行排序。应该注意的是set中数元素的值不能直接被改变。
set是自动排序的，默认是从小到大排序，即取第一个元素就是最小值。使用multiset<int, greater<int> > 定义就是由大到小排序。当需要使用greater<int>时，在头文件里需要添加#include<functional>

面试题31：连续子数组的最大和

**输入一个整型数组，数组中有正数也有负数。数组中一个或连续多个正数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为o(n)。

class Solution {
public:
   int maxSubArray(vector<int>& nums) {
       if (nums.size() == 0)
       {
           return INT_MIN;
       }
       if (nums.size() == 1)
       {
           return nums[0];
       }
       int sum = nums[0], max = nums[0];
       for(int i = 1; i < nums.size(); i++)
       {
           if (sum > max)
           {
               max = sum;
           }
           // cout << max << endl;
           if (sum < 0)
           {
               sum = nums[i];
           }
           else
           {
               sum = sum + nums[i];
           }
       }
       if (sum > max)
       {
           max = sum;
       }
       return max;
   }
};

解题思路：
解法一：找规律考虑数组{1, -2, 3, 10, -4, 7, 2, -5}。在遇到前面数组的和为负数情况下，舍弃前面所有数据，开始重新累计。遇到负数情况下，记录当前子数组和，和最大值进行比较，若大于最大值，替换，小于，舍弃，继续执行。写代码可以简化，因为当前数据是负数，相加肯定会让sum变小，所以每步判断当前sum和max即可，不需要判断当前数据是否为负数。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if (nums.size() == 0)
        {
            return INT_MIN;
        }
        if (nums.size() == 1)
        {
            return nums[0];
        }
        int sum = nums[0], max = nums[0];
        for(int i = 1; i < nums.size(); i++)
        {
            if (sum > max)
            {
                max = sum;
            }
            // cout << max << endl;
            if (sum < 0)
            {
                sum = nums[i];
            }
            else
            {
                sum = sum + nums[i];
            }
        }
        if (sum > max)
        {
            max = sum;
        }
        return max;
    }
};

解法二：应用动态规划
用函数f(i)表示到以第i个元素结尾的最大子数组的数字和。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if (nums.size() == 0)
        {
            return INT_MIN;
        }
        if (nums.size() == 1)
        {
            return nums[0];
        }
        int n = nums.size();
        int sum[n];
        sum[0] = nums[0];
        int max = nums[0];
        // 动态规划，用数组存结果
        for(int i = 1; i < n; i++)
        {
            if (sum[i-1] < 0)
            {
                sum[i] = nums[i];
            }
            else
            {
                sum[i] = sum[i-1] + nums[i];
            }
            if (sum[i] > max)
            {
                max = sum[i];
            }
        }
        return max;
    }
};

面试题32：从1到n整数中1出现的次数

输入一个整数n，求1到n这n个整数中十进制表示1出现的次数。例如输入12，从1到12包含1的数字有1，10，11，12，1一共出现了5次。
leetcode链接 https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/

class Solution {
public:
   int countNumber1(const char* strN)
   {
       if (!strN || *strN > '9' || *strN < '0' || *strN == '\0' || atoi(strN) < 1)
       {
           return 0;
       }
       int first = *strN - '0';
       unsigned int len = strlen(strN);
       if (first == 0 && len == 1)
       {
           return 0;
       }
       if (first > 0 && len == 1)
       {
           return 1;
       }
       int high;    // 最高位是1的个数
       if (first > 1)
       {
           high = pow(10, len - 1);
       }
       else{
           high = atoi(strN + 1) + 1;
       }
       // cout << first << " " << len << endl;
       int mid = first * (len - 1) * pow(10, len - 2);// 其余位是1的个数是个排列组合
       int i = 1;
       while(*(strN + i) == '0')  //  感觉书上写的那个缺这部分去0，譬如101这种，直接+1传过去的是01
       {
           i++;
       }
       int low = countNumber1(strN + i);  // 递归剩余部分
       // cout << high << " " << mid << " " << low << endl;
       return high + mid + low;
   }
   int countDigitOne(int n) {
       if (n == 0)
       {
           return 0;
       }
       if (n == 1)
       {
           return 1;
       }
       // 涉及最高位删除，转换成字符串操作比较方便
       char strN[50];
       sprintf(strN, "%d", n);
       return countNumber1(strN);
   }
};

解题思路：从数据规律着手。考虑11-110中1出现的个数，百位出现次数（1）+ 10位出现次数10-19（10）+ 个位出现次数11，21，31...101（10）= 21个。考虑15-114中1出现的个数，百位出现次数100-114（15）+ 10位出现次数15-19，110-114（10）+ 个位出现次数21-91，101，111（10）= 35个。115-214同上。发现除了最高位不同，百位和十位都是相同的，其个数为排列组合，固定一个值是1，其余另一位可以取0-9共10个数，所以是
取一个比较大的数进行分析，譬如取21345，将数据分为两段，1-1345，1346-21345。由前面判断，可得到1346-21345中1的个数=最高位中1的个数10000-19999（10000）+ 其余位中1的个数1346-11345，11346-21346（2410^3 = 8000) = 18000, 1-1345中1的个数，同样需要一步一步拆分，可以用递归来实现。

面试题33：把数组排成最小的数

输入一个正整数数组，把数组中的所有数字拼接排列成一个数，打印能排列出的数字中最小的一个。例如输入数组{3, 32, 321}, 则打印出这3个数字能排列成的最小数字是321323。
leetcode链接 https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/

class Solution(object):
   def compare(self, a, b):
       # print "a: " + a + " b: " + b + " ",
       if (a+b) < (b+a):
           # print "-1"
           return -1
       elif (a+b) > (b+a):
           # print "1"
           return 1
       # print "0"
       return 0
   def minNumber(self, nums):
       """
       :type nums: List[int]
       :rtype: str
       """
       # 先将int转string
       for i in range(0, len(nums)):
           nums[i] = str(nums[i])
       nums = sorted(nums, cmp = self.compare)
       result = ""
       for i in range(0, len(nums)):
           result += nums[i]
       return result

解题思路：将数字转换成字符串，按从小到大排序，之后组合即可。注意排序规则是字符串x和字符串y，若x+y>y+x，则x>y。用sort自定义函数的功能进行排序。这种转字符串的python比较简单，用python写了。

第二版面试题44：数字序列中某一位数字

数字以012345678910111213排列。在这个序列中，第5位是5（从0开始计数），第13位是1。实现函数，求第n位的数字
leetcode链接 https://leetcode-cn.com/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof/

class Solution {
public:
   int countDigit(int n)
   {
       // 计算几位数都有几个数字
       if (n == 1)
       {
           return 10;
       }
       return pow(10, n) - pow(10, n - 1);
   }
   int findNthDigit(int n) {
       // 先确定范围
       int digits = 1;
       while(true)
       {
           int tmp = countDigit(digits);
           if (tmp >= int(INT_MAX / digits))   // 这里一定要注意下判断越界问题
           {
               break;
           }
           int num = tmp * digits;
           if (n < num)
           {
               break;
           }
           n = n - num;
           digits++;
       }
       // cout << n << " " << digits << endl;
       if (digits == 1)
       {
           return n;
       }
       int wei = n / digits;
       int mid = n % digits;
       // cout << "wei: " << wei << " mid: " << mid << endl;
       int result = pow(10, digits - 1 ) + wei;
       // cout << "result: " << result << endl;
       return (result / int(pow(10, digits - 1 - mid))) % 10;
   }
};

解题思路：由于一位数，两位数，三位数占用长度都是固定的，可以先求得n位数所在范围。以1001位为例，由于0-9占用前10位，只有一个数字，1001显然在后面，因此找10开始第991个数字。由于10-99占902=180位，不够991，因此找100开始第811位。接下来100-999=9003=2700位，则1001在这里面。由于811=270*3 + 1。因此1001是从100开始第270个数字，即370中间的那位，即为7。