[技术| 编程·课件·Linux] 100道经典算法题（51-75)

sissi · 发布于 2012-10-19 12:07 · 1373 次阅读
163

51.和为n连续正数序列。
题目：输入一个正数n，输出所有和为n连续正数序列。

例如输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以输出3个连续序列1-5、4-6和7-8。
分析：这是网易的一道面试题。

52.二元树的深度。
题目：输入一棵二元树的根结点，求该树的深度。
从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
例如：输入二元树：
                                            10
                                          /     \
                                        6        14
                                      /         /   \
                                    4         12     16
输出该树的深度3。
二元树的结点定义如下：
struct SBinaryTreeNode // a node of the binary tree
{
      int               m_nValue; // value of node
      SBinaryTreeNode  *m_pLeft;  // left child of node
      SBinaryTreeNode  *m_pRight; // right child of node
};
分析：这道题本质上还是考查二元树的遍历。

53.字符串的排列。
题目：输入一个字符串，打印出该字符串中字符的所有排列。
例如输入字符串abc，则输出由字符a、b、c所能排列出来的所有字符串
abc、acb、bac、bca、cab和cba。
分析：这是一道很好的考查对递归理解的编程题，
因此在过去一年中频繁出现在各大公司的面试、笔试题中。

全排列树

54.调整数组顺序使奇数位于偶数前面。
题目：输入一个整数数组，调整数组中数字的顺序，使得所有奇数位于数组的前半部分，
所有偶数位于数组的后半部分。要求时间复杂度为O(n)。

55.
题目：类CMyString的声明如下：
class CMyString
{
public:
      CMyString(char* pData = NULL);
      CMyString(const CMyString& str);
      ~CMyString(void);
      CMyString& operator = (const CMyString& str);
private:
      char* m_pData;
};
请实现其赋值运算符的重载函数，要求异常安全，即当对一个对象进行赋值时发生异常，对象的状态不能改变

考虑new异常。分配内存空间时，内存空间不够时就会抛出该异常。


对该异常进行处理，利用try-catch模块函数，将内存分配语句放在try中，这样出现了异常就会立刻获得，从而转入匹配的catch块进行处理。catch的参数是异常类型，这里为std::bad_alloc。

56.最长公共字串。
题目：如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中，
则字符串一称之为字符串二的子串。
注意，并不要求子串（字符串一）的字符必须连续出现在字符串二中。
请编写一个函数，输入两个字符串，求它们的最长公共子串，并打印出最长公共子串。
例如：输入两个字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它们的最长公共子串，
则输出它们的长度4，并打印任意一个子串。
分析：求最长公共子串（Longest Common Subsequence, LCS）是一道非常经典的动态规划题，
因此一些重视算法的公司像MicroStrategy都把它当作面试题。


我们可以把该问题定义如下：
给出两个字符串S和T，S的长度为m，T的长度为n，找出S与T的最长公共子串。
假设S = “ABAB”，T=“BABA”，我们可以构造一个如下的矩阵：
ABAB
00000
B00101
A01020
B00203
A01030
对于数组array[m][n]，扩展为array[m+1][n+1]，这样是为了方便初始化，减少循环中对边界的判断。
  • if( S == T[j] ) array[i+1][j+1] = array[j] + 1
  • if( S != T[j] ) array[i+1][j+1] = 0
以下给出源码：
[url=]file:///C:/Users/ADMINI~1/AppData/Local/Temp/enhtmlclip/Image.gif[/url]
1 #include <string.h> 2 #include <stdlib.h> 3 #include <stdio.h> 4 5 const char * LongestCommonSubstring(const char * strA, const char * strB) 6 { 7     char * LCS = NULL; 8     const size_t LengthA = strlen(strA); 9     const size_t LengthB = strlen(strB);10     size_t LCSLength = 0;11     unsigned int PositionX = 0;12     unsigned int PositionY = 0;13     14     int i, j;15     int Matrix[LengthA + 1][LengthB + 1];;16     17     for(i = 0; i < LengthA ; ++i)18     {19         for(j = 0; j < LengthB ; ++j)20         {21             Matrix[j] = 0;22         }23     }    24     25     for(i = 0; i < LengthA; ++i)26     {27         for(j = 0; j < LengthB; ++j)28         {29             if(strA == strB[j])30             {31                 if((i == 0)||(j == 0))32                     Matrix[j] = 1;33                 else                34                     Matrix[j] = Matrix[i - 1][j - 1] + 1;35             }36             if(Matrix[j] > LCSLength)37             {38                 LCSLength = Matrix[j];39                 PositionX = i;40                 PositionY = j;41             }42         }43     }        44     45     46     LCS = (char *)malloc(LCSLength + 1);47     int index = LCSLength - 1;48     while(index >= 0)49     {50         LCS[index] = strA[PositionX];51         --index;52         --PositionX;53     }54     LCS[LCSLength] = '\0';    55     56     return LCS;57 }58 int main(int argc, char **argv) 59 {60     const char * strA = "abab";61     const char * strB = "baba";62     const char * LCS = LongestCommonSubstring(strA, strB);63     printf("Longest Common Substring is %s\n", LCS);64     return 0;65 }题目：某队列的声明如下：template<typename T> class CQueue
{
public:
      CQueue() {}
      ~CQueue() {}      void appendTail(const T& node);  // append a element to tail
      void deleteHead();               // remove a element from headprivate:
     T> m_stack1;
     T> m_stack2;
};分析：从上面的类的声明中，我们发现在队列中有两个栈。
因此这道题实质上是要求我们用两个栈来实现一个队列。
相信大家对栈和队列的基本性质都非常了解了：栈是一种后入先出的数据容器，
因此对队列进行的插入和删除操作都是在栈顶上进行；队列是一种先入先出的数据容器，
我们总是把新元素插入到队列的尾部，而从队列的头部删除元素。

