Q1 设计个用bit形式表示时间（小时：分钟）的clock，
e.g 10:15 可以写作1010:1111，每个bit是一个小灯泡，when the digit ==1, 灯泡亮，打印所有有且仅有n盏灯亮着的时间 in (24 hours a day)， e.g. n＝0 就只有0:0一种可能。
暴力解： 遍历所有可能，并且对于代码的结构是有优化的，对于重复利用的函数需要放到外面作为一个函数来调用，这样程序的构造性会比较好。
int CountOne(int num) {
int num = 0;
while (num) {
if (num & 1) num++;
num = num >> 1;
}
return num;
}
vector<string> getTime(int n) {
//minites
int buf[60];
vector<string> rst;
for (int i = 0; i < 24; i++) {
int total = 0;
//count the num of 1s
int num = CountOne(i);
buf[i] = num;
if (num > n) continue;
for (int j = 0; j < 60; j++) {
int num1 = j;
if (buf[j] == 0 ) {
buf[j] = CountOne(num1);
}
if (buf[j] > n) continue;
total = num + buf[j];
if (total == n) {
rst.push_back(i + ‘:’+j);
}
}
}
return rst;
}
Q2. Card shuffler：shuffle的程序是一个简单的array，array里的值代表当前位置卡
片的下一个位置 e.g 当前卡片位置ABCDE shuffle array是01234的话下个卡片位置还是ABCDE，43210的 话下个卡片位置是EDCBA。
问给定一个shuffle array，不断用这个array去shuffle，能否得到最初的card deck，
能得话要多少次。
step1: check no missing number in the position array
step2: for each element, get the num of steps in order to get the original position
step3: calculate the LCM of all these steps.
int gcd(int a, int b) {
int c = 0;
while (a != 0) {
c = a;
a = b%a;
b = c;
}
return b;
}
int lcm(int a, int b) {
return a * b / gcd(a, b);
}
int CardShuffler(vector<int> &input, string &card) {
//check no missing number in input
int sizec = card.size();
int M[sizec] = {0};
int flag = true;
for (int i = 0; i < input.size(); i++) {
if (M[i] == 0) M[i] = 1;
else flag = false;
}
if (flag == false) return -1;
//for each element, get the num of steps to get the original ones
for (int i = 0; i < sizec; i++) {
int step = 0;
int num = input[i];
while (num != i) {
step++;
num = input[num];
}
M[i] = step+1;
}
//calculate the LCM of M[i]
//1. calculate the lcm
int lcm1 = M[0];
for (int i = 1; i < sizec; i++) {
lcm1 = lcm(lcm1, M[i]);
}
return lcm1;
}
Q3:
Given a string that contains two types of chars ‘+’ or ‘-’ only, Player A and Player B takes turns to set ‘++’ to ‘--’, Each round, can only set one ‘++’ to ‘--’, when a player find no ‘++’ remained in the string, then he loss the game. Write a function CanWin(string S) to check if A can win the game when A first starts.
模拟双人游戏， dfs 遍历所有的可能，A 可能会赢只在一种情况下成立，那就是B可能会输的情况下，只要发现一种情况下B会输，那么A就可能会赢，返回true。
DFS的题目，不管什么类型的题，只要能够画出DFS recursion tree，那么代码就很容易写出来了，记得DFS tree返回上一个状态的时候状态要还原。
++++
/ | \
A: --++ +--+ ++--
/ | \
B: ---- A win ----
bool CanWin(string s) {
int player = 1; //player a
bool flag = false;
helper(s, 1, flag);
return flag;
}
void helper(string s, int player, bool &flag) {
//base case
vector<int> buf;
for (int i = 0; i < s.size()-1; i++) {
if (s[i] == '+' && s[i+1] == '+') {
buf.push_back(i);
}
}
//B can’t find ++, A win
if (buf.size() == 0 && player == -1) {
flag = true;
return;
}
for (int j = 0; j < buf.size(); j++) {
int id = buf[j];
s[id] = '-';
s[id+1] = '-';
helper(s, player*(-1),flag);
s[id] = '+';
s[id+1] = '+';
}
return;
}
Q4 Given an array of integers. Find two disjoint contiguous subarrays in it such that the absolute value of the difference between the sums of two subarray is maximum. Return the maximum difference. For example:
Array: { 1, -3, 1, -4, 3, 4 }
Result subarrays: {-3, 1, -4 }, { 3, 4 }
Maximum difference = 13
对于这种contiguous subarray的问题（eg: sum）, 常见的思路有： 1. maximum/minimal subarray sum 2. sliding window + hash_table. 这个题目就是用的1， 分析题目问题， 求两个不想交的subarray的差值最大， |SumA - SumB|最大，那么可以使得SumA 最大， SumB最小，或者SumA最小， SumB最大， 并且A，B的边界是不相交的，对于第一种情况可以想到可以从 0-i 求maximum subarray sum， 从 n-i求minimal subarray sum ， 最后找相差最大的就是解，同理对于第二种情况，0-i minimal subarray sum， n-i求maximal subarray sum。
int MaxDiff(vector<int> &input) {
//sanity check
if (input.size() == 0) return 0;
int global = INT_MIN;
int M1[input.size()];
int M2[input.size()];
int N1[input.size()];
int N2[input.size()];
//fill out M1;
//base case
M1[0] = input[0];
N1[0] = input[0];
for (int i = 1; i < input.size(); i++) {
M1[i] = max(input[i], input[i] + M1[i-1];
N1[i] = min(input[i], input[i] + N1[i-1];
}
//fill out M2
//base cae
M2[input.size()-1] = input[input.size()-1];
N2[input.size()-1] = input[input.size()-1];
for (int i = input.size()-2; i >= 0; i--) {
M2[i] = max(input[i], input[i] + M2[i+1]);
N2[i] = min(input[i], input[i]+N2[i+1]);
}
//get global_max
for (int i = 1; i < input.size(); i++) {
global = max(global, M1[i] - N2[i-1]);
global = max(global, M2[i] - N1[i-1]);
}
return global;
}
Q6:
把一个数拆分成任意个平方和的最小拆分：
eg: 4 = 1+1+1+1, or ２＾２
如果要求这些可能平方和拆分中的最小拆分， dp,
M[i] 表示i拆分成任意个平方和的最小拆分个数
induction rule: M[i] = min(M[i-j]) + 1 , for each j, j*j <= i, 从所有1-i的平方和算起。
//use dp
//return
int findSquare(int num) {
int M[num+1];
//base case
M[0] = 0;
M[1] = 1;
for (int i = 2; i <= num; i++) {
int min_num = num;
for (int j = 1; j * j <= i; j++) {
min_num = min(min_num, M[i - j*j]);
}
M[i] = 1 + min_num;
}
return M[num];
}
No comments:
Post a Comment