1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target  的那 两个 整数,并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1:

输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。

示例 2:

输入:nums = [3,2,4], target = 6
输出:[1,2]

示例 3:

输入:nums = [3,3], target = 6
输出:[0,1]

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> m;
        for(int i=0;i<nums.size();i++)
        {
            auto ite=m.find(target-nums[i]);    //find()是找key,不是val,所以把值当成key,下标当成val
            if(ite!=m.end())
            {
                return{ite->second,i};
            }
            m[nums[i]]=i;
        }
        return{};
    }
};
  • 使用map查找时间复杂度为O(1)
  • map::find()函数查找的是key,而不是val]

2. 两数相加

给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。

请你将两个数相加,并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外,这两个数都不会以 0 开头。

示例 1:

输入:l1 = [2,4,3], l2 = [5,6,4]
输出:[7,0,8]
解释:342 + 465 = 807.
示例 2:

输入:l1 = [0], l2 = [0]
输出:[0]
示例 3:

输入:l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出:[8,9,9,9,0,0,0,1]

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *pre=new ListNode (0);
        ListNode *ls=pre;
        int add=0;
        int t;

        while(l1!=NULL||l2!=NULL)
        {
            int x=l1==NULL?0:l1->val;
            int y=l2==NULL?0:l2->val;
            int sum=x+y+add;
            if(sum>=10) 
            {
                add=1;
                sum-=10;
            }
            else add=0;
            ls->next=new ListNode(sum);
            if(l1!=NULL) l1=l1->next;
            if(l2!=NULL) l2=l2->next;
            ls=ls->next;
        }
        if(add==1)
        {
            ls->next=new ListNode (1);
        }

        return pre->next;
    }
  • 当l1或l2为空时,无l1->val,则用0占位
  • 巧用前置节点pre和当前节点ls,使ls=pre,操作ls,最后返回pre->next即可。
  • 注意判断最后一个节点的进位问题,如果需要进位则需要再创建一个新节点然后赋值为1

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

给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = “abcabcbb”
输出: 3 
解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。

示例 2:

输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。

示例 3:

输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”,所以其长度为 3。
     请注意,你的答案必须是 子串 的长度,“pwke” 是一个子序列,不是子串。

示例 4:

输入: s = “”
输出: 0

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> st;
        int n=s.size();
        int maxLen=1;
        if(s=="") return 0;
        
        int left=0;
        for(int i=0;i<n;i++)
        {
            while((st.find(s[i]))!=st.end())
            {
                st.erase(s[left]);
                left++;
            }
            maxLen=max(maxLen,i-left+1);
            st.insert(s[i]);
        }
        return maxLen;
    }
};
  • 滑动窗口,左指针,哈希集合
  • 用哈希集合存已经查找且没有重复的数据
  • 当遍历到哈希集合中存在的数据时,删除集合中左指针指向的数据,直到找不到重复的为止。

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

给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1:

输入:nums1 = [1,3], nums2 = [2]
输出:2.00000
解释:合并数组 = [1,2,3] ,中位数 2

示例 2:

输入:nums1 = [1,2], nums2 = [3,4]
输出:2.50000
解释:合并数组 = [1,2,3,4] ,中位数 (2 + 3) / 2 = 2.5

示例 3:

输入:nums1 = [0,0], nums2 = [0,0]
输出:0.00000

示例 4:

输入:nums1 = [], nums2 = [1]
输出:1.00000

示例 5:

输入:nums1 = [2], nums2 = []
输出:2.00000

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        vector<int> s;
        double ans;
        for(int i=0;i<nums1.size();i++)
        {
            s.push_back(nums1[i]);
        }
        for(int i=0;i<nums2.size();i++)
        {
            s.push_back(nums2[i]);
        }
        sort(s.begin(),s.end(  ));
        int l=0,r=0;
        if(s.size()%2==1)
        {
            while(r!=s.size()-1)
            {
                l++;
                r+=2;
            }
            ans=s[l];
        }
        else
        {
            if(s.size()==2)
            {
                return (s[l]+s[l+1])*1.0/2.0;
            }
            while(r!=s.size()-2)
            {
                
                l++;
                r+=2;
            }
            ans=(s[l]+s[l+1])*1.0/2.0;
        }
        return ans;
    }
};
  • 合并数组+排序
  • 时间复杂度O(m+n)
  • 空间复杂度O(m+n)

15. 三数之和

给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。

注意:答案中不可以包含重复的三元组。

示例 1:

输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]

示例 2:

输入:nums = []
输出:[]

示例 3:

