c++练习(9)：数组和字符串

题目1：给定两个字符串，确定是否互相排列组合

思路: 无论如何变幻，每个字符出现的次数一定相同，一旦需要统计元素集中出现的次数，我们就应该想到hash table

bool isPermutation(string stringA,string stringB)
{
	if (stringA.length()!=stringB.length())   
	{
		return false;
	}
	unordered_map hashMapA;
	unordered_map hashMapB;
	
	for(int i=0;i
		hashMapA[stringA[i]]++;
		hashMapB[stringB[i]++];
	}
	
	if (hashMapA.size() != hashMapB.size())
	{
		return false;
	}
	
	unordered_map::iterator it;
	for(it=hashMapA.begin();it!=hashMapA.end();it++)
	{
		if(it->second !=hashMapB[it->first])
		{
			return false;
		}
	}
	return true;
}

题目2：给定报纸和消息都是字符串，检查消息是否可以利用报纸中的字符构成

思路:message中用到的字符必须出现在newspaper中。其次,message中任意字符出现的次数一定少于其中newspaper中出现的次数。统计一个元素集中元素出现的次数，我们就应该想到hash table

bool canCompose(string newspaper,string message)
{
	unordered_map hashMap;
	int i;
	if(newspaper.length()
		return false;
	}
	for(i=0;i
		hashMap[newspaers[i]]++;
	}
	
	for(i=0;i
		if(hashMap.cout(message[i])==0) //cout 检查是否有该key值，有返回1，没有0
		{
			return false;
		}
		if(--hashMap[message[i]]<0)  //如果message 中字符次数大于newspaer次数，则返回false
		{
			return false;
		}
	}
	return ture;
}

题目3：写一个anagram(s,t)，来判断两个字符可以通过变化各自顺序，从而相等

例如: 给定s=“abcd” t=“dcab” return true
时间复杂度要求:O(n) extra space

思路: 判断两个字符串，包含的字符及次数是否相等

使用hashmap方式

bool anagram(string s,string t)
{
	if(s.empty()||t.empty())
	{
		return false;
	}
	if(s.size()!=t.size())   //string.length() 和string.size() 失效效果一模一样
	{
		return false;
	}
	int letterCount[256]={0};
	
	for(int i=0;i
		++letterCount[s[i]];
		--letterCount[t[i]];
	}
	for(int i=0;i
		if(letterCount[t[i]]<0) return false;
	}
	return true;
}

使用 sort

//sort
bool anagram(string s, string t)
{
	if(s.empty()||t.empty())
	{
		return false;
	}
	if(s.size()!=t.size())   //string.length() 和string.size() 失效效果一模一样
	{
		return false;
	}
	
	sort(s.begin(),s.end());
	sort(t.begin(),t.end());
	if(s==t) return true;
	return false;
}

题目4：从一个数组中找到两个元素，使得两数之和等于给定的target,并返回两元素的下标

思路: 最直观的方法是再次扫描数组，判断target-array[i]是否存在数组中，这样做的时间复杂度是O(n^2)

如何保存之前的处理结果？可以使用hash table "target-array[i]"是否存在数组中

vector addsToTarget(vector&numbers,int target)
{
	unordered_map numToIndex;
	vector vi(2);  //初始化2个元素，值为编译器的默认值
	for (auto it=numbers.begin();it!=numbers.end();it++)
	{
		if(numToIndex.cout(target-*it))
		{
			vi[0]=numToIndex[target-*it]+1;
			vi[1]=(int)(it - numbers.begin())+1;
			return vi;
		}
		numToIndex[*it]=(int)(it - numbers.begin());
	}	
}

题目4：从数组中计算最长的连续元素长度

例如：给定[31,6,32,1,3,2]，最长的连续元序列是[1,2,3]，返回长度:3

思路：判断array[i]-1,array[i]+1是否存在于数组中。如何保存之前的处理结果？可以使用hash table由于序列是一系列的连续整数，只要序列的最小值以及最大值，就能唯一确定序列。而所谓的“作为后继加入序列”，“作为前驱加入序列”，更新最大最小值。
hash table的value可以是一个记录最大/最小值的structure，用以描述当前节点参与构成的最长序列

struct Bound
{
	int high;
	int low;
	Bound(int h=0;int l=0)
	{
		high=h;
		low=l;
	}
}

int lognestConsecutive(vector&num)
{
	unordered_map table;
	
	int local;
	int maxLen=0;
	
	for(int i=0;i
		if(table.count(num[i]))  
		{
			continue;
		}
		local=num[i];
		int low =local,high=local;
		
		if(table.count(local-1))
		{
			low=table[local-1].low;
		}
		if(table.count(local+1))
		{
			high=table[local+1].high;
		}
		
		table[low].high = table[local].high=high;
		table[high].low=table[local].low=low;
		
		if(high-low+1 > maxLen)
		{
			maxLen=high-low+1;
		}
	}
	return maxLen;
}

题目5：两个字符串最长的共有的字符

给定两个字符串，找到最长的共有的字符，并返回这个字符的长度
例如：
假定 A=“ABCD” B=“CBCE” return 2 公共是BC

