去哪儿

admin 管理员组

文章数量: 887021

去哪儿

去哪儿三道大题，说难都不难，但是如果不熟可能也写不好

1 一个数组里有数字 1,22， 13 ，43.....如何排列组成一个数是最小数，比方说1132243，就是四个数组成的最小数。

当时我的思路就是如何定义比较两个数大小，肯定是先比最高位，小的排在前面，如果相等在比下一位，如果一直相等，有一个短，那么短的在前面，之前先把两个数放到数组中，方便处理。

然后再用一种排序方法调用这个比较方法两两比较。

下面代码是剑指offer中的，思路类似，只是比较方法更巧妙，如果两个数为m，n，那么也就是比较mn和nm大小，就是把两个数连接起来，当然也是存在数组中，小的在前面。

int compare(const void* strNumber1, const void* strNumber2);// int型整数用十进制表示最多只有10位
const int g_MaxNumberLength = 10;char* g_StrCombine1 = new char[g_MaxNumberLength * 2 + 1];
char* g_StrCombine2 = new char[g_MaxNumberLength * 2 + 1];void PrintMinNumber(int* numbers, int length)
{if(numbers == NULL || length <= 0)return;char** strNumbers = (char**)(new int[length]);for(int i = 0; i < length; ++i){strNumbers[i] = new char[g_MaxNumberLength + 1];sprintf(strNumbers[i], "%d", numbers[i]);}qsort(strNumbers, length, sizeof(char*), compare);for(int i = 0; i < length; ++i)printf("%s", strNumbers[i]);printf("\n");for(int i = 0; i < length; ++i)delete[] strNumbers[i];delete[] strNumbers;
}// 如果[strNumber1][strNumber2] > [strNumber2][strNumber1], 返回值大于0
// 如果[strNumber1][strNumber2] = [strNumber2][strNumber1], 返回值等于0
// 如果[strNumber1][strNumber2] < [strNumber2][strNumber1], 返回值小于0
int compare(const void* strNumber1, const void* strNumber2)
{// [strNumber1][strNumber2]strcpy(g_StrCombine1, *(const char**)strNumber1);strcat(g_StrCombine1, *(const char**)strNumber2);// [strNumber2][strNumber1]strcpy(g_StrCombine2, *(const char**)strNumber2);strcat(g_StrCombine2, *(const char**)strNumber1);return strcmp(g_StrCombine1, g_StrCombine2);
}

  2 写一个stl中的stack

以前看过记不太清了

主要应该包括的方法

空构造函数，拷贝构造函数

push，pop，top

emtpy，size等

关系运算符，以及返回常引用等可以略去，基本功能一定要实现

成员变量下面代码就是一个容器，有些地方，用一个指针表示基地址，也就是头指针，top表示尾指针，还有当前大小，容量等等。相对来说下面代码用现成容器存储简化了很多操作，比较可取。

#pragma once
#ifndef _STACK_
#define _STACK_
#ifndef RC_INVOKED
#include <deque>#ifdef _MSC_VER#pragma pack(push,_CRT_PACKING)#pragma warning(push,3)
#endif  /* _MSC_VER */
_STD_BEGIN// TEMPLATE CLASS stack
template<class _Ty,class _Container = deque<_Ty> >class stack{    // LIFO queue implemented with a container
public:typedef _Container container_type;typedef typename _Container::value_type value_type;typedef typename _Container::size_type size_type;typedef typename _Container::reference reference;typedef typename _Container::const_reference const_reference;stack(): c(){    // construct with empty container}explicit stack(const _Container& _Cont): c(_Cont){    // construct by copying specified container}bool empty() const{    // test if stack is emptyreturn (c.empty());}size_type size() const{    // test length of stackreturn (c.size());}reference top(){    // return last element of mutable stackreturn (c.back());}const_reference top() const{    // return last element of nonmutable stackreturn (c.back());}void push(const value_type& _Val){    // insert element at endc.push_back(_Val);}void pop(){    // erase last elementc.pop_back();}const _Container& _Get_container() const{    // get reference to containerreturn (c);}protected:_Container c;    // the underlying container};// stack TEMPLATE FUNCTIONS
template<class _Ty,class _Container> inlinebool operator==(const stack<_Ty, _Container>& _Left,const stack<_Ty, _Container>& _Right){    // test for stack equalityreturn (_Left._Get_container() == _Right._Get_container());}template<class _Ty,class _Container> inlinebool operator!=(const stack<_Ty, _Container>& _Left,const stack<_Ty, _Container>& _Right){    // test for stack inequalityreturn (!(_Left == _Right));}template<class _Ty,class _Container> inlinebool operator<(const stack<_Ty, _Container>& _Left,const stack<_Ty, _Container>& _Right){    // test if _Left < _Right for stacksreturn (_Left._Get_container() < _Right._Get_container());}template<class _Ty,class _Container> inlinebool operator>(const stack<_Ty, _Container>& _Left,const stack<_Ty, _Container>& _Right){    // test if _Left > _Right for stacksreturn (_Right < _Left);}template<class _Ty,class _Container> inlinebool operator<=(const stack<_Ty, _Container>& _Left,const stack<_Ty, _Container>& _Right){    // test if _Left <= _Right for stacksreturn (!(_Right < _Left));}template<class _Ty,class _Container> inlinebool operator>=(const stack<_Ty, _Container>& _Left,const stack<_Ty, _Container>& _Right){    // test if _Left >= _Right for stacksreturn (!(_Left < _Right));}
_STD_END#ifdef _MSC_VER#pragma warning(pop)#pragma pack(pop)
#endif  /* _MSC_VER */#endif /* RC_INVOKED */
#endif /* _STACK_ */

3 利用上面的stack，写一个算术表达式求值

首先定义一个运算符优先级表，方便查找两个运算符的优先级大小关系

定义两个栈，一个存储操作数，一个存储运算符

算法思想：
1。初始化，操作数栈置空；操作符栈压入'#'。
2。从左往右读取算术表达式（从第二个字符开始），当读到'#'且操作符栈栈顶也是'#'时则算法结束。
3。如果读到的是操作数则压入操作数栈中，转到步骤2。
4。如果读到是操作符，则比较其与操作符栈栈顶操作符的优先级。
5。如果栈顶操作符的优先级高，则栈顶操作符出栈，并从操作数栈中弹出两个操作数进行相应的运算，再把运

算结果压入操作数栈中，转至步骤4。
6。如果栈顶操作符的优先级低，则把当前操作符压入操作符栈，转至步骤2。
7。如果栈顶操作符与当前操作符优先级相同，则只可能是'('跟')'，把操作符从栈中弹出即可，转至步骤2。

详细算法

和严老师数据结构教程的差不多。

本文标签： 去哪儿