58.从尾到头输出链表。
题目：输入一个链表的头结点，从尾到头反过来输出每个结点的值。链表结点定义如下：
struct ListNode
{
      int       m_nKey;
      ListNode* m_pNext;
};
分析：这是一道很有意思的面试题。
该题以及它的变体经常出现在各大公司的面试、笔试题中。
解答：
方法一、先把链表反向，然后再从头到尾遍历一遍。
方法二、设一个栈，从头到尾遍历一次，把结点值压力栈中，再出栈打印。
方法三、递归。

59.不能被继承的类。
题目：用C++设计一个不能被继承的类。
分析：这是Adobe公司2007年校园招聘的最新笔试题。
这道题除了考察应聘者的C++基本功底外，还能考察反应能力，是一道很好的题目。
解答：把构造函数写成私有。

60.在O（1）时间内删除链表结点。
题目：给定链表的头指针和一个结点指针，在O(1)时间删除该结点。链表结点的定义如下：
struct ListNode
{
      int        m_nKey;
      ListNode*  m_pNext;
};
函数的声明如下：
void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted);
分析：这是一道广为流传的Google面试题，能有效考察我们的编程基本功，还能考察我们的反应速度，
更重要的是，还能考察我们对时间复杂度的理解。
解答：
在链表中删除一个结点，最常规的做法是从链表的头结点开始，顺序查找要删除的结点，找到之后再删除。由于需要顺序查找，时间复杂度自然就是O(n) 了。
我们之所以需要从头结点开始查找要删除的结点，是因为我们需要得到要删除的结点的前面一个结点。我们试着换一种思路。我们可以从给定的结点得到它的下一个结点。这个时候我们实际删除的是它的下一个结点，由于我们已经得到实际删除的结点的前面一个结点，因此完全是可以实现的。当然，在删除之前，我们需要需要把给定的结点的下一个结点的数据拷贝到给定的结点中。此时，时间复杂度为O(1)。
上面的思路还有一个问题：如果删除的结点位于链表的尾部，没有下一个结点，怎么办？我们仍然从链表的头结点开始，顺便遍历得到给定结点的前序结点，并完成删除操作。这个时候时间复杂度是O(n)。那题目要求我们需要在O(1)时间完成删除操作，我们的算法是不是不符合要求？实际上，假设链表总共有n个结点，我们的算法在n-1总情况下时间复杂度是O(1)，只有当给定的结点处于链表末尾的时候，时间复杂度为O(n)。那么平均时间复杂度[(n-1)*O(1)+O(n)]/n，仍然为O(1)。

#include <iostream>
using namespace std;

typedef struct LNode{
     int data;
     LNode *next;
}LNode, *List;

void InsertList(List &l, int data)//头插入节点
{
     List head;
     LNode *p=new LNode;
     p->data=data;
     if(NULL==l)
          p->next=NULL;
     else
          p->next=l;
     l=p;
}

void PrintList(List l)//打印链表
{
     LNode *p=l;
     while(p)
     {
          cout<<p->data<<" ";
          p=p->next;
     }
     cout<<endl;
}

void DeleteNode(List &l, LNode *toBeDeleted)//删除链表l中的toBeDeleted节点
{
     LNode *p;
     if(!l || !toBeDeleted)
          return;

     if(l==toBeDeleted)//若删除的节点时表头
     {
          p=l->next;
          delete toBeDeleted ;
          l=p;         
     }
     else
     {
          if(toBeDeleted->next==NULL)//若删除的节点时最后一个节点
          {
               p=l;
               while(p->next!=toBeDeleted)
                    p=p->next;
               p->next=NULL;
               delete toBeDeleted;
          }
          else//删除节点时中间节点
          {
               p=toBeDeleted->next;
               toBeDeleted->data=p->data;
               toBeDeleted->next=p->next;
               delete p;

          }

     }

}

void main()
{
     List l=NULL;
     LNode *p;
     int n;
     InsertList(l, 3);
     InsertList(l, 7);
     InsertList(l, 12);
     InsertList(l, 56);
     InsertList(l, 33);
     InsertList(l, 78);
     InsertList(l, 20);
     InsertList(l, 89);

     PrintList(l);
     cout<<"请输入要删除的节点：";
     cin>>n;

     p=l;
     while(p->data!=n && p)
          p=p->next;

     if(!p)
     {
          cout<<"不存在这样的节点！"<<endl;
          return;
     }
     else
          DeleteNode(l, p);

     cout<<"删除后的链表：";
     PrintList(l);



   

}

61.找出数组中两个只出现一次的数字
题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。
请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
分析：这是一道很新颖的关于位运算的面试题。
解答：
  可能大家都见识过找出一个只出现一次的数，直接把所有的数异或就可以了，最终的结果就是这个数了。但是如果出现两个这样的数，那又将如何呢？
　　假如这两个数为a和b，那么将所有的数异或得到的数必定为a^b。由于a和b不相等，那么a^b != 0，也就是说在a^b中必定至少有一位为1，对应位上a与b不一样，根据这一位，我们可以将a和b分开，并将数分成两组。注意，两个相同的数肯定会被分到同一个组。这样，分别对每一组进行取异或，就能求出这两个数了。


#include<iostream>
using namespace std;
int findFirstOne(int value);
bool testBit(int value,int pos);
int findNums(int date[],int length,int &num1,int &num2){
    if(length<2){return -1;}
    int ansXor=0;
    for(int i=0;i<length;i++){
        ansXor^=date;               //异或
    }
    int pos=findFirstOne(ansXor);
    num1=num2=0;
    for(int i=0;i<length;i++){
        if(testBit(date,pos))
            num1^=date;
        else
            num2^=date;
    }
    return 0;
}
int findFirstOne(int value){     //取二进制中首个为1的位置
    int pos=1;
    while((value&1)!=1){
        value=value>>1;
        pos++;
    }
    return pos;
}
bool testBit(int value,int pos){  //测试某位置是否为1
    return ((value>>pos)&1);
}
int main(void){
    int date[10]={1,2,3,4,5,6,4,3,2,1};
    int ans1,ans2;
    if(findNums(date,10,ans1,ans2)==0)
        cout<<ans1<<" "<<ans2<<endl;
    else
        cout<<"error"<<endl;
    return 0;
}



