双指针
lc3
无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
示例 4:
输入: s = ""
输出: 0
提示：
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
需要两部分。
1.一个类似于map的机构，记录字符出现的位置。
2.双指针，移动。
如果重复的话，左指针移动到字符出现位置+1，字符出现位置更新为右指针在的位置，右指针再加1
这里判断是否出现过用asc[s[i]]>=left, 因为↑行为只更新重复字符出现位置，没有更新对应map中其它是否出现过的值，但左指针之前的已无比较价值，因此可以帮助排除。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
//字符有限制 hashset
int ans=0;
if(s.length()==0)
return ans;
int len=s.length();
// int z[len];
int asc[128];
memset(asc,-1,sizeof(asc));
// fill(z,z+s.length(),1);
int left=0;
int right=-1;
for(int i=0;i<len;i++){
if(asc[s[i]]>=left){
left=asc[s[i]]+1;
right+=1;
}else{
right+=1;
}
asc[s[i]]=i;
ans=max(ans,right-left+1);
// cout<<z[i]<<endl;
}
// sort(z,z+len);
return ans;
}
};
环形链表快慢指针
lc141&142
1.一个快指针，一次走两步，一个慢指针，一次走一步。
如果快能追上慢，则是环形链表。
2.找到环入口。
两者相遇后，一个指针放在头，一个指针放在相遇点，每次都走一步，则再次相遇点是环的入口。
对于这种问题，也可以用map来做，即map<ListNode*,int> 一个节点遍历，第一次发现重复出现的节点，就是环的入口。
方法1：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
//找到环的入口
ListNode * tmp;
if(!head||!head->next)
return NULL;
ListNode *fast=head->next->next;
ListNode *slow=head->next;
while(fast!=slow){
slow=slow->next;
if(fast&&fast->next)
fast=fast->next->next;
else
return NULL;
}
if(!fast)
return NULL;
ListNode *pre=fast;
ListNode *now=head;
while(now!=pre){
now=now->next;
pre=pre->next;
}
return now;
}
};
方法2：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
//找到环的入口
map<ListNode*,int> res;
ListNode* cur=head;
if(!cur){
return nullptr;
}
int index=0;
while(cur){
if(res.find(cur)==res.end())
res[cur]=1;
else{
return cur;
}
index+=1;
cur=cur->next;
}
return NULL;
}
};
lc26& lc19
https://www.jianshu.com/p/f1416af4cfde
挡板类问题（lc11&lc42)
https://www.jianshu.com/p/14952c22473a
对称二叉树（lc101）
判断二叉树是否是对称的
1.层次遍历，最好想，因为每次往队列里push left、right相反顺序的值就可。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isSymmetric(TreeNode* root) {
//一个右中左
//一个左中右
//得到两个vector，看看是否一致。1、大小是否一致。2、内容是否一致
//↑这样想是不对的。例子中某一个就不对。
if(!root)
return true;
queue<TreeNode*> t1;
queue<TreeNode*> t2;
t1.push(root);
t2.push(root);
while(!t1.empty()&&!t2.empty()){
TreeNode* tmp1;
TreeNode* tmp2;
tmp1=t1.front();
tmp2=t2.front();
t1.pop();
t2.pop();
//cout<<tmp1->val<<tmp2->val<<endl;;
if(tmp1->val!=tmp2->val)
return false;
if(tmp1->left&&tmp2->right){
t1.push(tmp1->left);
t2.push(tmp2->right);
}else if(!(!tmp1->left&&!tmp2->right))
return false;
if(tmp1->right&&tmp2->left){
t1.push(tmp1->right);
t2.push(tmp2->left);
}else if(!(!tmp1->right&&!tmp2->left))
return false;
}
if(!t1.empty()||!t2.empty())
return false;
return true;
// return checksym(root,root);
}
};
2.递归。
同时传入两个指针，这两个指针每次对比相反方向的值就可
↑这个一直没有转过来，一直没有想明白
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool checksym(TreeNode* leftnode,TreeNode*rightnode){
if(!leftnode&&!rightnode)
return true;
if(!leftnode||!rightnode)
return false;
return (leftnode->val==rightnode->val) && (checksym(leftnode->left,rightnode->right)) &&(checksym(leftnode->right,rightnode->left));
}
bool isSymmetric(TreeNode* root) {
//一个右中左
//一个左中右
//得到两个vector，看看是否一致。1、大小是否一致。2、内容是否一致
//↑这样想是不对的。
if(!root)
return true;
return checksym(root,root);
}
};
网友评论