【100题】第六十一题~第六十五题（数组中只出现一次的数、链表公共点、删除字串特定字符、寻找丑数、输出从1到最大的N 位数）

mmdev

浏览: 12916583 次
性别:
来自: 大连

最近访客更多访客>>

jklwan

u012363178

anttu

devcang

博主相关

博客

微博

相册

留言

关于我

文章分类

全部博客 (15973)

社区版块

存档分类

2013-03 ( 14)
2013-02 ( 88)
2013-01 ( 196)
更多存档...

一，找出数组中两个只出现一次的数字

1）题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。

请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)

例如：A[ ]={1,1,2,2,3,3,4,4,5,6}; 需要找出5 和 6

2）分析：由异或运算的性质：任何一个数字异或它自己都等于0。依次异或数组中的每一个数字，结果是两个只出现一次的数字的异或，那些出现两次的数字全部在异或中抵消掉了。
如果能够把原数组分为两个子数组。在每个子数组中，包含一个只出现一次的数字，而其他数字都出现两次。这样拆分原数组，还是从头到尾依次异或数组中的每一个数字，那么最终得到的结果就是两个只出现一次的数字的异或结果。

如何拆分数组呢？

由于这两个数字肯定不一样，那么这个异或结果肯定不为0，也就是说在这个结果数字的二进制表示中至少就有一位为1。

1> 我们在结果数字中找到第一个为1的位的位置，记为第N位。

2> 以第N位是不是1为标准把原数组中的数字分成两个子数组，第一个子数组中每个数字的第N位都为1，而第二个子数组的每个数字的第N位都为0。
3> 现在已经把原数组分成了两个子数组，每个子数组都包含一个只出现一次的数字，而其数字都出现了两次。因此到此为止，所有的问题都已经解决

3）源码:

#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[i];               //异或 
     
    int pos=findFirstOne(ansXor); 
    num1=num2=0; 
    
    for(int i=0;i<length;i++)
	{ 
        if(testBit(date[i],pos)) //如果该位为1 
            num1^=date[i]; 
        else
            num2^=date[i]; 
    } 
    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; 
}

二，找出链表的第一个公共结点

1）题目：两个单向链表，找出它们的第一个公共结点。

链表的结点定义为：

struct ListNode

{

int data;

ListNode *m_pNext;

};

2）分析：

1）如果两个链表相交，则从相交点开始，后面的节点都相同，即最后一个节点肯定相同；
2）从头到尾遍历两个链表，并记录链表长度，当二者的尾节点不同，则二者肯定不相交；
3）尾节点相同，如果A长为LA，B为LB，如果LA>LB,则A前LA-LB个先跳过，然后二者一起向后遍历，直到遇到相同的节点；LA<LB类似处理
因为第一个公共节点距起始节点的距离start_a满足： LA - start_a == LB - start_b。

3）源码：

#include <iostream>
using namespace std; 

struct   ListNode
{
      int                  data;
      ListNode     *m_pNext;
};

unsigned int ListLength(ListNode* pHead)
{

      unsigned int nLength = 0;
      ListNode* pNode = pHead;
      while(pNode != NULL)
      {
            ++ nLength;
            pNode = pNode->m_pNext;
      }
      return nLength;
}

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;

}

三，在字符串中删除特定的字符。

1）题目：输入两个字符串，从第一字符串中删除第二个字符串中所有的字符。

例如，输入”They are students.”和”aeiou”，则删除之后的第一个字符串变成”Thy r stdnts.”。

2）分析：

1）首先处理字串二（”aeiou”），遍历字符串，如果存在则HashTable[ ]=1

2）策略一：每一次遍历字串一，则查找HashTable。存在则删除（数组删除复杂度高）

策略二：采用两个指针，指向字串一。其中begin记录要保存的字符的当前位置，end用来查看是否存在HashTable，如果end所指字符出现，则跳过（不保存）否则，保存到begin所指位置，然后begin++，最后begin='\0'。

3）源码：

#include <stdio.h>
#include <memory.h>
int delchar(char *src, char *dst)
{
    char *begin = src;
    char *end   = src;
    char hashtable[256];
    int i = 0;
    memset(hashtable,0,sizeof(hashtable));//将hashtable中每一个值都初始化为 0
	 
    while(*dst) //遍历dest 并标记每一个 出现的字符 
        ++hashtable[*dst++];
    /*begin记录要保存的位置 
      end  记录要保存的字符
	  如果end所指字符出现 在字串二，则跳过（不保存）
	  否则，保存到begin所指位置，然后begin++  
	*/ 
    while(*end)
    {
        if(!hashtable[*end])//如果 
        {
            *begin = *end ;
            ++begin;
        }
        ++end;

    }
    
    *begin= '\0';
}
int main()
{
    char src[] = "They are students.";
    char del[] = "aeiou";
    delchar(src, del);
    printf("Output : %s\n",src);
    return 0;
}