62.找出链表的第一个公共结点。
题目：两个单向链表，找出它们的第一个公共结点。
链表的结点定义为：
struct ListNode
{
      int         m_nKey;
      ListNode*   m_pNext;
};
分析：这是一道微软的面试题。微软非常喜欢与链表相关的题目，
因此在微软的面试题中，链表出现的概率相当高。

解答：
如果两个单向链表有公共的结点，也就是说两个链表从某一结点开始，它们的 m_pNext 都指向同一个结点。但由于是单向链表的结点，每个结点只有一个 m_pNext ，因此从第一个公共结点开始，之后它们所有结点都是重合的，不可能再出现分叉。所以，两个有公共结点而部分重合的链表，拓扑形状看起来像一个 Y ，而不可能像 X 。
看到这个题目，第一反应就是蛮力法：在第一链表上顺序遍历每个结点。每遍历一个结点的时候，在第二个链表上顺序遍历每个结点。如果此时两个链表上的结点是一样的，说明此时两个链表重合，于是找到了它们的公共结点。如果第一个链表的长度为 m ，第二个链表的长度为 n ，显然，该方法的时间复杂度为 O(mn) 。
接 下来我们试着去寻找一个线性时间复杂度的算法。我们先把问题简化：如何判断两个单向链表有没有公共结点？前面已经提到，如果两个链表有一个公共结点，那么 该公共结点之后的所有结点都是重合的。那么，它们的最后一个结点必然是重合的。因此，我们判断两个链表是不是有重合的部分，只要分别遍历两个链表到最后一 个结点。如果两个尾结点是一样的，说明它们用重合；否则两个链表没有公共的结点。
在上面的思路中，顺序遍历两个链表到尾结点的时候，我们不能保证在两个链表上同时到达尾结点。这是因为两个链表不一定长度一样。但如果假设一个链表比另一个长 l 个结点，我们先在长的链表上遍历 l 个结点，之后再同步遍历，这个时候我们就能保证同时到达最后一个结点了。由于两个链表从第一个公共结点考试到链表的尾结点，这一部分是重合的。因此，它们肯定也是同时到达第一公共结点的。于是在遍历中，第一个相同的结点就是第一个公共的结点。
在这个思路中，我们先要分别遍历两个链表得到它们的长度，并求出两个长度之差。在长的链表上先遍历若干次之后，再同步遍历两个链表，知道找到相同的结点，或者一直到链表结束。此时，如果第一个链表的长度为 m ，第二个链表的长度为 n ，该方法的时间复杂度为 O(m+n) 。
基于这个思路，我们不难写出如下的代码：
///////////////////////////////////////////////////////////////////////
// Find the first common node in the list with head pHead1 and
// the list with head pHead2
// Input: pHead1 - the head of the first list
//        pHead2 - the head of the second list
// Return: the first common node in two list. If there is no common
//         nodes, return NULL
///////////////////////////////////////////////////////////////////////
ListNode * FindFirstCommonNode ( ListNode *pHead1 , ListNode *pHead2 )
{
      // Get the length of two lists
      unsigned int nLength1 = ListLength (pHead1 );
      unsigned int nLength2 = ListLength (pHead2 );
      int nLengthDif = nLength1 - nLength2 ;
      // Get the longer list
      ListNode *pListHeadLong = pHead1 ;
      ListNode *pListHeadShort = pHead2 ;
      if (nLength2 > nLength1 )
      {
            pListHeadLong = pHead2 ;
            pListHeadShort = pHead1 ;
            nLengthDif = nLength2 - nLength1 ;
      }
      // Move on the longer list
      for (int i = 0; i < nLengthDif ; ++ i )
            pListHeadLong = pListHeadLong ->m_pNext ;
      // Move on both lists
      while ((pListHeadLong != NULL ) &&
            (pListHeadShort != NULL ) &&
            (pListHeadLong != pListHeadShort ))
      {
            pListHeadLong = pListHeadLong ->m_pNext ;
            pListHeadShort = pListHeadShort ->m_pNext ;
      }
      // Get the first common node in two lists
      ListNode *pFisrtCommonNode = NULL ;
      if (pListHeadLong == pListHeadShort )
            pFisrtCommonNode = pListHeadLong ;
      return pFisrtCommonNode ;
}
///////////////////////////////////////////////////////////////////////
// Get the length of list with head pHead
// Input: pHead - the head of list
// Return: the length of list
///////////////////////////////////////////////////////////////////////
unsigned int ListLength (ListNode * pHead )
{
      unsigned int nLength = 0;
      ListNode * pNode = pHead ;
      while (pNode != NULL )
      {
            ++ nLength ;
            pNode = pNode ->m_pNext ;
      }
      return nLength ;
}


63.在字符串中删除特定的字符。
题目：输入两个字符串，从第一字符串中删除第二个字符串中所有的字符。
例如，输入”They are students.”和”aeiou”，
则删除之后的第一个字符串变成”Thy r stdnts.”。
分析：这是一道微软面试题。在微软的常见面试题中，与字符串相关的题目占了很大的一部分，
因为写程序操作字符串能很好的反映我们的编程基本功。
#include <stdio.h>
#include <memory.h>
/***********************************************************************************

输入两个字符串，从第一字符串中删除第二个字符串中所有的字符。
例如，输入”They are students.”和”aeiou”，则删除之后的第一个字符串变成”Thy r stdnts.”。
***********************************************************************************/
int delchar(char *src, char *dst);
int main()
{
    char src[] = "They are students.";
    char del[] = "aeiou";
    delchar(src, del);
    printf("Output : %s\n",src);
    return 0;
}

