场景题
题三：进制转换
2019哈罗单车实习生笔试题
将一个10进制整数转换成36进制的数，可以用0-9A-Z表示0-35.
/**
* Hellobike 2019 interview.
*/
#include <iostream>
#include <string>
using namespace std;
class Solution {
public:
string itob36(int n) {
int r = 0; // remainder of n mod 36
string tmp;
// iteratively divde by 36 to get each digit
while (n) {
r = n % 36;
tmp += MAP[r];
n /= 36;
}
// reverse tmp to ret
string ret;
cout << "tmp is " << tmp << endl;
for (auto iter = tmp.rbegin(); iter != tmp.rend(); ++iter)
ret.push_back(*iter);
return ret;
}
private:
string MAP[36] = {"0", "1", "2", "3", "4", "5", \
"6", "7", "8", "9", "A", "B", \
"C", "D", "E", "F", "G", "H", \
"I", "J", "K", "L", "M", "N", \
"O", "P", "Q", "R", "S", "T", \
"U", "V", "W", "X", "Y", "Z"};
};
// test
int main() {
int number = 12345;
cout << Solution().itob36(number);
return 0;
}题五：输出数组的全排列
给定一个数组，求其全排列。
Idea: pick one element as prefix, then add to the permutations of the rest n-1 elems. Reference: https://www.cnblogs.com/ranjiewen/p/8059336.html
#include <iostream>
#include <iterator>
#include <algorithm>
void Permute(int arr[], int beg, int end)
{
if (beg == end)
{
std::copy(arr, arr + end, std::ostream_iterator<int>(std::cout));
std::cout << std::endl;
}
for (int i = beg; i != end; ++i)
{
std::swap(arr[i], arr[beg]);
Permute(arr, beg + 1, end);
std::swap(arr[i], arr[beg]);
}
}
int main()
{
int arr[] = {0,1,2,3,4,5,6,7,8,9};
Permute(arr, 0, 5);
return 0;
}题六：斜线填充
给定n x m的矩阵，按照从右上往左下的斜线填充 1 到 n*m 的值。 例如，对于一个3x3的矩阵,
1 2 4
3 5 7
6 8 9 (3x3)
1 2 4 7
3 5 8 10
6 9 11 12 (3x4)
思路：干就完了。先填充左上角的三角区域，再填充右下角的三角区域。注意边界条件，无论行或列到达边界，记得跳转。
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
Solution(int n, int m)
{
// fill with 0
for (int i = 0; i != n; ++i)
mat.push_back(vector<int>(m, 0));
}
void skewFill(int n, int m)
{
int cnt = 1;
// fill the up-left triangle
for (auto col = 0; col != m; ++col)
{
for (auto i = 0, j = col; i != n && j >= 0; ++i)
mat[i][j--] = cnt++;
}
// fill the bottom-right triangle
for (auto row = 1; row != n; ++row)
{
for (auto j = m-1, i = row; i != n && j >= 0; ++i)
mat[i][j--] = cnt++;
}
}
/// print the matrix
void printer()
{
for (auto &row : mat)
{
for (auto &col : row)
printf("%3d ", col);
cout << endl;
}
}
private:
vector<vector<int>> mat;
};
// test
int main()
{
int n = 0, m = 0;
cin >> n >> m;
Solution s(n, m);
s.skewFill(n, m);
s.printer();
return 0;
}题七：螺旋矩阵
按顺时针填充螺旋填充矩阵。例如：
9 8 7
2 1 6
3 4 5 (3x3)
12 11 10 9
3 2 1 8
4 5 6 7 (3x4)
Idea: Imagine there are for borders that surround the matrix. We walk through the mat, and once achieve a border, we change the direction. Each time we finished a circle, we will shrink our border, and start next circle. After we fill (row * col) elems in the matrix, we are done!
Note: this solution is the most elegant in my opinion, for it’s simple boundray case.
#include <iostream>
#include <vector>
using std::vector;
class Solution
{
public:
Solution(int rows, int cols)
: mat_(rows, vector<int>(cols, 0))
{
}
void BuildMat()
{
// 4 border
int top = 0;
int bot = mat_.size() - 1;
int left = 0;
int right = mat_[0].size() - 1;
int N = (bot + 1) * (right + 1);
for (int i = 0, j = 0; N != 0; --N)
{
// make sure fill exactly one element at each loop
mat_[i][j] = N;
if (i == top)
{
if (j < right) ++j; // go right
else if (j == right) ++i; // checkpoint
}
else if (j == right)
{
if (i < bot) ++i; // go down
else if (i == bot) --j;
}
else if (i == bot)
{
if (j > left) --j; // go left
else if (j == left) --i;
}
else if (j == left)
{
if (i > top + 1) --i; // go up
else if (i == top + 1)
{
++j;
// shrink borders
++top, --bot, ++left, --right;
}
}
else
{
throw std::runtime_error("not behaved expectedly");
}
}
}
void Print()
{
for (auto &r : mat_)
{
for (auto &c : r)
printf("%2d ", c);
std::cout << std::endl;
}
}
private:
vector<vector<int> > mat_;
};
// test
int main()
{
Solution so(3, 4);
so.BuildMat();
so.Print();
return 0;
}扔骰子的期望
拼多多2019校招正式批
扔n个骰子，第i个骰子有可能掷出种等概率的不同结果，数字从1到. 比如, 就等可能的出现1点或2点。所有骰子的结果的最大值将作为最终结果。求最终结果的期望。
输入描述： 第一行一个整数n，表示n个骰子。（1 ⇐ n ⇐ 50） 第二行n个整数，表示每个骰子的结果数. ()
输出描述： 输出最终结果的期望，保留两位小数。
示例输入：
2
2 2
示例输出：
1.75
主要考察事件概率的计算。
假设有3个骰子，最大点数分别为2,3,4点。那么扔n个骰子，最终结果为1的概率如下
同理，最终结果为2, 也就是说三个骰子中最大的点数为2, 考虑每个骰子都点数都小于或等于2的概率，再减去每个骰子都小于或等于1的概率，即为
这就求得了最终结果的所有可能的值对应的概率，可以看出相加为1, 现在可以求期望了。
注意，当要求的点数大于当前骰子的最大点数时，那么该骰子掷出小于该点数的概率为1. 比如让一个最大点数为2的骰子掷出小于3的点数，显然概率为1.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<double> Distribution(const vector<int>& die_ranges, int support)
{
vector<double> probs;
for (int i = 1; i <= support; ++i)
{
double pprob = 1.0; // for previous prob
double prob = 1.0; // for current prob
for (auto e : die_ranges)
{
pprob *= min(double(i-1) / double(e), 1.0);
prob *= min(double(i) / double(e), 1.0);
}
probs.push_back(prob - pprob);
}
return probs;
}
int main()
{
int num_die;
cin >> num_die;
int maxpoint = 0;
vector<int> die_ranges;
for (int i = 0, tmp; i != num_die; ++i)
{
cin >> tmp;
if (tmp > maxpoint)
maxpoint = tmp;
die_ranges.push_back(tmp);
}
// io done
vector<double> probs = Distribution(die_ranges, maxpoint);
double expectation = 0.0;
for (int i = 1; i <= maxpoint; ++i)
{
expectation += (probs[i-1] * i);
}
printf("%.2f", expectation);
return 0;
}数据结构相关
大部分出自《剑指Offer》
反向打印链表
给定一个单链表，反向打印每个节点的值。
/*
* 1. use stack
* 2. use recursion
*/
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
class ListNode {
public:
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
class Solution {
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> ret;
// boundary case
if (head == nullptr) return ret;
stack<int> s;
for (auto p = head; p != nullptr; p = p -> next) {
s.push(p -> val);
}
while (!s.empty()) {
ret.push_back(s.top());
s.pop();
}
return ret;
}
// recursive needs a member variable
// use recursion stack, tricky
vector<int> arr;
vector<int> reversePrint(ListNode* head) {
if (head) {
reversePrint(head -> next);
arr.push_back(head -> val);
}
return arr;
}
/*
* Consider the closure, at one recursive step,
* what I should do? Let's drop all the details,
* just look one recursive step.
* What had I done?
* Oh gee, I see if the head is not null,
* I must push the value to the vector,
* but before this, I should take a look at
* `head -> next`, since I have to push
* the tail first. So which one can help me
* do this? Yes, the function itself! Then
* after I have addressed the tail, now I'm
* going to push current value to the vector.
* That's all I need!
* The key is you work in one recursive step, and
* form a closure for the next, and do not forget
* the base case (stopping rules). That how
* recursion runs! And you are free of those
* confusing details.
*/
};求整数的二进制表示中“1”的个数
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
/*
* `n` and `n-1` are the same from high bit position
* to low, they differs from the last bit of 1 of n,
* let's name it x. Have a look from x to the lowest
* bit position,
* n: 010101000
* & x <--- position x
* n-1: 010100111
* ---------------
* 010100000 <--- n&(n-1)
* It erases the last bit of 1 in n!!!
*
* This is why the following procedure will work. :)
*/
#include <iostream>
int NumOf1(int n) {
int cnt = 0;
while (n) {
n = n & (n-1);
++cnt;
}
return cnt;
}
int main() {
int N = 0;
std::cin >> N;
std::cout << NumOf1(N);
return 0;
}不可描述
求出113的整数中1出现的次数,并算出1001300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有
1、10、11、12、13
因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。
/*
* Credits: unknown
*
* Idea:
* 1) Focus exactly one decimal position, calculate the
* number of ones.
* 2) Run out from lowest to highest position, add them
* together, it's the answer.
*
* Imaging the numbers from 1 to n sits in a line in
* front of you. Now you're required to calculates all
* the ones in the sequence. A basic way is that, each
* time I focus on the same digit pos, and count all
* ones in that pos. Next time I focus on another pos.
* And I sum them all together, finally got the answer.
*
* See how can we count the num of ones in a specific
* decimal pos? Let's do that! Suppose N = 301563.
*
* Step 1.
* Now I focus the hundred position, and split N into `a`
* and `b`, where
*
* a = ceil(N / 100) = 3015
* b = N % 100 = 63
*
* 1). There are (a / 10 + 1) = 302 hits of one
* 2). Each of length 100
* 3). Totally (a/10 + 1) * 100 hits of one
*
* Let me explain a little:
* (000-301)5(00-99) -> (000-301)1(00-99)
*
* The digits above hundred pos have 302 variants, and
* the digits under hundred pos has 100 variants, thus
* gives a total (a/10 + 1) * 100.
*
* Step 2.
* This time I focus on thousand pos, and now
*
* a = N / 1,000 = 301
* b = N % 1,000 = 563
*
* 1). There are (a/10) = 30 hits of one
* 2). Each of length 1000
* 3). And a tail hits of 564
*
* (00-29)1(000-999) + 301(000-563)
* This gives 30 * 1000 + 564 = (a/10)*1000+(b+1)
*
* Step 3.
* Now move to ten thousand pos, with
*
* a = N / 10,000 = 30
* b = N % 10,000 = 1563
*
* 1). There are total (a/10)=3 hit
* 2). Each of length 10,000
*
* (0-2)1(0000-9999)
* gives 3 * 10,000 = (a/10).
*
* That's all 3 cases. Let's write!
*/
class Solution {
public:
int NumOnes(int n) {
int ones = 0;
for (long long m = 1; m <= n; m *= 10) {
ones +=
/*
* this covers case 1 & 3
* since (a+8)/10 = a/10 + 1 if a%10 >= 2
* (a+8)/10 = a/10 if a%10 == 0
*/
(n/m + 8) / 10 * m
+
// case 2
(n/m % 10 == 1) * (n%m + 1);
}
return ones;
}
};K轮换
原题：https://leetcode.com/problems/rotate-array/
Given an array, rotate the array to the right by k steps, where k is non-negative.
Example 1:
Input: [1,2,3,4,5,6,7] and k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]
Example 2:
Input: [-1,-100,3,99] and k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]
Note:
- Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
- Could you do it in-place with O(1) extra space?
提供三种方法：第一种，效率最低，因为vector从头插入元素开销很大；第二种，花费额外的空间，来降低时间开销；第三种，挺好的，std::reverse用的是首尾交换元素，无额外空间开销。
class Solution {
public:
void rotate(vector<int>& nums, int k) {
#if false // method 1.
if (k == 0) return;
nums.insert(nums.begin(), nums.back());
nums.pop_back();
rotate(nums, k-1);
#elif false // method 2.
vector<int> dummy(nums);
for (int i = 0; i != dummy.size(); ++i)
{
nums[(i+k) % nums.size()] = dummy[i];
}
#elif true // method 3.
k %= nums.size();
std::reverse(nums.begin(), nums.end());
std::reverse(nums.begin(), nums.begin() + k);
std::reverse(nums.begin() + k, nums.end());
#endif
}
};Move zeros
原题：https://leetcode.com/problems/move-zeroes/
Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements.
Example:
Input: [0,1,0,3,12]
Output: [1,3,12,0,0]
Note:
- You must do this in-place without making a copy of the array.
- Minimize the total number of operations.
思路：记录数字0出现的个数count。如果当前数字是0，给count加一；如果不是0，将这个值往前挪count位。最后将最后count个元素置0.
class Solution {
public:
void moveZeroes(vector<int>& nums) {
if (nums.size() < 2) return;
// c.f. https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/727/
int numzeros = 0;
for (int i = 0; i != nums.size(); ++i)
{
if (nums[i] == 0)
++numzeros;
else
nums[i-numzeros] = nums[i];
}
// set the tails to 0
while (numzeros)
{
nums[nums.size() - numzeros] = 0;
--numzeros;
}
}
};Kth Largest Element in an Array
From: LeetCode125.
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
Example 1:
Input: [3,2,1,5,6,4] and k = 2
Output: 5
Example 2:
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
Note: You may assume k is always valid, 1 ≤ k ≤ array’s length.
思路：利用快排的partition思想，每次选取一个pivot，将数组分为小于pivot和大于pivot的两部分。此时pivot的index就是排好序之后的index，与k相比，如果出较小，则在后半部分（大于pivot）再次划分，如果较大，则在前半部分划分。直到划分出来的pivot的index等于k。还要注意的是，这样找出来的是第k小，用数组长度减一下，才是第k大，注意index的变换。
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
// from 王小康：快排partition知道吧？
// 就一刀一刀地劈开，劈一次你知道pivot的index，
// 如果比k小，继续在右边劈，如果比k大，就在左边劈！
if (nums.empty()) throw std::invalid_argument("empty arr");
if (nums.size() == 1) return nums.front();
// else @nums has >= 2 elems
int mid = Partition(nums, 0, nums.size());
k = nums.size() - k; // kth large = len+1-k small
while (mid != k)
{
if (mid < k)
mid = Partition(nums, mid + 1, nums.size());
else
mid = Partition(nums, 0, mid);
}
return nums[mid];
}
size_t Partition(vector<int>& arr, size_t beg, size_t end)
{
size_t pivot = beg;
size_t i = pivot + 1;
for (auto j = pivot + 1; j < end; ++j)
{
if (arr[j] < arr[pivot])
{
std::swap(arr[j], arr[i]);
++i;
}
}
std::swap(arr[i-1], arr[pivot]);
return i - 1;
}
};
int main()
{
vector<int> nums = {3,2,1,5,6,4};
Solution so;
cout << so.findKthLargest(nums, 2);
return 0;
}最大连续子列
From: LeetCode53.
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
设置两个变量，一个记录当前连加的值，另一个记录目前位置最大连续子序列，迭代更新。
int MaxSubArray(const vector<int>& arr)
{
int max_so_far = INT_MIN;
int sum = 0;
for (int e : arr)
{
if (sum > 0)
sum += e;
else
sum = e;
max_so_far = max(max_so_far, sum);
}
return max_so_far;
}