Leetcode热题100

哈希

1.两数之和

java版本

class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer,Integer> map = new HashMap<>();int n = nums.length;for(int i = 0; i < n; i++){int x = target -nums[i];if(map.containsKey(x)){return new int[]{map.get(x),i};}map.put(nums[i],i);}return new int[]{};}
}

cpp版本

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int,int> m;for(int i = 0; i < nums.size(); i++){int x = target - nums[i];if(m.find(x) != m.end()){return {m[x],i};}m[nums[i]] = i;}return {};}
};

49.字母异位词分组

java版本

class Solution {public List<List<String>> groupAnagrams(String[] strs) {Map<String,List<String>> m = new HashMap<>();for(String S:strs){char []s = S.toCharArray();int []cnt = new int[26];for(char c:s){++cnt[c-'a'];}StringBuilder sb = new StringBuilder();for(int i = 0; i < 26; i++){if(cnt[i] != 0){sb.append(cnt[i]).append((char)'a'+i);}}String key = sb.toString();List<String> list = m.getOrDefault(key,new ArrayList<String>());list.add(S);m.put(key,list);}return new ArrayList<List<String>>(m.values());}
}

cpp版本

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {vector<vector<string>> res;unordered_map<string,vector<string>> m;for(string s :strs){vector<int> cnt(26,0);for(char c:s){++cnt[c-'a'];}string ss = "";for(int i = 0; i < 26; i++){if(cnt[i]){ss.push_back(cnt[i]);ss.push_back(i+'a');}}m[ss].push_back(s);}for(auto &[k,v]:m){res.push_back(v);}return res;}
};

128.最长连续序列

java版本

class Solution {public int longestConsecutive(int[] nums) {Set<Integer> s = new HashSet<>();int res = 0;for(int x:nums)s.add(x);for(int x:nums){if(!s.contains(x-1)){int curLen = 1,curNum = x;while(s.contains(curNum+1)){++curLen;++curNum;}res = Math.max(res,curLen);}}return res;}
}

cpp版本

class Solution {
public:int longestConsecutive(vector<int>& nums) {unordered_set<int> s(nums.begin(),nums.end());int res = 0;for(int x:nums){if(!s.count(x-1)){int curLen = 1,curNum = x;while(s.count(curNum+1)){++curLen;++curNum;}res = max(res,curLen);}}return res;}
};

双指针

283.移动零

java版本

class Solution {public void moveZeroes(int[] nums) {int index = 0,n = nums.length;for(int i = 0; i < n; i++){if(nums[i] != 0){int t = nums[i];nums[i] = nums[index];nums[index++] = t;}}}
}

cpp版本

class Solution {
public:void moveZeroes(vector<int>& nums) {int index = 0, i = 0, n = nums.size();while(i < n){if(nums[i]){swap(nums[i],nums[index++]);}++i;}}
};

11.盛最多水的容器

java版本

class Solution {public int maxArea(int[] height) {int res = 0 , l = 0, r = height.length-1;while(l < r){res = Math.max((r-l)*Math.min(height[l],height[r]),res);if(height[l] < height[r]){++l;}else{--r;}}return res;}
}

cpp版本

class Solution {
public:int maxArea(vector<int>& height) {int res = 0, n = height.size(), l = 0, r = n-1;while(l <= r){res = max(res,(r-l)*min(height[l],height[r]));if(height[l] < height[r]){++l;}else{--r;}}return res;}
};

15.三数之和

java版本

class Solution {public List<List<Integer>> threeSum(int[] nums) {if(nums == null || nums.length < 3) return new ArrayList<>();int n = nums.length;Arrays.sort(nums);List<List<Integer>> res = new ArrayList<>();for(int i = 0; i < n; i++){if(nums[i] > 0)break;if(i >0 && nums[i] == nums[i-1]) continue;int target = -nums[i];int left = i+1, right = n-1;while(left < right){if(nums[left] +nums[right] == target){res.add(new ArrayList<>(Arrays.asList(nums[i],nums[left],nums[right])));++left;--right;while(left < right && nums[left] == nums[left-1])++left;while(left < right && nums[right] == nums[right+1])--right;}else if(nums[left]+nums[right] > target){--right;}else ++left;}}return res;}
}

cpp版本

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {if(nums.size() < 3)return {};ranges::sort(nums);int n = nums.size();vector<vector<int>> res;for(int i = 0; i < n; i++){if(nums[i] > 0)break;if(i > 0 && nums[i] == nums[i-1]) continue;if(nums[i]+nums[n-1]+nums[n-2] < 0)continue;int target = -nums[i], l = i+1, r = n-1;while(l < r){if(target == nums[l]+nums[r]){res.push_back({nums[i],nums[l],nums[r]});++l;--r;while(l < r && nums[l] == nums[l-1]) ++l;while(l < r && nums[r] == nums[r+1]) --r;}else if(nums[l]+nums[r] < target){++l;}else{--r;}}}return res;}
};

42.接雨水

java版本

class Solution {public int trap(int[] height) {if(height.length==1 && height[0] == 0)return 0;int n = height.length , maxIndex = -1,maxValue = 0;for(int i = 0; i < n; i++){if(height[i] > maxValue){maxIndex = i;maxValue = height[i];}}int res = 0;for(int left = 0; left <= maxIndex; ++left){for(int i = left+1; i <= maxIndex; i++){if(height[left] > height[i]){res += height[left]-height[i];}else{left = i;}}}for(int right = n-1; right >= maxIndex; --right){for(int i = right-1;i >= maxIndex; i--){if(height[right] > height[i]){res += height[right]-height[i];}else{right = i;}}}return res;}
}

cpp版本

class Solution {
public:int trap(vector<int>& height) {int n = height.size(), maxIndex = -1,maxValue = -1;for(int i = 0; i< n; i++){if(height[i] > maxValue){maxValue = height[i];maxIndex = i;}}int res = 0;for(int left = 0; left <= maxIndex; left++){for(int i = left+1; i <= maxIndex; i++){if(height[i] < height[left]){res += (height[left]-height[i]);}else{left = i;}}}for(int right = n-1; right >= maxIndex; right--){for(int i = right-1; i >= maxIndex; i--){if(height[i] < height[right]){res += (height[right]-height[i]);}else{right = i;}}}return res;}
};

滑动窗口

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

java版本

class Solution {public int lengthOfLongestSubstring(String s) {int n = s.length(), l = 0, r = 0,res = 0;char[] S = s.toCharArray();boolean[] hash = new boolean[128];while(r < n){while(hash[S[r]]){hash[S[l++]] = false;}hash[S[r++]] = true;res = Math.max(res,r-l);}return res;}
}

cpp版本

class Solution {
public:int lengthOfLongestSubstring(string s) {if(s.size() < 2)return s.size();unordered_set<int> st;int l = 0, r = 0, n = s.size(),res = 0;while(r < n){while(st.find(s[r]) != st.end()){st.erase(s[l++]);}st.insert(s[r++]);res = max(res,r-l);}return res;}};

438.找到字符串中所有字母异位词

java版本

class Solution {public List<Integer> findAnagrams(String s, String p) {int m = s.length(), n = p.length();if(m < n)return new ArrayList<>();List<Integer> res = new ArrayList<>();int[] cnt1 = new int[26];int[] cnt2 = new int[26];for(int i = 0; i < n; i++){++cnt1[s.charAt(i)-'a'];++cnt2[p.charAt(i)-'a'];}if(Arrays.equals(cnt1,cnt2))res.add(0);int l = 0, r = n;while(r < m){++cnt1[s.charAt(r++)-'a'];--cnt1[s.charAt(l++)-'a'];if(Arrays.equals(cnt1,cnt2))res.add(l);}return res;}
}

cpp版本

class Solution {
public:vector<int> findAnagrams(string s, string p) {int m = s.size(), n = p.size();if(m < n)return {};vector<int> res,cnt1(26,0),cnt2(26,0);for(int i = 0; i < n; i++){++cnt1[s[i]-'a'];++cnt2[p[i]-'a'];}if(cnt1 == cnt2)res.push_back(0);int l = 0, r = n;while(r < m){--cnt1[s[l++]-'a'];++cnt1[s[r++]-'a'];if(cnt1 == cnt2)res.push_back(l);}return res;}
};

子串

560.和为K的子数组

java版本

class Solution {public int subarraySum(int[] nums, int k) {Map<Integer,Integer> m = new HashMap<>();m.put(0,1);int res = 0,preSum = 0;for(int x:nums){preSum += x;if(m.containsKey(preSum-k)){res += m.get(preSum-k);}m.put(preSum,m.getOrDefault(preSum,0)+1);}return res;}
}

cpp版本

class Solution {
public:int subarraySum(vector<int>& nums, int k) {unordered_map<int,int> m;long long preSum = 0;int res = 0;m[0] = 1;for(int num:nums){preSum += num;if(m[preSum-k]){res += m[preSum-k]; }++m[preSum];}return res;}
};

239.滑动窗口最大值

java版本

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {PriorityQueue<int[]> q= new PriorityQueue<int[]>(new Comparator<int[]>(){public int compare(int []p1,int []p2){return p1[0] != p2[0] ? p2[0]-p1[0] : p2[1]-p1[1];}});int  n = nums.length;int []res = new int[n-k+1];for(int i = 0; i < k; i++){q.offer(new int[]{nums[i],i});}res[0] = q.peek()[0];for(int i = k; i < n; i++){q.offer(new int[]{nums[i],i});while(i-q.peek()[1] >= k)q.poll();res[i-k+1] = q.peek()[0];}return res;}
}

cpp版本

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {vector<int> res;//单调队列，维护单调递减的队列deque<int> q;for(int i = 0; i < nums.size(); i++){while(!q.empty() && nums[i] >= nums[q.back()]){q.pop_back();}q.push_back(i);if(i-q.front() >= k)q.pop_front();if(i >= k-1)res.push_back(nums[q.front()]);}return res;}
};

76.最小覆盖子串

java版本

class Solution {Map<Character, Integer> cnt = new HashMap<>();Map<Character, Integer> m = new HashMap<>();public  boolean check() {for (char k : cnt.keySet()) {if (m.getOrDefault(k, 0) < cnt.get(k)) {return false;}}return true;}public String minWindow(String s, String t) {int n = s.length();for (char c : t.toCharArray()) {cnt.put(c, cnt.getOrDefault(c, 0) + 1);}int l = 0, r = 0, resLeft = -1, resRight = n;while (r < n) {char rightChar = s.charAt(r);m.put(rightChar, m.getOrDefault(rightChar, 0) + 1);while (check()) {if (r - l < resRight - resLeft) {resLeft = l;resRight = r;}char leftChar = s.charAt(l);m.put(leftChar, m.get(leftChar) - 1);if (m.get(leftChar) == 0) {m.remove(leftChar);}l++;}r++;}return resLeft < 0 ? "" : s.substring(resLeft, resRight + 1);}}

cpp版本