输入:nums = [0]
输出:[]

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> vec;
        sort(nums.begin(),nums.end());
        int left,right;
        if(nums.size()<3) return vec;
        for(int i=0;i<nums.size();i++)
        {
            if(nums[i]>0) return vec;
            if(i>0&&nums[i]==nums[i-1]) continue;
            left=i+1;
            right=nums.size()-1;
            while(left<right)
            {
                int sum=nums[i]+nums[left]+nums[right];
                if(sum==0)
                {
                    vec.push_back({nums[i],nums[left],nums[right]});
                    while(left<right&&nums[left]==nums[left+1]) left++;
                    while(left<right&&nums[right]==nums[right-1]) right--;
                    left++;
                    right--;
                }
                else if(sum<0) left++;
                else if(sum>0) right--;
            }
        }
        return vec;
    }
};
  • 三循环——>单循环+双指针
  • 排序
  • 从i=0,left=i+1,right=n开始判断
  • 如果nums[i]大于0,因为排序是从小到大,得出nums[i]后面的数也大于0,所以sum肯定大于0,直接返回
  • 如果sum=0且nums[left]==nums[left+1]会产生重复值,则left++,right同理
  • if(i>0&&nums[i]==nums[i-1]) continue; 中的i>0的目的是防止数组越界访问,当i=0时,nums[i-1]会越界
  • 当sum>0时说明right大了,则right–,left同理

##17. 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

示例 1:

输入:digits = “23”
输出:[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]

示例 2:

输入:digits = “”
输出:[]

示例 3:

输入:digits = “2”
输出:[“a”,“b”,“c”]

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if(digits.size()==0) return {};
        unordered_map<int,string> m;
        vector<string> vec;
        m.insert({2,"abc"});
        m.insert({3,"def"});
        m.insert({4,"ghi"});
        m.insert({5,"jkl"});
        m.insert({6,"mno"});
        m.insert({7,"pqrs"});
        m.insert({8,"tuv"});
        m.insert({9,"wxyz"});
        queue<string> q;
        int num=digits[0]-'0';
        string temp=m.at(num);
        for(int i=0;i<temp.size();i++) 
        {
            string s=temp.substr(i,1);
            q.push(s);
        }
        for(int i=1;i<digits.size();i++)
        {
            int n=digits[i]-'0';
            string s=m.at(n);  
            while(q.front().size()<=i)
            {           
                for(int j=0;j<s.size();j++)
                {
                    string c=s.substr(j,1);
                    q.push(q.front()+c);
                }
                q.pop();
            }
        }
        while(!q.empty())
        {
            vec.push_back(q.front());
            q.pop();
        }
        return vec;        
    }
};
  • 队列法
  • 先把第一个数字对应的字母入队,从第二个数字开始,队首的字母再分别与第2个数字对应的字母组合,组合完毕后移出队列。
  • 到与第i个数字组合时,队首字符串的长度为i,组合完毕加入队列的字符串长度为i+1。所以当队首字符串长度大于i时,证明与当前数字对应的字母组合完毕
  • 循环下去,当队首字符串的长度<=i时(下标从0开始),循环继续。当队首字符串长度>i时,循环结束。

//以234举例 2->a b c //3->d e f //4->g h i

a b c

a b c ad ae af //与第1个数字3开始组合

b c ad ae af bd be bf …->

ad ae af bd be bf cd ce cf //因为队首字符串长度=2>1 所以更换下一个数字4,以此类推

ad ae af bd be bf cd ce cf adg adh adi …->

[“adg”,“adh”,“adi”,“aeg”,“aeh”,“aei”,“afg”,“afh”,“afi”,“bdg”,“bdh”,“bdi”,“beg”,“beh”,“bei”,“bfg”,“bfh”,“bfi”,“cdg”,“cdh”,“cdi”,“ceg”,“ceh”,“cei”,“cfg”,“cfh”,“cfi”] //最后结果

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

给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。

示例 1:

输入:head = [1,2,3,4,5], n = 2
输出:[1,2,3,5]

示例 2:

输入:head = [1], n = 1
输出:[]

示例 3:

输入:head = [1,2], n = 1
输出:[1]

遍历两次法

