题目一：请编写一个函数func，输入一个正整数n，返回一个最小的正整数m(m>9,即m至少包含两位数)，使得m的各位乘积等于n，例如输入36，输出49；输入100，输出455，如果对于某个n不存在着这样的m，请输出-1.语言不限，但不要用伪代码作答，函数输入输出请参考如下函数原型。int func(int n);
分析：
采用递归思想解决。func(n) = k * func(n/k); (k <10)
class Solution{public:int func( int n ){vector<int> result;separationNum( n, 0, result );sort( result.begin(), result.end() );return result[0];}void separationNum( int n, int p, vector<int>& result ){if ( n < 10 )result.push_back( p*10+n );for ( int i = 2; i <= 9; i++ ) {if ( n%i == 0 ){separationNum( n/i, p*10+i, result );}}}};int main( void ){Solution sos;int result = sos.func( 36 );cout << result << endl;return 0;}
题目二：非递归方式实现二叉树的先序遍历，并将每个节点的值保存在数组中，语言不限，但不要用伪代码作答，函数输出请参考如下函数原型。struct TreeNode{int value;TreeNode* left;TreeNode* right;};void TraverseTreeInPreOrder(std::vector<int>& values, const TreeNode* root);
分析：
使用辅助栈实现二叉树的非递归遍历。
class Solution{public:void TraverseTreeInPreOrder( std::vector<int>& values, const TreeNode* root ){if ( root == NULL ) return ;stack<TreeNode*>* traverseStack = new stack<TreeNode*>();TreeNode* pRoot = const_cast<TreeNode*>(root);TreeNode *prePop = (TreeNode*)-100;traverseStack->push( pRoot );values.push_back( pRoot->value );while ( !traverseStack->empty() ){if ( traverseStack->top()->left != NULL && prePop != traverseStack->top()->left&& prePop != traverseStack->top()->right ){traverseStack->push( traverseStack->top()->left );values.push_back( traverseStack->top()->value );}else if ( traverseStack->top()->right != NULL && prePop != traverseStack->top()->right ){traverseStack->push( traverseStack->top()->right );values.push_back( traverseStack->top()->value );}else{prePop = traverseStack->top();traverseStack->pop();}}}};
题目三：请编写程序计算第K个能表示为2^i * 3^j * 5^k的正整数（其中i，j，k为整数）。例如前5个满足这个条件的数分别时：1,2，3,4,5,6,8,9,10,12,15.语言不限，函数输入输出参考：int KthNumber(int k);
分析：
根据描述就是输出丑数。关于丑数的概念可以参考《剑指offer》面试题34.
class Solution{public:int KthNumber( int k ){vector<int> uglyNum;uglyNum.push_back(1);int p2 = 0, p3 = 0, p5 = 0;for ( int i = 1; i < k; i++ ){while ( uglyNum[p2]*2 <= uglyNum.back() )p2++;while ( uglyNum[p3]*3 <= uglyNum.back() )p3++;while ( uglyNum[p5]*5 <= uglyNum.back() )p5++;int tip = min( uglyNum[p2]*2, uglyNum[p3]*3, uglyNum[p5]*5 );uglyNum.push_back( tip );}return uglyNum.back();}int min( int a, int b, int c ){int d = a < b ? a : b;int e = d < c ? d : c;return e;}};int main( void ){Solution sos;cout << sos.KthNumber( 11 ) << endl;return 0;}