class Solution {
public:unordered_map<char,int> cnt,m;bool check(){for(auto [k,v]:cnt){if(m[k] < v){return false;}}return true;}string minWindow(string s, string t) {int n = s.size();for(char c:t){++cnt[c];}int l = 0, r = 0, res_left = -1,res_right = n;while(r < n){++m[s[r]];while(check()){if(r-l < res_right-res_left){res_left = l;res_right = r;}--m[s[l++]];}++r;}return res_left < 0 ? "":s.substr(res_left,res_right-res_left+1);}
};

普通数组

53.最大子数组和

java版本

class Solution {public int maxSubArray(int[] nums) {int res = nums[0],sum = nums[0];for(int i = 1; i < nums.length; i++){if(sum> 0){sum += nums[i];}else{sum = nums[i];}res = Math.max(res,sum);}return res;}
}

cpp版本

class Solution {
public:int maxSubArray(vector<int>& nums) {int sum = nums[0], res = sum , n = nums.size();for(int i = 1; i <n; i++){if(sum > 0){sum += nums[i];}else{sum = nums[i];}res = max(res,sum);}return res;}
};

56.合井区间

java版本

class Solution {public int[][] merge(int[][] intervals) {Arrays.sort(intervals,(p,q)->p[0]-q[0]);int n = intervals.length;List<int[]> list = new ArrayList<int[]>();for(int i = 0; i < n; i++){int L = intervals[i][0], R = intervals[i][1];if(list.isEmpty() || L > list.get(list.size()-1)[1]){list.add(new int[]{L,R});}else{list.get(list.size()-1)[1] = Math.max(list.get(list.size()-1)[1],R);}}return list.toArray(new int[list.size()][]);}
}

cpp版本

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {auto cmp = [](auto a,auto b){return a[0] < b[0];};ranges::sort(intervals,cmp);vector<vector<int>> res;for(auto i:intervals){if(res.empty() || res.back()[1] < i[0]){res.push_back(i);}else{res.back()[1] = max(res.back()[1],i[1]);}}return res;}
};

189.轮转数组

java版本

class Solution {public void rotate(int[] nums, int k) {int n = nums.length;k %= n;reverse(nums,0,n-1);reverse(nums,0,k-1);reverse(nums,k,n-1);}public void reverse(int[] nums,int l,int r){while(l < r){int x = nums[l];nums[l++] = nums[r];nums[r--] = x;}}
}

cpp版本

class Solution {
public:void rotate(vector<int>& nums, int k) {int n = nums.size();k %= n;reverse(nums,0,n-1);reverse(nums,0,k-1);reverse(nums,k,n-1);}void reverse(vector<int>& nums,int l,int r){int x;while(l < r){x = nums[l];nums[l++] = nums[r];nums[r--] = x;}}
};

238.除自身以外数组的乘积

java版本

class Solution {public int[] productExceptSelf(int[] nums) {int n = nums.length;int[] res = new int[n];res[0] = 1;for(int i = 1; i < n; i++){res[i] = res[i-1]*nums[i-1];}int r = 1;for(int i = n-1; i >= 0; i--){res[i] *= r;r *= nums[i];}return res;}
}

cpp版本

class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int n = nums.size();vector<int> res(n);res[0] = 1;for(int i = 1; i < n; i++){res[i] = res[i-1]*nums[i-1];}int r = 1;for(int i = n-1; i >= 0; i--){res[i] *= r;r *= nums[i];}return res;}
};

41.缺失的第一个正数

java版本

class Solution {public int firstMissingPositive(int[] nums) {int n = nums.length;for(int i = 0; i < n; ){int val = nums[i];if(val > 0 && val < n && val-1 != i && nums[val-1] != nums[i]){int t = nums[val-1];nums[val-1] = nums[i];nums[i] = t;}else{++i;}}for(int i = 0; i < n; i++){if(nums[i] != i+1){return i+1;}}return n+1;}
}

cpp版本

class Solution {
public:int firstMissingPositive(vector<int>& nums) {int n = nums.size();for(int i = 0; i < n; ){int val = nums[i];if(val > 0 && val < n && val-1 != i && nums[val-1] != nums[i]){int t = nums[val-1];nums[val-1] = nums[i];nums[i] = t;}else{++i;}}for(int i = 0; i < n; i++){if(nums[i] != i+1)return i+1;}return n+1;}
};

矩阵

73.矩阵置零

java版本

class Solution {public void setZeroes(int[][] matrix) {int m = matrix.length , n = matrix[0].length;boolean row0 = false,col0 = false;for(int i = 0; i < m; i++){if(matrix[i][0] == 0)col0 = true;}for(int j = 0; j < n; j++){if(matrix[0][j] == 0){row0 = true;}}for(int i = 1; i < m; i++){for(int j = 1; j < n; j++){if(matrix[i][j] == 0){matrix[i][0] = matrix[0][j] = 0;}}}for(int i = 1; i < m; i++){for(int j = 1; j < n; j++){if(matrix[i][0] == 0 || matrix[0][j] == 0){matrix[i][j] = 0;}}}if(col0){for(int i = 0; i < m; i++){matrix[i][0] = 0;}}if(row0){for(int j = 0; j < n; j++){matrix[0][j] = 0;}}}
}

cpp版本

class Solution {
public:void setZeroes(vector<vector<int>>& matrix) {int m = matrix.size(), n = matrix[0].size();bool row0 = false, col0 = false;for(int i = 0; i < m; i++)if(matrix[i][0] == 0) col0 = true;for(int i = 0; i < n; i++){if(matrix[0][i] == 0) row0 = true;}for(int i = 1; i < m; i++){for(int j = 1; j < n; j++){if(matrix[i][j] == 0)matrix[i][0] = matrix[0][j] = 0;}}for(int i = 1; i < m; i++){for(int j = 1; j < n; j++){if(matrix[i][0] == 0 || matrix[0][j] == 0){matrix[i][j] = 0;}}}if(col0)for(int i = 0; i < m; i++){matrix[i][0] = 0;}if(row0)for(int i = 0; i < n; i++)matrix[0][i] = 0;}
};

54.螺旋矩阵

java版本

class Solution {public List<Integer> spiralOrder(int[][] matrix) {int m = matrix.length, n = matrix[0].length;;int up = 0, down = m-1, left = 0, right = n-1;List<Integer> res = new  ArrayList<>();while(true){for(int i = left;i <= right; i++){res.add(matrix[up][i]);}if(++up > down)break;for(int i = up; i <= down; i++){res.add(matrix[i][right]);}if(--right < left)break;for(int i = right; i >= left; i--){res.add(matrix[down][i]);}if(--down < up)break;for(int i = down ; i >= up; i--){res.add(matrix[i][left]);}if(++left > right)break;}return res;}
}

cpp版本

class Solution {
public:vector<int> spiralOrder(vector<vector<int>>& matrix) {if(matrix.size() == 0 ) return {};vector<int> res;int m = matrix.size(), n = matrix[0].size();int up = 0, down = m-1, left = 0, right = n-1;while(true){for(int i = left; i <= right; i++)res.push_back(matrix[up][i]);if(++up > down)break;for(int i = up; i <= down; i++)res.push_back(matrix[i][right]);if(--right < left) break;for(int i = right; i >= left; i--)res.push_back(matrix[down][i]);if(--down < up) break;for(int i = down; i >= up; i--)res.push_back(matrix[i][left]);if(++left > right)break;}return res;}
};

48.旋转图像

java版本

class Solution {public void rotate(int[][] matrix) {int n = matrix.length, tmp;for(int i = 0; i < n/2; i++){for(int j = 0; j < n; j++){tmp = matrix[i][j];matrix[i][j] = matrix[n-1-i][j];matrix[n-1-i][j] = tmp;}}for(int i = 0; i < n; i++){for(int j = 0; j< i ; j++){tmp = matrix[i][j];matrix[i][j] = matrix[j][i];matrix[j][i] = tmp;}}}
}

cpp版本

class Solution {
public:void rotate(vector<vector<int>>& matrix) {int m = matrix.size();for(int i = 0; i < m/2; i++){for(int j = 0; j< m; j++){swap(matrix[m-1-i][j],matrix[i][j]);}}for(int i = 0; i < m; i++){for(int j = 0; j <i; j++){swap(matrix[i][j],matrix[j][i]);}}}
};

240.搜索二维矩阵 II

java版本

class Solution {public boolean searchMatrix(int[][] matrix, int target) {if(matrix.length == 0 || matrix[0].length == 0)return false;int row = matrix.length, col = matrix[0].length,x = 0,y = col-1;while(x < row && y >= 0){if(matrix[x][y] == target)return true;else if(matrix[x][y] > target) --y;else ++ x;}return false;}
}

cpp版本

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int m = matrix.size(), n = matrix[0].size(), row = 0, col = n-1;while(row < m && col >= 0){if(matrix[row][col] == target) return true;else if(matrix[row][col] > target) --col;else ++row;}return false;}
};

链表

160.相交链表

java版本

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode  p = headA, q = headB;while(p != q){p = p == null ? headB : p.next;q = q == null ? headA : q.next;}return p;}
}

cpp版本

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode *p1 = headA, *p2= headB;while(p1 != p2){p1 = p1 == nullptr ? headB :p1->next;p2 =  p2 == NULL ? headA : p2->next;}return p1;}
};

206.反转链表

java版本

class Solution {public ListNode reverseList(ListNode head) {ListNode dummy= null, p = head;while(p != null){ListNode nextNode = p.next;p.next = dummy;dummy = p;p =nextNode;}return dummy;}
}

cpp版本

class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode *dummy = nullptr,*p = head;while(p){ListNode *nextNode = p->next;p->next = dummy;dummy = p;p = nextNode;}return dummy;}
};

234.回文链表

java版本

class Solution {public boolean isPalindrome(ListNode head) {if(head == null ||  head.next == null) return true;ListNode middle = findMiddle(head);ListNode second = reverse(middle.next);ListNode p = head,q = second;boolean res = true;while(res && q != null){if(p.val != q.val){res = false;break;}p = p.next;q = q.next;}middle.next = reverse(second);return res;}public ListNode findMiddle(ListNode root){ListNode fast =root,slow = root;while(fast.next != null && fast.next.next != null){fast = fast.next.next;slow = slow.next;}return slow;}public ListNode reverse(ListNode root){ListNode pre = null, p = root;while(p != null){ListNode nextNode = p.next;p.next = pre;pre = p;p = nextNode;}return pre;}}

cpp版本

class Solution {
public:bool isPalindrome(ListNode* head) {if(head  == nullptr) return true;ListNode *middle = findMiddle(head);ListNode *second = reverse(middle->next);bool res = true;ListNode *p1 = head,*p2 = second;while(true && p2){if(p1->val != p2->val){res = false;break;}p1 = p1->next;p2 = p2->next;}middle->next = reverse(second);return res;}ListNode *findMiddle(ListNode *head){ListNode *fast = head,*slow = head;while(fast->next && fast->next->next){fast = fast->next->next;slow = slow->next;}return slow;}ListNode *reverse(ListNode *head){ListNode *pre = nullptr, *cur = head;while(cur){ListNode *nextNode = cur->next;cur->next = pre;pre = cur;cur = nextNode;}return pre;}
};

141.环形链表

java版本

public class Solution {public boolean hasCycle(ListNode head) {if(head == null || head.next == null)return false;ListNode fast = head,slow = head;while(fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;if(fast == slow)return true;}return false;}
}