int delchar(char *src, char *dst)
{
    char *begin = src;
    char *end   = src;
    char hashtable[256];
    int i = 0;
    memset(hashtable,0,sizeof(hashtable));
    while(*dst)
        ++hashtable[*dst++];
    while(*end)
    {
        if(!hashtable[*end])//del character not detected
        {
            *begin = *end ;
            ++begin;
        }
        ++end;

    }
   
    *begin= '\0';
}

64. 寻找丑数。
题目：我们把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，
但14不是，因为它包含因子7。习惯上我们把1当做是第一个丑数。
求按从小到大的顺序的第1500个丑数。
分析：这是一道在网络上广为流传的面试题，据说google曾经采用过这道题。
分析：假设数组ugly[N]中存放不断产生的丑数，初始只有一个丑数ugly[0]=1，由此出发，下一个丑数由因子2,3,5竞争产生，得到ugly[0]*2, ugly[0]*3, ugly[0]*5， 显然最小的那个数是新的丑数，所以第2个丑数为ugly[1]=2，开始新一轮的竞争，由于上一轮竞争中，因子2获胜，这时因子2应该乘以ugly[1]才显得公平，得到ugly[1]*2,ugly[0]*3,ugly[0]*5， 因子3获胜，ugly[2]=3，同理，下次竞争时因子3应该乘以ugly[1]，即：ugly[1]*2, ugly[1]*3, ugly[0]*5, 因子5获胜，得到ugly[3]=5，重复这个过程，直到第n个丑数产生。总之：每次竞争中有一个（也可能是两个）因子胜出，下一次竞争中 胜出的因子就应该加大惩罚！

程序如下所示（只要把程序中的因子改一下就可以得到新的题目），耗时忽略不计：
运行结果：第1500个丑数：859963392， 第1691个丑数2 125 764 000，第1692个丑数就越界了。
int表示的最大整数是2,147,483,647，可由std::cout<<(std::numeric_limits<int>::max)()<<"\n";给出！
#include <iostream>   
file:///C:/Users/ADMINI~1/AppData/Local/Temp/enhtmlclip/Image(1).gifusing namespace std;   
  
int mymin(int a, int b, int c)   
file:///C:/Users/ADMINI~1/AppData/Local/Temp/enhtmlclip/Image(2).giffile:///C:/Users/ADMINI~1/AppData/Local/Temp/enhtmlclip/Image(3).gif{   
file:///C:/Users/ADMINI~1/AppData/Local/Temp/enhtmlclip/Image(4).gif    int temp = (a < b ? a : b);   
    return (temp < c ? temp : c);   
file:///C:/Users/ADMINI~1/AppData/Local/Temp/enhtmlclip/Image(8).gif}   
int FindUgly(int n) //
{   
    int* ugly = new int[n];   
    ugly[0] = 1;   
    int index2 = 0;   
    int index3 = 0;   
    int index5 = 0;   
    int index = 1;   
    while (index < n)   
file:///C:/Users/ADMINI~1/AppData/Local/Temp/enhtmlclip/Image(5).giffile:///C:/Users/ADMINI~1/AppData/Local/Temp/enhtmlclip/Image(6).gif    {   
        int val = mymin(ugly[index2]*2, ugly[index3]*3, ugly[index5]*5); //竞争产生下一个丑数   
        if (val == ugly[index2]*2) //将产生这个丑数的index*向后挪一位；  
            ++index2;   
        if (val == ugly[index3]*3)   //这里不能用elseif，因为可能有两个最小值，这时都要挪动；
            ++index3;   
        if (val == ugly[index5]*5)   
            ++index5;   
        ugly[index++] = val;   
file:///C:/Users/ADMINI~1/AppData/Local/Temp/enhtmlclip/Image(7).gif    }   
/*/
    for (int i = 0; i < n; ++i)   
        cout << ugly << endl;   
//*/
    int result = ugly[n-1];   
    delete[] ugly;   
    return result;   
}   

int main()   
{   
    int num=1;
      printf("input the number: \n");
    scanf("%d", &num);
    printf("%d \n",FindUgly(num));   
    return 0;   
}


65.输出1到最大的N位数
题目：输入数字n，按顺序输出从1最大的n位10进制数。比如输入3，
则输出1、2、3一直到最大的3位数即999。
分析：这是一道很有意思的题目。看起来很简单，其实里面却有不少的玄机。

66.颠倒栈。
题目：用递归颠倒一个栈。例如输入栈{1, 2, 3, 4, 5}，1在栈顶。
颠倒之后的栈为{5, 4, 3, 2, 1}，5处在栈顶。

67.俩个闲玩娱乐。
1.扑克牌的顺子
从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。
2-10为数字本身，A为1，J为11，Q为12，K为13，而大小王可以看成任意数字。
2.n个骰子的点数。
把n个骰子扔在地上，所有骰子朝上一面的点数之和为S。输入n，
打印出S的所有可能的值出现的概率。


