面试手撕优化
LRU 缓存
1 /* 2 每次get一个key有两种情况，要么链表里面没有这个key那么可以直接返回-1， 3 如果链表里面有这个key，我们需要把查到的这个节点给移到链表头部， 4 对于put操作，我们直接通过调用get返回结果： 5 如果返回不是-1，说明链表里面已有key，那么我们的get函数会给他排到链表前面去。 6 如果返回-1，说明链表里面没有key，那么我们需要插入这个key，分两种情况: 7 如果容量满了，就删除最后一个节点再把新的key加进来作为链表头结点 8 否则直接加入当前的key到链表头结点 9 */ 10 class LRUCache { 11 public: 12 int cap; 13 list<int>st;//使用C++自带的双向链表list 14 unordered_map<int,list<int>::iterator>mp;//key需要映射到链表元素的迭代器 15 unordered_map<int,int>mp1;//保存key-value键值对，方便查询元素value 16 LRUCache(int capacity) { 17 cap=capacity; 18 } 19 int get(int key) { 20 if(mp.count(key)){ 21 auto it=mp[key]; 22 //splice(const_iterator pos, list& other, const_iterator it)表示把结点it移到other链表的pos位置之前 23 st.splice(st.begin(),st,it); 24 return mp1[key]; 25 } 26 else return -1; 27 } 28 void put(int key, int value) { 29 if(get(key)!=-1){ 30 mp1[key]=value; 31 } 32 else{ 33 if(mp.size()==cap){ //如果容量满了，就删除最后一个再把新的key加进来作为链表头结点 34 int x=st.back(); 35 mp.erase(x); 36 st.pop_back(); 37 st.push_front(key); 38 mp1[key]=value; 39 auto it=st.begin(); 40 mp[key]=it; 41 } 42 else{ //否则直接加入当前的key到链表头结点 43 st.push_front(key); 44 mp1[key]=value; 45 auto it=st.begin(); 46 mp[key]=it; 47 } 48 } 49 } 50 };
删除链表的倒数第 N 个结点
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode() : val(0), next(nullptr) {} 7 * ListNode(int x) : val(x), next(nullptr) {} 8 * ListNode(int x, ListNode *next) : val(x), next(next) {} 9 * }; 10 */ 11 class Solution { 12 public: 13 ListNode* removeNthFromEnd(ListNode* head, int n) { 14 ListNode *p = head, *q = head, *pre = head; 15 if (!p->next) { 16 delete(head); 17 head = nullptr; 18 return head; 19 } 20 int cnt = 0; 21 while (q) { 22 if (cnt < n) { 23 cnt++; 24 q = q->next; 25 } 26 else { 27 q = q->next; 28 pre = p; 29 p = p->next; 30 } 31 } 32 if (pre == p) { 33 p = p->next; 34 delete(head); 35 head = p; 36 return head; 37 } 38 pre->next = p->next; 39 delete(p); 40 return head; 41 } 42 };
K 个一组翻转链表
1 class Solution { 2 public: 3 ListNode* reverseKGroup(ListNode* head, int k) { 4 ListNode *p=head; 5 if(k==1||p->next==NULL)return p; 6 ListNode *pre=NULL; 7 ListNode *tail=NULL; 8 ListNode *prehead=NULL; 9 ListNode *ans; 10 int n=0; 11 while(p){ 12 n++; 13 p=p->next; 14 } 15 int h=0; 16 p=head; 17 ListNode *nowhead=NULL; 18 while(p){ 19 h++; 20 if(h%k==1){ 21 nowhead=p; 22 if(h>=(n-n%k)&&(n%k!=0)){ 23 prehead->next=nowhead; 24 break; 25 } 26 } 27 if(h%k==0){ 28 tail=p; 29 if(h==k)ans=p; 30 if(h>k){ 31 prehead->next=tail; 32 } 33 prehead=nowhead; 34 35 } 36 ListNode *q=p->next; 37 p->next=pre; 38 pre=p; 39 p=q; 40 if(h==n){ 41 nowhead->next=NULL; 42 break; 43 } 44 } 45 return ans; 46 } 47 };
合并 K 个升序链表
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode() : val(0), next(nullptr) {} 7 * ListNode(int x) : val(x), next(nullptr) {} 8 * ListNode(int x, ListNode *next) : val(x), next(next) {} 9 * }; 10 */ 11 struct node{ 12 int val; 13 ListNode *pt; 14 bool operator <(const node&t)const{ 15 return val>t.val; 16 } 17 }; 18 class Solution { 19 public: 20 ListNode* mergeKLists(vector<ListNode*>& lists) { 21 ListNode *head=new ListNode(0,NULL); 22 ListNode *pre=head; 23 priority_queue<node>q; 24 for(auto p:lists){ 25 if(p)q.push(node{p->val,p}); 26 } 27 while(!q.empty()){ 28 node now=q.top(); 29 pre->next=now.pt; 30 q.pop(); 31 if(now.pt->next)q.push(node{now.pt->next->val,now.pt->next}); 32 pre=now.pt; 33 } 34 return head->next; 35 } 36 };
寻找两个正序数组的中位数
1 class Solution { 2 public: 3 //这个函数用于寻找两个有序数组合并后的第 k 个最小元素 4 int getk(vector<int>& nums1, vector<int>& nums2, int k) { 5 int n = nums1.size(); // 数组 nums1 的长度 6 int m = nums2.size(); // 数组 nums2 的长度 7 int id1 = 0, id2 = 0; // id1, id2 分别是数组 nums1 和 nums2 的当前索引位置 8 while (true) { 9 if (id1 == n) return nums2[id2 + k - 1]; // 如果 nums1 已经全部考虑完毕，直接从 nums2 中取第 k 个元素 10 if (id2 == m) return nums1[id1 + k - 1]; // 如果 nums2 已经全部考虑完毕，直接从 nums1 中取第 k 个元素 11 if (k == 1) return min(nums1[id1], nums2[id2]); // 如果 k 为1，返回两个数组当前元素的最小值 12 // 计算新的搜索区间 13 int nid1 = min(id1 + k / 2 - 1, n - 1); // 在 nums1 中向前搜索 k/2 个元素的位置 14 int nid2 = min(id2 + k / 2 - 1, m - 1); // 在 nums2 中向前搜索 k/2 个元素的位置 15 int x = nums1[nid1]; 16 int y = nums2[nid2]; 17 if (x <= y) { 18 k -= (nid1 - id1 + 1); // 减少 k 的值，移动 nums1 的索引 19 id1 = nid1 + 1; 20 } else { 21 k -= (nid2 - id2 + 1); // 减少 k 的值，移动 nums2 的索引 22 id2 = nid2 + 1; 23 } 24 } 25 } 26 //计算两个有序数组的中位数 27 double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { 28 int n = nums1.size(); // 数组 nums1 的长度 29 int m = nums2.size(); // 数组 nums2 的长度 30 // 如果两数组长度之和为奇数，直接返回中间的元素 31 if ((n + m) % 2) return getk(nums1, nums2, (n + m + 1) / 2); 32 // 如果为偶数，返回中间两个元素的平均值 33 else return (getk(nums1, nums2, (n + m) / 2) + getk(nums1, nums2, (n + m) / 2 + 1)) / 2.0; 34 } 35 };
用队列实现栈
1 class MyStack { 2 public: 3 queue<int> q1, q2; 4 MyStack() {} 5 void push(int x) { 6 q2.push(x); 7 while (!q1.empty()) { 8 q2.push(q1.front()); 9 q1.pop(); 10 } 11 swap(q1,q2); 12 } 13 int pop() { 14 if(!q1.empty()) { 15 int x = q1.front(); 16 q1.pop(); 17 return x; 18 } 19 return -1; 20 } 21 int top() { 22 if (q1.empty()) return -1; 23 return q1.front(); 24 } 25 bool empty() { 26 return q1.empty(); 27 } 28 };
验证IP地址
1 class Solution { 2 public: 3 int check(string sp){ 4 int n=sp.size(); 5 if(n<1||n>4)return 0; 6 for(auto c:sp){ 7 if(!isdigit(c))return 0; 8 } 9 int x=stoi(sp); 10 if(x<0||x>255)return 0; 11 if(sp[0]=='0'&&sp.length()>1)return 0; 12 return 1; 13 } 14 int ipv4(string s){ 15 if(s[s.size()-1]=='.')return 0; 16 stringstream ss(s); 17 string sp; 18 vector<string>v; 19 while(getline(ss,sp,'.')){ 20 v.push_back(sp); 21 } 22 if(v.size()!=4)return 0; 23 for(auto sp:v){ 24 if(!check(sp))return 0; 25 } 26 return 1; 27 } 28 int check1(string sp){ 29 int n=sp.size(); 30 if(n<1||n>4)return 0; 31 for(auto c:sp){ 32 if(!isdigit(c)&&!((c>='a'&&c<='f')||(c>='A'&&c<='F')))return 0; 33 } 34 return 1; 35 } 36 int ipv6(string s){ 37 if(s[s.size()-1]==':')return 0; 38 stringstream ss(s); 39 string sp; 40 vector<string>v; 41 int x=0; 42 while(getline(ss,sp,':')){ 43 x++; 44 if(x>8)return 0; 45 v.push_back(sp); 46 } 47 if(v.size()!=8)return 0; 48 for(auto sp:v){ 49 if(!check1(sp))return 0; 50 } 51 return 1; 52 } 53 string validIPAddress(string queryIP) { 54 if(queryIP.size()==0)return "Neither"; 55 if(ipv4(queryIP))return "IPv4"; 56 else if(ipv6(queryIP))return "IPv6"; 57 else return"Neither"; 58 } 59 };
最大子数组和
1 //dp思想，如果加上当前位置的数后累计的和变为负数，则当前位置以及之前的所有元素都可以丢弃 2 class Solution { 3 public: 4 int maxSubArray(vector<int>& nums) { 5 int n=nums.size(); 6 int ans=-1e9,res=0,mx=-1e9; 7 for(int i=0;i<n;i++){ 8 mx=max(mx,nums[i]); 9 res+=nums[i]; 10 if(res>0){ 11 ans=max(ans,res); 12 continue; 13 } 14 else res=0; 15 } 16 if(mx<=0)ans=mx; 17 return ans; 18 } 19 };
最长公共子序列
1 // 遍历text1，在text1和text2中寻找以text1[i]为末尾元素的最长公共子序列， 2 // 如果text2[j] != text1[i]，dp[j]等于text2中以text2[j]为末尾元素的子序列和text1的子串 text1[0]~text1[i - 1] 的最长公共子序列的长度； 3 // 如果text2[j] == text1[i]，dp[j]等于text1的子串 text1[0]~text1[i - 1] 和text2的子串 text2[0]~text2[j - 1]的最长公共子序列的长度再加1。 4 // 即dp[j] = max(dp[k]) + 1, k∈[0,j), 且dp[k]为上一轮循环的结果，而不是本轮循环更新过的值。 5 class Solution { 6 public: 7 int longestCommonSubsequence(string text1, string text2) { 8 vector<int> dp(text2.size(), 0); 9 for (int i = 0; i < text1.size(); ++i) { 10 int maxlen = 0; 11 for (int j = 0; j < text2.size(); ++j) { 12 int newlen = max(maxlen, dp[j]); 13 if (text1[i] == text2[j]) { 14 dp[j] = maxlen + 1; 15 } 16 maxlen = newlen; 17 } 18 } 19 return *max_element(dp.cbegin(), dp.cend()); 20 } 21 };
正则表达式匹配
1 //d[i][j] 表示 s 的前 i 个字符与 p 中的前 j 个字符是否能够匹配 2 class Solution { 3 public: 4 bool isMatch(string s, string p) { 5 int n = s.size(); 6 int m = p.size(); 7 vector<vector<int>> d(n+1,vector<int>(m+1,0)); 8 d[0][0] = true; 9 for(int i=1;i<=m;i++){ 10 if(i<m&&p[i-1]!='*'&&p[i]!='*')break; 11 if(i==m-1&&p[i]!='*')break; 12 d[0][i]=1; 13 } 14 for(int i=1;i<=n;i++){ 15 char pre='A'; 16 for(int j=1;j<=m;j++){ 17 if(p[j-1]!='*')pre=p[j-1]; 18 if(p[j-1]=='*'){ 19 if(pre=='.'){ 20 d[i][j]=d[i-1][j]|d[i][j-1]; 21 if(j>=2)d[i][j]=d[i][j]|d[i][j-2]; 22 d[i-1][j]=d[i-1][j-2]|d[i-1][j]; 23 } 24 else{ 25 if(pre==s[i-1]){ 26 d[i][j]=d[i-1][j]|d[i][j-1]; 27 d[i][j]=d[i][j]|d[i][j-2]; 28 } 29 else{ 30 d[i-1][j]=d[i-1][j-2]|d[i-1][j]; 31 d[i][j]=d[i][j-2]; 32 } 33 } 34 } 35 else if(p[j-1]=='.'||p[j-1]==s[i-1]){ 36 d[i][j]=d[i-1][j-1]; 37 } 38 } 39 } 40 return d[n][m]; 41 } 42 };
多线程
实现一个固定容量的阻塞队列，用生产者消费者测试。
1 package com.venux.train.common.util; 2 3 import java.util.LinkedList; 4 import java.util.Queue; 5 import java.util.concurrent.locks.Condition; 6 import java.util.concurrent.locks.ReentrantLock; 7 8 /** 9 * 一个具有固定大小的阻塞队列，支持线程安全的操作。 10 * 它允许在不发生死锁的情况下添加和移除元素。 11 * 12 * @param <T> 队列中元素的类型 13 */ 14 public class FixedSizeBlockingQueue<T> { 15 private final int capacity;// 队列容量 16 private final Queue<T> queue;// 底层的队列 17 private final ReentrantLock lock;// 用于同步的锁 18 private final Condition notFull;// 队列不满的条件变量，用于阻塞等待队列不满，以便添加元素 19 private final Condition notEmpty;// 队列不空的条件变量，用于阻塞等待队列不空，以便移除元素 20 private volatile boolean isClosed = false; // 用于标记队列是否已关闭 21 22 // 构造函数，初始化队列的容量，以及相关的锁和条件变量 23 public FixedSizeBlockingQueue(int capacity) { 24 this.capacity = capacity; 25 this.queue = new LinkedList<>(); 26 this.lock = new ReentrantLock(); 27 this.notFull = lock.newCondition(); 28 this.notEmpty = lock.newCondition(); 29 } 30 // 将元素放入队列，如果队列已满，则阻塞当前线程，直到队列不满或者队列被关闭 31 public void put(T item) throws InterruptedException { 32 lock.lock(); 33 try { 34 while (queue.size() == capacity || isClosed) { // 检查队列是否已满或已关闭 35 if (isClosed) { 36 throw new IllegalStateException("Queue is closed"); 37 } 38 notFull.await(); 39 } 40 queue.add(item); 41 notEmpty.signal(); 42 } finally { 43 lock.unlock(); 44 } 45 } 46 // 从队列中取出一个元素，如果队列为空，则阻塞当前线程，直到队列不空或者队列被关闭 47 public T take() throws InterruptedException { 48 lock.lock(); 49 try { 50 while (queue.isEmpty()) { 51 notEmpty.await(); 52 } 53 T item = queue.poll(); 54 notFull.signal(); 55 return item; 56 } finally { 57 lock.unlock(); 58 } 59 } 60 // 返回队列中当前元素的数量 61 public int size() { 62 lock.lock(); 63 try { 64 return queue.size(); 65 } finally { 66 lock.unlock(); 67 } 68 } 69 // 关闭队列，不再接受新的元素 70 public void close() { 71 lock.lock(); 72 try { 73 isClosed = true; // 设置关闭标志 74 // 可选：唤醒所有等待的put线程 75 notFull.signalAll(); 76 } finally { 77 lock.unlock(); 78 } 79 } 80 public static void main(String[] args) { 81 FixedSizeBlockingQueue<Integer> queue = new FixedSizeBlockingQueue<>(5); 82 Thread producer = new Thread(() -> { 83 for (int i = 0; i < 10; i++) { 84 try { 85 queue.put(i); 86 System.out.println("Produced: " + i); 87 } catch (InterruptedException e) { 88 e.printStackTrace(); 89 } 90 } 91 }); 92 Thread consumer = new Thread(() -> { 93 for (int i = 0; i < 10; i++) { 94 try { 95 int item = queue.take(); 96 System.out.println("Consumed: " + item); 97 } catch (InterruptedException e) { 98 e.printStackTrace(); 99 } 100 } 101 }); 102 producer.start(); 103 consumer.start(); 104 try { 105 producer.join(); 106 consumer.join(); 107 } catch (InterruptedException e) { 108 e.printStackTrace(); 109 } 110 System.out.println("Queue size: " + queue.size()); 111 queue.close(); 112 System.out.println("Queue closed."); 113 } 114 }
生产者消费者多线程实现， 使用了Java包的BlockingQueue作为阻塞队列。
1 import java.util.concurrent.ArrayBlockingQueue; 2 import java.util.concurrent.BlockingQueue; 3 4 public class ProducerConsumerExample { 5 6 // 创建一个BlockingQueue，容量为10 7 private static final BlockingQueue<Integer> queue = new ArrayBlockingQueue<>(10); 8 9 // 生产者线程 10 static class Producer implements Runnable { 11 public void run() { 12 int value = 0; 13 while (true) { 14 try { 15 // 生产数据 16 Thread.sleep(1000); // 模拟耗时操作 17 value++; 18 System.out.println("生产者生产了：" + value); 19 20 // 将生产的数据放入队列 21 queue.put(value); 22 23 } catch (InterruptedException e) { 24 Thread.currentThread().interrupt(); 25 } 26 } 27 } 28 } 29 30 // 消费者线程 31 static class Consumer implements Runnable { 32 public void run() { 33 while (true) { 34 try { 35 // 从队列中取出数据 36 Integer value = queue.take(); 37 System.out.println("消费者消费了：" + value); 38 39 // 假设消费者处理数据也需要一些时间 40 Thread.sleep(500); 41 42 } catch (InterruptedException e) { 43 Thread.currentThread().interrupt(); 44 } 45 } 46 } 47 } 48 49 public static void main(String[] args) { 50 // 创建并启动生产者线程 51 Thread producerThread = new Thread(new Producer()); 52 producerThread.start(); 53 54 // 创建并启动消费者线程 55 Thread consumerThread = new Thread(new Consumer()); 56 consumerThread.start(); 57 } 58 }