cpp版本

class Solution {
public:bool hasCycle(ListNode *head) {if(head == nullptr || head->next == nullptr) return false;ListNode *fast = head,*slow =head;while(fast->next && fast->next->next){fast = fast->next->next;slow = slow->next;if(slow == fast){return true;}}return false;}
};

142.环形链表 II

java版本

public class Solution {public ListNode detectCycle(ListNode head) {if(head == null || head.next == null)return null;ListNode fast = head,slow = head;while(fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;if(fast == slow){fast = head;while(fast != slow){fast = fast.next;slow = slow.next;}return fast;}}return null;}
}

cpp版本

class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode fast = head,slow = head;while(fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;if(fast == slow){fast = head;while(fast != slow){fast = fast.next;slow = slow.next;}return fast;}}return null;}
};

21.合井两个有序链表

java版本

class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode dummy = new ListNode(-1), p = dummy;while(list1 != null && list2 != null){if(list1.val < list2.val){p.next = list1;list1 = list1.next;}else{p.next = list2;list2 = list2.next;}p = p.next;}p.next = list1 == null ? list2 : list1;return dummy.next;}
}

cpp版本

class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {if(list1 == nullptr) return list2;if(list2 == nullptr) return list1;ListNode *dummy = new ListNode(0,nullptr),*p = dummy;while(list1 && list2){if(list1->val < list2->val){p->next = list1;list1 = list1->next;}else{p->next = list2;list2 = list2->next;}p = p->next;}p->next = (list1 == nullptr ? list2 : list1);return dummy->next;}
};

2.两数相加

java版本

class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {if(l1 == null)  return l2;if(l2 == null)  return l1;ListNode dummy = new ListNode(-1),p = dummy;int carry = 0;while(l1 != null || l2 != null || carry != 0){int val1 = l1 == null ? 0 : l1.val;int val2 = l2 == null  ? 0 : l2.val;int sum = val1 + val2 + carry;ListNode newNode = new ListNode(sum%10);carry= sum / 10;p.next = newNode;p = p.next;l1 = l1 == null ? null : l1.next;l2 = l2 == null ? null : l2.next;}return dummy.next;}
}

cpp版本

class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode *head = new ListNode(-1);ListNode *p = head;int carry = 0;while(l1 || l2 || carry != 0){int l1Value = l1 == NULL ? 0:l1->val;int l2Value = l2 == NULL ? 0 :l2->val;int sum = l1Value + l2Value + carry;carry = sum/10;ListNode *newNode = new ListNode(sum%10);p->next = newNode;p = p->next;if(l1) l1= l1->next;if(l2) l2 = l2->next;}return head->next;}
};

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

java版本

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(-1,head),slow = dummy, fast = head;for(int i = 0; i< n; i++)fast = fast.next;while(fast != null){fast = fast.next;slow = slow.next;}slow.next = slow.next.next;return dummy.next;}
}

cpp版本

class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode dummy = new ListNode(-1,head),slow = dummy, fast = head;for(int i = 0; i< n; i++)fast = fast.next;while(fast != null){fast = fast.next;slow = slow.next;}slow.next = slow.next.next;return dummy.next;}
};

24.两两交换链表中的节点

java版本

class Solution {public ListNode swapPairs(ListNode head) {ListNode dummy = new ListNode(-1,head), pre = dummy,cur = head;while(cur != null && cur.next != null){ListNode nextNode = cur.next;cur.next = nextNode.next;nextNode.next = pre.next;pre.next = nextNode;pre = cur;cur = pre.next;}return dummy.next;}
}

cpp版本

class Solution {
public:ListNode* swapPairs(ListNode* head) {if(head == nullptr || head->next == nullptr) return head;ListNode *dummy = new ListNode(-1,head), *p = dummy;while(p->next  && p->next->next){ListNode *q = p->next->next;p->next->next = q->next;q->next = p->next;p->next = q;p = q->next;}return dummy->next;}
};

25.K个一组翻转链表

java版本

class Solution {public ListNode reverseKGroup(ListNode head, int k) {ListNode dummy = new ListNode(-1,head),pre = dummy,cur = head;int len = 0;while(cur != null){++len;cur = cur.next;}cur = head;for(int i = 0; i < len/k; i++){for(int j = 0; j < k-1; j++){ListNode nextNode = cur.next;cur.next = nextNode.next;nextNode.next = pre.next;pre.next = nextNode;}pre = cur;cur = cur.next;}return dummy.next;}}

cpp版本

class Solution {
public:ListNode* reverseKGroup(ListNode* head, int k) {int len = 0;ListNode *dummy = new ListNode(-1,head),*pre = dummy,*cur = head;while(cur){++len;cur = cur->next;}cur = head;for(int i = 0; i < len/k; i++){for(int j = 0; j < k-1; j++){ListNode *nextNode = cur->next;cur->next = nextNode->next;nextNode->next = pre->next;pre->next = nextNode;}pre = cur;cur = pre->next;}return dummy->next;}
};

138.随机链表的复制

java版本

class Solution {public Node copyRandomList(Node head) {if(head == null)return head;Node cur = head;while(cur != null){Node nextNode = new Node(cur.val,cur.next);cur.next = nextNode;cur = cur.next.next;}cur = head;while(cur != null){if(cur.random != null){cur.next.random = cur.random.next;}cur = cur.next.next;}cur = head;Node copyHead = cur.next, curCopy = copyHead;while(cur != null){cur.next = curCopy.next;cur = cur.next;if(cur != null)curCopy.next = cur.next;curCopy = curCopy.next;}return copyHead;}
}

cpp版本

class Solution {
public:Node* copyRandomList(Node* head) {if(head == nullptr) return head;Node *cur = head;while(cur){Node *newNode = new Node(cur->val);newNode->next = cur->next;cur->next = newNode;cur = cur->next->next;}cur = head;while(cur){if(cur->random){cur->next->random = cur->random->next;}cur = cur->next->next;}cur = head;Node *copyHead = cur->next,*curCopy = copyHead;while(cur){cur->next = cur->next->next;cur = cur->next;if(cur){curCopy->next = cur->next;}curCopy = curCopy->next;}return copyHead;}
};

148.排序链表

cpp版本

class Solution {
public:ListNode* sortList(ListNode* head) {ListNode dummyHead(0);dummyHead.next = head;auto p = head;int length = 0;while (p) {++length;p = p->next;}for (int size = 1; size < length; size <<= 1) {auto cur = dummyHead.next;auto tail = &dummyHead;while (cur) {auto left = cur;auto right = cut(left, size); cur = cut(right, size); tail->next = merge(left, right);while (tail->next) {tail = tail->next;}}}return dummyHead.next;}ListNode* cut(ListNode* head, int n) {auto p = head;while (--n && p) {p = p->next;}if (!p) return nullptr;auto next = p->next;p->next = nullptr;return next;}ListNode* merge(ListNode* l1, ListNode* l2) {ListNode dummyHead(0);auto p = &dummyHead;while (l1 && l2) {if (l1->val < l2->val) {p->next = l1;p = l1;l1 = l1->next;       } else {p->next = l2;p = l2;l2 = l2->next;}}p->next = l1 ? l1 : l2;return dummyHead.next;}
};

23.合并K个升序链表

java版本

class Solution {public ListNode mergeKLists(ListNode[] lists) {Comparator<ListNode> cmp = (a,b)->a.val - b.val;PriorityQueue<ListNode> q = new PriorityQueue<>(cmp);for(ListNode head:lists){if(head != null)q.offer(head);}ListNode dummy = new ListNode(-1), cur = dummy;while(!q.isEmpty()){ListNode p = q.poll();cur.next = p;cur = cur.next;if(p.next != null)q.offer(p.next);}return dummy.next;}
}

cpp版本

class Solution {public ListNode mergeKLists(ListNode[] lists) {Comparator<ListNode> cmp = (a, b) -> a.val - b.val;PriorityQueue<ListNode> q = new PriorityQueue<>(cmp);for (ListNode head : lists) {if (head != null) {q.add(head);}}ListNode dummy = new ListNode(-1);ListNode cur = dummy;while (!q.isEmpty()) {ListNode p = q.poll();cur.next = p;cur = cur.next;if (p.next != null) {q.add(p.next);}}return dummy.next;}
}

146.LRU 缓存

java版本

class LRUCache {
class Node{int key,val;Node pre,next;public Node(){}public Node(int key,int value){this.key = key;this.val = value;}
}
private HashMap<Integer,Node> cache = new HashMap<>();
private int size;
private int capacity;
private Node head = new Node();
private Node tail = new Node();public LRUCache(int capacity) {this.capacity = capacity;size = 0;head.next = tail;tail.pre = head;}public int get(int key) {Node node = cache.get(key);if(node == null)return -1;moveToHead(node);return node.val;}public void put(int key, int value) {Node node = cache.get(key);if(node != null){node.val = value;moveToHead(node);}else{Node newNode = new Node(key,value);cache.put(key,newNode);addToHead(newNode);++size;if(size > capacity){Node removeNode = removeTail();cache.remove(removeNode.key);--size;}}}public void moveToHead(Node node){removeNode(node);addToHead(node);}public void removeNode(Node node){node.pre.next = node.next;node.next.pre = node.pre;}public void addToHead(Node node){node.pre = head;node.next = head.next;head.next.pre = node;head.next = node;}public Node removeTail(){Node removeNode = tail.pre;removeNode(removeNode);return removeNode;}
}

cpp版本

class LRUCache {
public:struct Node {int key, val;Node* pre;Node* next;Node() : key(0), val(0), pre(nullptr), next(nullptr) {}Node(int k, int v) : key(k), val(v), pre(nullptr), next(nullptr) {}};unordered_map<int, Node*> cache;int size;int capacity;Node* head;Node* tail;void moveToHead(Node* node) {removeNode(node);addToHead(node);}void removeNode(Node* node) {node->pre->next = node->next;node->next->pre = node->pre;}void addToHead(Node* node) {node->pre = head;node->next = head->next;head->next->pre = node;head->next = node;}Node* removeTail() {Node* remove = tail->pre;removeNode(remove);return remove;}LRUCache(int capacity) : size(0), capacity(capacity) {head = new Node();tail = new Node();head->next = tail;tail->pre = head;}int get(int key) {if (cache.find(key) == cache.end()) {return -1;}Node* node = cache[key];moveToHead(node);return node->val;}void put(int key, int value) {if (cache.find(key) != cache.end()) {Node* node = cache[key];node->val = value;moveToHead(node);} else {Node* newNode = new Node(key, value);cache[key] = newNode;addToHead(newNode);size++;if (size > capacity) {Node* removeNode = removeTail();cache.erase(removeNode->key);delete removeNode;size--;}}}
};

二叉树

94.二叉树的中序遍历

java版本

class Solution {public List<Integer> inorderTraversal(TreeNode root) {Stack<TreeNode> s = new Stack<>();TreeNode p  = root;List<Integer> res = new LinkedList<>();while(p != null || !s.isEmpty()){if(p != null){s.push(p);p = p.left;}else{p = s.pop();res.add(p.val);p = p.right;}}return res;}
}