/**
 * 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* removeNthFromEnd(ListNode* head, int n) {
        ListNode*pre=head;
        ListNode*cur=head;
        int len=0;
        if(head->next==NULL) return NULL;
        while(head!=NULL)
        {
            head=head->next;
            len++;	//求链表长度
        }
        int num=len-n-1;
        if(n==1)	//倒数第一个节点为尾删除
        {
            while(num--)
            {
                cur=cur->next;
            }
            cur->next=NULL;
        }
        else if(n==len)	//第一个节点为头删除
        {
            return  pre->next;
        }
        else		//其他为中间删除
        {
            while(num--)
            {
                cur=cur->next;
            }
            cur->next=cur->next->next;
        }
        return pre;
    }
};

双指针法

/**
 * 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* removeNthFromEnd(ListNode* head, int n) {
        ListNode *pre=new ListNode(0);
        pre->next=head;
        ListNode*l=pre;
        ListNode *r=pre;
        while(n--)
        {
            r=r->next;
        }
        while(r->next!=NULL)
        {
            r=r->next;
            l=l->next;
        }
        l->next=l->next->next;
        return pre->next;;
    }
};
  • 在链表头结点之前new一个空间pre作为链表新头结点
  • 快指针先走n步,然后快慢指针同时走,直到快指针到达链表的最后一个节点(r->null==0)
  • 删除慢指针的下一个节点,即 l->next=l->next->next,返回pre->next即可

##20. 有效的括号
给定一个只包括 ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ 的字符串 s ,判断字符串是否有效。

有效字符串需满足:

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例 1:

输入:s = “()”
输出:true

示例 2:

输入:s = “()[]{}”
输出:true

示例 3:

输入:s = “(]”
输出:false

示例 4:

输入:s = “([)]”
输出:false

示例 5:

输入:s = “{[]}”
输出:true

class Solution {
public:
    bool isValid(string s) {
        if(s.size()%2!=0) return false;
        unordered_map<char,char> m;
        m['(']=')';
        m['{']='}';
        m['[']=']';
        stack<char> sk;
        for(int i=0;i<s.size();i++)
        {
            char c=s[i];
            auto ite=m.find(c);
            if(ite!=m.end())
            {
                sk.push(m[c]);
            }
            else
            {
                if(sk.empty()||sk.top()!=c) return false;
                else
                    sk.pop();
            }
        }
        if(sk.empty()) return true;
        return false;
    }
};
  • 辅助栈法
  • 遍历字符串,在map中查找
    • 当找到当前字符时,把当前字符对应的字符即m[c]入栈
    • 没找到时在栈顶找
      • 当栈顶为空时说明字符不匹配,返回FALSE
      • 当栈顶元素和当前查找字符不相等时,返回false
      • 当栈顶元素和当前查找字符相等时,说明当前字符匹配,,移出栈顶元素,继续匹配下一个字符
  • 当遍历完毕后,栈为空,则证明匹配完毕所有字符,返回true,否则返回FALSE

##21. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1:

输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]

示例 2:

输入:l1 = [], l2 = []
输出:[]

示例 3:

输入:l1 = [], l2 = [0]
输出:[0]

/**
 * 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* mergeTwoLists(ListNode* list1, ListNode* list2) {
        multiset<int> s;
        while(list1!=NULL)
        {
            s.insert(list1->val);
            list1=list1->next;
        }
        while(list2!=NULL)
        {
            s.insert(list2->val);
            list2=list2->next;
        }
        auto ite=s.begin();
        ListNode *cur=new ListNode(0);
        ListNode *pre=cur;
        while(ite!=s.end())
        {
            ListNode *cur1=new ListNode(*ite);
            cur->next=cur1;
            cur=cur->next;
            ite++;
        }
        return pre->next;
        
    }
};
  • 合并到multiset中,再遍历生成链表

法2

/**
 * 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* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list1==NULL)
        {
            return list2;
        }
        else if(list2==NULL)
        {
            return list1;
        }
        else if(list1->val<list2->val)
        {
            list1->next=mergeTwoLists(list1->next, list2);
            return list1;
        }
        else
        {
            list2->next=mergeTwoLists(list1, list2->next);
            return list2;
        }
        return {};
    }
};
  • 递归法

##22. 括号生成
数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。

示例 1:

输入:n = 3
输出:[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]

示例 2:

输入:n = 1
输出:[“()”]

class Solution {
public:
    vector<string> vec;
    vector<string> generateParenthesis(int n) {
        if(n<=0) return {};
        f("",n,n);
        return vec;
    }

    void f(string s,int l,int r)
    {
        if(r==0&&l==0)
        {
            vec.push_back(s);
            return ;
        }
        if(l==r)
        {
            f(s+"(",l-1,r);
        }
        else if(l<r)
        {
            if(l>0)
                f(s+"(",l-1,r);
            f(s+")",l,r-1);
        }
    }
};

  • 如果剩余左括号和右括号数量都为0,返回
  • 如果剩余左括号数量与右括号数量相等,下一个一定是左括号
  • 如果剩余左括号和右括号不相等,下一个都可以

23. 合并K个升序链表

给你一个链表数组,每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中,返回合并后的链表。

示例 1:

输入:lists = [[1,4,5],[1,3,4],[2,6]]
输出:[1,1,2,3,4,4,5,6]
解释:链表数组如下:
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2:

输入:lists = []
输出:[]

示例 3:

输入:lists = [[]]
输出:[]

小根堆

/**
 * 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) {
        priority_queue<int, vector<int>, greater<int>> q;
        for(int i=0;i<lists.size();i++)
        {
            while(lists[i]!=NULL)
            {
                q.push(lists[i]->val);
                lists[i]=lists[i]->next;
            }
        }

        ListNode *pre= new ListNode (0);
        ListNode *head= new ListNode (0);
        pre=head;
        while(!q.empty())
        {
            head->next=new ListNode(q.top());
            head=head->next;
            q.pop();
        }
        return pre->next;
    }
};
  • priority_queue<int, vector, greater> q; //小根堆
  • priority_queue<int, vector, less> q; //大根堆

mutiset

/**
 * 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) {
        multiset<int> s;
        for(int i=0;i<lists.size();i++)
        {
            while(lists[i]!=NULL)
            {
                s.insert(lists[i]->val);
                lists[i]=lists[i]->next;
            }
        }

        ListNode *pre= new ListNode (0);
        ListNode *head= new ListNode (0);
        pre=head;
        for(auto ite=s.begin();ite!=s.end();ite++)
        {
            head->next=new ListNode(*ite);
            head=head->next;
        }
        return pre->next;
    }
};

Q.E.D.