• 力扣刷题1-10

1、两数之和

1.1 题目

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

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

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

1.2 分析

C++中map，有三种类型：

std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。

同理，std::map 和std::multimap 的key也是有序的（这个问题也经常作为面试题，考察对语言容器底层的理解）。更多哈希表的理论知识请看关于哈希表，你该了解这些！

这道题目中并不需要key有序，选择std::unordered_map 效率更高！使用其他语言的录友注意了解一下自己所用语言的map结构的内容实现原理。

接下来需要明确两点：

map用来做什么
map中key和value分别表示什么
map目的用来存放我们访问过的元素，因为遍历数组的时候，需要记录我们之前遍历过哪些元素和对应的下表，这样才能找到与当前元素相匹配的（也就是相加等于target）

接下来是map中key和value分别表示什么。

这道题 我们需要 给出一个元素，判断这个元素是否出现过，如果出现过，返回这个元素的下标。

那么判断元素是否出现，这个元素就要作为key，所以数组中的元素作为key，有key对应的就是value，value用来存下标。

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

在遍历数组的时候，只需要向map去查询是否有和目前遍历元素比配的数值，如果有，就找到的匹配对，如果没有，就把目前遍历的元素放进map中，因为map存放的就是我们访问过的元素。

1.3 代码实现

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {std::unordered_map<int,int> hashmap;for(int i=0;i<nums.size();i++){auto iter=hashmap.find(target-nums[i]);if(iter==hashmap.end()){//没有找到，插入hashmap.insert({nums[i],i});}else{return {iter->second,i};}}return {};}
};

2、两数相加

2.1 题目

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

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

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

2.2 分析

2.3 代码实现

/*** 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* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode *head=nullptr,*tail=nullptr;int carry=0;while(l1 || l2){//链表未扫描结束int n1=l1 ? l1->val:0;int n2=l2 ? l2->val:0;int sum=(n1+n2+carry)%10;carry=(n1+n2+carry)/10;if(!head)//第一个值插入head=tail= new ListNode (sum);else{//剩下的值插入tail->next=new ListNode(sum);tail=tail->next;}if(l1)l1=l1->next;if(l2)l2=l2->next;}if(carry>0)//最后有进位要附加一个节点tail->next= new ListNode(carry);return head;}
};

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

3.1 题目

3.2 分析

3.3 代码实现

class Solution {
public:int lengthOfLongestSubstring(string s) {unordered_set<char> occ;int rk=-1;//右指针初始为字符串左边界的左侧int ans=0;for(int i=0;i<s.size();i++){if(i){occ.erase(s[i-1]);//左指针移动，则删除前面一个字符}while(rk+1<s.size() && occ.find(s[rk+1])==occ.end()){//还没遍历完且当前指向字符不在子串中occ.insert(s[rk+1]);++rk;}ans=max(ans,rk+1-i);}return ans;}
};

4、寻找两个有序数组的中位数

4.1 题目

4.2 分析

由于两个数组的长度已知，因此中位数对应的两个数组的下标之和也是已知的。维护两个指针，初始时分别指向两个数组的下标 000 的位置，每次将指向较小值的指针后移一位（如果一个指针已经到达数组末尾，则只需要移动另一个数组的指针），直到到达中位数的位置。

4.3 代码实现

class Solution {
public:int findKthElememt(const vector<int>& nums1, const vector<int>& nums2,int k){int m=nums1.size(),n=nums2.size();int index1=0,index2=0;while (true){if(index1==m)//nums1的数全部排除return nums2[index2+k-1];if(index2==n)//nums2的数全部排除return nums1[index1+k-1];if(k==1)return min(nums1[index1],nums2[index2]);int newindex1=min(index1+k/2-1,m-1);int newindex2=min(index2+k/2-1,n-1);int pri1=nums1[newindex1];int pri2=nums2[newindex2];if(pri1>=pri2){k-=newindex2-index2+1;//排除比较之后更小值所在数组的[index,newindex]范围的数index2=newindex2+1;}else{k-=newindex1-index1+1;index1=newindex1+1;}}}double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int m=nums1.size(),n=nums2.size();if((m+n)%2)return findKthElememt(nums1, nums2,(m+n)/2+1);//总长为奇数elsereturn (findKthElememt(nums1, nums2,(m+n)/2)+findKthElememt(nums1, nums2,(m+n)/2+1))/2.0;}
};

5、最长回文子串

5.1 题目

5.2 分析

5.3 代码实现

class Solution {
public:int expandAroundCenter(string s,int left,int right){while(left>=0 && right<s.size() && s[left]==s[right]){left--;right++;//向外扩展}return right-left-1;}string longestPalindrome(string s) {if(s.size()<1)return "";if(s.size()==1)return s;int n=s.size();int maxlen=0;int left,right;for(int i=0;i<n;i++){int len1=expandAroundCenter(s,i,i);int len2=expandAroundCenter(s,i,i+1);int len=max(len1,len2);if(len>maxlen){maxlen=len;left=i-(len-1)/2;right=i+len/2;}}return s.substr(left,maxlen);}
};

6、Z 字形变换

6.1 题目

6.2 分析

6.3 代码实现

7、整数反转

7.1 题目

7.2 分析

7.3 代码实现

8、字符串转换整数 (atoi)

8.1 题目

8.2 分析

8.3 代码实现

9、回文数

9.1 题目

9.2 分析

9.3 代码实现

10、正则表达式匹配

10.1 题目

10.2 分析

10.3 代码实现