• 双指针算法

    笔记来源：

    LeetCode 101: A LeetCode Grinding Guide (C++ Version)
    作者：高畅 Chang Gao

    1.简介

     2.和的问题——

    167. Two Sum II - Input array is sorted (Easy)

    题解

            因为数组已经排好序，我们可以采用方向相反的双指针来寻找这两个数字，一个初始指向最 小的元素，即数组最左边，向右遍历；一个初始指向最大的元素，即数组最右边，向左遍历。
    重点：
            如果两个指针指向元素的和等于给定值，那么它们就是我们要的结果。如果两个指针指向元 素的和（只能是和，不能是积，但平方和是可以的）小于给定值，我们把左边的指针右移一位，使得当前的和增加一点。如果两个指针指向元 素的和大于给定值，我们把右边的指针左移一位，使得当前的和减少一点。
    这个就当定理记下来，下一段的证明也不必太太懂。
            
    可以证明，对于排好序且有解的数组，双指针一定能遍历到最优解。证明方法如下：假设最
    优解的两个数的位置分别是 l 和 r。我们假设在左指针在 l 左边的时候，右指针已经移动到了 r； 此时两个指针指向值的和小于给定值，因此左指针会一直右移直到到达 l。同理，如果我们假设 在右指针在 r 右边的时候，左指针已经移动到了 l；此时两个指针指向值的和大于给定值，因此 右指针会一直左移直到到达 r。所以双指针在任何时候都不可能处于 (l,r) 之间，又因为不满足条 件时指针必须移动一个，所以最终一定会收敛在 l 和 r。 
    1. vector<int> twoSum(vector<int>& numbers, int target) {
    2.     int l = 0, r = numbers.size() - 1, sum;
    3.     while (l < r) {
    4.         sum = numbers[l] + numbers[r];
    5.         if (sum == target) break;
    6.         if (sum < target) ++l;
    7.         else --r;
    8.     }
    9.     return vector<int>{l + 1, r + 1};
    10. }

    633. Sum of Square Numbers (Easy)

     这里困难主要是一个开根要想到，然后这个数字太大溢出也要想到。

    1.  
    2. class Solution {
    3. public:
    4.     //这个思路没有问题，也利用了定理，但是看到平方就要对越界敏感，这个Int d明显装不下呀，long也不行，的long long但是这样
    5.     //太费空间，所以这里关注一个常用操作：减法！！！
    6.     bool judgeSquareSum(int c) {
    7.         int a = 0;
    8.         int b = sqrt(c);
    9.         while (a <= b) {
    10.             int d = a * a + b * b;
    11.             if ( d == c) {
    12.                 return true;
    13.             }
    14.             else if (d < c) {
    15.                 ++a;
    16.                 continue;
    17.             }
    18.             else {
    19.                 --b;
    20.                 continue;
    21.             }
    22.         }
    23.         return false;
    24.     }
    25.  
    26.     bool judgeSquareSum2(int c){
    27.         int a = 0;
    28.         int b = sqrt(c);
    29.         while (a <= b) {
    30.             if (c - a * a < b * b) {
    31.                 --b;
    32.                 continue;
    33.             }
    34.             else if (c - a * a > b * b) {
    35.                 ++a;
    36.                 continue;
    37.             }
    38.             else {
    39.                 return true;
    40.             }
    41.         }
    42.         return false;
    43.     }
    44.  
    45.  
    46.  
    47. };
    48.

    680. Valid Palindrome II (Easy)

     难点在于第一次要删除时，怎么判断能否成为回文串，双指针是比较明显的

    1. class Solution {
    2. public:
    3.     //这道简单题居然一时做不出来，因为我被双指针限制了，这里双指针太明显，其实不是重点，而是
    4.     //我们要想到删除这一个难点，我们需要分析出来，需要第一次删除时，
    5.     //此时子串范围为(i+1, j)或(i, j-1)的俩子串只要有任意一个是回文串，则结果就是回文串，否则就不是。
    6.     bool isVaild(string s, int low, int high) {
    7.         while (low < high) {
    8.             if (s[low] != s[high]) {
    9.                 return false;
    10.             }
    11.             ++low;
    12.             --high;
    13.         }
    14.         return true;
    15.     }
    16.  
    17.     bool validPalindrome(string s) {
    18.         int low = 0;
    19.         int high = s.size() - 1;
    20.         bool flag = 0;
    21.         while (low < high) {
    22.             if (s[low] == s[high]) {
    23.                 ++low;
    24.                 --high;
    25.                 continue;
    26.             }
    27.             else {
    28.                 return isVaild(s, low + 1, high) || isVaild(s, low, high - 1);
    29.             }
    30.         }
    31.         return true;
    32.  
    33.  
    34.     }
    35. };

    3.归并的问题——

    88. Merge Sorted Array (Easy)

     记录本人做题时遇到的问题和思考：

     //法一从后往前，每次把比较大的选出来，这样子只要关注索引为0的问题，不需要像从前往后一样
     //关注被覆盖的问题，比如nums1[0]>nums2[0],那么nums1[0]=nums2[0],原来的nums1[0]就被覆盖了，在后面没法参与比较了（因为都要放到Nums1里面）

    1.  void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    2.  
    3.         int pos = n + m - 1;
    4.         n = n - 1;
    5.         m = m - 1;
    6.         while (pos >= 0) {
    7.             if (m < 0) {
    8.                 nums1[pos--] = nums2[n--]; continue;
    9.             }
    10.             if (n < 0) {
    11.                 nums1[pos--] = nums1[m--]; continue;
    12.             }
    13.  
    14.             if (nums1[m] > nums2[n]) {
    15.                 nums1[pos--] = nums1[m--];
    16.       
    17.             }
    18.             else {
    19.                 nums1[pos--] = nums2[n--];
    20.  
    21.             }  
    22.         }
    23.     }

    法二：

    1. void merge2(int nums1[], int m, int nums2[], int n)
    2. {
    3.     int p = m-- + n-- - 1;
    4.     while (m >= 0 && n >= 0) {
    5.         nums1[p--] = nums1[m] > nums2[n] ? nums1[m--] : nums2[n--];
    6.     }
    7.     while (n >= 0) {
    8.         nums1[p--] = nums2[n--];
    9.     }
    10. }

    524. Longest Word in Dictionary through Deleting (Medium)

     这不难，但是高效的方法可能要想一下

    1. class Solution {
    2. public:
    3.     bool isContain(string s, string t) {
    4.         int i = 0;
    5.         int j = 0;
    6.         if (s.size() < t.size())return false;
    7.         for (; i < s.size(); ++i) {
    8.             if (j == t.size()) {
    9.                 return true;
    10.             }
    11.             if (s[i] == t[j]) {
    12.                 j++;
    13.             }
    14.         }
    15.         if (j == t.size()) {
    16.             return true;
    17.         }
    18.         return false;
    19.  
    20.     }
    21.  
    22.  
    23.     string findLongestWord(string s, vector& dictionary) {
    24.         int max_size = 0;
    25.         int pos = -1;
    26.         for (int i = 0; i < dictionary.size(); ++i){
    27.             if (isContain(s, dictionary[i])) {
    28.                 if (max_size < dictionary[i].size()) {
    29.                     max_size = dictionary[i].size();
    30.                     pos = i;
    31.                 }
    32.                 else if (max_size == dictionary[i].size()) {
    33.                     if (dictionary[i] < dictionary[pos]) {
    34.                         pos = i;
    35.                     }
    36.                 }
    37.             }
    38.         }
    39.         if (pos != -1) {
    40.             return dictionary[pos];
    41.         }
    42.         else {
    43.             return "";
    44.         }
    45.  
    46.     }
    47. };

    补充一个简洁c#版的

    1. public class Solution {
    2.     public string FindLongestWord(string s, IList<string> dictionary) {
    3.         string res = "";
    4.         foreach (string t in dictionary) {
    5.             int i = 0, j = 0;
    6.             while (i < t.Length && j < s.Length) {
    7.                 if (t[i] == s[j]) {
    8.                     ++i;
    9.                 }
    10.                 ++j;
    11.             }
    12.             if (i == t.Length) {
    13.                 if (t.Length > res.Length || (t.Length == res.Length && t.CompareTo(res) < 0)) {
    14.                     res = t;
    15.                 }
    16.             }
    17.         }
    18.         return res;
    19.     }
    20. }
    21.

    4.快慢指针——

    142. Linked List Cycle II (Medium)

     题解：

    对于链表找环路的问题，有一个通用的解法—— 快慢指针（ Floyd 判圈法） 。给 定两个指针， 分别命名为 slow 和 fast，起始位置在链表的开头。每次 fast 前进两步，slow 前进一步。如果 fast 可以走到尽头，那么说明没有环路；如果 fast 可以无限走下去，那么说明一定有环路，且一定存在一个时刻 slow 和 fast 相遇。当 slow 和 fast 第一次相遇时，我们将 fast 重新移动到链表开头，并让 slow 和 fast 每次都前进一步。当 slow 和 fast 第二次相遇时，相遇的节点即为环路的开始点。
    这也就当一个定理记下来！！ 
    1.  
    2. struct ListNode {
    3.     int val;
    4.     ListNode *next;
    5.     ListNode(int x) : val(x), next(NULL) {}
    6. };
    7.  
    8. class Solution {
    9. public:
    10.     //这里涉及一个数学上快慢指针定理，没办法，要记住哦
    11.     ListNode* detectCycle(ListNode* head) {
    12.         ListNode* slow = head, * fast = head;
    13.         // 判断是否存在环路
    14.         do {
    15.             if (!fast || !fast->next) return nullptr;
    16.             fast = fast->next->next;
    17.             slow = slow->next;
    18.         } while (fast != slow);
    19.         // 如果存在，查找环路节点
    20.         fast = head;
    21.         while (fast != slow) {
    22.             slow = slow->next;
    23.             fast = fast->next;
    24.         }
    25.         return fast;
    26.  
    27.     }
    28. };

    5.滑动窗口——

    76. Minimum Window Substring (Hard)

     这里映射的思想很重要！然后for里面的while也是很难写的。

    340. Longest Substring with At Most K Distinct Characters (Hard)

    题目描述：给定一个字符串 *s* ，找出 至多 包含 k 个不同字符的最长子串 *T*。

    输入: s = "eceba", k = 2
    输出: 3
    解释: 则 T 为 "ece"，所以长度为 3。

    输入: s = "aa", k = 1
    输出: 2
    解释: 则 T 为 "aa"，所以长度为 2。

    这个就比较明显，滑动窗口，先找到一个串，然后左端点动，破坏条件（使得kk 

    1. class Solution {
    2. public:
    3.     int lengthOfLongestSubstringKDistinct(string s, int k) {
    4.         int max_size = 0;
    5.         int l = 0;
    6.         int r = 0;
    7.         bool flag[128];//映射用的
    8.         int char_nums[128];
    9.         memset(char_nums, 0, sizeof(char_nums));
    10.         memset(flag, 0, sizeof(flag));
    11.         int cnt = 0;//记录长度
    12.         int kk = 0;//记录有没有超过k
    13.         for (; r < s.size(); ++r) {
    14.             if (flag[s[r]]) {
    15.                 ++cnt; 
    16.                 ++char_nums[s[r]];
    17.                 continue;
    18.             }
    19.             if (!flag[s[r]]) {
    20.                 while (kk == k) {
    21.                     if (cnt > max_size) {
    22.                         max_size = cnt;
    23.                     }
    24.                     if (--char_nums[s[l]] == 0) {
    25.                         --kk;
    26.                         flag[s[l]] = false;
    27.                     }
    28.                     ++l;
    29.                     --cnt;
    30.                 }
    31.                 
    32.                 ++cnt;
    33.                 ++kk;
    34.                 flag[s[r]] = true;
    35.                 ++char_nums[s[r]];
    36.       
    37.             }
    38.         }
    39.         return cnt;
    40.     }
    41.  
    42. };

    我上面用的是ASCII码的映射，下面的用的是哈希表+滑动窗口

    1. class Solution {
    2. public:
    3.     int lengthOfLongestSubstringKDistinct(string s, int k) {
    4.         if(k == 0) return 0;  	//k=0的话自然没有符合条件的子串
    5.         if(s.size() == 1) return 1;   //已经排除了k=0的情况，那么不管k等于多少长度都只有1
    6.         map<char,int> match;  //哈希表
    7.         int len = 0;  //长度
    8.         int kind = 0;  //不同字符的个数
    9.         int maxLen = 0;  //最大长度，最终返回的是这个
    10.         int start = 0,end = 0;   //双指针
    11.         
    12.         while(endsize()){
    13.             if(start == end){
    14.                 match[s[start]] ++; //该字母的个数++
    15.                 len++;   
    16.                 kind++; 
    17.                 end++; //右指针往右移动
    18.             }
    19.  
    20.             if(match[s[end]] == 0 && kind == k)  //遇到一个新的字符，且超出了k的限度，调整start
    21.             {
    22.                 maxLen = max(len,maxLen);  //保存目前的len
    23.                 match[s[start]] --; //该字母的个数--
    24.                 len--;  //长度--
    25.                 if(match[s[start]] == 0)kind--; //不同字符的个数--
    26.                 start++;  //左指针往右移动
    27.             }else //没到限度，调整end
    28.             {
    29.                 if(match[s[end]] == 0)kind++;  //遇到新字符
    30.                 match[s[end]]++;
    31.                 len++;
    32.                 end++;
    33.             }
    34.  
    35.             maxLen = max(len,maxLen);
    36.         }
    37.         return maxLen;
    38.     }
    39. };
    40.

    补充一个java版：

    1. class Solution {
    2.     public int lengthOfLongestSubstringKDistinct(String ss, int k) {
    3.         char[] s = ss.toCharArray();
    4.         Map map = new HashMap<>();
    5.         int n = s.length, l = 0, r = 0;
    6.         while(r
    7.             if(!map.containsKey(s[r])){
    8.                 map.put(s[r],0);
    9.             }
    10.             map.put(s[r],map.get(s[r])+1);
    11.             r++;
    12.             if(map.size()>k){
    13.                 map.put(s[l],map.get(s[l])-1);
    14.                 if(map.get(s[l]) == 0) map.remove(s[l]);
    15.                 l++;
    16.             }
    17.         }
    18.         return n-l;
    19.     }
    20. }

  • 相关阅读:
    vue的路由懒加载
    itbuilder软件在线设计数据库模型，AI与数据库擦出的火花
    MySQL下载和安装（Windows）
    platform和led中断项目
    arcgis 栅格数据处理2——栅格转地级市（栅格转矢量图）
    多线程(一)
    torch.torchvision
    【开发教程10】疯壳·开源蓝牙心率防水运动手环-蓝牙 BLE 收发
    贝叶斯定理，先验信念，似然，后验概率
    Python服务器监测测试策略与工具：确保应用的高可用性！
  • 原文地址：https://blog.csdn.net/keepstrivingchy/article/details/126727929