cpp版本

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {if(root == nullptr)return {};stack<TreeNode *> s;vector<int> res;TreeNode *p = root;while(p || !s.empty()){if(p){s.push(p);p = p->left;}else{p = s.top();res.push_back(p->val);s.pop();p = p->right;    }}return res;}
};

104.二叉树的最大深度

java版本

class Solution {public int maxDepth(TreeNode root) {if(root == null)return 0;int res = 0;Queue<TreeNode> q = new LinkedList<>();q.offer(root);while(!q.isEmpty()){++res;int size = q.size();for(int i= 0; i < size; i++){TreeNode p = q.poll();if(p.left != null)q.offer(p.left);if(p.right != null)q.offer(p.right);}}return res;}
}

cpp版本

class Solution {
public:int maxDepth(TreeNode* root) {if(root  == nullptr)return 0;int res = 0;queue<TreeNode *> q;q.push(root);while(!q.empty()){int size = q.size();++res;for(int i = 0; i < size; i++){TreeNode *p = q.front();q.pop();if(p->left)q.push(p->left);if(p->right) q.push(p->right);}}return res;}
};

226.翻转二叉树

java版本

class Solution {public TreeNode invertTree(TreeNode root) {if(root == null)return root;TreeNode l = invertTree(root.left);TreeNode r = invertTree(root.right);root.left = r;root.right = l;return root;}
}

cpp版本

class Solution {
public:TreeNode* invertTree(TreeNode* root) {if(root == nullptr)return nullptr;TreeNode *l = invertTree(root->left);TreeNode *r = invertTree(root->right);root->left = r;root->right = l;return root;}
};

101.对称二叉树

java版本

class Solution {public boolean isSymmetric(TreeNode root) {if(root == null)return true;return isSame(root.left,root.right);}public boolean isSame(TreeNode l,TreeNode r){if(l == null && r == null)return true;if(l == null || r == null)return false;if(l.val != r.val)return false;return isSame(l.left,r.right) && isSame(l.right,r.left);}
}

cpp版本

class Solution {
public:bool isSymmetric(TreeNode* root) {if(root == nullptr)return true;return isSame(root->left,root->right);}bool isSame(TreeNode *l,TreeNode* r){if(l == nullptr && r == nullptr)return true;if(l == nullptr || r == nullptr)return false;if(l->val != r->val)return false;return isSame(l->left,r->right) && isSame(l->right,r->left);}
};

543.二叉树的直径

java版本

class Solution {int res = 0;public int diameterOfBinaryTree(TreeNode root) {depth(root);return res;}public int depth(TreeNode root){if(root == null) return 0;int l = depth(root.left);int r = depth(root.right);res = Math.max(res,l+r);return Math.max(l,r)+1;}
}

cpp版本

class Solution {
public:int diameterOfBinaryTree(TreeNode* root) {int res = 0;function<int(TreeNode*)> depth = [&](TreeNode* root){if(root == nullptr)return 0;int l = depth(root->left);int r = depth(root->right);res = max(res,l+r);return max(l,r)+1;};depth(root);return res;}
};

102.二叉树的层序遍历

java版本

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {Queue<TreeNode> q = new LinkedList<>();q.offer(root);List<List<Integer>> res = new ArrayList<>();if(root == null)return res;while(!q.isEmpty()){int size = q.size();List<Integer> tmp = new ArrayList<>();for(int i = 0; i < size; i++){TreeNode p = q.poll();tmp.add(p.val);if(p.left != null)q.offer(p.left);if(p.right != null)q.offer(p.right);}res.add(tmp);}return res;}
}

cpp版本

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {if(root == nullptr)return {};vector<vector<int>> res;queue<TreeNode *> q;q.push(root);while(!q.empty()){int size = q.size();vector<int> tmp;for(int i = 0; i < size; i++){TreeNode *p = q.front();tmp.push_back(p->val);if(p->left) q.push(p->left);if(p->right)q.push(p->right);q.pop();}res.push_back(tmp);}return res;}
};

108.将有序数组转换为二叉搜索树

java版本

class Solution {public TreeNode sortedArrayToBST(int[] nums) {return construct(nums,0,nums.length-1);}public TreeNode construct(int[] nums,int l,int r){if(l > r)return null;int mid = ((r-l)>>1)+l;TreeNode root = new TreeNode(nums[mid]);root.left = construct(nums,l,mid-1);root.right = construct(nums,mid+1,r);return root;}
}

cpp版本

class Solution {
public:TreeNode* sortedArrayToBST(vector<int>& nums) {int r = nums.size()-1;return construct(nums,0,r);}TreeNode *construct(vector<int>& nums,int l,int r){if(l > r)return nullptr;int mid = ((r-l)>>1)+l;TreeNode *root = new TreeNode(nums[mid]);root->left = construct(nums,l,mid-1);root->right =construct(nums,mid+1,r);return root;}
};

98.验证二叉搜索树

java版本

class Solution {public boolean isValidBST(TreeNode root) {long pre = (long)Integer.MIN_VALUE - 1;TreeNode p = root;Stack<TreeNode> s = new Stack<>();while(p != null || !s.isEmpty()){if(p != null){s.push(p);p = p.left;}else{p = s.pop();if(p.val <= pre)return false;pre = p.val;p = p.right;}}return true;}
}

cpp版本

class Solution {
public:bool isValidBST(TreeNode* root) {long long pre = (long long)INT_MIN-1;stack<TreeNode*> s;TreeNode *p = root;while(p || !s.empty()){if(p){s.push(p);p = p->left;}else{p = s.top();s.pop();if(p->val <= pre)return false;pre = p->val;p = p->right;}}return true;}
};

230.二叉搜索树中第 K小的元素

java版本

class Solution {public int kthSmallest(TreeNode root, int k) {int num = 0, res = 0;Deque<TreeNode> s = new LinkedList<>();while(!s.isEmpty() || root != null){while(root != null){s.push(root);root = root.left;}root = s.pop();if(++num == k){res = root.val;break;}root = root.right;} return res;}
}

cpp版本

class Solution {
public:int kthSmallest(TreeNode* root, int k) {int num = 0,res=-1;stack<TreeNode *> s;TreeNode *p = root;while(p || !s.empty()){if(p){s.push(p);p = p->left;}else{p = s.top();if(++num == k){res = p->val;break;}s.pop();p = p->right;}}return res;}
};

199.二叉树的右视图

java版本

class Solution {public List<Integer> rightSideView(TreeNode root) {List<Integer> res = new ArrayList<>();dfs(root,0,res);return res;}public void dfs(TreeNode root,int depth,List<Integer> res){if(root == null) return ;if(res.size() == depth){res.add(root.val);}dfs(root.right,depth+1,res);dfs(root.left,depth+1,res);}
}

cpp版本

class Solution {
public:vector<int> rightSideView(TreeNode* root) {vector<int> res;dfs(root,0,res);return res;}void dfs(TreeNode *root,int depth,vector<int>& res){if(root == nullptr)return ;if(res.size() == depth){res.push_back(root->val);}dfs(root->right,depth+1,res);dfs(root->left,depth+1,res);}
};

114.二叉树展开为链表

java版本

class Solution {public void flatten(TreeNode root) {while(root != null){if(root.left == null){root = root.right;}else{TreeNode pre = root.left;while(pre.right != null){pre = pre.right;}pre.right = root.right;root.right = root.left;root.left = null;root = root.right;}}}
}

cpp版本

class Solution {
public:void flatten(TreeNode* root) {while(root != null){if(root.left == null){root = root.right;}else{TreeNode pre = root.left;while(pre.right != null){pre = pre.right;}pre.right = root.right;root.right = root.left;root.left = null;root = root.right;}}}
};

105.从前序与中序遍历序列构造二叉树

java版本

class Solution {private HashMap<Integer,Integer> map = new HashMap<>();public TreeNode buildTree(int[] preorder, int[] inorder) {for(int i = 0; i < inorder.length; i++){map.put(inorder[i],i);}return construct(preorder,0,preorder.length-1,inorder,0,inorder.length-1);}public TreeNode construct(int []preorder,int preStart,int preEnd,int []inorder,int inStart,int inEnd){if(preStart > preEnd || inStart > inEnd)return null;TreeNode root = new TreeNode(preorder[preStart]);int i = map.get(root.val);root.left = construct(preorder,preStart+1,preStart+i-inStart,inorder,inStart,i-1);root.right = construct(preorder,preStart+i-inStart+1,preEnd,inorder,i+1,inEnd);return root;}
}

cpp版本

class Solution {
public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {return constructTree(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1);}TreeNode *constructTree(vector<int>& pre,int preStart,int preEnd,vector<int>& in,int inStart,int inEnd){if(preStart > preEnd || inStart > inEnd)return nullptr;TreeNode *root = new TreeNode(pre[preStart]);for(int i = 0; i < in.size(); i++){if(pre[preStart] == in[i]){root->left = constructTree(pre,preStart+1,preStart+i-inStart,in,inStart,i-1);root->right = constructTree(pre,preStart+i-inStart+1,preEnd,in,i+1,inEnd);}}return root;}
};

437.路径总和 III

java版本

class Solution {public int pathSum(TreeNode root, int targetSum) {if(root == null)return 0;return dfs(root,targetSum,0) + pathSum(root.left,targetSum)+pathSum(root.right,targetSum);}public int dfs(TreeNode root,int targetSum, long sum){if(root == null)return 0;sum += root.val;int res = sum == targetSum ? 1 : 0;return res + dfs(root.left,targetSum,sum) + dfs(root.right,targetSum,sum);}
}

cpp版本

class Solution {
public:int pathSum(TreeNode* root, int targetSum) {if(root == nullp)return 0;return dfs(root,targetSum,0)+pathSum(root.left,targetSum)+pathSum(root.right,targetSum);}int dfs(TreeNode root,int targetSum,long long sum){if(root == null)return 0;sum += root.val;int res = sum == targetSum ? 1 : 0;return res + dfs(root.left,targetSum,sum)+dfs(root.right,targetSum,sum);}
};

236.二叉树的最近公共祖先

java版本

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root == null || root == p || root == q)return root;TreeNode l = lowestCommonAncestor(root.left,p,q);TreeNode r = lowestCommonAncestor(root.right,p,q);if(l != null && r != null)return root;else if(l != null)return l;return r;}
}

cpp版本

class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root == nullptr || root ==p || root == q) return root;TreeNode *l = lowestCommonAncestor(root->left,p,q);TreeNode *r = lowestCommonAncestor(root->right,p,q);return (l && r) ? root : (l ? l : r); }
};

124.二叉树中的最大路径和

java版本

class Solution {int res = Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {dfs(root);return res;}public int dfs(TreeNode root){if(root == null)return 0;int l = Math.max(dfs(root.left),0);int r = Math.max(dfs(root.right),0);res = Math.max(res,root.val+l+r);return root.val + Math.max(l,r);}
}

cpp版本

class Solution {
public:int res = INT_MIN;int maxPathSum(TreeNode* root) {dfs(root);return res;}int dfs(TreeNode *root){if(root == nullptr)return 0;int l = max(dfs(root->left),0);int r = max(dfs(root->right),0);res = max(res,root->val+l+r);return root->val+max(l,r);}
};