四，寻找丑数。

1）题目：我们把只包含因子2、3 和5 的数称作丑数（Ugly Number）。例如6、8 都是丑数，但14 不是，因为它包含因子7。习惯上我们把1 当做是第一个丑数。求按从小到大的顺序的第1500 个丑数。

2）分析：

思路一：从1开始判断每一个数是否为丑数，如果是则count++ ，直到count=1500 则输出该数。

缺点：每一个数都要遍历，时间复杂度高

思路二：只需要遍历每一个丑数

我们假设一个数组中已经有若干丑数，并且这些丑数是按顺序排列的，我们把现有的最大丑数记为max，则下一个丑数肯定是前面丑数乘以2，3，5得到的。

乘以2：把数组中的每一个数都乘以2，由于原数组是有序的，因为乘以2后也是有序递增的，这样必然存在一个数M2，它前面的每一个数都是小于等于max，而包括M2在内的后面的数都是大于max的，因为我们还是要保持递增顺序，所以我们取第一个大于max的数M2。

乘以3：可以取第一个大于max的数M3

乘以5：可以取第一个大于max的数M5。

　　最终下一个丑数取:min{M2,M3,M5}即可

其中pMultiply2 , *pMultiply3 , *pMultiply5 分别保存，乘以该基数能得到最接近丑数数组最大值的丑数数组下标

3）源码：

第一种：

//主程序有两个算法
//第一个算法很朴素，从1开始判断，时间较长
//第二个算法省去了不是丑数的判断，但是到1690时崩溃了。。。
#include "iostream"
#define MAX_NUM 10
bool IsUglyNum(long number)
{
	long num=number;
	while (0==num%2)
	{
		num=num/2;
	}
	while(0==num%3)
	{
		num=num/3;
	}
	while(0==num%5)
	{
		num=num/5;
	}
	if (num==1)
	{
		//printf("%d  ",number);
		return true;
	}
	else
		return false;
}
void GetUglynumFunc1()
{
	long count=0;//the number of uglynum
	long i=1;
	//for(long i=1;i<=MAX_NUM;i++)
	while(count<MAX_NUM)
	{
		if(IsUglyNum(i))
			count++;
		i++;
	}
	printf("\n FUNC1:the %d ugly number is %d",MAX_NUM,i-1);
}

int main()
{
	GetUglynumFunc1();
	
}

//主程序有两个算法
//第一个算法很朴素，从1开始判断，时间较长
//第二个算法省去了不是丑数的判断，但是到1690时崩溃了。。。
#include "iostream"
#define MAX_NUM 10

long Min(long number1, long number2, long number3)
{
	long min = (number1 < number2) ? number1 : number2;
	min = (min < number3) ? min : number3;
	return min;
}
long _GetUglynumFunc2(long index)
{
	if(index <= 0)
		return 0;
		
	long *pUglyNumbers = new long[index];
	pUglyNumbers[0] = 1;
	long nextUglyIndex = 1;//个数 
	
	long *pMultiply2 = pUglyNumbers;
	long *pMultiply3 = pUglyNumbers;
	long *pMultiply5 = pUglyNumbers;
	
	while(nextUglyIndex < index)
	{
		long min = Min(*pMultiply2 * 2, *pMultiply3 * 3, *pMultiply5 * 5);// 
		pUglyNumbers[nextUglyIndex] = min;
		
		while((*pMultiply2)* 2 <= pUglyNumbers[nextUglyIndex])
			++pMultiply2;//下一个丑数下标 
			
		while((*pMultiply3)* 3 <= pUglyNumbers[nextUglyIndex])
			++pMultiply3;//下一个丑数下标 
			
		while((*pMultiply5)* 5 <= pUglyNumbers[nextUglyIndex])
			++pMultiply5;//下一个丑数下标  
			
		++nextUglyIndex;
	}
	long ugly = pUglyNumbers[nextUglyIndex - 1];
	delete[] pUglyNumbers;
	return ugly;
}
int main()
{
	long max_uglynum=_GetUglynumFunc2(MAX_NUM);
	printf("\n FUNC2:the %d ugly number is %d\n",MAX_NUM,max_uglynum);
	
}

五，输出从1到最大的N 位数

1）题目：输入数字n，按顺序输出从1 到最大的n位10 进制数。比如输入3，则输出1、2、3 、4……999。

