242. 有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram" 输出: true
示例 2:
输入: s = "rat", t = "car" 输出: false
参考代码
#include<bits/stdc++.h> using namespace std; int arr[27]; bool isAnagram(string s, string t) { int temp,temp2; if(s.size()!=t.size()) { return false; } for(int i = 0; i<s.size(); i++) { temp = s[i]-'a'; temp2 = t[i]-'a'; arr[temp]++; arr[temp2]--; } for(int i = 0; i < 27; i++) { if(arr[i]!=0) { return false; } } return true; } bool isAnagram2(string s, string t) { if(s.size()!=t.size()) { return false; } sort(s.begin(),s.end()); sort(t.begin(),t.end()); if(s==t) { return true; } return false; } int main() { return 0; }
141. 环形链表
给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。
进阶：
你能用 O(1)（即，常量）内存解决此问题吗？
示例 1
输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1 输出：false 解释：链表中没有环。
题目分析:
参考代码:
#include<bits/stdc++.h> using namespace std; struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; bool hasCycle(ListNode *head) { ListNode *slow = head; ListNode *fast = head; while(fast!=NULL){ fast = fast->next; if(fast!=NULL){ fast = fast->next; }else{ continue; } slow = slow->next; if(fast==slow){ return true; } } return false; } int main() { return 0; }
21. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = [] 输出：[]
示例 3：
输入：l1 = [], l2 = [0] 输出：[0]
方法一
链表的基本使用.
参考代码:
#include<bits/stdc++.h> using namespace std; struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} }; // 链表的基本使用.. ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { // ListNode *head1 = new ListNode(-1,l1); // ListNode *head2 = new ListNode(-1,l2); ListNode *head3 = new ListNode(-1); ListNode *p = l1; ListNode *q = l2; ListNode *r = head3; while(p!=nullptr&&q!=nullptr) { if(p->val<=q->val) { r->next = p;//r的next指向小的节点. r = r->next;//r更新 p=p->next; }else{ r->next = q; r = r->next; q = q->next; } } if(p==nullptr) { r->next = q; } if(q==nullptr){ r->next = p; } // delete head1,head2; return head3->next; } int main() { return 0; }
方法2
递归
参考代码
#include<bits/stdc++.h> using namespace std; struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} }; // 链表的基本使用.. ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if(l1==nullptr) { return l2; } if(l2==nullptr) { return l1; } if(l1->val <= l2->val) { l1->next = mergeTwoLists(l1->next,l2); return l1;//下面的语句不会执行了 } else { l2->next = mergeTwoLists(l1,l2->next);//l1->val > l2->val return l2; } } int main() { return 0; } //merge(1,1): 1->4->5->null, 1->2->3->6->null // merge(2,1) 4->5->null, 1->2->3->6->null // merge(2,2) 4->5->null,2->3->6->null // merge(2,3) 4->5->null,3->6->null // merge(2,4) 4->5->null,6->null // merge(3,4) 5->null,6->null // merge(4,4) null,6->null // return l2: 6->null // return l1.next 5->6->null // return l1.next 4->5->6->next // return l2.next 3->4->5->6 // return l2.next-> 2->3->4->5->6 // return 12->next 1->2->3->4->5->6 //return l1->next = 1->1->2->3->4->5->6 return l1
203. 移除链表元素
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]
示例 2：
输入：head = [], val = 1 输出：[]
示例 3：
输入：head = [7,7,7,7], val = 7 输出：[]
题目分析
同上
参考代码:
#include<bits/stdc++.h> using namespace std; struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} }; ListNode* removeElements(ListNode* l, int val) { ListNode *head = new ListNode(-1,l); ListNode *p = head; while(p->next!=nullptr) { if(p->next->val=val) { p->next = p->next->next; } else { p = p->next; } } return head->next; } ListNode* removeElements2(ListNode* l, int val) { ListNode *head = new ListNode(-1,l); ListNode *p = head; ListNode *q = head; while(p->next!=nullptr) { p = p->next; if(p->val==val) { q->next = p->next; // q = q->next;// 如果相等,则q不用变化了.. } else { q = q->next; } } return head->next; } int main() { return 0; }