图论

200.岛屿数量

java版本

class Solution {public int numIslands(char[][] grid) {int m = grid.length, n = grid[0].length, res = 0;for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(grid[i][j] == '1'){dfs(grid,i,j);++res;}}}return res;}public void dfs(char[][] grid,int i,int j){if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0')return ;grid[i][j] = '0';dfs(grid,i-1,j);dfs(grid,i,j+1);dfs(grid,i+1,j);dfs(grid,i,j-1);}
}

cpp版本

class Solution {
public:int numIslands(vector<vector<char>>& grid) {int res=0, m = grid.size(), n = grid[0].size();queue<pair<int,int>> q;int next[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};function<void(int,int)> bfs = [&](int i,int j){grid[i][j] = '0';q.push(make_pair(i,j));while(!q.empty()){auto x = q.front();q.pop();for(int k = 0; k < 4; k++){int nx = x.first + next[k][0];int ny = x.second + next[k][1];if(nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == '1'){grid[nx][ny] = '0';q.push(make_pair(nx,ny));}}}};for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(grid[i][j] == '1'){++res;bfs(i,j);}}}return res;}
};

994.腐烂的橘子

java版本

class Solution {public int orangesRotting(int[][] grid) {int []dx = new int[]{-1,0,1,0};int []dy = new int[]{0,1,0,-1};int m = grid.length, n = grid[0].length;Queue<int[]> q = new LinkedList<>();int freshNums = 0;for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(grid[i][j] == 1){++freshNums;}else if(grid[i][j] == 2){q.offer(new int[]{i,j});}}}int minutes = 0;while(!q.isEmpty()){if(freshNums == 0)return minutes;++minutes;int size = q.size();for(int k = 0; k < size; k++){int[] x = q.poll();for(int i = 0; i < 4; i++){int nx = x[0] + dx[i];int ny = x[1] + dy[i];if(nx < 0 || nx >= m || ny < 0 || ny >= n || grid[nx][ny] != 1) continue;--freshNums;grid[nx][ny] = 2;q.offer(new int[]{nx,ny});}}}return freshNums > 0 ? -1 : minutes;}
}

cpp版本

class Solution {
public:int orangesRotting(vector<vector<int>>& grid) {int next[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};int m = grid.size(), n = grid[0].size(),freshNums = 0,minutes = 0;queue<pair<int,int>> q;for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(grid[i][j] == 2){q.push(make_pair(i,j));}else if(grid[i][j] == 1){++freshNums;}}}while(!q.empty()){if(freshNums == 0)return minutes;++minutes;int size = q.size();for(int i = 0; i < size; i++){auto x = q.front();q.pop();for(int k = 0; k < 4; k++){int nx = x.first + next[k][0];int ny = x.second + next[k][1];if(nx < 0 || nx >= m || ny < 0 || ny >= n || grid[nx][ny] != 1)continue;--freshNums;grid[nx][ny] = 2;q.push(make_pair(nx,ny));}}}return freshNums > 0 ? -1 :minutes;}
};

207.课程表

java版本

class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {List<List<Integer>> edges = new ArrayList<>();int[] inDegrees = new int[numCourses];for(int i = 0; i < numCourses; i++){edges.add(new ArrayList<>());} for(int []p:prerequisites){edges.get(p[1]).add(p[0]);++inDegrees[p[0]];}Queue<Integer> q = new LinkedList<>();for(int i = 0; i < numCourses; i++){if(inDegrees[i] == 0){q.offer(i);}}int res = 0;while(!q.isEmpty()){int x = q.poll();++res;for(int y : edges.get(x)){if(--inDegrees[y] == 0){q.offer(y);}}}return res == numCourses;}
}

cpp版本

class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {vector<vector<int>> g(numCourses);vector<int> inDegree(numCourses);for(auto &p:prerequisites){g[p[1]].push_back(p[0]);++inDegree[p[0]];}queue<int> q;for(int i = 0; i < numCourses; i++){if(inDegree[i] == 0){q.push(i);}}int res = 0;while(!q.empty()){auto x = q.front();q.pop();++res;for(int y:g[x]){if(--inDegree[y] == 0){q.push(y);}}}return res == numCourses;}
};

208.实现 Trie (前缀树)

java版本

class Trie {
class Node{boolean isEnd;Node[] next;public Node(){isEnd = false;next = new Node[26];}
}
private Node root = new Node();public Trie() {}public void insert(String word) {Node node = root;for(char c:word.toCharArray()){if(node.next[c-'a'] == null){node.next[c-'a'] = new Node();}node = node.next[c-'a'];}node.isEnd = true;}public boolean search(String word) {Node node = root;for(char c:word.toCharArray()){node = node.next[c-'a'];if(node == null){return false;}}return node.isEnd;}public boolean startsWith(String prefix) {Node node = root;for(char c:prefix.toCharArray()){node = node.next[c-'a'];if(node == null){return false;}}return true;}
}

cpp版本

class Trie {
private:bool isEnd;Trie *next[26];
public:Trie() {isEnd = false;memset(next,0,sizeof(next));}void insert(string word) {Trie *node = this;for(char c:word){if(node->next[c-'a'] == nullptr)node->next[c-'a']  = new Trie();node = node->next[c-'a'];}node->isEnd = true;}bool search(string word) {Trie *node = this;for(char c:word){node = node->next[c-'a'];if(node == nullptr) return false;}return node->isEnd;}bool startsWith(string prefix) {Trie *node = this;for(char c:prefix){node = node->next[c-'a'];if(node == nullptr) return false;}return true;}
};

回溯

46.全排列

java版本

class Solution {public List<List<Integer>> permute(int[] nums) {List<List<Integer>> res = new ArrayList<>();dfs(nums,0,res);return res;}public void dfs(int[] nums,int index,List<List<Integer>> res){if(index == nums.length){res.add(new ArrayList<>(Arrays.asList(nums)));return ;}for(int i = index; i < nums.length; i++){swap(nums,i,index);dfs(nums,index+1,res);swap(nums,i,index);}}public void swap(int[] nums,int i,int j){int t = nums[i];nums[i] = nums[j];nums[j] = t;}
}

cpp版本

class Solution {
public:vector<vector<int>> permute(vector<int>& nums) {vector<vector<int>> res;int n =nums.size();function<void(int)> backtrack = [&](int index){if(index == nums.size()){res.push_back(nums);}for(int i = index; i < n; i++){swap(nums[i],nums[index]);backtrack(index+1);swap(nums[i],nums[index]);}};backtrack(0);return res;}
};

78.子集

java版本

class Solution {public List<List<Integer>> subsets(int[] nums) {int n = nums.length;List<List<Integer>> res = new ArrayList<>();for(int mask = 0; mask < (1<<n); mask++){List<Integer> tmp = new ArrayList<>();for(int i = 0; i < n; i++){if((mask&(1<<i)) != 0){tmp.add(nums[i]);}}res.add(tmp);}return res;}
}

cpp版本

class Solution {
public:vector<vector<int>> subsets(vector<int>& nums) {vector<vector<int>> res;vector<int> tmp;res.push_back(tmp);function<void(int)> backtrack = [&](int index){if(index >= nums.size())return ;for(int i = index; i < nums.size(); i++){tmp.push_back(nums[i]);res.push_back(tmp);backtrack(i+1);tmp.pop_back();}};backtrack(0);return res;}
};

17.电话号码的字母组合

java版本

class Solution {Map<Character,String> phoneMap = new HashMap<>(){{put('2',"abc");put('3',"def");put('4',"ghi");put('5',"jkl");put('6',"mno");put('7',"pqrs");put('8',"tuv");put('9',"wxyz");}};public List<String> letterCombinations(String digits) {List<String> res = new ArrayList<>();if(digits.length() == 0)return res;backtrack(digits,0,phoneMap,new StringBuilder(),res);return res;}public void backtrack(String digits,int index,Map<Character,String> phoneMap,StringBuilder sb,List<String> res){if(index > digits.length()) return ;if(sb.length() == digits.length()){res.add(sb.toString());return ;}char ix = digits.charAt(index);String ss = phoneMap.get(ix);for(int i = 0; i < ss.length(); i++){sb.append(ss.charAt(i));backtrack(digits,index+1,phoneMap,sb,res);sb.deleteCharAt(index);}}
}

cpp版本

class Solution {
public:vector<string> letterCombinations(string digits) {if(digits.size() == 0)return {};vector<string> res;string s[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};function<void(int,string)> backtrack =[&](int index,string tmp){if(index == digits.size()){res.push_back(tmp);return ;}string ss = s[digits[index]-'0'];for(int i = 0; i < ss.size(); i++){tmp.push_back(ss[i]);backtrack(index+1,tmp);tmp.pop_back();}};backtrack(0,"");return res;}
};

39.组合总和

java版本

class Solution {public List<List<Integer>> combinationSum(int[] candidates, int target) {List<List<Integer>> res = new ArrayList<>();backtrack(candidates,0,0,target,new ArrayList<>(),res);return res;}public void backtrack(int[] candidates,int index,int tmp,int target,List<Integer> path,List<List<Integer>> res){if(tmp > target || index >= candidates.length)return ;if(tmp == target){res.add(new ArrayList<>(path));}for(int i = index; i < candidates.length; i++){path.add(candidates[i]);backtrack(candidates,i,tmp+candidates[i],target,path,res);path.remove(path.size()-1);}}
}

cpp版本

class Solution {
public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {vector<vector<int>> res;vector<int> tmp;int n = candidates.size();function<void(int,int)> backtrack = [&](int index,int sum){if(sum > target || index >= candidates.size())return ;if(sum == target){res.push_back(tmp);}for(int i = index; i < candidates.size(); i++){tmp.push_back(candidates[i]);backtrack(i,sum+candidates[i]);tmp.pop_back();}};backtrack(0,0);return res;}
};

22.括号生成

java版本

class Solution {public List<String> generateParenthesis(int n) {List<String> res = new ArrayList<>();backtrack(res,new StringBuilder(),0,0,n);return res;}public void backtrack(List<String> res,StringBuilder sb,int left,int right,int n){if(sb.length() == 2*n){res.add(sb.toString());return ;}if(left < n){sb.append('(');backtrack(res,sb,left+1,right,n);sb.deleteCharAt(sb.length()-1);}if(right < left){sb.append(')');backtrack(res,sb,left,right+1,n);sb.deleteCharAt(sb.length()-1);}}
}

cpp版本

class Solution {
public:vector<string> generateParenthesis(int n) {vector<string> res;function<void(int,int,string)> backtrack = [&](int left,int right,string s){if(s.size()== 2*n){res.push_back(s);return ;}if(left < n){backtrack(left+1,right,s+'(');}if(right < left){backtrack(left,right+1,s+')');}};  backtrack(0,0,"");return res;}
};

79.单词搜索

java版本

