面试题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
| 步骤 | 操作 | result | num |
|---|---|---|---|
| 1 | 2 | 2 | 1 |
| 2 | 3 != 2 | 3 | 1 |
| 3 | 3 == 3 | 3 | 2 |
| 4 | 2 != 3 | 3 | 1 |
| 5 | 4 != 2 | 4 | 1 |
| 6 | 5 != 4 | 5 | 1 |
| 7 | 2 != 5 | 2 | 1 |
| 8 | 2 == 2 | 2 | 2 |
| 9 | 2 == 2 | 2 | 3 |
| 10 | 2 == 2 | 2 | 4 |
| 11 | 5 != 2 | 2 | 3 |
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即可，不需要判断当前数据是否为负数。
| 步骤 | 操作 | 累加的子数组和 | 最大的子数组和 |
|---|---|---|---|
| 1 | 加1 | 1 | 1 |
| 2 | 加-2 | -1(负数，舍弃） | 1 |
| 3 | 加3 | 3 | 3 |
| 4 | 加10 | 13 | 13 |
| 5 | 加-4 | 9 | 13（负数，不更新最大值） |
| 6 | 加7 | 16 | 16 |
| 7 | 加2 | 18 | 18 |
| 8 | 加-5 | 13 | 18（负数，不更新最大值） |
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。
