leetcode算法刷题记录--7

两数之和（leetcode1）

C++

#include <vector>
#include <unordered_map>
using namespace std;// 两数之和
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {vector<int> ans;// 定义unordered_map存储值和索引unordered_map<int,int> tmp;for(int i=0;i<nums.size();i++){auto it = tmp.find(target - nums[i]);if(it != tmp.end()){ans.push_back(it->second);ans.push_back(i);return ans;}tmp[nums[i]]=i;}return ans;}
};

Python

from typing import List
# 两数之和
class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:# 创建一个字典存储数值和对应的下标dic = {}for i,num in enumerate(nums):if (target-num) in dic:return [dic[target-num],i]dic[num] = ireturn []

买卖股票的最佳时机（leetcode121）

C++

#include <vector>
using namespace std;
class Solution {
public:int maxProfit(vector<int>& prices) {int profit = 0;int min_prices = prices[0];for(int i=1;i<prices.size();i++){profit = max(profit,prices[i]-min_prices);min_prices = min(min_prices,prices[i]);}return profit;}
};

Python

from typing import List
# 买卖股票的最佳时机
class Solution:def maxProfit(self, prices: List[int]) -> int:profit = 0min_price = prices[0]for i in prices[1:]:profit = max(profit,i-min_price)min_price = min(min_price, i)return profit

有效的括号（leetcode20） 

C++

#include<string>
#include <vector>
using namespace std;
// 有效的括号
class Solution {
public:bool isValid(string s) {vector<char> stack;for (int i=0;i<s.length();i++) {if(s[i]==']'){if(!stack.empty() && stack.back()=='['){stack.pop_back();}else{return false;}}else if(s[i]=='}'){if(!stack.empty() && stack.back()=='{'){stack.pop_back();}else{return false;}}else if(s[i]==')'){if(!stack.empty() && stack.back()=='('){stack.pop_back();}else{return false;}}else{stack.push_back(s[i]);}}if(stack.empty()) return true;return false;}
};

Python

# 有效的括号
class Solution:def isValid(self, s: str) -> bool:# 使用一个列表模拟栈操作stack = []for i in s:# 右括号则匹配if i == ")":if stack and stack[-1]=="(":del stack[-1]else:return Falseelif i == "}":if stack and stack[-1]=="{":del stack[-1]else:return Falseelif i == "]":if stack and stack[-1]=="[":del stack[-1]else:return False# 左括号则进入栈中else:stack.append(i)if len(stack)==0:return Truereturn False

合并两个有序数组（leetcode88）

C++