class Solution {public boolean exist(char[][] board, String word) {boolean flag = false;int row = board.length;int col = board[0].length;boolean[][] visited = new boolean[row][col];for(int i = 0; i < row; i++){for(int j = 0; j < col; j++){if(check(board,i,j,word,visited,0))return true;}}return false;}public boolean check(char[][] board,int i,int j,String word,boolean[][] visited,int idx){if(board[i][j] != word.charAt(idx))return false;if(idx == word.length()-1) return true;visited[i][j] = true;int[][] directions = {{-1,0},{0,1},{1,0},{0,-1}};for(int[] dir: directions){int tx = i + dir[0];int ty = j + dir[1];if(tx < 0 || tx >= board.length || ty < 0 || ty >= board[0].length || visited[tx][ty] == true) continue;if(check(board,tx,ty,word,visited,idx+1))return true;}visited[i][j] = false;return false;}
}

cpp版本

class Solution {
public:bool exist(vector<vector<char>>& board, string word) {int next[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};int m = board.size(), n = board[0].size();vector<vector<bool>> vis(m,vector<bool>(n,false));function<bool(int,int,int)> backtrack = [&](int i,int j,int index){if(index == word.size()-1){return true;}vis[i][j] = true;for(int k = 0; k < 4; k++){int nx = i + next[k][0];int ny = j + next[k][1];if(nx >= 0 && nx < m && ny >= 0 && ny < n && !vis[nx][ny] && board[nx][ny] == word[index+1]){if(backtrack(nx,ny,index+1))return true;}}vis[i][j] = false;return false;};for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(word[0] == board[i][j])if(backtrack(i,j,0))return true;}}return false;}
};

131.分割回文串

java版本

class Solution {public List<List<String>> partition(String s) {List<List<String>> ret = new ArrayList<List<String>>();int len = s.length();if(len == 0) return ret;Deque<String> stack = new ArrayDeque<String>();trackBack(s,0,len,stack,ret);return ret;}public void trackBack(String s,int start, int len,Deque<String> stack, List<List<String>> ret){if(start == len){ret.add(new ArrayList<>(stack));return ;}for(int i = start; i < len; i++){if(!check(s,start,i)){continue;}stack.addLast(s.substring(start,i+1));trackBack(s,i+1,len,stack,ret);stack.removeLast();}}public boolean check(String s,int left, int right){while(left < right){if(s.charAt(left) != s.charAt(right)){return false;}++left;--right;}return true;}
}

cpp版本

class Solution {
public:vector<vector<string>> partition(string s) {vector<vector<string>> res;vector<string> tmp;function<void(int)> backtrack = [&](int index){if(index == s.size()){res.push_back(tmp);return ;}for(int i = index; i < s.size(); i++){string ss = s.substr(index,i-index+1);if(!check(ss))continue;tmp.push_back(ss);backtrack(i+1);tmp.pop_back();}} ;backtrack(0);return res;}bool check(string s){int l = 0, r = s.size()-1;while(l <= r){if(s[l++] != s[r--])return false;}return true;}
};

51.N 皇后

java版本

class Solution {public List<List<String>> solveNQueens(int n) {List<List<String>> res = new ArrayList<List<String>>();int []queens = new int[n];Arrays.fill(queens,-1);Set<Integer> columns = new HashSet<>();Set<Integer> diagonals1 = new HashSet<>();Set<Integer> diagonals2= new HashSet<>();backtrack(0,n,queens,res,columns,diagonals1,diagonals2);return res;}public List<String> generateBoard(int []queens,int n){List<String> board = new ArrayList<>();for(int i = 0; i < n; i++){char []c = new char[n];Arrays.fill(c,'.');c[queens[i]] = 'Q';board.add(new String(c));}return board;}public void backtrack(int row,int n, int[] queens,List<List<String>> res,Set<Integer> columns,Set<Integer> diagonals1,Set<Integer> diagonals2){if(row == n){List<String> board = generateBoard(queens,n);res.add(board);return ;}for(int i = 0; i < n; i++){int diagonal1 = row-i;int diagonal2 = row+i;if(columns.contains(i) || diagonals1.contains(diagonal1) || diagonals2.contains(diagonal2)) continue;queens[row] = i;columns.add(i);diagonals1.add(diagonal1);diagonals2.add(diagonal2);backtrack(row+1,n,queens,res,columns,diagonals1,diagonals2);queens[row] = -1;columns.remove(i);diagonals1.remove(diagonal1);diagonals2.remove(diagonal2);}        }
}

cpp版本

class Solution {
public:vector<vector<string>> solveNQueens(int n) {vector<vector<string>> res;vector<int> queen(n,-1);unordered_set<int> col,diagnoals1,diagnoals2;function<void(int)> backtrack = [&](int row){if(row == n){vector<string> board = generatedBoard(queen,n);res.push_back(board);return ;}for(int i = 0; i < n; i++){int diagnoal1 = i+row, diagnoal2 = i - row;if(col.count(i) || diagnoals1.count(diagnoal1) || diagnoals2.count(diagnoal2))continue;queen[row] = i;col.insert(i);diagnoals1.insert(diagnoal1);diagnoals2.insert(diagnoal2);backtrack(row+1);queen[row] = -1;col.erase(i);diagnoals1.erase(diagnoal1);diagnoals2.erase(diagnoal2);}};backtrack(0);return res;}vector<string> generatedBoard(vector<int> queen,int n){vector<string> res;for(int i = 0; i < n; i++){string s(n,'.');s[queen[i]] = 'Q';res.push_back(s); }return res;}
};

二分查找

35.搜索插入位置

java版本

class Solution {public int searchInsert(int[] nums, int target) {int n = nums.length , l = 0, r = n-1;while(l <= r){int mid = ((r-l)>>1)+l;if(nums[mid] < target){l = mid+1;}else{r = mid-1;}}return l;}
}

cpp版本

class Solution {
public:int searchInsert(vector<int>& nums, int target) {int l = 0,r = nums.size()-1;while(l <= r){int mid = ((r-l)>>1)+l;if(nums[mid] < target) l = mid+1;else r = mid-1;}return l;}
};

74.搜索二维矩阵

java版本

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length , n = matrix[0].length;int l = 0, r = m*n-1;while(l <= r){int mid = ((r-l)>>1)+l, num = matrix[mid/n][mid%n];if(num == target){return true;}else if(num < target){l = mid+1;}else{r = mid-1;}}return false;}
}

cpp版本

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int i = 0, j = matrix[0].size()-1;while(i < matrix.size() && j >= 0){if(matrix[i][j] == target){return true;}else if(matrix[i][j] < target){++i;}else{--j;}}return false;}
};

34.在排序数组中查找元素的第一个和最后一个位置

java版本

class Solution {public int[] searchRange(int[] nums, int target) {int begin = lower_bound(nums,target);if(begin == nums.length || nums[begin] != target){return new int[]{-1,-1};}int end = lower_bound(nums,target+1);return new int[]{begin,end-1};}public int lower_bound(int[] nums,int target){int n = nums.length , l = 0, r = n-1;while(l <= r){int mid = ((r-l)>>1)+l;if(nums[mid] < target){l = mid+1;}else{r = mid-1;}}return l;}
}

cpp版本

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {int begin = lower_bound(nums,target);if(begin == nums.size() || nums[begin] != target)return {-1,-1};int end = lower_bound(nums,target+1);return {begin,end-1};}int lower_bound(vector<int>& nums,int target){int l = 0, r = nums.size()-1;while(l <= r){int mid = ((r-l)>>1)+l;if(nums[mid] < target){l = mid+1;}else{r = mid-1;}}return l;}
};

33.搜索旋转排序数组

java版本

class Solution {public int search(int[] nums, int target) {int l = 0, r = nums.length-1;while(l <= r){int mid = ((r-l)>>1)+l;if(nums[mid] == target){return mid;}else if(nums[l] <= nums[mid]){if(target >= nums[l] && target < nums[mid]){r = mid-1;}else{l = mid+1;}}else{if(target > nums[mid] && target  <= nums[r]){l = mid+1;}else{r = mid-1;}}}return -1;}
}

cpp版本

class Solution {
public:int search(vector<int>& nums, int target) {int l = 0, r = nums.size()-1;while(l <= r){int mid = ((r-l)>>1)+l;if(nums[mid] == target){return mid;}else if(nums[l] <= nums[mid]){if(target >= nums[l] && target < nums[mid]){r = mid-1;}else{l = mid+1;}}else{if(target > nums[mid] && target <= nums[r]){l = mid+1;}else{r = mid-1;}}}return -1;}
};

153.寻找旋转排序数组中的最小值

java版本

class Solution {public int findMin(int[] nums) {int l = 0, r = nums.length-1;while(l < r){int mid = ((r-l)>>1)+l;if(nums[l] < nums[r]){return nums[l];}else if(nums[mid] < nums[r]){r = mid;}else{l = mid+1;}}return nums[l];}
}

cpp版本

class Solution {
public:int findMin(vector<int>& nums) {int l = 0, r = nums.size()-1;while(l <= r){int mid = ((r-l)>>1)+l;if(nums[l] <= nums[r])return nums[l];else if(nums[mid] < nums[r]) r = mid;else l = mid+1;}return nums[l];}
};

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

cpp版本

class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {priority_queue<int> qMax;priority_queue<int,vector<int>,greater<int>> qMin;for(int num:nums1){qMax.push(num);qMin.push(qMax.top());qMax.pop();if(qMax.size() < qMin.size()){qMax.push(qMin.top());qMin.pop();}}for(int num:nums2){qMax.push(num);qMin.push(qMax.top());qMax.pop();if(qMax.size() < qMin.size()){qMax.push(qMin.top());qMin.pop();}}if(qMax.size() > qMin.size())return qMax.top();return (qMax.top()+qMin.top())*1.0/2;}
};

栈

20.有效的括号

java版本

class Solution {public boolean isValid(String s) {if(s.length()%2 == 1){return false;}Deque<Character> stk = new LinkedList<>();char[] S = s.toCharArray();for(char c:S){if(c == '('){stk.push(')');}else if(c == '{'){stk.push('}');}else if(c == '['){stk.push(']');}else if(stk.isEmpty() || stk.peek() != c){return false;}else{stk.pop();}}return stk.isEmpty();}
}

cpp版本

class Solution {
public:bool isValid(string s) {if(s.size() % 2 == 1)return false;stack<int> stk;for(char c:s){if(c == '(')stk.push(')');else if(c == '{')stk.push('}');else if(c == '[')stk.push(']');else if(stk.empty() || c != stk.top())return false;else stk.pop();}return stk.empty();}
};

155.最小栈

java版本

class MinStack {Deque<Integer> s;int minElement = Integer.MAX_VALUE;public MinStack() {s = new LinkedList<>();}public void push(int val) {if(s.isEmpty()){s.push(val);minElement = val;}else{if(val <= minElement){s.push(minElement);minElement = val;}s.push(val);}}public void pop() {if(s.isEmpty())return ;if(s.peek() == minElement){if(s.size() > 1){s.pop();minElement = s.peek();}else{minElement = Integer.MAX_VALUE;}}s.pop();}public int top() {return s.peek();}public int getMin() {return minElement;}
}

cpp版本

class MinStack {
public:int minn = INT_MAX;stack<int> s;MinStack() {}void push(int val) {if(s.empty()){s.push(val);minn = val;}else{if(val <= minn){s.push(minn);minn = val;}s.push(val);}}void pop() {if(s.empty())return ;if(s.top() == minn){if(s.size() == 1){minn = INT_MAX;}else{s.pop();minn = s.top();}}s.pop();}int top() {return s.top();}int getMin() {return minn;}
};

