前言
c/c++把常量字符串放到单独的一个内存区域。当几个指针赋值给相同的常量字符串时,他们实际上会指向相同的内存地址:
int main()
{
char str1[] = "hello world";
char str2[] = "helle world";
char* str3 = "hello world";
char* str4 = "hello world";
if(str1 == str2)
cout << "str1 and str2 are same.\n";
else
cout << "str1 and str2 are not same.\n";
if(str3==str4)
cout << "str3 and str4 are same.\n";
else
cout << "str3 and str4 are not same.\n";
return 0;
}
./main
str1 and str2 are not same.
str3 and str4 are same.
第一个不同是因为两个不同的数组地址;第二个相同是因为常量字符串在内存中只有一个拷贝,他们都指向同一地址。
- 替换空格
请实现一个函数,将一个字符串中的每个空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
- 解析:先计算增大串长后的长
newStrLength
,用指针2指向该位置,同时指针1指向未增长时串中字符的结尾'\0'
,从后遍历复制指针1、2上的字符。
class Solution {
public:
void replaceSpace(char *str,int length) {
if(str==nullptr || length<=0)
return;
int strLength=0, space=0;
//先求替换后的字符串大小
while(str[strLength]!='\0')
{
if(str[strLength]==' ')
++space;
++strLength;
}
//strLength指向终止符处
//增大后的串长
int newStrLength = strLength+2*space;
if (newStrLength > length)//length为该串总容量
return;
while(strLength>=0 && newStrLength>strLength)
{
if(str[strLength]==' ')
{
str[newStrLength--] = '0';
str[newStrLength--] = '2';
str[newStrLength--] = '%';
}
else
{
str[newStrLength--]=str[strLength];
}
--strLength;
}
}
};
19、正则表达式
请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符,而'*'表示它前面的字符可以出现任意次(包含0次)。 在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串"aaa"与模式"a.a"和"abaca"匹配,但是与"aa.a"和"ab*a"均不匹配
- 解:当遇到
*
的时候可以当做前面的字符(一个字符)出现了0次,也就是忽略*
直接前移2步,也可以当做出现n次,在原处待着不动,让str前移n步去比较;退出条件是看str是否为空且模式也为空就是匹配上,否则没有匹配上,递归的调用看各种情况下返回的是否有一个满足条件。
class Solution {
public:
bool match(char* str, char* pattern)
{
if(str==nullptr || pattern==nullptr)
return false;
return matchCore(str, pattern);
}
private:
bool matchCore(char* str, char* pattern)
{
//若同时结束对比为匹配
if(*str=='\0' && *pattern=='\0')
return true;
if(*str!='\0' && *pattern=='\0')
return false;
if(*(pattern+1)=='*')//若下一个字符为需要匹配的字符
{
//当前以及匹配
if(*pattern==*str || (*pattern =='.' && *str!='\0'))
{
//move on the next state || stay on current state || 向前移动2步,忽略一个‘*’匹配;
return matchCore(str+1, pattern+2) || matchCore(str+1,pattern) || matchCore(str, pattern+2);
}
else
//向前移动2步,忽略一个‘*’匹配;
return matchCore(str,pattern+2);
}
// 当前字符以及匹配,去往下面的字符;
if (*str==*pattern || (*pattern=='.' && *str!='\0'))
return matchCore(str+1, pattern+1);
return false;
}
};
38、字符串的排列
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
- 解析:第一个字符固定为i,剩下其他字符的全排列在后面;i的取值是整个字符串的取值,因此,每次交换头字符,还有后面字符串中的下一个字符;递归结束条件是该字符串已经找到;
class Solution {
public:
vector<string> Permutation(string str)
{
vector<string> result;
if(str.empty()) return result;
Permutation(str,result,0);
// 此时得到的result中排列并不是字典顺序,可以单独再排下序
sort(result.begin(),result.end());
return result;
}
void Permutation(string str,vector<string> &result,int begin)
{
if(begin == str.size()-1) // 递归结束条件:索引已经指向str最后一个元素时
{
if(find(result.begin(),result.end(),str) == result.end())
{
// 如果result中不存在str,才添加;避免aa和aa重复添加的情况
result.push_back(str);
}
}
else
{
// 第一次循环i与begin相等,相当于第一个位置自身交换,关键在于之后的循环,
// 之后i != begin,则会交换两个不同位置上的字符,直到begin==str.size()-1,进行输出;
for(int i=begin;i<str.size();++i)
{
swap(str[i],str[begin]);
Permutation(str,result,begin+1);
swap(str[i],str[begin]); // 复位,用以恢复之前字符串顺序,达到第一位依次跟其他位交换的目的
}
}
}
void swap(char &fir,char &sec)
{
char temp = fir;
fir = sec;
sec = temp;
}
};
链表
前言
- 内存分配不是在创建链表时一次完成的,而是每次添加一个节点是分配内存;因此没有闲置的内存,链表的空间效率比数组高。
- 指针的指针:
// Example program
#include <iostream>
#include <string>
#include<vector>
using namespace std;
int main()
{
int i=1;
int *pi = &i;
int **ppi = π
cout<<"*pi :" << *pi << endl;
cout<<"&pi :" << &pi << endl;
cout <<"*ppi :" << *ppi<<endl;
return 0;
}
*pi :1
&pi :0x70aa208f64e8
*ppi :0x70aa208f64e4
- 链表的尾部添加节点和删除值为某数的节点如下:
// Example program
#include <iostream>
#include <string>
#include<vector>
using namespace std;
struct ListNode
{
int value;
ListNode *pNext;
};
//pHead是二级指针,指向指针的指针
void AddToTail(ListNode** pHead,int value)
{
ListNode* pNew = new ListNode();
pNew->value = value;
pNew->pNext = nullptr;
//是否为根节点
if((*pHead)==nullptr)
{
//取出头指针指向当前新节点
*pHead = pNew;
}
else
{
ListNode *pNode=*pHead;
//通过指针链接新节点在尾部
while(pNode->pNext!=nullptr)
pNode = pNode->pNext;
pNode->pNext =pNew;
}
}
//删除某值元素
void RemoveNode(ListNode** pHead, int value)
{
if(pHead==nullptr || *pHead==nullptr)
return;
//指向要删除的元素标记指针
ListNode* pToBeDeleted = nullptr;
//判断是否删除位置在头结点
if((*pHead)->value == value)
{
//标记
pToBeDeleted = *pHead;
//新的头结点位置在下一个位置
*pHead=(*pHead)->pNext;
}
else
{
//根节点的地址
ListNode* pNode=*pHead;
while(pNode->pNext != nullptr
&& pNode->pNext->value!=value)
pNode=pNode->pNext;
//找到该元素的位置,为pNode的下一个位置
if(pNode->pNext!=nullptr && pNode->pNext->value==value)
{
//该元素位置下一个位置赋给pToBeDeleted
pToBeDeleted = pNode->pNext;
//删除元素前一个位置的pNext链接到删除元素的下一个位置;之后就可以安全的删除了
pNode->pNext = pNode->pNext->pNext;
}
}
//删除该标记指针
if(pToBeDeleted!=nullptr)
{
delete pToBeDeleted;
pToBeDeleted = nullptr; //避免出错,赋为空
}
}
int main()
{
ListNode *test;
ListNode** PP = &test;
AddToTail(PP, 20);
cout << test->value << endl;
AddToTail(PP, 30);
cout << test->pNext->value << endl;
RemoveNode(PP,20);
cout << test->value << endl;
return 0;
}
20
30
30
- 输入一个链表,按链表值从尾到头的顺序返回一个
ArrayList
。
class Solution {
public:
//递归求解,或者用栈来求解。
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> ans;
stack<ListNode*> st;
while(head!=nullptr)
{
st.push(head);
head = head->next;
}
while(!st.empty())
{
ans.push_back(st.top()->val);
st.pop();
}
return ans;
}
- 删除链表中重复的元素
在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1->2->5
class Solution {
public:
//需要三个指针前中后
ListNode* deleteDuplication(ListNode* pHead)
{
if(pHead==nullptr) return nullptr;
ListNode *pPreNode = nullptr; //前一个节点
ListNode *pNode = pHead; //当前节点
while(pNode!=nullptr)
{
ListNode * pNextNode = pNode->next;//重置为当前节点的下一节点
bool needDelete=false;
//下一节点和当前节点是否是重复的
if(pNextNode!=nullptr && pNode->val==pNextNode->val)
needDelete = true;
if(!needDelete)//没有重复,往下走
{
pPreNode = pNode;
pNode = pNode->next;
}
else //重复节点
{
//取出值,删除连续等于该值的节点
int value = pNode->val;
ListNode* pToBeDel = pNode;
//连续删除
while(pToBeDel != nullptr && pToBeDel->val == value)
{
pNextNode = pToBeDel->next;
delete pToBeDel;
pToBeDel = nullptr;
pToBeDel = pNextNode;
}
//确定是否是头结点
if(pPreNode == nullptr)
pHead = pNextNode;
else//删除之后重链接删除后的节点
pPreNode->next = pNextNode;
pNode=pNextNode;
}
}
return pHead;
}
};
- 输入一个链表,输出该链表中倒数第k个结点。
- 双指针开始走,第一个走到k-1步时,第二个开始从根节点走。判断链长是否有k,没有解返回。
class Solution {
public:
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
if(!pListHead || k==0) return nullptr;
ListNode* preListNode=nullptr;
ListNode* curListNode=pListHead;
//第一个指针走了k-1步,加上本身是一个位移,总共k位移,第二个指针开始从头结点走1步
for(unsigned i=1;i<k;++i)
{
if(curListNode->next!=nullptr)
{
curListNode=curListNode->next;
}
else //链表长度不足
{
return nullptr;
}
}
//开始走
preListNode = pListHead;
//下一个节点指针非空
while(curListNode->next!=nullptr)
{
curListNode=curListNode->next;
preListNode=preListNode->next;
}
return preListNode;
}
};
23.链表中环的入口节点
给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。
解:1. 确定链表是否有环;(设置一个走得快的指针是否能追上走得慢的指针;)
2. 环的大小是多少;
3. 快指针先走环的大小步数,慢指针再走,必然在环的入口处相遇。
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead)
{
//meetingnode返回该链表是否有环,有的情况下,返回快慢指针相遇的节点
ListNode* ListMeetNode=MeetingNode(pHead);
if(ListMeetNode==nullptr)
return nullptr;
int countLoop=1;
ListNode* pNode = ListMeetNode;
while(pNode->next!=ListMeetNode)
{
countLoop++;
pNode=pNode->next;
}
pNode=pHead;
ListNode *slowNode=pHead;
//先走k-1步
for(int i=0;i<countLoop;++i)
{
pNode=pNode->next;
}
while(pNode!=slowNode)
{
pNode=pNode->next;
slowNode=slowNode->next;
}
return slowNode;
}
private:
ListNode* MeetingNode(ListNode* head)
{
if(head == nullptr)//空链表的情况
return nullptr;
ListNode* pslow=head->next;
if(pslow==nullptr)//无环的情况
return nullptr;
ListNode* pfast=pslow->next;//快一步
while(pfast!= nullptr && pslow!=nullptr)
{
if(pfast==pslow)//有环
return pfast;
pslow = pslow->next;
pfast = pfast->next;
if(pfast!=nullptr)//多走一步
pfast=pfast->next;
}
return nullptr;
}
};
35、复杂链表的复制
输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)
- 解析:重复各个节点,然后关联新的重复节点的random,再然后重链接取出偶数链接的链表。
class Solution {
public:
//复制原始链表的任一节点N并创建新节点N',再把N'链接到N的后边
void CloneNodes(RandomListNode* pHead)
{
RandomListNode* pNode=pHead;
while(pNode!=NULL)
{
RandomListNode* pCloned=new RandomListNode(0);
pCloned->label=pNode->label;
pCloned->next=pNode->next;
pCloned->random=NULL;
pNode->next=pCloned;
pNode=pCloned->next;
}
}
//如果原始链表上的节点N的random指向S,则对应的复制节点N'的random指向S的下一个节点S'
void ConnectRandomNodes(RandomListNode* pHead)
{
RandomListNode* pNode=pHead;
while(pNode!=NULL)
{
RandomListNode* pCloned=pNode->next;
if(pNode->random!=NULL)
pCloned->random=pNode->random->next;
pNode=pCloned->next;
}
}
//把得到的链表拆成两个链表,奇数位置上的结点组成原始链表,偶数位置上的结点组成复制出来的链表
RandomListNode* ReConnectNodes(RandomListNode* pHead)
{
RandomListNode* pNode=pHead;
RandomListNode* pClonedHead=NULL;
RandomListNode* pClonedNode=NULL;
//初始化
if(pNode!=NULL)
{
pClonedHead=pClonedNode=pNode->next;
pNode->next=pClonedNode->next;
pNode=pNode->next;
}
//循环
while(pNode!=NULL)
{
pClonedNode->next=pNode->next;
pClonedNode=pClonedNode->next;
pNode->next=pClonedNode->next;
pNode=pNode->next;
}
return pClonedHead;
}
//三步合一
RandomListNode* Clone(RandomListNode* pHead)
{
CloneNodes(pHead);
ConnectRandomNodes(pHead);
return ReConnectNodes(pHead);
}
};
52、两个链表的第一个公共节点
输入两个链表,找出它们的第一个公共结点。
- 解: 方法1:对链表1中每一个节点,都遍历一遍链表2,复杂度为O(mn);m\n分别为两个链表的长度;
方法2:若中间某一个节点相同,之后剩下的节点都是一样的地址存在,因此结尾处都一样,
设置栈结构,从尾部排除,遇到不相等的元素时,之前的那个元素便是第一个相同的元素点,空间换时间
的O(m+N)空间换取时间为O(m+n);
方法3:先遍历两个链表得到最长链表的长度s1与短链表的长度s2,在最长链表上先移动s1-s2,再同时移动
链表1,2,且不断比较直到相等;
方法3的原因是:链表长度是,链表长度是,他们的公共部分长度是,那么不妨设长度更长,那么有:,那么与的公共部分至少在后面的长度还有这么长的时候才有可能。
public:
/*
*/
ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
if(!pHead1 || !pHead2) return nullptr;
ListNode *pDupHead1 = pHead1;
ListNode *pDupHead2 = pHead2;
int count1=0, count2=0;
while(pHead1)
{
count1++;
pHead1=pHead1->next;
}
while(pHead2)
{
count2++;
pHead2=pHead2->next;
}
if(count1>count2) //链表1最长
{
int lCount = count1 - count2;
while(lCount--)
pDupHead1=pDupHead1->next;
}
else
{
int lCount = count2 - count1;
while(lCount--)
pDupHead2 = pDupHead2->next;
}
while(pDupHead1 && pDupHead2 && (pDupHead1!=pDupHead2))
{
pDupHead1 = pDupHead1->next;
pDupHead2 = pDupHead2->next;
}
ListNode * pFirstCommonNode = pDupHead1;
return pFirstCommonNode;
}
};
50、第一个只出现一次的字符
在一个字符串(0<=字符串长度<=10000,全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1(需要区分大小写).
- :方法1:暴力求解,对当前每一个字符,搜索后面的真个字符串,复杂度是O(n^2);
方法2:哈希表:自建一个简单哈希表;
可以把哈希表设为256,因为char是8bit的类型,总共只有256个字符,
可以设置哈希表为负,第一次插入后为正,再次插入同样的字符,设为负,下次只有找出数组非负的位置便是对应的第一次出现的字符
class Solution {
public:
int FirstNotRepeatingChar(string str) {
if(str.empty()) return -1;
vector<int> arr(26*2,0);
for(auto i:str)
{
if('a'<=i && i<='z')
arr[int(i-'a')]+=1;
else
arr[int(i-'A')+26]+=1;
}
for(int j=0; j<str.size(); ++j)
{
int numj;
if('a'<=str[j] && str[j]<= 'z')
numj=int( str[j]-'a');
else
numj=int( str[j]-'A'+26);
if(arr[numj] == 1)
return j;
}
}
};
58、反转单词顺序字符串
牛客最近来了一个新员工Fish,每天早晨总是会拿着一本英文杂志,写些句子在本子上。同事Cat对Fish写的内容颇感兴趣,有一天他向Fish借来翻看,但却读不懂它的意思。例如,“student. a am I”。后来才意识到,这家伙原来把句子单词的顺序翻转了,正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行,你能帮助他么?
- 先反转整个串,再反转每一个单词;
class Solution {
public:
string ReverseSentence(string str) {
if(str.empty()) return str;
int begin=0,end=0;
reverse(str.begin(),str.end());
int size = str.size();
while(begin<size)
{
//起点为空,重置游标
while(begin<size && str[begin]==' ') begin++;
end=begin;
//终点不为空,一直往前走到头
while(end<size && str[end]!=' ') end++;
reverse(str.begin()+begin, str.begin()+end);
//反转之后,起点的顺序是重点的顺序
begin = end;
}
return str;
}
};
2。左旋转字符串
字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果,即“XYZdefabc”。是不是很简单?OK,搞定它!
- 先翻转这个串的前后两部分,然后再全部一次性翻转
class Solution {
public:
string LeftRotateString(string str, int n) {
if(str.empty() || n<=0) return str;
reverse(str.begin(),str.begin()+n);
reverse(str.begin()+n,str.end());
reverse(str.begin(),str.end());
return str;
}
};
67、将一个字符串转换成一个整数
将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能,但是string不符合数字要求时返回0),要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0。
public:
int StrToInt(string str) {
long long int num = 0;
if(str.empty()) return num;
int minus;
if(str[0] == '+')
minus = 1;
if(str[0] == '-')
minus = -1;
int i;
if(str[0]!='+' && str[0]!='-') i=0;
else i=1;
for(;i<str.size();++i)
{
if(str[i]>='0' && str[i]<='9')
{
num = num * 10 + minus * (str[i]-'0');
}
else
{
num = 0;
break;
}
}
return (int)num; //类型转换
}
};
50、字符流中第一个出现的字符
方法1:用常规方法来解:
class Solution
{
public:
//Insert one char from stringstream
string str;
//全部初始化为0
int hash[256]= {0};
void Insert(char ch)
{
str+=ch;
hash[ch]++;
}
//return the first appearence once char in current stringstream
char FirstAppearingOnce()
{
int size = str.size();
for(int i=0; i<size; ++i)
{
if(hash[str[i]]==1)
return str[i];
}
return '#';
}
};
方法2:用stl来解:
class Solution
{
public:
//Insert one char from stringstream
string str;
map<char,int> m; //用map来记录字符出现的次数
void Insert(char ch)
{
str += ch;
m[ch]++;
}
//return the first appearence once char in current stringstream
char FirstAppearingOnce()
{
for(auto it : str)
{
if(m[it] == 1)
{
return it;
}
}
return '#';
}
};
、请实现一个函数用来判断字符串是否表示数值(包括整数和小数)。例如,字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。
class Solution {
public:
bool isNumeric(char* str) {
// 标记符号、小数点、e是否出现过
bool sign = false, decimal = false, hasE = false;
for (int i = 0; i < strlen(str); i++) {
if (str[i] == 'e' || str[i] == 'E') {
if (i == strlen(str)-1) return false; // e后面一定要接数字
if (hasE) return false; // 不能同时存在两个e
hasE = true;
} else if (str[i] == '+' || str[i] == '-') {
// 第二次出现+-符号,则必须紧接在e之后
if (sign && str[i-1] != 'e' && str[i-1] != 'E') return false;
// 第一次出现+-符号,且不是在字符串开头,则也必须紧接在e之后
if (!sign && i > 0 && str[i-1] != 'e' && str[i-1] != 'E') return false;
sign = true;
} else if (str[i] == '.') {
// e后面不能接小数点,小数点不能出现两次
if (hasE || decimal) return false;
decimal = true;
} else if (str[i] < '0' || str[i] > '9') // 不合法字符
return false;
}
return true;
}
};