68.把数组排成最小的数。
题目：输入一个正整数数组，将它们连接起来排成一个数，输出能排出的所有数字中最小的一个。
例如输入数组{32,  321}，则输出这两个能排成的最小数字32132。
请给出解决问题的算法，并证明该算法。
分析：这是09年6月份百度的一道面试题，
从这道题我们可以看出百度对应聘者在算法方面有很高的要求。
思路：先将整数数组转为字符串数组，然后字符串数组进行排序，最后依次输出字符串数组即可。这里注意的是字符串的比较函数需要重新定义，不是比较a和b，而是比较ab与 ba。如果ab < ba，则a < b；如果ab > ba，则a > b；如果ab = ba，则a = b。比较函数的定义是本解决方案的关键。这道题其实就是希望我们能找到一个排序规则，根据这个规则排出来的数组能排成一个最小的数字。
      证明：为什么这样排个序就可以了呢？简单证明一下。根据算法，如果a < b，那么a排在b前面，否则b排在a前面。可利用反证法，假设排成的最小数字为xxxxxx，并且至少存在一对字符串满足这个关系：a > b，但是在组成的数字中a排在b前面。根据a和b出现的位置，分三种情况考虑：
      （1）xxxxab，用ba代替ab可以得到xxxxba，这个数字是小于xxxxab，与假设矛盾。因此排成的最小数字中，不存在上述假设的关系。
      （2）abxxxx，用ba代替ab可以得到baxxxx，这个数字是小于abxxxx，与假设矛盾。因此排成的最小数字中，不存在上述假设的关系。
      （3）axxxxb，这一步证明麻烦了一点。可以将中间部分看成一个整体ayb，则有ay < ya，yb < by成立。将ay和by表示成10进制数字形式，则有下述关系式，这里a，y，b的位数分别为n，m，k。
        关系1： ay < ya => a * 10^m + y < y * 10^n + a => a * 10^m - a < y * 10^n - y => a( 10^m - 1)/( 10^n - 1) < y
        关系2： yb < by => y * 10^k + b < b * 10^m + y => y * 10^k - y < b * 10^m - b => y < b( 10^m -1)/( 10^k -1)
        关系3： a( 10^m - 1)/( 10^n - 1) < y < b( 10^m -1)/( 10^k -1)  => a/( 10^n - 1)< b/( 10^k -1) => a*10^k - a < b * 10^n - b =>a*10^k + b < b * 10^n + a => a < b
       这与假设a > b矛盾。因此排成的最小数字中，不存在上述假设的关系。
       综上所述，得出假设不成立，从而得出结论：对于排成的最小数字，不存在满足下述关系的一对字符串：a > b，但是在组成的数字中a出现在b的前面。从而得出算法是正确的。
代码一：利用指针。
[html] view plaincopyprint?
  • #include <iostream>
  • #include <string.h>
  • using namespace std;
  • const int g_MaxNumberLength=10;
  • char* g_StrCombine1=new char[g_MaxNumberLength*2+1];
  • char* g_StrCombine2=new char[g_MaxNumberLength*2+1];
  • int compare(const void* strNumber1, const void* strNumber2)
  • {
  •     strcpy(g_StrCombine1, *(const char**)strNumber1);
  •     strcat(g_StrCombine1, *(const char**)strNumber2);
  •     strcpy(g_StrCombine2, *(const char**)strNumber2);
  •     strcat(g_StrCombine2, *(const char**)strNumber1);
  •     return strcmp(g_StrCombine1, g_StrCombine2);
  • }
  • 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=new char[g_MaxNumberLength+1];
  •         sprintf(strNumbers, "%d", numbers);
  •     }
  •     qsort(strNumbers, length, sizeof(char*), compare);
  •     for(i=0; i<length; i++)
  •         cout<<strNumbers;
  •     cout<<endl;
  •     for(i=0; i<length; i++)
  •         delete[] strNumbers;
  •     delete[] strNumbers;
  • }
  • void main()
  • {
  •     int Num;
  •     cin>>Num;
  •     int *numbers=new int[Num];
  •     for(int i=0; i<Num; i++)
  •         cin>>numbers;
  •     PrintMinNumber(numbers, Num);
  • }


代码二：利用string类。
[cpp] view plaincopyprint?
  • #include <iostream>
  • #include <string>
  • #include <sstream>
  • #include <algorithm>
  • using namespace std;
  • bool compare(const string& str1, const string &str2)
  • {
  •     string s1=str1+str2;
  •     string s2=str2+str1;
  •     return s1<s2;
  • }
  • void ComArrayMin(int *pArray, int num)
  • {
  •     int i;
  •     string *pStrArray=new string[num];
  •     for(i=0; i<num; i++)
  •     {
  •         stringstream stream;
  •         stream<<pArray;
  •         stream>>pStrArray;
  •     }
  •     sort(pStrArray, pStrArray+num, compare);
  •     for(i=0; i<num; i++)
  •         cout<<pStrArray;
  •     cout<<endl;
  •     delete[] pStrArray;
  • }
  • void main()
  • {
  •     int Num;
  •     cin>>Num;
  •     int *pArray=new int[Num];
  •     for(int i=0; i<Num; i++)
  •         cin>>pArray;
  •     ComArrayMin(pArray, Num);
  • }




69.旋转数组中的最小元素。
题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个排好序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数组的最小值为1。

http://blog.csdn.net/mingming_bupt/article/details/6324886
    分析：这道题最直观的解法并不难。从头到尾遍历数组一次，就能找出最小的元素，时间复杂度显然是O(N)。但这个思路没有利用输入数组的特性，我们应该能找到更好的解法。
我们注意到旋转之后的数组实际上可以划分为两个排序的子数组，而且前面的子数组的元素都大于或者等于后面子数组的元素。我们还可以注意到最小的元素刚好是这两个子数组的分界线。我们试着用二元查找法的思路在寻找这个最小的元素。
首先我们用两个指针，分别指向数组的第一个元素和最后一个元素。按照题目旋转的规则，第一个元素应该是大于或者等于最后一个元素的（这其实不完全对，还有特例。后面再讨论特例）。
接着我们得到处在数组中间的元素。如果该中间元素位于前面的递增子数组，那么它应该大于或者等于第一个指针指向的元素。此时数组中最小的元素应该位于该中间元素的后面。我们可以把第一指针指向该中间元素，这样可以缩小寻找的范围。同样，如果中间元素位于后面的递增子数组，那么它应该小于或者等于第二个指针指向的元素。此时该数组中最小的元素应该位于该中间元素的前面。我们可以把第二个指针指向该中间元素，这样同样可以缩小寻找的范围。我们接着再用更新之后的两个指针，去得到和比较新的中间元素，循环下去。
按照上述的思路，我们的第一个指针总是指向前面递增数组的元素，而第二个指针总是指向后面递增数组的元素。最后第一个指针将指向前面子数组的最后一个元素，而第二个指针会指向后面子数组的第一个元素。也就是它们最终会指向两个相邻的元素，而第二个指针指向的刚好是最小的元素。这就是循环结束的条件。