2）分析：这是一道很有意思的题目。看起来很简单，其实里面却有不少的玄机。

思路一：利用整形表示法

缺点：超过整形表示的范围就会溢出

void Print1ToMaxOfNDigits1(int n)
{
	int number=1;
	int i=0;
	while(i++<n)
		number*=10;

	for(i=1; i<number; i++)
		cout<<i<<" ";
}

思路二：利用字符串模拟加减法

用字符串表达数字的时候，最直观的方法就是字符串里每个字符都是’0’到’9’之间的某一个字符，表示数字中的某一位。因为数字最大是n位的，因此我们需要一个n+1位字符串（最后一位为结束符号’\0’）。当实际数字不够n位的时候，在字符串的前半部分补零。这样，数字的个位永远都在字符串的末尾（除去结尾符号）。

首先我们把字符串中每一位数字都初始化为’0’。然后每一次对字符串表达的数字加1，再输出。

因此我们只需要做两件事：一是在字符串表达的数字上模拟加法。另外我们要把字符串表达的数字输出。值得注意的是，当数字不够n位的时候，我们在数字的前面补零。输出的时候这些补位的0不应该输出。比如输入3的时候，那么数字98以098的形式输出，就不符合我们的习惯了。

#include <iostream>
using namespace std; 
bool Increment(char* number)
{
	bool isOverflow=false;
	int nTakeOver=0;
	int nLength=strlen(number);
	
	for(int i=nLength-1; i>=0; i--)
	{
		int nSum=number[i]-'0'+nTakeOver;
		if(i==nLength-1)
			nSum++;
		
		if(nSum>=10)
		{
			if(i==0)
				isOverflow=true;
			else
			{
				nSum-=10;
				nTakeOver=1;
				number[i]='0'+nSum;
			}
		}
		else
		{
			number[i]='0'+nSum;
			break;
		}

	}
	
	return isOverflow;

}

void PrintNumber(char* number)
{
	bool isBeginning0=true;
	int nLength=strlen(number);

	for(int i=0; i<nLength; i++)
	{
		if(isBeginning0 && number[i]!='0')//如果第一个为0 接着判断下一个是否为 0 
			isBeginning0=false;

		if(!isBeginning0)		
			cout<<number[i];
		
	}
	cout<<" ";
}

void Print1ToMaxOfNDigits2(int n)
{
	if(n<=0)
		return;
	char *number=new char[n+1];
	memset(number, '0', n);
	number[n]='\0';

	while(!Increment(number))
	{
		PrintNumber(number);

	}
	cout<<endl;
	delete[] number;
}

int main()
{
	Print1ToMaxOfNDigits2(2); 
}

思路三：求n位数的0~9的全排列

第二种思路基本上和第一种思路相对应，只是把一个整型数值换成了字符串的表示形式。第二种思路虽然比较直观，但由于模拟了整数的加法，代码有点长。要在面试短短几十分钟时间里完整正确写出这么长代码，不是件容易的事情。接下来我们换一种思路来考虑这个问题。如果我们在数字前面补0的话，就会发现n位所有10进制数其实就是n个从0到9的全排列。也就是说，我们把数字的每一位都从0到9排列一遍，就得到了所有的10进制数。只是我们在输出的时候，数字排在前面的0我们不输出罢了。

全排列用递归很容易表达，数字的每一位都可能是0到9中的一个数，然后设置下一位。递归结束的条件是我们已经设置了数字的最后一位。

#include <iostream>
using namespace std; 

void PrintNumber(char* number)
{
	bool isBeginning0=true;
	int nLength=strlen(number);

	for(int i=0; i<nLength; i++)
	{
		if(isBeginning0 && number[i]!='0')
			isBeginning0=false;

		if(!isBeginning0)
		{
			cout<<number[i];
		}
	}
	cout<<" ";
}

void Print1ToMaxOfNDigitsRecursively(char *number, int length, int index)
{
	if(index==length-1)
	{
		PrintNumber(number);
		return;
	}
	
	for(int i=0; i<10; i++)
	{
		number[index+1]=i+'0';
		Print1ToMaxOfNDigitsRecursively(number, length, index+1);
		
	}
}

void Print1ToMaxOfNDigit3(int n)
{
	if(n<0)
		return;
	
	char *number=new char[n+1];
	number[n]='\0';
	
	for(int i=0; i<10; i++)
	{
		number[0]=i+'0';
		Print1ToMaxOfNDigitsRecursively(number, n, 0);
	}
}

int main()
{
	Print1ToMaxOfNDigit3(2); 
}

分享到：