算法（七）剑指offer数组系列
翻转字符串里的单词
题目
给定一个字符串，逐个翻转字符串中的每个单词。
说明：
无空格字符构成一个 单词 。
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
题解
先所有字符翻转，然后在单词内翻转(leetcode上要考虑各种情况，其实没必要)，示例代码如下：
class Solution {
public:
string reverseWords(string s) {
if (s.empty()) {
return s;
}
reverse(s.begin(), s.end());
int low = 0;
int high = 0;
while (low <= s.size() - 1) {
while (high < s.size() && s[high] != ' ') {
++high;
}
reverse(s.begin() + low, s.begin() + high);
low = high + 1;
high = low;
}
std::string result;
result.assign(s.begin() + low_thre, s.begin() + up_thre + 1);
return result;
}
};
找出数组中重复的数字(剑指offer_3)
题目
在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了， 也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2, 3, 1, 0, 2, 5, 3}，那么对应的输出是重复的数字2或者3。
题解
如果第i个位置上的元素不是i, 看nums[i]和nums[nums[i]]是否相同，如果相同的话，则证明有重复， 直接返回，否则交换nums[i]和nums[nums[i]],如果交换之后nums[i]和i还是不相同，则 接着重复上述操作，直到把所有元素都遍历完成为止。
示例代码如下：
class Solution {
public:
int duplication_detection(std::vector<int> nums) {
if (nums.empty()) {
return -1;
}
int length = nums.size();
for (int i = 0; i < length; ++i) {
if (nums[i] < 0 || nums[i] >= length) {
return -1;
}
}
for (int i = 0; i < length; ++i) {
while (nums[i] != i) { // 只要对应位置元素不是对应位置，就继续找
if (nums[i] == nums[nums[i]]) {
return nums[i];
}
// 找的手段是交换nums[i]和nums[nums[i]]
int temp = nums[i];
nums[i] = nums[temp];
nums[temp] = temp;
}
}
return -1;
}
};
数组中出现次数超过一半的数字(剑指offer_39)
题目
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2
题解
类似位运算处理，定义times来记录遍历过程中当前遍历元素在之前的遍历过程中出现的次数，初始值为1，定义result为最终结果，在遍历过程中其永远都等于出现次数最多的元素。遍历过程中如果result等于当前遍历元素则++times，否则–times，如果times变为0，则将当前遍历元素赋值给result，times重新赋值为1，遍历结束后返回result即可。
示例代码如下
class Solution {
public:
int majorityElement(vector<int>& nums) {
int length = nums.size();
if (length == 0) {
return -1;
}
int result = nums[0];
int times = 1;
for (int i = 1; i < length; ++i) {
if (times == 0) {
times = 1;
result = nums[i];
} else if (result == nums[i]) {
++times;
} else {
--times;
}
}
return times > 0 ? result : -1;
}
};
和为s的连续正数序列(剑指offer_57)
题目
输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
示例 1：
输入：target = 9
输出：[[2,3,4],[4,5]]
示例 2：
输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]
题解
正常遍历解决方案，示例代码如下
class Solution {
public:
vector<vector<int>> findContinuousSequence(int target) {
vector<vector<int>> result;
if (target <= 0) {
return result;
}
int low = 1;
int high = 2;
while (low < high) {
int cur_sum = (low + high) * (high - low + 1) / 2;
if (cur_sum > target) {
++low;
} else if (cur_sum == target) {
vector<int> tmp_result;
for (int i = low; i <= high; ++i) {
tmp_result.emplace_back(i);
}
result.emplace_back(tmp_result);
++low; // 这里++high和++low效果是一样的
} else {
++high;
}
}
return result;
}
};
二维数组中的查找(剑指offer_4)
题目
在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
示例:
现有矩阵 matrix 如下：
[
[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]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。
题解
由于数组从左到右、从上到下都是递增的，因而可以考虑从右上角开始遍历，如果发现右上角元素小于target，则证明所在行元素都小于target，可以从下面一行开始继续寻找目标；如果右上角元素大于target，则证明所在列元素都大于target，可以从左边一列开始继续寻找目标，示例代码如下所示：
class Solution {
public:
bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
if (matrix.empty() || matrix[0].empty()) {
return false;
}
int rows = matrix.size();
int cols = matrix[0].size();
int row = 0;
int col = cols - 1;
while (row < rows && col >= 0) {
if (matrix[row][col] > target) {
--col;
} else if (matrix[row][col] < target) {
// ++row的原因在于当前位置所在行右边的元素已经都比target大了
// 但不能保证row+1行col左侧的数据比target大，因而这里需要++row
++row;
} else {
return true;
}
}
return false;
}
};
数组中数字出现的次数(剑指offer_56)
题目
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
示例 1：
输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]
示例 2：
输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]
题解
将数组中所有的元素异或，即可得到只出现一次的两个元素a、b的异或值，可以找到a和b异或值二进制表达值的任意一位为1的位置，数组中这一位为1分为一组，为0分为一组，两组数据分别异或即可得到a和b。示例代码如下所示：
class Solution {
public:
vector<int> singleNumbers(vector<int>& nums) {
int ret = 0;
for (const auto& elem: nums) {
ret ^= elem;
}
int div = 1; // 注意标志位的初始化
while ((div & ret) == 0) { // & 能够找到只出现一次的两个数二进制表示的第一个不相同位
div <<= 1;
}
int a = 0;
int b = 0;
for (const auto& elem: nums) {
if (elem & div) { // & 能将a和b区分开来，原因同上
a ^= elem;
} else {
b ^= elem;
}
}
return vector<int>{a, b};
}
};
滑动窗口的最大值(剑指offer_59)
题目
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
题解
直观思路解决问题，具体思路如下：
- 构建目标数组max_window_ctnr和滑动过程中维系的滑动窗口 index。
- 首先构建初始滑动窗口index，窗口的front永远是当前数组中最大的元素。
- 遍历数组位置i直到i到达数组的尾部，遍历过程中完成如下操作：将index的front放入max_window_ctnr，滑动index，具体表现为如果front已经小于等于当前遍历位置i - k，这时弹出front，即可完成窗口的滑动。
- 遍历结束后需要把index的front放入max_window_ctnr，因为循环跳出时窗口的最后一个目标元素没有放入max_window_ctnr中。
示例代码如下：
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> max_window_ctnr;
if (nums.empty() || k <= 0 || nums.size() < k) {
return max_window_ctnr;
}
deque<int> index;
// 构建初始窗口阶段，index从头到尾必须是降序的，
// 且index的头部永远都是当前数组最大值对应的下标，下同
for (int i = 0; i < k; ++i) {
while (!index.empty() && nums[i] >= nums[index.back()]) {
index.pop_back();
}
index.push_back(i);
}
// 窗口滑动阶段
for (int i = k; i < nums.size(); ++i) {
max_window_ctnr.push_back(nums[index.front()]);
while (!index.empty() && nums[i] >= nums[index.back()]) {
index.pop_back();
}
if (!index.empty() && index.front() <= int(i - k)) {
index.pop_front();
}
index.push_back(i);
}
// 最后一个滑动窗口的最大值
max_window_ctnr.push_back(nums[index.front()]);
return max_window_ctnr;
}
};
机器人的运动范围(剑指offer_13)
题目
地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
示例 1：
输入：m = 2, n = 3, k = 1
输出：3
示例 2：
输入：m = 3, n = 1, k = 0
输出：1
提示：
1 <= n,m <= 100
0 <= k <= 20
题解
本题为<矩阵中的最长递增路径>的简化版，回溯法解决问题，值得注意的是这里定义二维数组visited，记录某个节点是否已经被走过，这样能够加速计算，示例代码如下：
class Solution {
public:
int movingCount(int m, int n, int k) {
if (m < 0 || n < 0 || k < 0) {
return 0;
}
vector<vector<bool>> visited(m, vector<bool>(n, false));
int r = 0;
int c = 0;
return moving_count_core(visited, m, n, r, c, k);
}
int count(int row, int col) {
int result = 0;
while (row) {
result += row % 10;
row /= 10;
}
while (col) {
result += col % 10;
col /= 10;
}
return result;
}
int moving_count_core(vector<vector<bool>>& visited, int m, int n, int r, int c, int k) {
if (r > m - 1 || c > n -1 || count(r, c) > k || visited[r][c]) {
return 0;
}
visited[r][c] = true; // 防止重复计算导致结果变大
return 1 + moving_count_core(visited, m, n, r + 1, c, k)
+ moving_count_core(visited, m, n, r, c + 1, k);
}
};
复杂度
时间：O(mn)
空间：O(mn)
数组中数值和下标相等的元素(剑指offer_53)
题目
假设一个单调递增的数组里的每个元素都是整数并且是唯一的。请编程实现一个函数找出数组中任意一个数值等于其下标的元素。例如，在数组{-3, -1, 1, 3, 5}中，数字3和它的下标相等。
题解
常规二分查找解决问题。示例代码如下：
class Solution {
public:
int findNumber(vector<int>& nums) {
int length = nums.size();
if (length == 0) {
return -1;
}
int low = 0;
int high = length - 1;
while (low <= high) { // 等号是核心
int mid = (low + high) / 2;
if (nums[mid] > mid) {
high = mid - 1;
} else if (nums[mid] < mid) {
low = mid + 1;
} else {
return mid;
}
}
return -1;
}
};
快速排序思想返回数组中位数
题解
快速排序的详解可以参照这里。返回中位数可以通过添加二分法来完成。示例代码如下所示：
int partition(vector<int>& array, int low, int high) {
int i = low - 1, x = array[high];
for (int j = low; j <= high - 1; j++) {
if (array[j] <= x) { // 这里能够显示出快速排序的不稳定性
swap(array[j], array[++i]);
}
}
swap(array[i + 1], array[high]);
return i + 1;
}
int get_mid(vector<int>& nums) {
int length = nums.size();
int low = 0;
int high = length - 1;
int result = -1;
int mid = low + (high - low) / 2;
while (low <= high) { // 注意等于号的重要性
int q = partition(nums, low, high);
if (mid == q) {
result = mid;
break;
} else if (q > mid) {
high = q - 1;
} else {
low = q + 1;
}
}
if (result == mid) {
return nums[mid];
}
return -1;
}
最小的k个数(剑指offer_40)
题目
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
示例 1：
输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]
示例 2：
输入：arr = [0,1,2,1], k = 1
输出：[0]
题解1 快速排序思想
示例代码如下所示：
class Solution {
public:
int partition(vector<int>& arr, int start, int end) {
int length = arr.size();
if (length == 0 || start < 0 || end >= length) {
return -1;
}
int i = start - 1;
int x = arr[end];
for (int j = start; j < end; ++j) {
if (arr[j] <= x) {
swap(arr[j], arr[++i]);
}
}
swap(arr[i + 1], arr[end]);
return i + 1;
}
vector<int> getLeastNumbers(vector<int>& arr, int k) {
vector<int> result;
int length = arr.size();
if (length == 0 || k <= 0) {
return result;
}
if (length <= k) {
return arr;
}
int start = 0;
int end = length - 1;
int index = partition(arr, start, end);
while (index != k - 1) {
if (index > k - 1) {
end = index - 1;
index = partition(arr, start, end);
} else {
start = index + 1;
index = partition(arr, start, end);
}
}
for (int i = 0; i <= index; ++i) {
result.emplace_back(arr[i]);
}
return result;
}
};
时间复杂度：理想情况下，每次遍历过程中只需要一半元素，因为我们是要找下标为k的元素，第一次切分的时候需要遍历整个数组 (0 ~ n) 找到了下标是 j 的元素，假如 k 比 j 小的话，那么我们下次切分只要遍历数组 (0~k-1)的元素就行啦，反之如果 k 比 j 大的话，那下次切分只要遍历数组 (k+1～n) 的元素就行啦，总之可以看作每次调用 partition 遍历的元素数目都是上一次遍历的 1/2，因此时间复杂度是 N + N/2 + N/4 + … + N/N = N*(2-1/(2^n)) = 2N, 因此时间复杂度是 O(N)。
空间复杂度：O(k)，最后存储结果的数组的长度为k。
题解2 堆排序思想
维护一个小顶堆q，先把数组中的前k个元素push到q中，不断地将数组中的元素push到q中，且维护这个大小为k的q，保证q中的元素一直都是当前最小的k个元素，最终q中剩下的元素即为目标元素。示例代码如下所示：
class Solution {
public:
vector<int> getLeastNumbers(vector<int>& arr, int k) {
vector<int> result;
if (k <= 0) {
return result;
}
int length = arr.size();
if (k >= length) {
return arr;
}
priority_queue<int> q;
for (int i = 0; i < k; ++i) {
q.push(arr[i]);
}
for (int i = k; i < length; ++i) {
if (q.top() > arr[i]) {
q.pop();
q.push(arr[i]);
}
}
for (int i = 0; i < k; ++i) {
result.emplace_back(q.top());
q.pop();
}
return result;
}
};
时间复杂度：维护一个大小为k的小顶堆的时间复杂度为O(logk)，最坏情况下数组中的元素都要在小顶堆中转一圈，因而总的时间复杂度为O(nlogk)。
空间复杂度：O(k)，因为小根堆的大小为k。
数组中的逆序对(剑指offer_51)
题目
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4]
输出: 5
题解
归并排序过程中记录待合并的前面数组比后面数组大的情况，示例代码如下所示：
class Solution {
public:
int reverse_pairs_inner(vector<int>& nums, int low, int high) {
if (low >= high) {
return 0;
}
int m = (low + high) / 2;
int result = reverse_pairs_inner(nums, low, m) + reverse_pairs_inner(nums, m + 1, high);
int i = low;
int j = m + 1;
for (int k = low; k <= high; ++k) {
tmp[k] = nums[k];
}
for (int k = low; k <= high; ++k) {
if (i == m + 1) {
nums[k] = tmp[j++];
} else if (j == high + 1 || tmp[i] <= tmp[j]) {
nums[k] = tmp[i++];
} else {
nums[k] = tmp[j++];
result += m + 1 - i;
}
}
return result;
}
int reversePairs(vector<int>& nums) {
int low = 0;
int high = nums.size() - 1;
tmp = vector<int>(nums.size(), 0);
return reverse_pairs_inner(nums, low, high);
}
private:
vector<int> tmp;
};
把数组排成最小的数(剑指offer_45)
题目
输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
示例 1:
输入: [10,2]
输出: "102"
示例 2:
输入: [3,30,34,5,9]
输出: "3033459"
题解
此题求拼接起来的最小数字，本质上是一个排序问题。设数组 nums 中任意两数字的字符串为 x 和 y，则规定 排序判断规则 为：
若拼接字符串 x + y > y + x，则 x “大于” y ；
反之，若 x + y < y + x，则 x “小于” y；
用上述规则进行排序即可得到结果，示例代码如下所示：
class Solution {
public:
void q_s(vector<string>& nums, int l, int r) {
if (l >= r) {
return;
}
int i = l;
int j = r;
while (i < j) {
// 必须先右后左，这样才能保证i和j遍历过程是正常的
while (i < j && nums[j] + nums[l] >= nums[l] + nums[j]) {
--j;
}
while (i < j && nums[i] + nums[l] <= nums[l] + nums[i]) {
++i;
}
swap(nums[i], nums[j]);
}
swap(nums[i], nums[l]);
q_s(nums, l, i - 1);
q_s(nums, i + 1, r);
}
string minNumber(vector<int>& nums) {
string result;
int length = nums.size();
if (length == 0) {
return result;
}
vector<string> tmp;
for (auto& num: nums) {
tmp.emplace_back(to_string(num));
}
q_s(tmp, 0, length - 1);
for (auto& str: tmp) {
result.append(str);
}
return result;
}
};
调整数组顺序使奇数位于偶数前面
题目
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
示例：
输入：nums = [1,2,3,4]
输出：[1,3,2,4]
注：[3,1,2,4] 也是正确的答案之一。
题解
双指针解决问题，示例代码如下所示：
class Solution {
public:
vector<int> exchange(vector<int>& nums) {
int length = nums.size();
if (length == 0) {
return vector<int>();
}
int begin = 0;
int end = length - 1;
while (begin < end) {
if (nums[begin] % 2 == 1) {
++begin;
continue;
}
if (nums[end] % 2 == 0) {
--end;
continue;
}
swap(nums[begin++], nums[end--]);
}
return nums;
}
};
合并排序的数组(常见面试)
题目
给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法，将 B 合并入 A 并排序。
初始化 A 和 B 的元素数量分别为 m 和 n。
示例:
输入:
A = [1,2,3,0,0,0], m = 3
B = [2,5,6], n = 3
输出: [1,2,2,3,5,6]
题解
从后向前赋值，这样能够保证不占用额外的空间复杂度。示例代码如下所示：
class Solution {
public:
void merge(vector<int>& A, int m, vector<int>& B, int n) {
int pa = m - 1;
int pb = n - 1;
int tail = m + n - 1;
int cur;
while (pa >= 0 || pb >= 0) {
if (pa == -1) {
cur = B[pb--];
} else if (pb == -1) {
cur = A[pa--];
} else if (A[pa] > B[pb]) {
cur = A[pa--];
} else {
cur = B[pb--];
}
A[tail--] = cur;
}
}
};
上一篇： [蓝桥杯][基础练习VIP]矩阵乘法