当前位置 博文首页 > DL_fan的博客：leetcode hot100(第一部分) + python(c++)
1-1.两数之和
思路１：两层for循环 Ｏ（ｎ2）
class Solution:
def twoSum(self, nums, target):
res = []
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if nums[i]+nums[j]==target:
res.extend([i, j])
break
print('==res:', res)
return res
nums = [2, 7, 6, 15]
target = 9
sol = Solution()
sol.twoSum(nums, target)
思路２：ｈａｓｈ
python代码
class Solution:
def twoSum(self, nums, target):
res_dict = {}
for i in range(len(nums)):
value = target - nums[i]
if value in res_dict:
return [res_dict[value], i]
res_dict[nums[i]] = i
print('==res_dict:', res_dict)
return [-1, -1]
nums = [2, 7, 6, 15]
target = 9
sol = Solution()
res = sol.twoSum(nums, target)
print('res:', res)
思路2:c++代码：
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <typeinfo>
using namespace std;
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
map<int, int> dict_;
for(int k=0;k<nums.size();k++)
{
dict_[nums[k]] = k;
}
map <int,int>::iterator iter = dict_.begin();
for (;iter!=dict_.end();iter++)
{
if(dict_[target - iter->first])
{
// cout<<iter->second<<dict_[target - iter->first]<<endl;
return {iter->first,target - iter->first};
}
}
return {-1,-1};
}
};
int main()
{
vector<int> nums;
nums = {2,7,11,15};
int target = 9;
// nums = [2,7,11,15]
Solution sol;
vector<int> res;
res = sol.twoSum(nums,target);
for(int k=0;k<res.size();k++)
{
cout<<"==res[k]:"<<res[k]<<endl;
}
return 0;
}1-2，两数之和 II - 输入有序数组
方法1：利用字典
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
res_dict = {}
for i in range(len(numbers)):
value = target - numbers[i]
if value in res_dict:
return [res_dict[value]+1, i+1]
res_dict[numbers[i]] = i方法2：双指针
class Solution:
def twoSum(self, numbers, target):
left=0
right = len(numbers)-1
while left<right:
sum_= numbers[left]+numbers[right]
if sum_==target:
return [left+1, right+1]
elif sum_<target:
left+=1
else:
right-=1
return [-1, -1]
sol = Solution()
numbers = [2, 7, 11, 15]
target = 9
res = sol.twoSum(numbers,target)
print('res:',res)
2.两数相加?
思路:开出一个head头,利用一个指针进行遍历,需要注意的是进位
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
head = ListNode(0)
new_node = head
carry = 0
while l1 and l2:
new_node.next =ListNode(l1.val+l2.val+carry)
carry = new_node.next.val//10
new_node.next.val = new_node.next.val%10
l1 = l1.next
l2= l2.next
new_node = new_node.next
# print(carry)
while l1:
new_node.next = ListNode(l1.val+carry)
carry = new_node.next.val//10
new_node.next.val = new_node.next.val%10
l1 = l1.next
new_node = new_node.next
while l2:
new_node.next = ListNode(l2.val+carry)
carry = new_node.next.val//10
new_node.next.val = new_node.next.val%10
l2 = l2.next
new_node = new_node.next
if carry:
new_node.next = ListNode(carry)
return head.nextc++实现:
/**
* 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 = new ListNode(0);
ListNode* new_head = head;
int carry = 0;
while(l1 && l2){
new_head->next = new ListNode(l1->val + l2->val + carry);
carry = new_head->next->val/10;
new_head->next->val = new_head->next->val%10;
new_head = new_head->next;
l1 = l1->next;
l2 = l2->next;
}
while(l1){
new_head->next = new ListNode(l1->val + carry);
carry = new_head->next->val/10;
new_head->next->val = new_head->next->val%10;
new_head = new_head->next;
l1 = l1->next;
}
while(l2){
new_head->next = new ListNode(l2->val + carry);
carry = new_head->next->val/10;
new_head->next->val = new_head->next->val%10;
new_head = new_head->next;
l2 = l2->next;
}
if(carry){
new_head->next = new ListNode(carry);
}
return head->next;
}
};?3.无重复字符的最长子串
思路:滑动窗口，先往右拓展字典进行加1，发现大于1的在往左压缩 python代码
class Solution:
def lengthOfLongestSubstring(self, s):
n = len(s)
left = 0
right = 0
dict_= {}
res = 0
while right<n:#往右拓展
dict_[s[right]] = dict_.get(s[right], 0)+1#出现就加1
while dict_[s[right]]>1:#解决这种两个连续ww的问题"pwwkew" 再次出现往左压缩
dict_[s[left]]-=1
left+=1
res = max(res, right-left+1)
right+=1
return res
# s = "abcabcbb"
# s = "dvdf"
s = "pwwkew"
sol = Solution()
sol.lengthOfLongestSubstring(s)c++代码:
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <typeinfo>
using namespace std;
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int left = 0, right = 0, res = 0;
unordered_map<char, int> dict_; //散列表实现 查找更高效
int length = s.size();
while(right < length){
dict_[s[right]]++;
while (dict_[s[right]] > 1){
dict_[s[left]]--;
left++;
}
right++;
res = max(right - left, res);
}
return res;
}
};
int main()
{
string s = "abcabc";
// Solution sol;
// int res;
// res= sol.lengthOfLongestSubstring(s);
int res;
Solution *sol = new Solution();
res = sol->lengthOfLongestSubstring(s);
delete sol;
sol = NULL;
cout<<"res:"<<res<<endl;
return 0;
}4.寻找两个正序数组的中位数
思路:双指针，走完剩下的在进行合并 时间复杂度o(m+n) 空间复杂度0(m+n)
class Solution:
def findMedianSortedArrays(self, nums1, nums2):
res = []
i, j = 0, 0
m, n = len(nums1), len(nums2)
while i < m and j < n:
if nums1[i] < nums2[j]:
res.append(nums1[i])
i += 1
else:
res.append(nums2[j])
j += 1
print('==res:', res)
print('==i:', i)
print('==j:', j)
if i < m:
res.extend(nums1[i:])
if j < n:
res.extend(nums2[j:])
print('==res:', res)
if (m+n)%2==0:#偶数
return (res[(m+n)//2]+res[(m+n)//2-1])/2
else:#奇数
return res[(m+n)//2]
# nums1 = [1, 1, 3]
# nums2 = [2]
nums1 = [1,2]
nums2 = [3,4]
sol = Solution()
res = sol.findMedianSortedArrays(nums1, nums2)
print(res)c++实现:
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size();
int n = nums2.size();
int i=0, j=0;
vector<double> res;
while(i<m && j<n){
if(nums1[i]<nums2[j]){
res.push_back(nums1[i]);
i++;
}
else{
res.push_back(nums2[j]);
j++;
}
}
while(i<m){
res.push_back(nums1[i]);
i++;
}
while(j<n){
res.push_back(nums2[j]);
j++;
}
// for(int i=0;i<res.size(); i++){
// cout<<"res:"<<res[i]<<endl;
// }
if((m+n)%2){
return res[(m+n)/2];
}
else{
return (res[(m+n)/2-1] + res[(m+n)/2])*1.0/2.;
}
return 0.;
}
};优化:双指针识别,不用开辟数组空间, 时间复杂度o((m+n)/2) 空间复杂度0(1)
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
//双指针吧
int m = nums1.size();
int n = nums2.size();
int i=0, j=0;
float preNum = 0, current = 0;
while((i + j) <= (m + n)/2){
preNum = current;
if((j >= n) || (i < m && nums1[i] < nums2[j])){
current = nums1[i];
i++;
}
else{
current = nums2[j];
j++;
}
}
if((m + n)%2 == 0){
return (current + preNum) / 2;
}
else{
return current;
}
}
};5.最长回文子串
思路:中心枚举
class Solution:
def helper(self,left,right,s):
while left>=0 and right<len(s) and s[left]==s[right]:
left-=1
right+=1
if len(s[left+1:right])>len(self.res):
self.res = s[left+1:right]
def longestPalindrome(self, s: str) -> str:
self.res = ''
for i in range(len(s)):
self.helper(i,i,s)
self.helper(i,i+1,s)
return self.res
c++实现:
class Solution {
public:
string res;
void help(int left, int right, string& s){
while(left >= 0 && right < s.size() && s[left] == s[right]){
left--;
right++;
}
left++;
right--;
if(right - left + 1 > res.size()){
res = s.substr(left, right - left + 1);
}
}
string longestPalindrome(string s) {
if(s.size() <= 1){
return s;
}
for(int i=1; i<s.size(); i++){
help(i-1, i+1, s);
help(i-1, i, s);
}
return res;
}
};
?6,盛最多水的容器
?
求Max{(j-i) * Min( h(i), h(j) )},?
思路：双指针
时间复杂度为 O(n)，空间复杂度为 O(1) 。?
#解法2
class Solution:
def maxarea(self,height):
left=0
right=len(height)-1
max_area=0
while left<right:
max_area = max(max_area,(right - left) * min(height[left], height[right]))
if height[left]<height[right]:
left+=1
else:
right-=1
# index_i = left
# index_j=right
return max_area
s=Solution()
height=[2,8,1,5,9,3,4]
max_area=s.maxarea(height)
print(max_area)c++实现:
class Solution {
public:
int maxArea(vector<int>& height) {
int left = 0;
int right = height.size() - 1;
int max_area = 0;
while(left < right){
max_area = max(max_area, min(height[left], height[right])*(right - left));
if(height[left]<height[right]){
left++;
}
else{
right--;
}
}
return max_area;
}
};?7.三数之和
思路1: 固定两数，寻找第三个数，两层循环，最复杂解法，列表比较大时，时间会很长
class Solution:
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
result=[]
nums.sort()
length=len(nums)
for i in range(length-1):
for j in range(i+1,length):
if -(nums[i]+nums[j]) in nums[j+1:]:
tmp=[nums[i],nums[j],-(nums[i]+nums[j])]
if tmp not in result:
result.append(tmp)
return result思路2: 双指针，固定一个数，让其余两个数从第一个数+1和尾 向中间靠近，只需要循环一遍
# 双指针:排好序以后，双指针去寻找两数之和等于第一个
class Solution:
def threeSum(self, nums):
nums = sorted(nums)
res = []
n = len(nums)
print('==nums:', nums)
for i in range(n):
if i>0 and nums[i]==nums[i-1]:#去除相同的第一个数[-1, 0, 1, 2, -1, -4]
continue
start = i + 1
end = n - 1
# print('==start:', start)
# print('==end:', end)
while start < end:
if nums[i] + nums[start] + nums[end] == 0:
res.append([nums[i], nums[start], nums[end]])
start += 1
end -= 1
while start<end and nums[start]==nums[start-1]:# 首部出现连续两个数[-2, 0, 0, 2, 2]
start+=1
while start<end and nums[end]==nums[end+1]:# 尾部出现连续两个数[-2, 0, 0, 2, 2]
end-=1
elif (nums[i] + nums[start] + nums[end]) > 0:
end -= 1
else:
start += 1
print('==res:', res)
return res
# nums = [-1, 0, 1, 2, -1, -4]
nums = [-2, 0, 0, 2, 2]
sol = Solution()
sol.threeSum(nums)
c++实现:
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(), nums.end());
int n = nums.size();
for(int i=0; i<n; i++){
if(i>0 && nums[i]==nums[i-1]){
continue;
}
int start = i + 1;
int end = n - 1;
while(start < end){
if(nums[i] + nums[start] + nums[end] == 0){
res.push_back({nums[i], nums[start], nums[end]});
start++;
end--;
while(start < end && nums[start]==nums[start-1]){
start++;
}
while(start < end && nums[end]==nums[end+1]){
end--;
}
}
else if((nums[i] + nums[start] + nums[end]) > 0){
end--;
}
else{
start++;
}
}
}
return res;
}
};思路3.利用两数之和
class Solution:
def twoSum(self, nums, target):
res_dict = {}
for i in range(len(nums)):
value = -target - nums[i]
if value in res_dict:
self.res.add((target, nums[i], value))
res_dict[nums[i]] = i
def threeSum(self, nums: List[int]) -> List[List[int]]:
self.res = set()
nums = sorted(nums)
for i in range(len(nums)):
if i>0 and nums[i] == nums[i-1]:
continue
self.twoSum(nums[i+1:], nums[i])
return list(self.res)
8.电话号码的字母组合
思路:组合问题 用回溯
class Solution:
def backtrace(self, digits, track):
if len(digits) == 0:#满足终止条件
self.res.append(track)
return
for letter in self.phone[digits[0]]:# for循环去遍历选择条件
store = track#保存中间结果用于回溯
track += letter
self.backtrace(digits[1:], track)
track = store#恢复中间结果回溯
def letterCombinations(self, digits):
self.res = []
if len(digits) == 0:
return self.res
self.phone = {'2': ['a', 'b', 'c'],
'3': ['d', 'e', 'f'],
'4': ['g', 'h', 'i'],
'5': ['j', 'k', 'l'],
'6': ['m', 'n', 'o'],
'7': ['p', 'q', 'r', 's'],
'8': ['t', 'u', 'v'],
'9': ['w', 'x', 'y', 'z']}
self.backtrace(digits, track='')
print('==self.res:', self.res)
return self.res
digits = "23"
sol = Solution()
sol.letterCombinations(digits)
9.删除链表的倒数第N个节点
思路：找到链表长度，通过在头结点补充一个节点找到要删除的节点的上一个节点，然后在进行删除
方法１：循环
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
length = 0
node = head
#获取链表长度
while node:
length+=1
node= node.next
# print(length)
curr_length = 0
new_head = ListNode(0)
new_head.next = head
node2=new_head
stop_length = length - n
#循环走到要删除节点的前一个节点
while stop_length:
stop_length-=1
node2 = node2.next
#跳过要删除的节点即可
node2.next = node2.next.next
return new_head.next
方法２：递归
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def __init__(self):
self.count = 0
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
if not head:
return head
head.next = self.removeNthFromEnd(head.next, n) # 递归调用
self.count += 1 # 回溯时进行节点计数
return head.next if self.count == n else head
方法3:双指针 推荐使用
fist 指针与second指针相隔n,这样first跑到尾部,second的下一个节点就是倒数第n个
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
# def __init__(self):
# self.count = 0
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
new_head = ListNode(0)
new_head.next = head
first = head
second = new_head
for i in range(n):
first = first.next
while first:
first = first.next
second = second.next
second.next = second.next.next
return new_head.nextc++实现:?
/**
* 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* new_head = new ListNode(0);
new_head ->next = head;
ListNode* first = head;
ListNode* second = new_head;
for(int i=0;i<n;i++){
first = first->next;
}
while(first){
first = first->next;
second = second->next;
}
second->next = second->next->next;
return new_head->next;
}
};10.有效的括号
思路: 栈
class Solution:
def isValid(self, s: str) -> bool:
stack= []
dict_ = {
')':'(',
'}':'{',
']':'[',
}
for i in range(len(s)):
if s[i] in dict_.keys():
if len(stack) == 0 or stack[-1] != dict_[s[i]]:
return False
else:
stack.pop()
else:
stack.append(s[i])
return len(stack) == 011.合并两个排序的链表
思路:引入一个指针头 python实现
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
head = ListNode(0)
node = head
while l1 and l2:
if l1.val < l2.val:
node.next = l1
l1 = l1.next
else:
node.next = l2
l2 = l2.next
node = node.next
if l1 is not None:
node.next= l1
if l2 is not None:
node.next= l2
return head.nextc++实现:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* new_head = new ListNode(0);
ListNode* node = new_head;
while(l1!=NULL && l2 !=NULL){
if(l1->val<l2->val){
node->next = l1;
l1 = l1->next;
}
else{
node->next = l2;
l2 = l2->next;
}
node = node->next;
}
if (l1!=NULL){
node->next = l1;
}
if(l2!=NULL){
node->next = l2;
}
return new_head->next;
}
};12.括号生成
思路:回溯剪枝
1.左右括号插入数量不能超过n
2.左括号数量大于右括号，就可以插入右括号
# 回溯法:插入数量不超过n
# 可以插入 ） 的前提是 ( 的数量大于 ）
class Solution(object):
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
self.res = []
self.dfs(n, n, '')
return self.res
def dfs(self, left, right, track):
if left == 0 and right == 0: # 递归终止条件 左括号与右括号都用完
self.res.append(track)
return
if left > 0: # 左括号个数
store = track #
track += '('
self.dfs(left - 1, right, track)
track = store
if left < right: # 左括号个数大于右括号 此时可以添加右括号
# store = track
track += ')'
self.dfs(left, right - 1, track)
# track = store
n = 2
sol = Solution()
res = sol.generateParenthesis(n)
print(res)13.合并K个升序链表
思路1:上一题合并两个变成for循环顺序合并
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwo(self, l1, l2):
if l1 is None:
return l2
if l2 is None:
return l1
head = ListNode(0)
node = head
while l1 and l2:
if l1.val <l2.val:
node.next = l1
l1 = l1.next
else:
node.next = l2
l2 = l2.next
node = node.next
if l1:
node.next = l1
if l2:
node.next = l2
return head.next
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
ans = None
for i in range(len(lists)):
ans = self.mergeTwo(ans,lists[i])
return ansc++:
/**
* 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* mergtwo(ListNode* l1, ListNode* l2){
if(l1==nullptr){
return l2;
}
if(l2==nullptr){
return l1;
}
ListNode* new_head= new ListNode(0);
ListNode* node = new_head;
while(l1 && l2){
if(l1->val<l2->val){
node->next = l1;
l1= l1->next;
}
else{
node->next = l2;
l2= l2->next;
}
node = node->next;
}
if(l1){
node->next = l1;
}
if(l2){
node->next = l2;
}
return new_head->next;
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode* res = nullptr;
for (int i=0;i<lists.size();i++){
res = mergtwo(res,lists[i]);
}
return res;
}
};