//============================================================================
// Name        : 100题之旋转数组中的最小元素.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
#include <iostream>
#include<string>
#include<exception>
using namespace std;
const int ERROR=-10000;
int reverse(int *a,int length)throw (exception)
{
     if(length<0||!a)
          throw new string("Invalid parameters");

     if(a[0]<a[length-1])
          return a[0];
     int low=0,high=length-1;
     int middle;
     while(low<=high)
     {
          middle=(low+high)/2;
          int temp=a[low];
          if(a[middle]>temp)
          {
               low=middle;
          }
          else if(a[middle]<temp)
          {
               high=middle;
          }
          else if(a[middle]==temp)
          {
               return a[middle+1];
          }
     }
}
int main() {
     int a[10]={1,2,2,2,1};
     int length=5;
     cout <<reverse(a,length) << endl;
     return 0;
}
70.给出一个函数来输出一个字符串的所有排列。
ANSWER 简单的回溯就可以实现了。当然排列的产生也有很多种算法，去看看组合数学，
还有逆序生成排列和一些不需要递归生成排列的方法。
印象中Knuth的<TAOCP>第一卷里面深入讲了排列的生成。这些算法的理解需要一定的数学功底，
也需要一定的灵感，有兴趣最好看看。


71.数值的整数次方。
题目：实现函数double Power(double base, int exponent)，求base的exponent次方。
不需要考虑溢出。
分析：这是一道看起来很简单的问题。可能有不少的人在看到题目后30秒写出如下的代码：
double Power(double base, int exponent)
{
      double result = 1.0;
      for(int i = 1; i <= exponent; ++i)
            result *= base;
      return result;
}


72.
题目：设计一个类，我们只能生成该类的一个实例。
分析：只能生成一个实例的类是实现了Singleton模式的类型。
http://www.cnblogs.com/wolenski/archive/2012/08/11/2633942.html

分析：只能生成一个实例的类是实现了Singleton模式的类型。

由于设计模式在面向对象程序设计中起着举足轻重的作用，在面试过程中很多公司都喜欢问一些与设计模式相关的问题。在常用的模式中，Singleton是唯一一个能够用短短几十行代码完整实现的模式。因此，写一个Singleton的类型是一个很常见的面试题。

事实上，要让一个类型是能创建一个实例不是一件很难的事情。我们可以把该类型的构造函数设为private，这样该类型的用户就不能创建该类型的实例了。然后我们在给类型中创建一个静态实例。当用户需要该类型的实例时，我们就返回这个实例。基于这个思路，我们可以用C#写出如下代码：

[url=]file:///C:/Users/ADMINI~1/AppData/Local/Temp/enhtmlclip/Image.gif[/url]
1 // We can only get an instance of the class Singleton1. The instance 2     // is created when class Singleton1 is referenced at the first time 3     public sealed class Singleton1 4     { 5         private Singleton1() 6         { 7         } 8   9         private static Singleton1 instance = new Singleton1();10         public static Singleton1 Instance11         {12             get13             {14                 return instance;15             }16         }17     }

由于类Singleton1 的实例是一个静态变量，因此它会在该类型的第一次引用的时候被创建，而不是第一次在调用Singleton1.get_Instance的时候被创建。如果我们此时并不需要该实例，那么我们就过早地初始化该实例，无论在内存空间还是CPU时间上都是一种浪费。

我们可以把上面的代码稍作改动，就能实现在第一次调用Singleton_getInstance时候才会创建类型的唯一实例：



1  // We can only get an instance of the class Singleton2. 2     // The instance is created when we need it explicitly. 3     public sealed class Singleton2 4     { 5         private Singleton2() 6         { 7         } 8   9         private static Singleton2 instance = null;10         public static Singleton2 Instance11         {12             get13             {14                 if (instance == null)15                     instance = new Singleton2();16  17                 return instance;18             }19         }20     }


我们在单线程环境下只能得到类型Singleton2的一个实例，但在多线程环境下情况就可能不同了。设想如果两个线程同时运行到语句if (instance == null)，而此时该实例的确没有创建，那么两个线程都会创建一个实例。此时，类型Singleton2就不在满足模式Singleton的要求了。

为了保证在多线程环境下我们还是只能得到类型的一个实例，我们应该在判断实例是否已经创建，以及在实例还没有创建的时候创建一个实例的语句上加一个同步锁。我们把Singleton2稍作修改就得到了如下代码：



1  // We can only get an instance of the class Singleton3, 2     // even when there are multiple threads which are trying 3     // to get an instance concurrently. 4     public sealed class Singleton3 5     { 6         private Singleton3() 7         { 8         } 9  10         private static readonly object syncObj = new object();11  12         private static Singleton3 instance = null;13         public static Singleton3 Instance14         {15             get16             {17                 lock (syncObj)18                 {19                     if (instance == null)20                         instance = new Singleton3();21                 }22  23                 return instance;24             }25         }26     }


说明一下，由于C/C++没有为线程同步提供直接的支持。为了让代码显得简洁，而不是让大量的代码在实现同步锁而偏离了实现Singleton的主题，本文的代码用C#实现。

