LeetCode每日一题

欢迎来到Cefler的博客😁
🕌博客主页：折纸花满衣
🏠个人专栏：题目解析

---

160. 相交链表

原题链接:相交链表

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {vector<ListNode *> va,vb;ListNode * headA_tmp = headA,*headB_tmp = headB;while(headA_tmp!=nullptr){va.push_back(headA_tmp);headA_tmp = headA_tmp->next;}while(headB_tmp!=nullptr){vb.push_back(headB_tmp);headB_tmp = headB_tmp->next;}if(va.back()!=vb.back()) return nullptr;int i = va.size()-2, j = vb.size()-2;while(i>=0&&j>=0){if(va[i]!=vb[j])break;i--;j--;}return va[i+1];}
};

402. 移掉 K 位数字

原题链接:移掉 K 位数字

class Solution {
public:string minnum = "";void dfs(string num,string s,int begin,int len){if(s.size()==len){int num1 = std::atoi(s.c_str());int num2 = std::atoi(minnum.c_str());if(num1<num2)minnum = s;return;}for(int i = begin;i<num.size();i++){dfs(num,s+num[i],i+1,len);}}string removeKdigits(string num, int k) {// minnum = num;// string s = "";// int len = num.size() - k;// dfs(num,s,0,len);// minnum = to_string(atoi(minnum.c_str()));// return minnum;vector<char> stk;for(auto ch:num){while(stk.size()>0&&stk.back()>ch&&k){stk.pop_back();k--;}stk.push_back(ch);}while(k--){stk.pop_back();//将剩余没有pop掉的给pop}string ans = "";bool isLeadingZero = true;for (auto& digit: stk) {if (isLeadingZero && digit == '0') {continue;}isLeadingZero = false;ans += digit;}return ans == "" ? "0" : ans;}
};

141. 环形链表

原题链接: 环形链表

class Solution {
public:bool hasCycle(ListNode *head) {set<ListNode*> st;int sz = st.size();while(head){st.insert(head);if(sz==st.size()){return true;}sz = st.size();head = head->next;}return false;}
};

快慢指针：

class Solution {
public:bool hasCycle(ListNode* head) {if (head == nullptr || head->next == nullptr) {return false;}ListNode* slow = head;ListNode* fast = head->next;while (slow != fast) {if (fast == nullptr || fast->next == nullptr) {return false;}slow = slow->next;fast = fast->next->next;}return true;}
};

主持人调度

原题链接:主持人调度

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param schedule int整型vector<vector<>> * @return bool布尔型*/bool hostschedule(vector<vector<int> >& schedule) {// write code here//进行升序排序sort(schedule.begin(),schedule.end(),[](const vector<int>& v1,const vector<int>& v2){return v1[0]<v2[0];});int prev = schedule[0][1];for(int i = 1;i<schedule.size();i++){if(schedule[i][0]<prev)return false;prev = schedule[i][1];}return true;}
};

有效三角形的个数

原题链接: 有效三角形的个数

class Solution {
public:// int count = 0;// void dfs(vector<int> group,vector<int>& nums,int pos)// {//     if(group.size()==3)//     {//         if(group[0]+group[1]>group[2]&&group[0]+group[2]>group[1]&&group[1]+group[2]>group[0])//             count++;//         return;//     }//     for(int i = pos;i<nums.size();i++)//     {//         group.push_back(nums[i]);//         dfs(group,nums,i+1);//         group.pop_back();//     }// }int triangleNumber(vector<int>& nums) {// vector<int> group;// dfs(group,nums,0);// return count;//排序+二分查找int n = nums.size();sort(nums.begin(),nums.end());int res = 0;for(int i = 0;i<n;i++){for(int j = i+1;j<n;j++){int left = j+1,right = n-1,k = j;while(left<=right){int mid = (left+right)/2;if(nums[mid]<nums[i]+nums[j]){k = mid;left = mid + 1;}else{right = mid-1;}}res+=k-j;}}return res;}
};