int longestCommonSubstring(string &A,string &B)
{
	if(A.empty() || B.empty())
	{
		return 0;
	}
	int lcs=0,lcs_temp=0;
	for(int i=0;i
		for(int j=0;j
			lcs_temp=0;
			while((i+lcs_temp
				++lcs_temp;
			}
			
			// update lcs
			if(lcs_temp>lcs)
			{
				lcs=lcs_temp;
			}	
		}
	}
	return lcs;
}

题目6：字符串中单词翻转

给定输入-> "I have 36 books, 40 pens2 ,输出->"I evah 36 skoob, 40 2snep""

解题分析:
每个以空格或符号为间隔的单词逆向输出，如果遇到纯数字，则不改变顺序。自然而然地，每次处理分为两个步骤 1)判断是否需要逆向 2)逆向当前单词。这样就可以分为两个子函数：一个负责判断，另一个负责逆向，然后进行分段处理。

bool isPunctuationOrSpace(char* character)
{
	return *character == ' ' || *character== ',' || *character == '.';
}

bool isNumber(char* character)
{
	return *character>='0' && *character <='9';
}

bool needReverse(char* sentence,int* offset)
{
	int length=(int)strlen(character);
	bool needReverse=false;
	*offset=0;
	while(!isPunctuationOrSpace(sentence +(*offset))&&(*offset)
		if(!isNumber(sentence+(*offset)))
		{
			needReverse = true;
		}
		(*ffset)++
	}
	return needReverse;
}

void reverse(char* word,int length)
{
	int i=0,j=length-1;
	while(i
		swap(*(word+i),*(word+j))
		{
			i++;
			j--;
		}
	}
}

void reverseSentence(char* sentence)
{
	int length=(int)strlen(sentence);
	int offset;
	for(int i=0;i
		if(needReverse(sentence+i,&offset))
		{
			reverseWord(sentence+i,offset);
		}
		i +=(offset+1);
	}
}

题目7：Rotate String

Given a string and an offset,rotate string by offset (rotate from left to right)
Example
Give “abcdefg”
for offset=0, return “abcdefg”
for offset=1, return “gabcdef”

public Solution
{
	public:
		string rotateString(string A,int offset)
		{
			if(A.empty() || A.size()==0)
			{
				return A;
			}
			int len=A.size();
			offset %=len;
			reverse(A,0,len-offset-1);
			reverse(A,len-offset,len-1);
			reverse(A,0,lem-1);
		}
	private：
		void reverse(string &str,int start,int end)
		{
			while(start < end)
			{
				char temp=str[start]
				str[start]=str[end]
				str[end]=temp;
				start++;
				end--;
			}
		}	
}

题目8：删除数组中指定元素

给定一个数组和要删除的值，删除数组中该值的所有值，返回数组新的长度

例如：
给定一个数组[0,4,4,0,0,2,4,4] ,要删除的值为4 ,返回最终剩余的元素的个数为4，和新的数组[0,0,0,2]

int removeElement(vector&A,int elem)
{
	for(vector::iterator iter=A.begin();iter
		if(*iter==elem)
		{
			iter=A.erase(iter);   //利用erase删除元素后，会返回下一个元素的迭代器
			--iter
		}
	}
	return A.size();
}

题目8：移除数组中重复的元素

给定一个排序好的数组，移除重复的元素，使得每个元素都是唯一的，并返回数组新的长度。

思路：对于一个数组而言，我们可以通过类似于两个指针的形式求解。初始时，第一个指针指向数组的第一个数字，第二个指针指向数组的第二个数字。如果两个数字不同，则第一个指针与第二个指针分别前进一位。例如：

 nums = { 1,2,3,3,3,3,4,5 };

初始时指针P1=1，指针P2=2

两者不同，所以分别进一位，将P2指针的数赋值给P1：

P1=2，指针P2=3

两者不同，所以分别进一位，将P2指针的数赋值给P1：

P1=3，指针P2=3

这时两个指针的数字相同，则第一个指针不动，第二个指针进一位：

P1=3，指针P2=3
…
直到:

P1=3，指针P2=4

两者不同，所以分别进一位，将P2指针的数赋值给P1：

P1=4，指针P2=5

两者不同，所以分别进一位，将P2指针的数赋值给P1：

P1=5，指针P2=null

因为已经走完了，所以程序跳出循环。

最后记录一下指针1走过了多少次再加一即得到了该数组中不同数字的个数了。

完整代码

int removeDuplicate(vectornums)
{
	if(nums.empty())
	{
		return 0;
	}
	int index=0;
	for(int j=1;j
		if(nums[index]!=nums[j])
		{
			index++;
			nums[index]=nums[j];
		}
	}
	return index+1;
	
}

题目9：合并两个排序好的Array

将两个排序好的数组，合并到新的数组
将数组B合并到数组A,，假设A有足够的空间

void mergeSortedArray(int A[],int m,int B[],int n)
{
	int index=m+n;
	while(m>0 && n>0)
	{
		if (A[m-1]>B[n-1])
		{
			A[--index]=A[--m];
		}
		else
		{
			A[--index]=B[--n];
		}
	}
	
	// m=0 n>0
	while(n>0)
	{
		A[--index]=B[--n];
	}
	
	// m>0 n=0
	while(m>0)
	{
		A[--index]=A[--m];
	}
}

题目9：将数组拆分为两个数组

给定一个数组有nums个整数，和一个整数k，将数组元素

c++练习(9)：数组和字符串

C/C++/C#相关栏目本月热门文章