394.字符串解码

java版本
cpp版本

class Solution {
public:string decodeString(string s) {vector<char> res;for(char c:s){if(c != ']'){res.push_back(c);}else{vector<char> copy_str;while(res.back() != '['){copy_str.push_back(res.back());res.pop_back();}res.pop_back();reverse(copy_str.begin(),copy_str.end());int copy_times = 0, ratio = 1;while(!res.empty() && res.back() >= '0' && res.back() <= '9'){copy_times += (res.back()-'0')*ratio;ratio *= 10;res.pop_back();}for(int i = 0; i < copy_str.size() * copy_times; i++){res.push_back(copy_str[i%copy_str.size()]);}}}return string(res.begin(),res.end());}
};

739.每日温度

java版本

class Solution {public int[] dailyTemperatures(int[] temperatures) {int n = temperatures.length;int[] res = new int[n];Deque<Integer> stk = new LinkedList<>();for(int i = 0; i < n; i++){while(!stk.isEmpty() && temperatures[i] > temperatures[stk.peek()]){int index = stk.pop();res[index] = i - index;}stk.push(i);}return res;}
}

cpp版本

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {stack<int> s;vector<int> res(temperatures.size());for(int i = 0; i < temperatures.size(); i++){while(!s.empty() && temperatures[i] > temperatures[s.top()]){int index = s.top();res[index] = i - index;s.pop();}s.push(i);}return res;}
};

84.柱状图中最大的矩形

java版本

class Solution {public int largestRectangleArea(int[] heights) {int n = heights.length,res = 0, h = 0, w = 0;Deque<Integer> s = new LinkedList<>();for(int i = 0; i < n; i++){while(!s.isEmpty() && heights[i] < heights[s.peek()]){h = heights[s.pop()];w = i;if(!s.isEmpty()){w = w - s.peek()-1;}res = Math.max(res,h*w);}s.push(i);}while(!s.isEmpty()){h = heights[s.pop()];w = n;if(!s.isEmpty()){w = w - s.peek() - 1;}res = Math.max(res,h*w);}return res;}
}

cpp版本

class Solution {
public:int largestRectangleArea(vector<int>& heights) {int res = 0,n = heights.size(), h ,w;stack<int> s;for(int i = 0;i < n; i++){while(!s.empty() && heights[i] < heights[s.top()]){h = heights[s.top()];s.pop();w = i;if(!s.empty()){w = w - s.top()-1;}res = max(res,h*w);}s.push(i);}while(!s.empty()){h = heights[s.top()];s.pop();w = n;if(!s.empty()){w = w - s.top()-1;}res = max(res,h*w);}return res;}
};

堆

215.数组中的第K个最大元素

java版本

class Solution {public int findKthLargest(int[] nums, int k) {List<Integer> list = new ArrayList<>();for(int num:nums){list.add(num);}return quickSelect(list,k);}public int quickSelect(List<Integer> nums,int k){Random random = new Random();int pivot = nums.get(random.nextInt(nums.size()));List<Integer> big = new ArrayList<>();List<Integer> equal = new ArrayList<>();List<Integer> small = new ArrayList<>();for(int num:nums){if(num > pivot){big.add(num);}else if(num == pivot){equal.add(num);}else{small.add(num);}}if(k <= big.size()){return quickSelect(big,k);}else if(k > equal.size() + big.size()){return quickSelect(small,k-equal.size()-big.size());}else{return pivot;}}
}

cpp版本

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {return quickSelect(nums,k);}int quickSelect(vector<int>& nums,int k){int pivot = nums[rand()%nums.size()];vector<int> big,equal,small;for(int i = 0; i < nums.size(); i++){if(nums[i] < pivot){small.push_back(nums[i]);}else if(nums[i] > pivot){big.push_back(nums[i]);}else{equal.push_back(nums[i]);}}if(k <= big.size()){return quickSelect(big,k);}else if(k > big.size()+equal.size()){return quickSelect(small,k-big.size()-equal.size());}else{return pivot;}}
};

347.前 K个高频元素

java版本

class Solution {public int[] topKFrequent(int[] nums, int k) {Map<Integer,Integer> map = new HashMap<>();PriorityQueue<int[]> q = new PriorityQueue<int[]>(Comparator.comparingInt(a->a[0]));for(int i = 0; i < nums.length; i++){map.put(nums[i],map.getOrDefault(nums[i],0)+1);}for(Integer key:map.keySet()){if(q.size() < k){q.offer(new int[]{map.get(key),key});}else{if(map.get(key) > q.peek()[0]){q.poll();q.offer(new int[]{map.get(key),key});}}}int []res = new int[k];int i = 0;while(!q.isEmpty()){res[i++] = q.peek()[1];q.poll();}return res;}
}

cpp版本

class Solution {
public:vector<int> topKFrequent(vector<int>& nums, int k) {unordered_map<int,int> m;for(int n:nums){++m[n];}priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;for(auto &[num,cnt]:m){if(q.size() < k){q.emplace(cnt,num);}else{if(cnt > q.top().first){q.pop();q.emplace(cnt,num);}}}vector<int> res;while(!q.empty()){res.push_back(q.top().second);q.pop();}return res;}
};

295.数据流的中位数

java版本

class MedianFinder {PriorityQueue<Integer> queMin;PriorityQueue<Integer> queMax;public MedianFinder() {queMax = new PriorityQueue<>((a,b)->(a-b));queMin = new PriorityQueue<>((a,b)->(b-a));}public void addNum(int num) {queMin.offer(num);queMax.offer(queMin.poll());if(queMin.size() < queMax.size()){queMin.offer(queMax.poll());}}public double findMedian() {if(queMin.size() > queMax.size()){return queMin.peek();}return (queMin.peek()+queMax.peek())/2.0;}
}

cpp版本

class MedianFinder {
public:priority_queue<int> qMax;priority_queue<int,vector<int>,greater<int>> qMin;MedianFinder() {}void addNum(int num) {qMax.push(num);qMin.push(qMax.top());qMax.pop();if(qMax.size() < qMin.size()){qMax.push(qMin.top());qMin.pop();}}double findMedian() {if(qMax.size() > qMin.size())return qMax.top();return (qMax.top()+qMin.top())*1.0/2;}
};

贪心算法

121.买卖股票的最佳时机

java版本

class Solution {public int maxProfit(int[] prices) {int buy = Integer.MAX_VALUE, sell = 0;for(int p:prices){buy = Math.min(buy,p);sell = Math.max(sell,p-buy);}return sell;}
}

cpp版本

class Solution {
public:int maxProfit(vector<int>& prices) {int buy = INT_MAX, sell = 0;for(int p:prices){buy = min(buy,p);sell = max(sell,p-buy);}return sell;}
};

55.跳跃游戏

java版本

class Solution {public boolean canJump(int[] nums) {int n = nums.length , maxPos = 0;for(int i = 0; i < n; i++){if(i <= maxPos){maxPos = Math.max(maxPos,i+nums[i]);if(maxPos >= n-1)return true;}}return false;}
}

cpp版本

class Solution {
public:bool canJump(vector<int>& nums) {int n = nums.size(), rightMost = 0;for(int i = 0; i < n; i++){if(i <= rightMost){rightMost = max(rightMost,i+nums[i]);if(rightMost >= n-1)return true;}}return false;}
};

45.跳跃游戏 II

java版本

class Solution {public int jump(int[] nums) {int res = 0,n = nums.length, end = 0, maxPos = 0;for(int i = 0; i < n-1; i++){maxPos = Math.max(maxPos,i+nums[i]);if(i == end){++res;end = maxPos;}}return res;}
}

cpp版本

class Solution {
public:int jump(vector<int>& nums) {int n = nums.size(), res = 0, maxPos = 0, end = 0;for(int i = 0; i < n-1; i++){maxPos = max(maxPos,i+nums[i]);if(i == end){++res;end = maxPos;}}return res;}
};

763.划分字母区间

java版本

class Solution {public List<Integer> partitionLabels(String s) {List<Integer> res = new ArrayList<>();int[] hash = new int[26];for(int i = 0; i <s.length(); i++){hash[s.charAt(i)-'a'] = i;}int l = 0, r = 0;for(int i = 0; i < s.length(); i++){r = Math.max(r,hash[s.charAt(i)-'a']);if(r == i){res.add(r-l+1);l = r+1;}}return res;}
}

cpp版本

class Solution {
public:vector<int> partitionLabels(string s) {int n = s.size();int hash[26];for(int i = 0; i < n; i++){hash[s[i]-'a'] = i;}int l = 0, r = 0;vector<int> res;for(int i = 0; i < n; i++){r = max(r,hash[s[i]-'a']);if(i == r){res.push_back(r-l+1);l = r+1;}}return res;}
};

动态规划

70.爬楼梯

java版本

class Solution {public int climbStairs(int n) {if(n == 1|| n== 2)return n;int f1 = 1 ,f2 = 2, res = 0;for(int i = 3; i <= n; i++){res = f1 + f2;f1 = f2;f2 = res;}return res;}
}

cpp版本

class Solution {
public:int climbStairs(int n) {if(n == 1 || n == 2)return n;int f1 = 1,f2 = 2,res = 0;for(int i = 3; i <= n; i++){res = f1+f2;f1 = f2;f2 = res;}return res;}
};

118.杨辉三角

java版本

class Solution {public List<List<Integer>> generate(int numRows) {List<List<Integer>> res = new ArrayList<>();for(int i = 0; i < numRows; i++){List<Integer> list = new ArrayList<>();for(int j = 0; j <= i; j++){if(j == 0 || j == i){list.add(1);}else{list.add(res.get(i-1).get(j)+res.get(i-1).get(j-1));}}res.add(list);}return res;}
}

cpp版本

class Solution {
public:vector<vector<int>> generate(int numRows) {vector<vector<int>> res(numRows);for(int i = 0; i < numRows; i++){res[i].resize(i+1);res[i][0] = res[i][i] = 1;for(int j = 1; j < i; j++){res[i][j] = res[i-1][j]+res[i-1][j-1];}}return res;}
};

198.打家劫舍

java版本

class Solution {public int rob(int[] nums) {int n = nums.length;int []dp = new int[n+1];dp[1] = nums[0];for(int i = 2; i <= n; i++){dp[i] = Math.max(dp[i-1],nums[i-1]+dp[i-2]);}return dp[n];}
}

cpp版本

class Solution {
public:int rob(vector<int>& nums) {int n = nums.size(), f1 = 0, f2 = nums[0];for(int i = 2; i <= n; i++){int t= f2;f2 = max(f2,f1+nums[i-1]);f1 = t;}return f2;}
};

279.完全平方数

java版本

class Solution {public int numSquares(int n) {int []dp = new int[n+1];Arrays.fill(dp,Integer.MAX_VALUE);dp[0] = 0;for(int i = 1; i*i <= n; i++){for(int j = 1; j <= n; j++){if(j >= i*i){dp[j] = Math.min(dp[j],dp[j-i*i]+1);}}}return dp[n];}
}

cpp版本