我们还是假设有两个线程同时想创建一个实例。由于在一个时刻只能有一个线程能得到同步锁。当第一个线程加上锁时，第二个线程只能在等待。当第一个线程发现实例还没有创建时，它创建出一个实例。接着第一个线程释放同步锁。此时第二个线程可以加上同步锁，并运行接下来的代码。由于此时实例已经被第一个线程创建出来了，第二个线程就不会重复创建实例了。于是保证了我们只能得到一个实例。

但是类型Singleton3还不是完美。由于我们每次调用Singleton3.get_Instance的时候，都会试图加上一个同步锁。由于加锁是一个非常耗时的操作，在没有必要的时候我们应该尽量避免这样的操作。

实际上，我们只是在实例还没有创建之前需要加锁操作，以保证只有一个线程创建出实例。而当实例已经创建之后，我们已经不需要再做加锁操作了。于是，我们可以把上述代码再作进一步的改进：



1  // We can only get an instance of the class Singleton4, 2     // even when there are multiple threads which are trying 3     // to get an instance concurrently. When the instance has 4     // been created, we don't need the lock any more. 5     public sealed class Singleton4 6     { 7         private Singleton4() 8         { 9         }10  11         private static object syncObj = new object();12  13         private static Singleton4 instance = null;14         public static Singleton4 Instance15         {16             get17             {18                 if (instance == null)19                 {20                     lock (syncObj)21                     {22                         if (instance == null)23                             instance = new Singleton4();24                     }25                 }26  27                 return instance;28             }29         }30     }


我们只需要在最开始调用Singleton4_getInstance（可能来自一个线程，也可能来自多个线程）的时候需要加锁。当实例已经创建之后，我们就不再需要作加锁操作，从而在后续调用Singleton4_getInstance时性能得到提升。

关于第一种写法的更多，请参考http://en.wikipedia.org/wiki/Double-checked_locking。站在面试的角度，本文的分析已经足够应付。但如果想展示更多对多线程编程的理解，更深入地了解这个问题总是有益的。



73.对称字符串的最大长度。
题目：输入一个字符串，输出该字符串中对称的子字符串的最大长度。
比如输入字符串“google”，由于该字符串里最长的对称子字符串是“goog”，因此输出4。
分析：可能很多人都写过判断一个字符串是不是对称的函数，这个题目可以看成是该函数的加强版。
http://www.cnblogs.com/python27/archive/2011/12/18/2291977.html
【思 路1】一看这题就是遍历！没错，我们最直观的往往也是最容易实现的，这里我们暂且不考虑效率的问题。我们的基本思路是：我们如果有一个判断一个字符串是不是对称的函数的话，我们就可以用这个子函数逐一检查原字符串中所有的字符串，然后输出长度最大的即可。
　　（1）怎样判断一个字符串是不是对称的字符串?我们可以用两个指针分别指向字符串的第一个字符和最后一个字符，判断是否相等，如果不等直接返回false，如果为真则接着比较下一对字符。（2）如果遍历遍历原字符串的所有子串，首先我们让一个指针从头至尾遍历，对于这个指针的每一个字符，我们在用另一个指针逐一指向它后面的每一个字符即可。好了，两个问题都解决了，我们可以写出如下的代码：

1 #include<iostream> 2 #include<string> 3 #include<cstring> 4 using namespace std; 5  6 /************************************************ 7 * 判断一个字符串是否是对称的 8 *************************************************/ 9 bool IsSymmetricalString(char* pstart,char* pend)10 {11     if(pstart == NULL || pend == NULL || pstart > pend)12         return false;13 14     while(pstart < pend)15     {16         if(*pstart != *pend)17         {18             return false;19         }20         else21         {22             pstart++;23             pend--;24         }25     }26 27     return true;28 }29 30 31 /*************************************************32 * 求最大对称子串的长度33 **************************************************/34 int MaxSymmetricalSubstringLenth(char *pstring)35 {36     if(pstring == NULL)37         return 0;38     39     int maxlength = 1;40     41     int length = strlen(pstring);42     char* pfirst = pstring;43     while(pfirst < &pstring[length - 1])44     {45         char* psecond = pfirst + 1;46         while(psecond <= &pstring[length - 1])47         {48             if(IsSymmetricalString(pfirst,psecond))49             {50                 int templength = psecond - pfirst + 1;51                 if(templength > maxlength)52                 {53                     maxlength = templength;54                 }55             }56             57             psecond++;58         }59         60         pfirst++;61     }62 63     return maxlength;64 }65 66 int main()67 {68     cout<<"Please Enter Your String(the length must <1000 ):"<<endl;69     char* yourstring = new char[1000];70     cin>>yourstring;71 72     cout<<"The Max Symmetrical SubString Length in Your String is:"<<endl;73     cout<<MaxSymmetricalSubstringLenth(yourstring)<<endl;74     75     return 0;76 }

　　运行结果如下：
file:///C:/Users/ADMINI~1/AppData/Local/Temp/enhtmlclip/Image(13).png
　　反思：我们现在来分析一下该算法的时间复杂度，首先遍历原字符串的所有子串有两个循环，这个时间复杂度是O(n2),我们在这两层循环之间有一个判断给定字符串是不是对称的子函数，这个子函数的时间复杂度是O(n)，所以总的时间复杂度是O(n3).由于我们是由外向内判断一个字符串是不是对称的，那么对于形如aba的字子串（b可以含有很多字符），我们判断aa相等后，还得判断b是否是对称；而在判断子串b的时候还得再判断一次，换句话说有很多的子串我们是重复判断的。那么我们能不能消除这种重复呢？、
　　【思 路2】根据上面的分析，我们很容易想到，如果我们从内向外比较字符，那么对于aba型的字符串，如果我们判断了b是对称的，只需要再左右各移一位就可以判断下一个字符串是否是对称的，这样我们就能避免重复；然而我们需要注意的是，对于原字符串中每一个字符有两种情况，一种是子串是以单个字符为中心对称分布的，换句话说，子串的长度是奇数；另一种情况是子串以两个字符串为中心，即子串的长度是偶数。至此我们就可以写出如下的代码：

