19 1 Write a function to swap a number in place without temporary variables
void swap(int &a, int &b)
{
b = a - b; // 4 = 9 - 5
a = a - b; // 5 = 9 - 4
b = a + b; // 9 = 4 + 5
}
void swap(int & a, int &b)
{
a = a^b;
b = a^b;
a = a^b;
}
19.3 Write an algorithm which computes the number of trailing zeros in n factorial
详细分析见编程之美
int numZeros(int num)
{
int res = ;
while(num > ){
res+= num /;
num/=;
} return res;
}
19.4 Write a method which fnds the maximum of two numbers You should not use if-else or any other comparison operator
EXAMPLE
Input: 5, 10
Output: 10
int getMax(int a, int b)
{
int c = a - b;
int k = (c>>) & 0x1;
return a - k * c;
}
19.5 The Game of Master Mind is played as follows:
The computer has four slots containing balls that are red (R), yellow (Y), green (G) or
blue (B) For example, the computer might have RGGB (e g , Slot #1 is red, Slots #2 and
#3 are green, Slot #4 is blue)
You, the user, are trying to guess the solution You might, for example, guess YRGB
When you guess the correct color for the correct slot, you get a “hit” If you guess
a color that exists but is in the wrong slot, you get a “pseudo-hit” For example, the
guess YRGB has 2 hits and one pseudo hit
For each guess, you are told the number of hits and pseudo-hits
Write a method that, given a guess and a solution, returns the number of hits and
pseudo hits
用hash存储计算机存储的个个slot值。
void estimate(String guess, String solution, int &hit, int &pesohit)
{
hit = ;
pesohit = ;
int hash = ;
for(int i = ; i< ; ++i)
hash |= <<(solution[i] - 'A'); for(int i = ; i< ;; ++i)
{
if(solution[i] == guess[i])
++hit;
else if( (<<(guess[i]-'A')) & hash >= )
++pesohit;
}
}
19.6 Given an integer between 0 and 999,999, print an English phrase that describes the integer (eg, “One Thousand, Two Hundred and Thirty Four”)
代码略长，感觉面试不会出
19.7 You are given an array of integers (both positive and negative) Find the continuous sequence with the largest sum Return the sum
EXAMPLE
Input: {2, -8, 3, -2, 4, -10}
Output: 5 (i e , {3, -2, 4} )
http://www.cnblogs.com/graph/archive/2013/05/23/3095831.html
19 8 Design a method to fnd the frequency of occurrences of any given word in a book
分清查询一次和多次的区别
19.9
19 10 Write a method to generate a random number between 1 and 7, given a method
that generates a random number between 1 and 5 (i e , implement rand7() using
rand5())
int rand7()
{
while(true)
{
int res = rand5() - + * (rand5() - );
if(res < )
{
return res% + ;
}
}
}
19.11 Design an algorithm to find all pairs of integers within an array which sum to a speci-
fed value
void printPairSums(vector<int> array, int sum)
{
sort(array.begin(), array,end());
int first = 0;
int last = array.size()-1;
while(firat <= last)
{
int temp = array[first] + array[last];
if(temp == sum){
cout<<array[first]<<" "<<array[last]<<endl;
}else if(temp < sum){
++first;
}else{
--last;
}
}
}