#include <vector>
using namespace std;
// 合并两个有序数组
class Solution {
public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {// muns1无值则将nums2逐个添加到nums1中if(m==0){for(int i=0;i<n;i++){nums1[i] = nums2[i];}}// nums2无值则不做处理if(n==0){return;}// 定义i指向nums1当前处理位置，int i = m-1;// 定义j指向nums2当前处理位置，int j = n-1;for(int index=0;index<m+n;index++){if(i<0 || j<0) break;if(nums1[i]>nums2[j]){nums1[m+n-1-index] = nums1[i];i--;}else{nums1[m+n-1-index] = nums2[j];j--;}}// 如果nums2未处理完，则将nums2中未处理的值填入到nums1中while(j>=0){nums1[j] = nums2[j];j--;}}
};

Python

from typing import List
# 合并两个有序数组
class Solution:def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:"""Do not return anything, modify nums1 in-place instead."""if m==0:for i in range(n):nums1[i] = nums2[i]if n==0:returni = m-1j = n-1for index in range(n+m):if i<0 or j<0:break# 判断将最大值向后填充if nums1[i]>nums2[j]:nums1[n+m-1-index] = nums1[i]i-=1else:nums1[n + m - 1 - index] = nums2[j]j -= 1# 如果nums2指针没走完，则将num2余下元素放置到nums1中if j>=0:for k in range(j+1):nums1[k] = nums2[k]
if __name__ == '__main__':# nums1 = [1, 2, 3, 0, 0, 0]# m = 3# nums2 = [2, 5, 6]# n = 3nums1 = [2,0]m = 1nums2 =[1]n=1s = Solution()s.merge(nums1,m,nums2,n)print(nums1)

LRU缓存（leetcode146）

C++

#include <unordered_map>
using namespace std;
// LRU缓存
struct DiListNode {int key;int val;DiListNode *pre;DiListNode *next;DiListNode() : key(0), val(0), pre(nullptr), next(nullptr) {}DiListNode(int key, int val) : key(key), val(val), pre(nullptr), next(nullptr) {}DiListNode(int key, int val, DiListNode *pre, DiListNode *next) : key(key), val(val), pre(pre), next(next) {}
};class LRUCache {
public:// 总容量int capacities;// 已使用容量int used;// 虚拟头节点DiListNode* dummy;// 尾节点DiListNode* end;// 存储key与节点对应关系的harsh表unordered_map<int, DiListNode*> cache;LRUCache(int capacity) {capacities = capacity;used = 0;dummy= new DiListNode(-1,0);end = nullptr;}int get(int key) {// 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1。if(cache.find(key)!=cache.end()){   //存在DiListNode *cur = cache.find(key)->second;// 将cur移动到链表头后，返回valif(cur->pre==dummy) return cur->val;    // 原本在表头则无需移动movetohead(cur);return cur->val;}return -1;}void put(int key, int value) {// 如果关键字 key 已经存在，则变更其数据值 value ；if(cache.find(key)!=cache.end()){// 变更其值DiListNode*cur = cache.find(key)->second;cur->val = value;// 移动到链表头部if(cur->pre==dummy) return;movetohead(cur);} else{     // 如果不存在，则向缓存中插入该组 key-value 。if(used==capacities){       // 如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字。cache.erase(end->key);end->pre->next = nullptr;end = end->pre;used--;}DiListNode *cur = new DiListNode(key, value);cache[key] = cur;cur->next = dummy->next;if(used!=0){dummy->next->pre = cur;}else{end = cur;}cur->pre = dummy;dummy->next = cur;used++;}}void movetohead(DiListNode* L){if(L==end){  // L是尾节点end->pre->next = nullptr;end = end->pre;}else{   //L是中间节点L->pre->next = L->next;L->next->pre = L->pre;}L->next = dummy->next;dummy->next->pre = L;L->pre = dummy;dummy->next = L;}
};

Python

# LRU缓存
# 定义双向链表用于
class DiLinkList:def __init__(self, key=0, val=0, pre=None, next=None):self.key = keyself.val = valself.pre = preself.next = nextclass LRUCache:def __init__(self, capacity: int):# 缓存容量self.capacity = capacity# 已使用容量self.used = 0# 定义一个字典存储键值对self.harsh = {}# 定义虚拟头节点self.dummy = DiLinkList(-1)     # 取-1作为key# 定义链表尾节点self.end = Nonedef get(self, key: int) -> int:if key in self.harsh:# 将对应节点移动到表头head = self.harsh[key]if head.pre==self.dummy:    # 是头节点则无需移动return self.harsh.get(key).valself.movetohead(head)return self.harsh.get(key).valreturn -1def put(self, key: int, value: int) -> None:# 如果关键词存在则变更其值，如果关键词不存在则插入，如果关键词超量则删除尾节点后在头节点插入# 存在if key in self.harsh:head = self.harsh[key]head.val = value# 移动到链表头if head.pre == self.dummy:  # 是头节点则无需移动returnself.movetohead(head)else:# 超量先删除尾节点,if self.used==self.capacity:# 更新链表,删除self.harsh.pop(self.end.key)self.end.pre.next = Noneself.end = self.end.preself.used -= 1# 插入，更新链表node = DiLinkList(key,value,self.dummy,self.dummy.next)if self.used !=0:   # 不是第一个节点self.dummy.next.pre = nodeself.dummy.next = nodeelse:self.dummy.next = nodeself.end = node    # 是第一个节点# 更新harsh表self.harsh[key] = node# 更新已使用空间self.used+=1def movetohead(self,head):  # 将某个节点移动到链表头部if head.next == None:  # 是尾节点self.end = head.prehead.pre.next = Noneelse:  # 不是尾节点head.pre.next = head.nexthead.next.pre = head.prehead.next = self.dummy.nexthead.pre = self.dummyself.dummy.next.pre = headself.dummy.next = headif __name__ == '__main__':lRUCache = LRUCache(2)lRUCache.put(2, 1)lRUCache.put(1, 1)lRUCache.put(2, 3)lRUCache.put(4, 1)print(lRUCache.get(1))print(lRUCache.get(2))