141. 环形链表
思路：判断链表中是否有环是经典的算法问题之一。常见的解决方案有多种，其中最经典、有效的一种方法是使用 快慢指针（Floyd’s Cycle-Finding Algorithm）。
- 初始化两个指针：一个快指针（
fast）指向头节点的下一个节点（head->next），一个慢指针（slow）指向头节点（head)。 - 移动指针：
- 慢指针每次移动一步。
- 快指针每次移动两步。
- 判断环的存在：
- 如果链表中存在环，那么快指针和慢指针最终会在环中相遇。
- 如果链表没有环，快指针会遇到
NULL（链表的末尾）。
解答如下：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
//如果头指针为空或者下一个为空即链表只有一个元素
//那么这个链表就不是循环的
if(head == nullptr || head->next == nullptr ){
return false ;
}
ListNode* slow = head;
ListNode* fast = head->next;
//循环停止的条件是slow和fast指向同一个元素
//或者 fast或fast->next指向NULL
while(slow != fast){
if(fast == nullptr || fast->next == nullptr ){
return false ;
}
slow = slow->next ;
fast = fast->next->next ;
}
return true ;
}
};循环条件也可以改为其他的形式，或者使用do-while循环，使用do-while循环，则需要对fast和slow的初值进行更改：
//使用do-while循环
class Solution {
public:
bool hasCycle(ListNode *head) {
//如果头指针为空或者下一个为空即链表只有一个元素
//那么这个链表就不是循环的
if(head == nullptr || head->next == nullptr ){
return false ;
}
ListNode* slow = head;
ListNode* fast = head;
//循环停止的条件是slow和fast指向同一个元素
//或者 fast或fast->next指向NULL
do{
if(fast == nullptr || fast->next == nullptr){
return false ;
}
slow = slow->next ;
fast = fast->next->next ;
}while(slow != fast);
return true ;
}
};另外也可以将fast != nullptr && fast->next != nullptr放在外层：
class Solution {
public:
bool hasCycle(ListNode *head) {
//如果头指针为空或者下一个为空即链表只有一个元素
//那么这个链表就不是循环的
if(head == nullptr || head->next == nullptr ){
return false ;
}
ListNode* slow = head;
ListNode* fast = head;
//循环停止的条件是slow和fast指向同一个元素
//或者 fast或fast->next指向NULL
while(fast != nullptr && fast->next != nullptr){
//在循环中应首先移动指针，然后再检查 slow 和 fast 是否相等
slow = slow->next ;
fast = fast->next->next ;
if(slow == fast){
return true ;
}
}
return false ;
}
};524. 通过删除字母匹配到字典里最长单词
题目描述：给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串。
思路：开始自己想起来有点乱糟糟的，看了一下官方给的思路，然后理了一下。
在写的过程中，while块中的语句些的稍微复杂了一点，看了别人的代码后改了一下，原来是这样写的：完全按照想的逻辑,没有思考简化
while(m<slen){//只要还没将s搜索完就要继续搜索
if(s[m] == dictionary[i][d]){
d++;
m++;
} else{
m++;
}
}然后就是if块中的代码，写得乱糟糟的也，看了一下别人的代码，茅塞顿开，我写的时候在想，怎么才能顺利的存进去第一个满足要求的字符串，因为最开始没有目标字符串，怎么比较长度呢，后来知道使用默认构造函数 string ans; 定义一个 std::string 对象时，它会被初始化为一个空字符串，长度为0，所以可以这样直接比较。
基础薄弱脑袋空空
正确代码如下：
class Solution {
public:
string findLongestWord(string s, vector<string>& dictionary) {
int k = dictionary.size();//长度为4
int slen = s.length();//长度为8
string obj ;
for(int i = 0;i<k;i++){
//int cnt = 0;
//获得每一个元素的长度len
int len = dictionary[i].size();//例如第一个元素为ale，长度就为3
//下面判断该元素是不是字符串s的子元素
int m=0,d=0;
while(m<slen){//只要还没将s搜索完就要继续搜索
if(s[m] == dictionary[i][d]){
d++;
}
m++;
}
//cnt==len说明该字符串在字典中存在
if(d == len ){
if(len > obj.length()){
obj = dictionary[i];
//有点奇怪，为什么要加一个dictionary[i] < obj这个条件
//原题目中字母序最小的字母序最小的字符串是这个意思嘛
//比较相同长度的字符串的大小，输出小的作为最后的结果
} else if((len == obj.length()) && dictionary[i] < obj){
obj = dictionary[i] ;
} else{
obj = obj ;
}
}
}
return obj;
}
};
//csdn上的答案
/*class Solution {
public:
string findLongestWord(string s, vector<string>& dictionary) {
//处理
string ans;
int n = s.size();//字符串的长度
//auto& str : dictionary 是 C++11 引入的范围基 for 循环的一部分
//用于遍历容器 dictionary 中的每个元素，并使用 str 作为对每个元素的引用。
for (auto& str : dictionary)
{
int m = str.size();//dictionary中元素的长度
int i = 0, j = 0;
while (i < m && j < n)
{
if (str[i] == s[j]) i++;
j++;
}
//处理
if (i == m)
{
if (str.size() > ans.size())
{
ans = str;
}
else if (str.size() == ans.size() && str < ans)
{
ans = str;
}
}
}
return ans;
}
};*/
双指针问题告一小段落，前面还有几题写了但是没有记录，懒得再整理了力扣上留有痕迹
