leetcode4.24-30

leetcode 4.24-4.30

4.24

5.最长回文子串 (双指针)

string longestPalindrome(string s) {
        string res;
        for(int i=0;i<s.length();i++){
            string s1=findson(s,i,i);
            string s2=findson(s,i,i+1);
            res=res.length()>s1.length()?res:s1;
            res=res.length()>s2.length()?res:s2;
        }
        return res;
    }
    string findson(string s,int l,int r){
        
        while(l>=0&&r<s.length()&&s[l]==s[r]){
            l--;
            r++;
        }
        return s.substr(l+1,r-l-1);
    }

从中间开始向外找，两端不相等时结束，

从中间往外又有两种情况，一种时123，的2，即奇数串的中间；另一种是1234的2，即偶数串的中间；

所以判断函数要有两个参数，奇数的时候参数相等，偶数的时候+1

链表

86 分隔链表

ListNode* partition(ListNode* head, int x) {
       ListNode* dummy1=new ListNode(-1);
       ListNode* dummy2=new ListNode(-1);
       ListNode* p1=dummy1,*p2=dummy2;
       ListNode* p=head;
       while(p){
           if(p->val<x){
           p1->next=p;
           p1=p1->next;
           }
           else{
               p2->next=p;
               p2=p2->next;
           }
           ListNode* temp=p->next;
           p->next=nullptr;
           p=temp;
       }
       p1->next=dummy2->next;
       return dummy1->next;

   }

23 合并K个升序链表

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode* res=nullptr;
        for(int i=0;i<lists.size();i++){
            res=mergetwolist(res,lists[i]);
        }
        return res;
    }
    ListNode* mergetwolist(ListNode* p1,ListNode* p2){
        ListNode* head=new ListNode(-1);
        ListNode* r=head;
        ListNode *ap=p1,*bp=p2;
        while(ap&&bp){
            if(ap->val<bp->val){
                head->next=ap;
                ap=ap->next;
            }
            else{
                head->next=bp;
                bp=bp->next;
            }
            head=head->next;
        }
        head->next=(ap==nullptr)?bp:ap;
        return r->next;
    }
};

用的比较原始的方法，先合并两个链表后，得到新的链表在继续与后面得链表合并，通过循环不断迭代

4.25

链表相交

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* cura=headA;
        ListNode* curb=headB;
        int la=0,lb=0;
        while(cura){
            la++;
            cura=cura->next;
        }
        while(curb){
            lb++;
            curb=curb->next;
        }
        cura=headA;
        curb=headB;
        int d=la>lb?la-lb:lb-la;
        if(la>lb)
        {
            while(d--){
                cura=cura->next;
            }
            while(cura&&curb){
                if(cura==curb)
                {
                    return cura;
                }
                cura=cura->next;
                curb=curb->next;
            }
        }
        else{
            while(d--){
                curb=curb->next;
            }
            while(cura&&curb){
                if(cura==curb)
                {
                    return cura;
                }
                cura=cura->next;
                curb=curb->next;
            }
        }
        return cura;
        
    }
};

143 环形链表||

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast=head;
        ListNode* slow=head;
        while(fast&&fast->next){
            fast=fast->next->next;
            slow=slow->next;
            if(fast==slow){
                break;
            }
        }
        if(fast==NULL||fast->next==NULL){
            return NULL;
        }
        slow=head;
        while(slow!=fast){
            slow=slow->next;
            fast=fast->next;
        }
        return slow;
    }
};

4.27

303 区域和检索 - 数组不可变

前缀和数组的方法

(这道题题目有些特殊，是设计一个类)

class NumArray {
public:
    NumArray(vector<int>& nums) {
        persum.resize(nums.size()+1);
        for(int i=1;i<persum.size();i++){
            persum[i]=persum[i-1]+nums[i-1];
        }

    }
    
    int sumRange(int left, int right) {
        return persum[right+1]-persum[left];
    }
private:
    vector<int> persum;
};

4.28

304 二维区域和检索 - 矩阵不可变

class NumMatrix {
private: vector<vector<int>> persum;
public:
    NumMatrix(vector<vector<int>>& matrix) {
      
        int m=matrix.size();
        int n=matrix[0].size();
        if(m==0||n==0) return;
        persum=vector<vector<int>> (m+1,vector<int>(n+1));
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                persum[i][j]=persum[i-1][j]+persum[i][j-1]+matrix[i-1][j-1]-persum[i-1][j-1];
            }
        }
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
    return persum[row2+1][col2+1]-persum[row1][col2+1]-persum[row2+1][col1]+persum[row1][col1];
    }
};

哈希表

1.有效的字母异位词

class Solution {
public:
    bool isAnagram(string s, string t) {
        unordered_map<char,int> a,b;
        for(int i=0;i<s.size();i++){
            a[s[i]]++;
        }
        for(int i=0;i<t.size();i++){
            b[t[i]]++;
        }
        if(a==b){
            return true;
        }
        else
        return false;

    }
};

4.29

哈希表

==什么时候使用哈希法 ：当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。==

349 两个数组的交集

这道题没看题解用了两个for循环，时间不是很理想，后来看来题解之后分析是没有用到哈希的思想

先上老版本

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res;
        int flag=1;
        for(int i=0;i<nums1.size();i++){
            for(int j=0;j<nums2.size();j++){
                if(nums1[i]==nums2[j]){
                    for(int k=0;k<res.size();k++){
                        if(res[k]==nums2[j]){
                            flag=0;
                            break;
                        }
                    }
                    if(flag) res.push_back(nums2[j]);
                }
                flag=1;
            }
        }
        return res;
    }
};

