• 【Leetcode热题】打卡day1——10

    目录

    1、两数之和 - 哈希表

    2、两数相加 - 链表

    3、无重复字符的最长子串 - 滑动窗口

    4、寻找两个正序数组的中位数 - 暴力合并两数组

    5、最长回文子串 - 中心扩展法 + dp动态规划

    （1）中心扩展法

    （2）dp

    6、三数之和 - 双指针 + 判重

    7、盛水最多的容器 - 思维 + 双指针

    8、电话号码的字母组合 - dfs + 组合

    9、删除链表的倒数第N个节点 - 链表 + 快慢指针 / 栈

    （1）暴力 计算链表长度

    （2）快慢指针

    （3）栈

    10、有效的括号 - 暴力 + 栈 + 哈希表

    （1）暴力+栈

    （2）哈希表+栈

    1、两数之和 - 哈希表

    1. 两数之和

    3fee9108bc5e423c8191a5c6c8ee1397.jpg

    思路：

    建立map，mp[nums[i]]=i 存储值所对应的下标

    顺序遍历每一个元素，先查找mp中是否存在与nums[i]匹配的值（target-nums[i]）

    如果存在，则返回【i，匹配值下标i】

    否则将该nums[i]存入map中

    为什么先查找，再存哈希表？

    因为题目要求，数组中同一元素不能重复出现，所以当遍历到自己时，先查找之前有没有存在的匹配值，再进行存储，这样避免了匹配到自己的情况

    1. class Solution {
    2.     public int[] twoSum(int[] nums, int target) {
    3.         Map mp = new HashMap<>();
    4.         for(int i=0; i < nums.length; i++ )
    5.         {
    6.             int t = target - nums[i];
    7.             if(mp.containsKey(t)) return new int[] {mp.get(t),i};
    8.             mp.put(nums[i],i);
    9.         }
    10.         return new int[] {};
    11.     }
    12. }
    1. class Solution {
    2. public:
    3.     vector<int> twoSum(vector<int>& nums, int target) {
    4.         int n=nums.size();
    5.         map<int,int> mp;
    6.         for(int i=0;i
    7.         {
    8.             int t=target-nums[i];
    9.             if(mp.find(t)!=mp.end())
    10.             return {i,mp.find(t)->second};
    11.             mp[nums[i]]=i;
    12.         }
    13.         return{};
    14.     }
    15. };

    2、两数相加 - 链表

    2. 两数相加

    fd064709c3a045c9a924188aa0fed129.png

    思路：

    l1和l2指针顺序向后遍历两链表 

    如果指到非空节点，存下各位之和sum和进位数t

    注意：如果遍历到最后仍有进位，需要再在链表后新增节点

    1.  
    2. class Solution {
    3. public:
    4.     ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    5.         ListNode *head = nullptr,*tail = nullptr;
    6.         int t = 0;
    7.         while(l1||l2)
    8.         {
    9.             int x1 = l1? l1->val:0;
    10.             int x2 = l2? l2->val:0;
    11.             int sum = (x1+x2+t)%10;
    12.             t = (x1+x2+t)/10;
    13.             if(!head)
    14.                 head = tail = new ListNode(sum);
    15.             else{
    16.                 tail->next = new ListNode(sum);
    17.                 tail = tail->next;
    18.             }
    19.             if(l1) l1 = l1->next;
    20.             if(l2) l2 = l2->next;
    21.         }
    22.         if(t>0) tail->next = new ListNode(t);
    23.         return head;
    24.     }
    25. };
    1.  
    2. class Solution {
    3.     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    4.     ListNode dummy=new ListNode();
    5.     ListNode cur=dummy;
    6.     int t=0;
    7.     while(l1!=null||l2!=null||t>0)
    8.     {
    9.         if(l1!=null) t+=l1.val;
    10.         if(l2!=null) t+=l2.val;
    11.         cur=cur.next=new ListNode(t%10);
    12.         t=t/10;
    13.         if(l1!=null) l1=l1.next;
    14.         if(l2!=null) l2=l2.next;
    15.     }
    16.     return dummy.next;
    17.     }
    18. }

    3、无重复字符的最长子串 - 滑动窗口

    3. 无重复字符的最长子串

    7e7e5f2865a24db0ac43432a366076fa.png

    思路：

    用set判重，双指针实现滑动窗口

    用maxx更新最长长度

    如果窗口内出现重复元素，缩左边界，并将不在窗口内的字符删去，直至窗口内无重复元素

    即若窗口内无重复元素，向右增大窗口，并更新最大长度，直至出现重复元素，缩小窗口，最后滑窗遍历完整个字符串，取最大窗口长度

    1. class Solution {
    2. public:
    3.     int lengthOfLongestSubstring(string s) {
    4.     set<char> word;
    5.     int st=0,maxx=0;
    6.     for(int ed=0;ed
    7.     {
    8.         while(word.count(s[ed]))
    9.         {
    10.             word.erase(s[st]);
    11.             st++;
    12.             
    13.             if(!word.count(s[ed]))continue;
    14.         }
    15.         if(ed-st+1>maxx) maxx=ed-st+1;
    16.         word.insert(s[ed]);
    17.         cout<' '<
    18.     }
    19.     return maxx;
    20.     }
    21. };

    4、寻找两个正序数组的中位数 - 暴力合并两数组

    4. 寻找两个正序数组的中位数

    0620b1af82f444dc9933e7e159c7f700.png

    思路：

    暴力求解，没啥好说的，进阶的不想看 

    1. class Solution {
    2. public:
    3.     double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    4.     int m=nums1.size(),n=nums2.size();
    5.     cout<" "<
    6.     int t=m+n+10;
    7.     int arr[t];
    8.     
    9.     int l1=0,l2=0,cnt=0;
    10.     while(l1
    11.     {
    12.         if(nums1[l1]>nums2[l2]) arr[cnt++]=nums2[l2],l2++;
    13.         else arr[cnt++]=nums1[l1],l1++;
    14.     }
    15.     while(l1
    16.     while(l2
    17.     if((m+n)%2) return arr[(m+n-1)/2];
    18.     else return (arr[(m+n)/2]+arr[(m+n)/2-1])*1.0/2;
    19.     }
    20. };

    5、最长回文子串 - 中心扩展法 + dp动态规划

    最长回文子串

    759cf22fdadc4fdd9232525ca877968f.png

    常规暴力O(n^3) 会tle 

    （1）中心扩展法

    思路：

    枚举每一个字符s[i]，同时设置左右指针l=i-1，r=i+1，最长回文子串长度len

    如果该子串为回文串，会有如下三种情况：

    • 左指针和中心字符相等，len+1，例如：abaacb
    • 右指针和中心字符相等，len+1，例如：abcaab
    • 左指针和右指针字符相等，len+2，如：abcacb

    如果左右指针不越界，循环拓展以上三种情况，并实时更新最长回文子串长度

    因为遍历的是以每一个字符为中心扩展的情况，因此遍历完字符串，所有情况的子串情况也都考虑到了，时间复杂度O(n^2)

    1. class Solution {
    2. public:
    3.     string longestPalindrome(string s) {
    4.     
    5.     string res="";
    6.     int n=s.size();
    7.     
    8.     for(int i=0;i
    9.     {
    10.         int len=1;
    11.         int l=i-1,r=i+1;
    12.         while(l>=0 && s[l]==s[i])
    13.             len++,l--;
    14.         while(r
    15.             len++,r++;
    16.         while(l>=0 && r
    17.             len+=2,l--,r++;
    18.         if(len>res.size())
    19.             res=s.substr(l+1,len);
    20.         
    21.     }
    22.     return res;
    23.     }
    24.  
    25. };

    （2）dp

    思路：

    • dp[i][j]：表示区间范围[i,j]的子串是否是回文子串，如果dp[i][j]为true，否则为false
    • 初始化dp[i][i] = true，因为单个字符自己就是回文串

    只考虑s[i]和s[j]相等的情况，因为不相等根本就不可能为回文串（初始化dp全为false，所以只要把所有是回文串的情况标为true即可）

    dp是以小范围的状态去更新大范围的状态，因此需要用短子串去更新长子串

    dp[i][j]的状态取决于dp[i+1][j-1]，如果i和j中间就1个字符，那必然是回文串，即就是j-1-(i+1)+1<2，化简即为j - i < 3，也就是说j - i < 3的情况dp[i][j]必为true

    其他情况则用dp[i+1][j-1]来更新

    最后遍历所有dp情况，如果dp=true，则更新最长回文子串长度

    1. class Solution {
    2.     public String longestPalindrome(String s) {
    3.     int n=s.length();
    4.     if(n<2) return s;
    5.     
    6.     boolean[][] dp=new boolean[n][n];
    7.     int maxlen=1,st=0;
    8.     
    9.     for(int i=0;i
    10.         dp[i][i]=true;
    11.         
    12.     for(int j=1;j
    13.         for(int i=0;i
    14.         {
    15.             if(s.charAt(i)==s.charAt(j))
    16.             {
    17.                 if(j-i<3) dp[i][j]=true;
    18.                 else dp[i][j]=dp[i+1][j-1];
    19.             }
    20.             
    21.             if(dp[i][j] && j-i+1>maxlen)
    22.             {  
    23.                 st=i;
    24.                 maxlen=j-i+1;
    25.             }
    26.         }
    27.      
    28.      return s.substring(st,st+maxlen);
    29.     }
    30. }

    6、三数之和 - 双指针 + 判重

    15. 三数之和

    5afff048d5dd4a159c6dce3162e312e6.png

    这题难点是：不能出现重复情况

    思路：

    首先对数组进行升序排序，因为三数之和=0，排序后能更好地去掉不可能为0的方案

    遍历数组中每一个数作为第一个数x1

    • 如果x1>0，后面的数都比x1大，不可能有=0的方案存在
    • 如果遍历到的x1和前一个遍历过的元素值相同，则所生成的方案也是相同的，跳过
    • l 和 r 分别指向x1后的最前和最末尾元素，如果指向的三个之和=0则记录方案
    • 注意：如果s【l+1】和s【l】值一样，则需要跳过，因为s【l】作为x2的方案之前已经考虑过，而题目要求不能有重复情况，s【r】同理
    • （若两个数固定，剩下一个必固定，题目要求不能重复）
    • 如果三数之和sum>0，则r--
    • 如果sum<0，l++
    1. class Solution {
    2. public:
    3.     vectorint>> threeSum(vector<int>& nums) {
    4.     vectorint>> res;
    5.     int n=nums.size();
    6.     sort(nums.begin(),nums.end());
    7.     
    8.     if(n<3) return res;
    9.     
    10.     for(int i=0;i
    11.     {
    12.         if(nums[i]>0) continue;
    13.         if(i>0&&nums[i]==nums[i-1]) continue;
    14.         int l=i+1,r=n-1;
    15.         while(l
    16.         
    17.         int sum=nums[i]+nums[l]+nums[r];
    18.         
    19.         if(sum==0)
    20.         {
    21.             res.push_back({nums[i],nums[l],nums[r]});
    22.             while(l1]) l++; //去重
    23.             while(l-1]) r--;
    24.             l++,r--; //若两个数固定，剩下一个必固定，题目要求不能重复，因此移动双指针
    25.             
    26.         }else if(sum>0) r--;
    27.         else l++;
    28.         }
    29.     }
    30.     return res;
    31.     }
    32. };

    7、盛水最多的容器 - 思维 + 双指针

    11. 盛最多水的容器

    da8f94e83744437eac57683861a3d0f4.png

    思路：

    从两侧枚举板子
    因为装水的高度取决于短板
    若移动短板，则短板为min(h[i],h[j])，短板有可能变长，水体积可能增加
    若移动长板，就算长板更长，也无法改变水的体积，因此水体积减小(间距变小)，因此绝对不能移动长板 

    1. class Solution {
    2. public:
    3.     int maxArea(vector<int>& h) {
    4.  
    5.     // 从两侧枚举板子
    6.     // 因为装水的高度取决于短板
    7.     // 若移动短板，则短板为min(h[i],h[j]),短板有可能变长，水体积可能增加
    8.     // 若移动长板，就算长板更长，也无法改变水的体积，因此水体积减小(间距变小)，因此绝对不能移动长板
    9.     int i=0,j=h.size()-1;
    10.     int res=0;
    11.     
    12.     while(i
    13.     {
    14.         res= h[i]>h[j]?
    15.         max(res,(j-i)*h[j--]):max(res,(j-i)*h[i++]);
    16.     }
    17.     return res;
    18.     }
    19. };

    8、电话号码的字母组合 - dfs + 组合

    17. 电话号码的字母组合

    610598572e464b2e84869a1a416b46e8.png

    思路：

    【leetcode学习计划】算法入门（14 / 14）完结！_leetcode算法学习计划_Roye_ack的博客-CSDN博客

    这题就是dfs组合问题的升级版

    根据题意，digits长度就是每个组合的长度，我们可以枚举每一个位置的数字

    用哈希表存每个数字对应的字母

    如果每个位置都枚举完，则将该种情况存入答案

    1. class Solution {
    2. public:
    3.     vector tele={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    4.     vector res;
    5.     string t;
    6.     
    7.     void dfs(int pos,string digits)
    8.     {
    9.         if(pos==digits.size())
    10.         {
    11.             res.push_back(t);
    12.             return;
    13.         }
    14.         int num=digits[pos]-'0';
    15.         for(int i=0;isize();i++)
    16.         {
    17.             t.push_back(tele[num][i]);
    18.             dfs(pos+1,digits);
    19.             t.pop_back();
    20.         }
    21.     }
    22.     
    23.     vector letterCombinations(string digits) {
    24.     if(digits.size()==0) return res;
    25.     dfs(0,digits);
    26.     return res;
    27.     }
    28. };

    9、删除链表的倒数第N个节点 - 链表 + 快慢指针 / 栈

    19. 删除链表的倒数第 N 个结点

    fe0547ea3f1c421f9d96e3c232775356.jpg

    （1）暴力 计算链表长度

    移动到要删除的节点的前一个，然后将该节点指向待删除节点的下一个，实现节点删除

    1. class Solution {
    2. public:
    3.     ListNode* removeNthFromEnd(ListNode* head, int n) {
    4.     ListNode* dummy=new ListNode(0);
    5.     dummy->next=head;
    6.     ListNode* cur=head;
    7.     int len=0;
    8.     while(cur!=nullptr)
    9.     {
    10.         len++;
    11.         cur=cur->next;
    12.     }
    13.     
    14.     cur=dummy;
    15.     for(int i=0;i
    16.     {
    17.         cur=cur->next;
    18.     }
    19.     cout<val<
    20.     cur->next=cur->next->next;
    21.     return dummy->next;
    22.     }
    23. };

    （2）快慢指针

    • 定义快指针q和慢指针p，两者初始同时指向虚拟节点dummy
    • 先移动快指针q使pq间隔n个元素，随后同时移动pq指针，直至q指向链表末尾null，此时，p指针的下一个节点就是待删除节点
    1.  
    2. class Solution {
    3.     public ListNode removeNthFromEnd(ListNode head, int n) {
    4.         ListNode dummy=new ListNode(0);
    5.         dummy.next=head;
    6.         ListNode p=dummy,q=dummy;
    7.         for(int i=0;i1;i++)
    8.             q=q.next;
    9.         while(q!=null)
    10.         {
    11.             p=p.next;
    12.             q=q.next;
    13.         }
    14.         p.next=p.next.next;
    15.         return dummy.next;
    16.  
    17.     }
    18. }

    （3）栈

    删除倒数第n个节点，可以利用栈的特性，让所有元素都入栈，然后扔出栈中n个节点，此时栈顶元素就是待删除的节点的前一个，然后再执行删除节点操作

    1. class Solution {
    2. public:
    3.     ListNode* removeNthFromEnd(ListNode* head, int n) {
    4.         ListNode* dummy = new ListNode(0, head);
    5.         stack stk;
    6.         ListNode* cur = dummy;
    7.         while (cur) {
    8.             stk.push(cur);
    9.             cur = cur->next;
    10.         }
    11.         for (int i = 0; i < n; ++i) {
    12.             stk.pop();
    13.         }
    14.         ListNode* prev = stk.top();
    15.         prev->next = prev->next->next;
    16.         ListNode* ans = dummy->next;
    17.         delete dummy;
    18.         return ans;
    19.     }
    20. };

     

    10、有效的括号 - 暴力 + 栈 + 哈希表

    20. 有效的括号

    （1）暴力+栈

    1. class Solution {
    2.     public boolean isValid(String s) {
    3.     if(s.length()%2==1) return false;
    4.     Deque stk=new LinkedList<>();
    5.     for(int i=0;ilength();i++)
    6.     {
    7.         char c=s.charAt(i);
    8.         if(c=='('||c=='['||c=='{')
    9.             stk.push(c);
    10.          else if(c==')')
    11.          {
    12.              if(stk.isEmpty()||stk.peek()!='(') return false;
    13.              stk.pop();
    14.          }else if(c==']')
    15.          {
    16.              if(stk.isEmpty()||stk.peek()!='[') return false;
    17.              stk.pop();
    18.          }else if(c=='}')
    19.          {
    20.              if(stk.isEmpty()||stk.peek()!='{') return false;
    21.              stk.pop();
    22.          }
    23.     }
    24.     if(!stk.isEmpty()) return false;
    25.     return true;
    26.     }
    27. }

    （2）哈希表+栈

    1. class Solution {
    2. public:
    3.     bool isValid(string s) {
    4.     int n=s.size();
    5.     if(n%2) return false;
    6.     
    7.     stack<char> stk;
    8.     unordered_map<char,char> mp={
    9.         {')','('},
    10.         {']','['},
    11.         {'}','{'}
    12.     };
    13.     
    14.     for(int i=0;i
    15.     {
    16.         if(mp.count(s[i]))
    17.             if(stk.empty()||mp[s[i]]!=stk.top())
    18.             return false;
    19.             else stk.pop();
    20.         else stk.push(s[i]);
    21.     }
    22.     return stk.empty();
    23.     }
    24. };

  • 相关阅读:
    无法启动此程序，因为计算机中丢失msvcp140.dll的修复方法与解决方法
    cesium 实体无法拾取
    认真过一遍webpack
    什么是单片机？聊聊它的历史
    数据分析和可视化平台：Splunk Enterprise for mac v9.1.1激活版 兼容m1
    Java通过javacv获取视频、音频、图片等元数据信息（分辨率、大小、帧等信息）
    史上最简单的Terraform教程不浪费时间
    【ClickHouse 基础】
    这个Spring Security登录插件牛啊，验证码、小程序、OAuth2都能快速接入
    【Linux】Docker安装
  • 原文地址：https://blog.csdn.net/weixin_61639349/article/details/132964391