53 表示数值的字符串
题目描述
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100”,”5e2”,”-123”,”3.1416”和”-1E-16”都表示数值。 但是”12e”,”1a3.14”,”1.2.3”,”+-5”和”12e+4.3”都不是。
示例1
输入：
返回值：
示例1
输入：
返回值：
思路：
设置3个标志位检查数字，小数点和e是否出现
当前字符是数字，isNum=true
当前字符是小数点，那么只有小数点第一次出现且小数点前面没有e的时候isPoint=true。
当前字符是e，只有前面出现过数字时e才能标为true，然后isNum要置为false，防止123e这种输入出现
‘+’和‘-’只能在字符串首为和e后面出现
去掉字符串前后的空格
其他情况均为非法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public:
bool isNumeric(string str) {
bool isNum=false,isPoint=false,ise=false;
int l=0,start=0;
while(str[l]==' ')l++;
start=l;
for(l;l<str.size();l++){
if(str[l]<='9'&&str[l]>='0')isNum=true;
else if(!isPoint&&str[l]=='.'&&!ise)isPoint=true;
else if(isNum&&!ise&&(str[l]=='e'||str[l]=='E')){
isNum=false;
ise=true;
}
else if((l==start||str[l-1]=='e'||str[l-1]=='E')&&(str[l]=='+'||str[l]=='-'))
continue;
else {
while(str[l]==' ')l++;
if(l==str.size())break;
return false;
}
}
return isNum;
}
};
|
54 字符流中第一个不重复的字符
题目描述
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符”go”时，第一个只出现一次的字符是”g”。当从该字符流中读出前六个字符“google”时，第一个只出现一次的字符是”l”。
思路：
用string保存输入的字符，用unordered_map记录每个字符出现的次数，遍历字符串返回第一个只出现一次的字符
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include<unordered_map>
class Solution
{
public:
unordered_map<char, int> map;
string s;
void Insert(char ch) {
s+=ch;
map[ch]++;
}
char FirstAppearingOnce() {
for(auto c:s){
if(map[c]==1)return c;
}
return '#';
}
};
|
55 链表中环的入口节点
题目描述
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
思路：
设置快慢指针，slow=slow->next;fast=fast->next->next;若链表包含环，则两个指针一定会在环内相遇。
相遇以后将一个指针指向链表头，从链表头和相遇的位置同时出发，每次走一步，再次相遇时刚好在入口。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead) {
ListNode* slow=pHead,*fast=pHead;
while(fast->next&&fast){
slow=slow->next;
fast=fast->next->next;
if(slow==fast)break;
}
if(!fast->next||!fast)return nullptr;
slow=pHead;
while(slow!=fast){
slow=slow->next;
fast=fast->next;
}
return slow;
}
};
|
56 删除链表中重复的结点
题目描述
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
示例1
输入：
返回值：
思路：
设置两个指针，若重复则指向下一位置，把不重复的结点接入结果链表。设置pre表示前一个节点，当fast指向空时判断slow是否为空且值与pre是否相等，决定其加不加入结果链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
class Solution {
public:
ListNode* deleteDuplication(ListNode* pHead) {
if(!pHead||!pHead->next)return pHead;
ListNode* slow=pHead,*fast=pHead->next,head(0);
ListNode* h=&head,*pre;
while(fast&&slow){
if(slow->val!=fast->val){
h->next=slow;
h=h->next;
slow=slow->next;
fast=fast->next;
}
else{
h->next=nullptr;
pre=fast;
slow=fast->next;
if(slow)
fast=slow->next;
}
}
if(slow&&pre->val!=slow->val)h->next=slow;
return head.next;
}
};
|
57 二叉树的下一个结点
题目描述
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
思路：
先找到根结点root，从根节点中序遍历，找到pNode的下一个结点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
class Solution {
public:
TreeLinkNode* GetNext(TreeLinkNode* pNode) {
TreeLinkNode* root=pNode;
while(root->next)root=root->next;
TreeLinkNode *res=nullptr;
bool find=false;
dfs(root,pNode,find,res);
return res;
}
void dfs(TreeLinkNode* root,TreeLinkNode* pNode,bool& find,TreeLinkNode*& res){
if(res)return;
if(root->left)dfs(root->left,pNode,find,res);
if(find){
res=root;
find=false;
return;
}
if(root==pNode)find=true;
if(root->right)dfs(root->right,pNode,find,res);
}
};
|