1 #include<iostream> 2 #include<string> 3 using namespace std; 4  5 /********************************************************************* 6 * 计算字符串最大对称子串的长度 7 *********************************************************************/ 8 int MaxSymmetricalSubstringLenth(char* pstring) 9 {10     int maxlength = 1;11 12     char* pchar = pstring + 1;13     while(*pchar != '\0')14     {15         //以该字符串为中心，子串长度为奇数16         char *pfirst = pchar - 1;17         char *psecond = pchar + 1;18         while(pfirst > pstring && psecond < &pstring[strlen(pstring) - 1] && *pfirst == *psecond)19         {20             pfirst--;21             psecond++;22         }23 24         int templength = psecond - pfirst + 1;25         if(templength > maxlength)26         {27             maxlength = templength;28         }29 30 31         //字该字符及之后的字符两个为中心，子串为偶数32         pfirst = pchar - 1;33         psecond = pchar;34         while(pfirst > pstring && psecond < &pstring[strlen(pstring) - 1] && *pfirst == *psecond)35         {36             pfirst--;37             psecond++;38         }39         40         templength = psecond - pfirst + 1;41         if(templength > maxlength)42         {43             maxlength = templength;44         }45         46         pchar++;47     }48 49     return maxlength;50 }51 52 int main()53 {54     cout<<"Please Enter Your String:"<<endl;55     char *yourstring = new char[1000];56     cin>>yourstring;57 58     cout<<"The Max Symmetrical SubString Length is:"<<endl;59     cout<<MaxSymmetricalSubstringLenth(yourstring)<<endl;60 61     delete[] yourstring;    62     return 0;63 }

　　测试结果如下：
file:///C:/Users/ADMINI~1/AppData/Local/Temp/enhtmlclip/Image(14).png
　　效率分析：这种算法首先需要遍历一边字符串，外层为n，对于每一个字符，需要从该字符开始有中间到两边遍历一遍，因而总的时间复杂度是O（n2）.


74.数组中超过出现次数超过一半的数字
题目：数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字。
http://blog.csdn.net/iefswang/article/details/7581613
分析：这是一道广为流传的面试题，包括百度、微软和Google在内的多家公司都
曾经采用过这个题目。要几十分钟的时间里很好地解答这道题，
除了较好的编程能力之外，还需要较快的反应和较强的逻辑思维能力。
  这个方法借用了别人的思路。
     在这里我做一下简单的分析。
     这个算法的时间复杂度是O(n)，另外用了两个辅助变量。
     k用于临时存储数组中的数据，j用于存储某个数出现的次数。
     开始时k存储数组中的第一个数,j为0，如果数组出现的数于k相等，则j加1，否则就减1，如果j为0，就把当前数组中的数赋给k
     因为指定的数出现的次数大于数组长度的一半，所有j++与j--相抵消之后，最后j的值是大于等于1的，k中存的那个数就是出现最多的那个数。    下面这个算法只适合数组中数组中某个数的出现次数超过数组长度一半的数组，符合题意。
方法三
int Search(int A[],int len)
{
     if(NULL==A || len<=0)
      {
          return -1;
     }
     int k, j=0;
     for(int i=0;i<len;++i)
      {
          if(j==0)
           {
               k=A;
           }
          if(k==A)
          {
               ++j;//有人说++j比j++有先天的优势，不知你是否听说，如果你也听说，有没有想过More Effective C++(C++程序员必看书籍)
          }
          else
          {
               --j;
          }
      }
     return k;
}


};


75.二叉排序树树两个结点的最低共同父结点
题目：二叉树的结点定义如下：
struct TreeNode
{
    int m_nvalue;
    TreeNode* m_pLeft;
    TreeNode* m_pRight;
};
输入二叉树中的两个结点，输出这两个结点在树中最低的共同父结点。
分析：求树中两个结点的最低共同结点是面试中经常出现的一个问题。这个问题至少有两个变种。
http://blog.csdn.net/dahai_881222/article/details/7801356
typedef struct BitTreeNode
{  
     int data;
     struct BitTreeNode *lf,*rh;
}node;

node *create(int a[] , int start , int end)
{
     int m = (start+end)/2;
     node *root = (node*)malloc(sizeof(node));
     root->data = a[m];
     node *p = root;
     if(m>=start && m<=end)
     {
            p->lf = create(a , start , m-1);
          p->rh = create(a , m+1 , end);
     }
    return root;
}

node *get(node *root , int x ,int y)
{
     if(root == NULL)
     {
          return NULL;
     }
     if(((x>root->data)&&(y<root->data)) ||((x<root->data)&&(y>root->data)))
     {
          printf("%d",root->data);
          return root;
     }
     if(((x>root->data)&&(y>root->data))) //right
     {
          get(root->rh , x ,y);
     }
     if(((x<root->data)&&(y<root->data)))
     {
          get(root->lf , x,y);
     }
}

void main()
{
     int a[]={4,6,8,10,12,14,16};
     node *root,*p;
     root = create(a,0 ,6);
     p = get(root , 4, 8);
}


顶 收藏 回复
转载文章时务必注明原作者及原始链接，并注明「发表于 软院网 RuanYuan.Net 」，并不得对作品进行修改。
共收到 2 条回复
726
独慕冷风 · #2 · 2012-10-19 18:42:37  回复 支持 反对
辛苦辛苦了
1260
twhdong · #3 · 2012-10-19 21:53:59  回复 支持 反对
好贴，果断要MARK的
回帖
B Color Image Link Quote Code Smilies
Command + Enter
本版积分规则
楼主相关话题
收藏
共收到 2 条回复
参与回复
快速回复 返回顶部 返回列表