class Solution {
public:int numSquares(int n) {vector<int> dp(n+1,n);dp[0] = 0;for(int i = 1; i*i <= n; i++){for(int j = i*i; j <= n; j++){dp[j] = min(dp[j],dp[j-i*i]+1);}}return dp[n];}
};

322.零钱兑换

java版本

class Solution {public int coinChange(int[] coins, int amount) {int n = coins.length;int[] dp = new int[amount+1];Arrays.fill(dp,amount+1);dp[0] = 0;for(int coin:coins){for(int j = coin; j <= amount; j++){dp[j] = Math.min(dp[j],dp[j-coin]+1);}}return dp[amount] > amount ? -1 : dp[amount];}
}

cpp版本

class Solution {
public:int coinChange(vector<int>& coins, int amount) {int n = coins.size();vector<int> dp(amount+1,amount+1);dp[0] = 0;for(int coin:coins){for(int j = coin; j <= amount; j++){dp[j] = min(dp[j],dp[j-coin]+1);}}return dp[amount] > amount ? -1 : dp[amount]; }
};

139.单词拆分

java版本

class Solution {public boolean wordBreak(String s, List<String> wordDict) {int n = s.length();boolean []dp = new boolean[n+1];dp[0] = true;for(int i = 1; i <= n; i++){for(String word:wordDict){int size = word.length();if(i-size >= 0 && i+1 <= n &&s.substring(i-size,i+1) == word){dp[i] = dp[i] || dp[i-size];}}}return dp[n];}
}

cpp版本

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {int n = s.size();vector<bool> dp(n+1,false);dp[0] = true;for(int i = 1; i <= n; i++){for(string &ss:wordDict){int size = ss.size();if(i - size >= 0 && s.substr(i-size,size) == ss){dp[i]  =dp[i] || dp[i-size];}}}return dp[n];}
};

300.最长递增子序列

java版本

class Solution {public int lengthOfLIS(int[] nums) {int n = nums.length;List<Integer> list = new ArrayList<>();for(int i = 0; i < n; i++){if(list.isEmpty() || nums[i] > list.get(list.size()-1)){list.add(nums[i]);}else{int index = -1, l = 0, r = list.size()-1;while(l <= r){int mid = ((r-l)>>1)+l;if(list.get(mid) < nums[i]){l = mid+1;}else{index = mid;r = mid-1;}}list.set(index,nums[i]);}}return list.size();}
}

cpp版本

class Solution {
public:int lengthOfLIS(vector<int>& nums) {int n = nums.size();vector<int> res;for(int i = 0; i < n; i++){if(res.empty() || nums[i] > res.back()){res.push_back(nums[i]);}else{int l = 0, r = res.size()-1;while(l <= r){int mid = ((r-l)>>1)+l;if(res[mid] < nums[i]){l = mid+1;}else{r = mid-1;}}res[l] = nums[i];}}return res.size();}
};

152.乘积最大子数组

java版本

class Solution {public int maxProduct(int[] nums) {int res = Integer.MIN_VALUE, maxn = 1, minn = 1, n = nums.length;for(int i = 0; i < n; i++){if(nums[i] < 0){int t = minn;minn = maxn;maxn = t;}maxn = Math.max(maxn*nums[i],nums[i]);minn = Math.min(minn*nums[i],nums[i]);res = Math.max(res,maxn);}return res;}
}

cpp版本

class Solution {
public:int maxProduct(vector<int>& nums) {long long res = INT_MIN, maxn = 1, minn = 1, t, n = nums.size();for(int i = 0; i < n; i++){if(nums[i] < 0){t = maxn;maxn = minn;minn = t;}if(maxn*nums[i] > nums[i]){maxn = maxn*nums[i];}else{maxn = nums[i];}if(nums[i]*minn < nums[i]){minn = nums[i]*minn;}else{minn = nums[i];}res = max(res,maxn);}return res;}
};

416.分割等和子集

java版本

class Solution {public boolean canPartition(int[] nums) {int len = nums.length, sum = 0, maxNum = 0;for(int x:nums){sum += x;maxNum = Math.max(maxNum,x);}if((sum & 1) != 0)return false;int target = sum / 2;if(maxNum > target)return false;boolean []dp = new boolean[target+1];dp[0] = true;for(int i = 0; i < len; i++){for(int j = target; j >= 0; j--){if(j >= nums[i]){dp[j] = dp[j] || dp[j-nums[i]];}}}return dp[target];}
}

cpp版本

class Solution {
public:bool canPartition(vector<int>& nums) {int sum = 0,n = nums.size();for(int i = 0; i < n; i++){sum += nums[i];}if(sum % 2 == 1)return false;int target = sum/2;vector<bool> dp(target+1,false);dp[0] = true;for(int arr:nums){for(int i = target; i >= arr; i--){dp[i] = dp[i] || dp[i-arr];}}return dp[target];}
};

32.最长有效括号

java版本

class Solution {public int longestValidParentheses(String s) {int res = 0, l = 0, r = 0;for(char c:s.toCharArray()){if(c == '(')++l;else++r;if(l == r){res = Math.max(res,2*l);}else if(r > l)l = r = 0;}l = r = 0;for(int i = s.length()-1; i >= 0; i--){if(s.charAt(i) == ')'){++r;}else{++l;}if(l == r){res = Math.max(res,2*l);}else if(l > r){l = r = 0;}}return res;}
}

多维动态规划

62.不同路径

java版本

class Solution {public int uniquePaths(int m, int n) {int[] dp = new int[n];Arrays.fill(dp,1);for(int i = 1; i < m; i++){for(int j = 1; j < n; j++){dp[j] += dp[j-1];}}return dp[n-1];}
}

cpp版本

class Solution {
public:int uniquePaths(int m, int n) {vector<int> dp(n,1);for(int i = 1; i < m; i++){for(int j = 1; j < n; j++)dp[j] += dp[j-1];}return dp[n-1];}
};

64.最小路径和

java版本

class Solution {public int minPathSum(int[][] grid) {int m = grid.length, n = grid[0].length;int [][]dp  = new int[m][n];dp[0][0] = grid[0][0];for(int i = 1; i < m; i++){dp[i][0] = dp[i-1][0] + grid[i][0];}for(int j = 1; j < n; j++){dp[0][j] = dp[0][j-1] + grid[0][j];}for(int i = 1; i < m; i++){for(int j = 1; j < n; j++){dp[i][j] =  Math.min(dp[i-1][j],dp[i][j-1]) + grid[i][j];}}return dp[m-1][n-1];}
}

cpp版本

class Solution {
public:int res[202];int minPathSum(vector<vector<int>>& grid) {memset(res,0x3f,sizeof(res));int m = grid.size(), n = grid[0].size();res[1] = 0;for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++){res[j] = min(res[j-1],res[j])+grid[i-1][j-1];}}return res[n];}
};

5.最长回文子串

java版本

class Solution {public String longestPalindrome(String s) {if(s.length() < 2){return s;}int []res = new int[2];int maxLen = 0, n = s.length();for(int i = 0; i < n-1; i++){int[] odd = centerSpread(s,i,i);int[] even = centerSpread(s,i,i+1);int[] maxn = odd[1] > even[1] ? odd : even;if(maxn[1] > maxLen){maxLen = maxn[1];res = maxn;}}return s.substring(res[0],res[0]+res[1]);}int[] centerSpread(String s,int l,int r){int n = s.length();while(l >= 0 && r < n){if(s.charAt(l) == s.charAt(r)){--l;++r;}else{break;}}return new int[]{l+1,r-l-1};}
}

cpp版本

class Solution {
public:string longestPalindrome(string s) {if(s.size() == 1)return s;int n = s.size(), maxLen = 0;vector<int> res(2);for(int i = 0; i < n-1; i++){vector<int> odd = centerSpread(s,i,i);vector<int> even = centerSpread(s,i,i+1);vector<int> bigger = odd[1] > even[1] ? odd : even;if(bigger[1] > maxLen){maxLen = bigger[1];res = bigger;}}return s.substr(res[0],res[1]);}vector<int> centerSpread(string s,int l,int r){int n = s.size();while(l >= 0 && r < n){if(s[l] == s[r]){--l;++r;}else{break;}}return {l+1,r-l-1};}
};

1143.最长公共子序列

java版本

class Solution {public int longestCommonSubsequence(String text1, String text2) {int m = text1.length(), n = text2.length();int[][] dp = new int[m+1][n+1];for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++){dp[i][j] = text1.charAt(i-1) == text2.charAt(j-1) ? dp[i-1][j-1]+1 : Math.max(dp[i-1][j],dp[i][j-1]);}}return dp[m][n];}
}

cpp版本

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {int m = text1.size(), n = text2.size();vector<vector<int>> dp(m+1,vector<int>(n+1,0));for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++){if(text1[i-1] == text2[j-1]){dp[i][j] = dp[i-1][j-1]+1;}else{dp[i][j] = max(dp[i-1][j],dp[i][j-1]);}}}return dp[m][n];}
};

72.编辑距离

java版本

class Solution {public int minDistance(String word1, String word2) {int m = word1.length(), n = word2.length();int[][] dp = new int[m+1][n+1];for(int i = 0; i <= m ;i++){dp[i][0] = i;}for(int j = 0; j <= n; j++){dp[0][j] = j;}for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++){if(word1.charAt(i-1) == word2.charAt(j-1)){dp[i][j] = dp[i-1][j-1];}else{dp[i][j] = 1 + Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]));}}}return dp[m][n];}
}

技巧

136.只出现一次的数字

java版本

class Solution {public int singleNumber(int[] nums) {int res = 0;for(int num:nums){res ^= num;}return res;}
}

169.多数元素

java版本

class Solution {public int majorityElement(int[] nums) {int res = nums[0],cnt = 1, n = nums.length;for(int i = 1; i < n; i++){if(res == nums[i]){++cnt;}else{if(--cnt == 0){res = nums[i];cnt = 1;}}}return res;}
}

75.颜色分类

java版本

class Solution {public void sortColors(int[] nums) {int l = 0, r = nums.length-1;for(int i = 0; i <= r; i++){while(i <= r && nums[i] == 2){swap(nums,i,r--);}if(nums[i] == 0){swap(nums,i,l++);}}}public void swap(int[] nums,int l,int r){int t = nums[l];nums[l] = nums[r];nums[r] = t;}
}

31.下一个排列

java版本

class Solution {public void nextPermutation(int[] nums) {int n = nums.length , i = n-2;while(i >= 0 && nums[i] >= nums[i+1])--i;if(i >= 0){int j = n-1;while(j >= 0 && nums[j] <= nums[i]){--j;}swap(nums,i,j);}reverse(nums,i+1,n-1);}public void swap(int[] nums,int l,int r){int t = nums[l];nums[l] = nums[r];nums[r] = t;}public void reverse(int[] nums,int l,int r){while(l <= r){swap(nums,l++,r--);}}
}

287.寻找重复数

java版本

class Solution {public int findDuplicate(int[] nums) {int fast = 0, slow = 0;do{fast = nums[nums[fast]];slow = nums[slow];}while(fast != slow);fast = 0;while(fast != slow){fast = nums[fast];slow = nums[slow];}return fast;}
}