很久很久以前，有人刷题不做记录，从Array刷到Array，刷了几年还是在刷Array。
这里记录一下做Elements of Programming Interviews的题目，避免四年之后还是在刷Array。
[TOC]
Array
数组的基本语法
//alloc
array<int, 3> A = {1,2,3};
vector<int> A = {1, 2, 3};
vector<int> sub_A(A.begin(), A.begin()+5);
//2d
array<array<int, 2>, 2> A={};
vector<vector<int>> A;
//
A.push_back();
A.emplace_back();
//algorithm
binary_search(A.begin(), A.end(), 42);
lower_bound(A.begin(), A.end(), 42);
upper_bound(A.begin(), A.end(), 42);
fill(A.begin(), A.end(), 42);
swap(x, y);
min_element(A.begin(), A.end());
max_element(A.begin(), A.end());
reverse(A.begin(), A.end());
rotate(A.begin(), A.begin()+shift, A.end()); //Performs a left rotation on a range of elements.
sort(A.begin(), A.end());
Bootcamp: Arrays
the even entries appear first
void EvenOdd(vector<int>* A_ptr) {
// TODO - you fill in here.
// 将奇数仍到数组尾部即可
vector<int>& A = *A_ptr;
int next_even = 0, next_odd = A.size() - 1;
while (next_even < next_odd) {
if (A[next_even] % 2 == 0) {
++next_even;
}
else {
std::swap(A[next_even], A[next_odd--]);
}
}
return;
}
The Dutch national flag problem
暴力解法需要O(n)的空间，使用数组自身将空间复杂度降低到O(1).
将数组中小于pivot的元素拍在最前面，等于pivot的排在中间，大于pivot的排在最后。
简单的想法是类似冒泡排序，通过两遍冒泡分别将小于和大于pivot的元素分配到两端。但是类似于上一题的思路，可以通过一遍直接扔的方式避免冒泡O(n^2)的复杂度。
void DutchFlagPartition(int pivot_index, vector<Color>* A_ptr) {
// TODO - you fill in here.
vector<Color> &A = *A_ptr; // 这个地方很蠢地忘记创建引用
Color pivot = A[pivot_index];
//小的扔到左边
int smaller = 0;
for (int i = 0; i < A.size(); ++i) {
if (A[i] < pivot) {
std::swap(A[i], A[smaller++]);
}
}
//大的扔到右边
int larger = A.size() - 1;
for (int i = A.size() - 1; i >= 0 && A[i] >= pivot; --i) {
if (A[i] > pivot) {
std::swap(A[i], A[larger--]);
}
}
return;
}
Increment an arbitrary-precision integer
<1, 2, 9> ==> <1, 3, 0>
需要处理的是第一位的进位问题。自己的实现调用了两遍reverse太过度了。EPI实现的代码就很简单。
vector<int> PlusOne(vector<int> A) {
// TODO - you fill in here.
std::reverse(A.begin(), A.end());
int cnt = 0;
++A[0];
for (int i = 0; i < A.size(); ++i) {
A[i] += cnt;
if (A[i] >= 10) {
A[i] -= 10;
cnt = 1;
}
else {
cnt = 0;
}
}
if (cnt != 0) {
A.push_back(cnt);
}
std::reverse(A.begin(), A.end());
return A;
}
//EPI代码
vector<int> PlusOne(vector<int> A) {
// TODO - you fill in here.
++A.back();
for (int i = A.size() - 1; i > 0 && A[i] >=10; --i) {
A[i] = 0;
++A[i-1];
}
if (A[0] == 10) {
A[0] = 0;
A.insert(A.begin(),1);
}
return A;
}
Multiply two arbitrary-precision integers
模拟乘法竖式
vector<int> Multiply(vector<int> num1, vector<int> num2) {
// TODO - you fill in here.
const int sign = num1.front() < 0 ^ num2.front() < 0 ? -1: 1;
num1.front() = abs(num1.front());
num2.front() = abs(num2.front());
// 存放结果
vector<int> result(num1.size() + num2.size(), 0);
for (int i = num1.size()-1; i >= 0; --i) {
for (int j = num2.size()-1; j >= 0; --j) {
result[i+j+1] += num1[i] * num2[j];
result[i+j] += result[i+j+1] / 10;
result[i+j+1] %= 10;
}
}
// 移除前导0 find_if_not
result = {
std::find_if_not(std::begin(result), std::end(result), [](int a){ return a==0;}),
std::end(result)
};
if (result.empty()) {
return {0};
}
result.front() *= sign;
return result;
}
Advancing through an array
数组中的每个元素给出最大移动步数，判断是否能移动到数组尾部。
~~题不刷，就会忘!~~
看了解法之后也比较好理解，记录当前最大能到达的位置，不断地更新这个值就好。
// 时间复杂度O(n)，空间复杂度O(1)
bool CanReachEnd(const vector<int>& max_advance_steps) {
// TODO - you fill in here.
// 记录当前最远位置
int furthest_so_far = 0, last_idx = max_advance_steps.size() - 1;
for (int i = 0; i <= furthest_so_far && i <= last_idx; ++i) {
furthest_so_far = std::max(furthest_so_far, max_advance_steps[i] + i);
}
return furthest_so_far >= last_idx;
}
Delete duplicates from a sorted array
这个从左往右码就行了，数组为空的情况需要处理一下。
// 时间复杂度O(n)，空间复杂度O(1)
int DeleteDuplicates(vector<int>* A_ptr) {
// TODO - you fill in here.
vector<int> &A = *A_ptr;
if (A.size() == 0) {
return 0;
}
int valid_idx = 0, cur_idx = 1, length = A.size();
while (cur_idx < length) {
if (A[cur_idx] == A[valid_idx]) {
++cur_idx;
}
else{
A[++valid_idx] = A[cur_idx++];
}
}
return valid_idx+1;
}
Buy and sell a stock once
买卖是按时间顺序的，计算今日卖出价格与历史最低价的差距，与最大收益比较即可。
double BuyAndSellStockOnce(const vector<double>& prices) {
// TODO - you fill in here.
double min_price = std::numeric_limits<double>::max(), max_profit = 0;
for (auto& price: prices) {
double profit_today = price - min_price;
max_profit = std::max(max_profit, profit_today);
min_price = std::min(min_price, price);
}
return max_profit;
}
Buy and sell a stock twice
相比与上一题，这里需要买卖两次。
如何才能将一次的买入卖出变成两次，在上一题的基础上，一个暴力解法是将时间段划分成两部分，前一部分做第一个交易，后一部分做第二次交易。外层O(n)的遍历加上内层BuyAndSellStockOnceO(n)的复杂度，总的时间复杂度是O(n^2)。
暴力的解法中有很多的重复计算，如时间划分点变动一天，但是前一部分的计算都要重新做一遍。 既然在思路上是可以将时间拆分成两端，利用BuyAndSellStockOnce方法，可以 对第一次买卖的收益只做一遍计算，对第二次买卖的收益也只做一次计算。
由此，先正向计算一遍，在当前时间点前买卖一次的最大收益是多少，再反向计算一遍在当前时间点之后买卖一次的最大收益是多少。这两个值和的最大值即为最大收益。
double BuyAndSellStockTwice(const vector<double>& prices) {
// TODO - you fill in here.
// vector 开成int的了，卡了好一会没搞定
vector<double> max_profit_first_buy(prices.size(), 0);
double total_max_profit = 0;
// 正向计算第一次买卖的收益变化
double min_price_so_far = std::numeric_limits<double>::max();
for (int i = 0; i < prices.size(); ++i) {
min_price_so_far = std::min(min_price_so_far, prices[i]);
total_max_profit = std::max(total_max_profit, prices[i] - min_price_so_far);
max_profit_first_buy[i] = total_max_profit;
}
// 反向计算第二次买卖的收益变化
double max_price_so_far = std::numeric_limits<double>::min();
for (int i = prices.size() - 1; i > 0; --i) {
max_price_so_far = std::max(max_price_so_far, prices[i]);
total_max_profit = std::max(total_max_profit, max_price_so_far - prices[i] + max_profit_first_buy[i - 1]);
}
return total_max_profit;
}
Computing an alternation
void
Enumerate all primes to n
直接打表筛查。
这里使用bool数组打表，遇到了之前见过的一个问题， 由于C++98的设计原因，vector<bool>使用的是bit保存的信息，而不是正常的byte保存bool， 这导致了操作符[]并不能真正返回布尔值对应的地址。所以这里应该使用deque<bool>
Why is vector not a STL container?
vector<int> GeneratePrimes(int n) {
// TODO - you fill in here.
std::deque<bool> sieve(n+1, true);
sieve[0] = false;
for (int i = 2; i < n/2+1; ++i) {
for (int j = 2; i*j <= n; ++j) {
sieve[i*j] = false;
}
}
vector<int> ret;
for (int i = 2; i <= n; ++i) {
if (sieve[i]) {
ret.push_back(i);
}
}
return ret;
}
Permute the elements of an array
给定一个数组和一个排列，将该排列作用的数组上。
直接开辟新数组，可以直接根据排列映射得到结果。 在避免申请新数组的情况下，需要用到一个特性
每个排列可由一组独立的排列构成，组内的每个排列都是循环的。
白话就是每个排列可分成多个圈， 每个圈内shift一次，等价于原排列。
这里使用了C++的lambda表达式，[]内的为引用捕获。
使用非成员函数begin和end在这里有解释：Why use non-member begin and end functions in C++11?
Free functions: 非成员函数
非成员函数
void ApplyPermutation(vector<int> perm, vector<int>* A_ptr) {
// TODO - you fill in here.
vector<int> &A = *A_ptr;
// 最多A.size个子排列
for (int i = 0; i < A.size(); ++i) {
int next = i;
// 对当前组内顺序平移一次
while (perm[next] >= 0) {
std::swap(A[i], A[perm[next]]);
int temp = perm[next];
// 使用负数表示已经被访问过， 避免申请新空间
perm[next] -= perm.size();
next = temp;
}
}
std::for_each(std::begin(perm), std::end(perm), [&perm](int &x) {x += perm.size();});
return;
}
Compute the next permutation
要生成一个排列的下一个排列，需要分析其内在的规律。
如<6, 2, 1, 5, 4, 3, 0>来说，其后缀<5, 4, 3, 0>已经是降序的，意味着该后缀是最大字典序，没有下一个排列。需要将1与后面的元素交换，需要在后缀中找到一个比1大(比1小的字典序更小，符合下一个排列的要求)的最小数(下一个字典序的变动应该是最小的)。 得到<6, 2, 3, 5, 4, 1, 0>，这样前缀已经是最小的了，但后缀还不是。交换后的后缀仍然是降序排列， 将其反转可得到最小后缀，即下一个排列为<6, 2, 3, 0, 1, 4, 5>
vector<int> NextPermutation(vector<int> perm) {
// TODO - you fill in here.
int k = perm.size() - 2;
// 找到最长递减后缀
while (k >= 0 && perm[k] >= perm[k+1]) {
--k;
}
if (k == -1) {
return {};
}
//从后向前查找第一个大于perm k的元素
//find_if返回Iterator，解引用后swap
std::swap(
*std::find_if(perm.rbegin(), perm.rend(), [&](int a) {return a > perm[k];}),
perm[k]
);
// 将后缀重新由小到大排列
std::reverse(perm.begin()+k+1, perm.end());
return perm;
}
Sample offline data
从数组中随机抽取k个元素。 每次从剩余数组中抽取一个元素，直至抽到k个。
这个代码很“C++11”... 直接random取余数并不能生成真正的均匀分布。
C++11把随机数分为引擎和分布两个部分，需要先指定一个随机数引擎，再根据分布生成随机数。
std::random_device is a non-deterministic uniform random bit generator, although implementations are allowed to implement std::random_device using a pseudo-random number engine if there is no support for non-deterministic random number generation.
random_device() 生成一个对象，其操作符()将推进引擎的状态，返回一个随机数，这里用于随机数引擎的种子。
这里的写法，我也没太看懂，为什么分布后面可以是花括号，将其换成圆括号是我能理解的写法。待更
void RandomSampling(int k, vector<int>* A_ptr) {
// TODO - you fill in here.
vector<int> &A = *A_ptr;
// default_random_engine 生成随机数引擎
// random_device()
std::default_random_engine seed((std::random_device())());
for (int i = 0; i < k; ++i) {
std::swap(
A[i],
A[std::uniform_int_distribution<int>{i, static_cast<int>(A.size()-1)}(seed)]
);
}
return;
}
Sample online data
很久很久以前，有个蓄水池算法，要从流中随机抽取k个元素。
假设目前已经接受了n个包并抽取了k个元素，当第n+1个包到达时，其属于抽样集的概率应为k/(n+1)，这时随机一个概率值，若当前包可被保留，则从原k个元素中随机剔除一个。
数学证明可见：水塘抽樣
// Assumption: there are at least k elements in the stream.
vector<int> OnlineRandomSample(vector<int>::const_iterator stream_begin,
const vector<int>::const_iterator stream_end,
int k) {
// TODO - you fill in here.
vector<int> ret;
// 先填充k个元素
for (int i = 0; i < k; ++i, ++stream_begin) {
ret.push_back(*stream_begin);
}
// 初始化随机数引擎
std::default_random_engine seed((std::random_device())());
int element_so_far = k;
while (stream_begin != stream_end) {
++element_so_far;
// 以 k/n+1的概率保留元素
int rand_val = std::uniform_int_distribution<int>(0, element_so_far-1)(seed);
if (rand_val < k) {
ret[rand_val] = *stream_begin;
}
++stream_begin;
}
return ret;
}
Compute a random permutation
生成一个随机的排列，每次从剩余集合中随机选择一个元素放置到当前位置。可使用之前的从离线采样函数，即从n个元素中随机抽取n个元素。
std::iota
Fills the range
[first, last)with sequentially increasing values, starting withvalueand repetitively evaluating ++value.Equivalent operation:
c++ *(d_first) = value; *(d_first+1) = ++value; *(d_first+2) = ++value; *(d_first+3) = ++value; ...
void RandomSampling(int k, vector<int> *A_ptr) {
// 离线采样
vector<int> &A = *A_ptr;
std::default_random_engine seed((std::random_device())());
for (int i = 0; i < k; ++i) {
std::swap(
A[i],
A[std::uniform_int_distribution<int>(i, static_cast<int>(A.size() - 1))(seed)]
);
}
return;
}
vector<int> ComputeRandomPermutation(int n) {
// TODO - you fill in here.
vector<int> perm(n);
// 生成序列
std::iota(perm.begin(), perm.end(), 0);
// 从n个采样n个，即随机打乱
RandomSampling(perm.size(), &perm);
return perm;
}
Compute a random subset
这个有些类似与离线采样的那题，但是当k<<n时，大多数的元素都是未用到的，申请O(n)的空间有些浪费。这里使用hash table记录。
在离线采样方法中，数组中存放0~n-1的结果，每次交换两个元素。通过hash table，可以保存每次交换元素的下标。这样对交换的两个元素，共有四种情况(都在table内，只有一个在，都不在)
//申请O(n)空间
//Average running time: 1 s
//Median running time: 969 ms
vector<int> RandomSubset(int n, int k) {
// TODO - you fill in here.
vector<int> A(n);
std::iota(A.begin(), A.end(), 0);
std::default_random_engine seed((std::random_device())());
for (int i = 0; i < k; ++i) {
std::swap(
A[i],
A[std::uniform_int_distribution<int>(i, static_cast<int>(A.size() - 1))(seed)]
);
}
return {A.begin(), A.begin() + k};
}
// Hash table
// Returns a random k-sized subset of {0, 1, ..., n - 1}.
vector<int> RandomSubset(int n, int k) {
// TODO - you fill in here.
std::default_random_engine seed((std::random_device())());
std::unordered_map<int, int> changed_elements;
for (int i = 0; i < k; ++i) {
int rand_idx = std::uniform_int_distribution<int>(i, n - 1)(seed);
auto ptr1 = changed_elements.find(i), ptr2 = changed_elements.find(rand_idx);
if (ptr1 == changed_elements.end() && ptr2 == changed_elements.end()) {
changed_elements[i] = rand_idx;
changed_elements[rand_idx] = i;
}
else if (ptr1 == changed_elements.end() && ptr2 != changed_elements.end()) {
changed_elements[i] = ptr2->second;
ptr2->second = i;
}
else if (ptr1 != changed_elements.end() && ptr2 == changed_elements.end()) {
changed_elements[rand_idx] = ptr1->second;
ptr1->second = rand_idx;
}
else {
std::swap(ptr1->second, ptr2->second);
}
}
vector<int> ret;
for (int i = 0; i < k; ++i) {
ret.push_back(changed_elements[i]);
}
return ret;
}
Generate nonuniform random numbers
按概率生成随机数。记得在做遗传算法的时候处理过这种问题，用饼图去累计概率。
int NonuniformRandomNumberGeneration(const vector<int>& values,
const vector<double>& probabilities) {
// TODO - you fill in here.
std::default_random_engine seed((std::random_device())());
double p = std::uniform_real_distribution<double> (0., 1.0)(seed);
double con_sum = 0.;
for (int i = 0; i < values.size(); ++i) {
con_sum += probabilities[i];
if (con_sum > p) {
return values[i];
}
}
return 0;
}
Multidimensional arrays
The Sudoku checker problem
判断一个未完成的数独盘是否是合法的。 我的做法比较粗暴，用3个集合分别检查3个约束是否满足。
// Check if a partially filled matrix has any conflicts.
bool IsValidSudoku(const vector<vector<int>>& partial_assignment) {
// TODO - you fill in here.
vector<std::unordered_set<int>> rows(9); //检测行冲突
vector<std::unordered_set<int>> cols(9); //检测列冲突
vector<std::unordered_set<int>> inner(9); //检测小9宫格冲突
for (int r_idx = 0; r_idx < 9; ++r_idx) {
for (int c_idx = 0; c_idx < 9; ++c_idx) {
int c_val = partial_assignment[r_idx][c_idx];
if (c_val == 0) {
continue;
}
auto &c_row = rows[r_idx];
if (c_row.find(c_val) != c_row.end()) {
return false;
}
else {
c_row.insert(c_val);
}
auto &c_col = cols[c_idx];
if (c_col.find(c_val) != c_col.end()) {
return false;
}
else {
c_col.insert(c_val);
}
int inner_idx = (r_idx / 3) * 3 + c_idx / 3;
auto &c_inner = inner[inner_idx];
if (c_inner.find(c_val) != c_inner.end()) {
return false;
}
else {
c_inner.insert(c_val);
}
}
}
return true;
}
Compute the spiral ordering of a 2D array
返回数组的螺旋序列。思路上是一层一层地对数组进行访问，最外圈访问完成后，该问题变成了相同形式，但规模更小的子问题。
这里刚开始时判断nextX和nextY时并没有考虑小于0的情况，但是也能通过测试样例，是因为在与size()相比较时，有符号的负值被转换为无符号，会满足第二个条件。当然在逻辑上是有漏洞的。
vector<int> MatrixInSpiralOrder(const vector<vector<int>>& square_matrix) {
// TODO - you fill in here.
// kShift 控制前进方向
const vector<vector<int>> kShift = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int dir = 0, x = 0, y = 0;
int nextX = 0, nextY = 0;
vector<vector<int>> visited(square_matrix);
vector<int> ret;
for (int i = 0; i < square_matrix.size() * square_matrix.size(); ++i) {
ret.push_back(square_matrix[x][y]);
visited[x][y] = 0;
nextX = x + kShift[dir][0];
nextY = y + kShift[dir][1];
if (nextX < 0 || nextX >= square_matrix.size() || nextY < 0 || nextY >= square_matrix.size() || visited[nextX][nextY] == 0) {
dir = (dir + 1) % 4;
nextX = x + kShift[dir][0];
nextY = y + kShift[dir][1];
}
x = nextX;
y = nextY;
}
return ret;
}
Rotate a 2D array
将2D矩阵顺时针旋转90°。
按层处理，每层每次处理四个元素。即将每条边上对应位置的元素交换位置
void RotateMatrix(vector<vector<int>>* square_matrix_ptr) {
// TODO - you fill in here.
vector<vector<int>> &square_matrix = *square_matrix_ptr;
const int mat_size = square_matrix.size() - 1;
for (int i = 0; i < square_matrix.size() / 2; ++i) {
for (int j = i; j < mat_size - i; ++j) {
int temp1 = square_matrix[i][j]; // top element
int temp2 = square_matrix[j][mat_size-i]; // right element
int temp3 = square_matrix[mat_size-i][mat_size-j]; // bottom element
int temp4 = square_matrix[mat_size-j][i]; // left element
square_matrix[i][j] = temp4; // left2top
square_matrix[j][mat_size-i] = temp1; //top2right
square_matrix[mat_size-i][mat_size-j] = temp2; // right2bottom
square_matrix[mat_size-j][i] = temp3; //bottom2left
}
}
return;
}
Compute rows in Pascal's Triangle
输出帕斯卡三角的前n行，直接模拟即可
vector<vector<int>> GeneratePascalTriangle(int num_rows) {
// TODO - you fill in here.
vector<vector<int>> ret = {{1}};
if (num_rows == 0) {
return {};
}
else if (num_rows == 1) {
return ret;
}
for (int i = 1; i < num_rows; ++i) {
vector<int> c_row;
c_row.emplace_back(1);
auto &last_row = ret[i-1];
for (int j = 0; j < last_row.size() - 1; ++j) {
c_row.push_back(last_row[j] + last_row[j+1]);
}
c_row.emplace_back(1);
ret.emplace_back(c_row);
}
return ret;
}
Comments !