这道题目，主要要学会使用一种哈希数据结构：unordered_set，这个数据结构可以解决很多类似的问题。

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result_set; // 存放结果，之所以用set是为了给结果集去重
        unordered_set<int> nums_set(nums1.begin(), nums1.end());
        for (int num : nums2) {
            // 发现nums2的元素 在nums_set里又出现过
            if (nums_set.find(num) != nums_set.end()) {
                result_set.insert(num);
            }
        }
        return vector<int>(result_set.begin(), result_set.end());
    }

这道题给出了数值范围，因此之间用数组表示hash会更高效

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
            int a[1001]={0};
            vector<int>v;
            for(int j=0;j<nums1.size();j++){
                a[nums1[j]]=1;
            }
            for(int j=0;j<nums2.size();j++){
               if(a[nums2[j]]==1){
                   v.push_back(nums2[j]);
                   a[nums2[j]]++;           //通过+1的操作避免重复放入，而且直接用向量就行
               }
            }
            return v;
    }
};

202.快乐数

这道题很难和哈希想到一起去。参考了代码随想录的题解，解题的关键在于如果出现了无限循环，那么题目中的sum一定会重复出现，所以只要出现重复的sum，肯定进入了死循环，直接返回false;

class Solution {
public:
    bool isHappy(int n) {
        unordered_set<int> sum;
        while(1){
            if(getsum(n)==1){
                return true;
            }
            else{
                if(sum.count(getsum(n))){
                    return false;
                }
                else{
                    sum.insert(getsum(n));
                }
            }
            n=getsum(n);
        }
    }
    int getsum(int n){
        int sum=0;
        while(n){
            sum+=(n%10)*(n%10);
            n=n/10;
        }
        return sum;
    }
};

但是我有点疑惑，难道不进入循环最终一定能变成1吗 ？

于是我参考了力扣的官方题解

根据我们的探索，我们猜测会有以下三种可能。

1. 最终会得到 111。

2. 最终会进入循环。

3. 值会越来越大，最后接近无穷大。

   第三个情况比较难以检测和处理。我们怎么知道它会继续变大，而不是最终得到 111 呢？我们可以仔细想一想，每一位数的最大数字的下一位数是多少。

   Digits Largest Next
   1 9 81
   2 99 162
   3 999 243
   4 9999 324
   13 9999999999999 1053
   对于 3位数的数字，它不可能大于 243。这意味着它要么被困在 243以下的循环内，要么跌到 1。4 位或 4 位以上的数字在每一步都会丢失一位，直到降到 3位为止。所以我们知道，最坏的情况下，算法可能会在 243以下的所有数字上循环，然后回到它已经到过的一个循环或者回到 1。但它不会无限期地进行下去，所以我们排除第三种选择。

   ​

unordered_set用法

unordered_set 容器，可直译为“无序 set 容器”，即 unordered_set 容器和 set 容器很像，唯一的区别就在于 set 容器会自行对存储的数据进行排序，而 unordered_set 容器不会。

总的来说，unordered_set 容器具有以下几个特性：

1.不再以键值对的形式存储数据，而是直接存储数据的值；

2.容器内部存储的各个元素的值都互不相等，且不能被修改。（即天然去重）

3.不会对内部存储的数据进行排序（这和该容器底层采用哈希表结构存储数据有关）

1.声明：

unordered_set a

2.查找容器中是否有该元素

a.count(i) //i为查找的元素 如果元素存在于容器中，则此函数返回1，否则返回0。

find(key)	查找以值为 key 的元素，如果找到，则返回一个指向该元素的正向迭代器；反之，则返回一个指向容器中最后一个元素之后位置的迭代器
begin()	返回指向容器中第一个元素的正向迭代器
end()	返回指向容器中最后一个元素之后位置的正向迭代器
insert()	向容器中添加新元素
erase()	删除指定元素

梦开始的地方—-1.两数之和

第一次做力扣就是这题，用了双重for循环。现在再做，还是想不到别的做法，看了题解才知道这题也可以用哈希表做。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> map;
        for(int i=0;i<nums.size();i++){
            if(map.count(target-nums[i])){
                return {i,map[target-nums[i]]};
            }
            else{
                map[nums[i]]=i;
            }
        }
        return {};
    }
};

这道题用到数组，set,map中的map，选择unordered_map,因为涉及到数组的值和索引值，

map中的存储结构为 {key：数据元素，value：数组元素对应的下标}

遍历数组，找当前数值对应的值(target-nums[i])是否已经在map中，如果在就可以直接返回索引；不在的话就先把当前遍历的放入map，后续遍历到该值对应的就可以直接返回了。

4.30

哈希表

454.四数相加two

这道题用的解法是真的想不到，太绝了。

将两个数组相加可能得到的值放map中，该值表示key，出现次数为value，这样正好表示不同的索引的个数；然后再遍历后面两个数组值相加的情况，只要后面两个值相加的相反数在map中，那么map的value就是后面两个值固定时前面索引变化对应的为0的所有情况。

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int,int> add;
        int count=0;
        for(int a:nums1){
            for(int b:nums2){
                add[a+b]++;
            }
        }
        for(int c:nums3){
            for(int d:nums4){
                if(add.count(-c-d)){
                    count+=add[-c-d];
                }
            }
        }
        return count;
    }
};

4.30 23:57 五月你好，希望五月会更好。 by JasonWang