難度分: 1263 定長度的 sliding window，秒殺 class Solution { public: int maxVowels(string s, int k) { int cnt = 0; unordered_set<char> set = {'a','e','i','o','u'}; for (int i = 0; i < k; i++) { if (set.count(s[i])) cnt++; } int res = cnt; for (int i = k; i < s.size(); i++) { if (set.count(s[i])) cnt++; if (set.count(s[i-k])) cnt--; res = max(res, cnt); } return res; } };
定長度的 sliding window pattern 步驟 construct sliding window + check condition move sliding window (1) remove item (2) check condition (3) add item class Window { public: virtual void add(int num) = 0; virtual void erase(int num) = 0; virtual bool check(int num) = 0; virtual ~Window() {} }; class Solution { private: unique_ptr<Window> _w; public: bool solve(vector<int>& nums, int k) { _w = make_unique<WindowImpl>(k); int n = nums.size(); for (int i = 0; i < n; i++) { if (i >= k) _w->erase(nums[i-k]); if (_w->check(nums[i])) return true; _w->add(nums[i]); } return false; } };
1. 定長滑動窗口 定長滑動窗口 pattern 1.1 基礎 1456. Maximum Number of Vowels in a Substring of Given Length(1263) 643. Maximum Average Subarray I 1343. Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold(1317) 2090. K Radius Subarray Averages(1358) 2379. Minimum Recolors to Get K Consecutive Black Blocks(1360) 1052. Grumpy Bookstore Owner(1418) 1461. Check If a String Contains All Binary Codes of Size K(1504) 2841. Maximum Sum of Almost Unique Subarray(1546) 2461. Maximum Sum of Distinct Subarrays With Length K(1553) 1423. Maximum Points You Can Obtain from Cards(1574) 1652. Defuse the Bomb 1297. Maximum Number of Occurrences of a Substring(1748) 1176. Diet Plan Performance(會員題) 1100. Find K-Length Substrings With No Repeated Characters(會員題) 1852. Distinct Numbers in Each Subarray(會員題) 1151. Minimum Swaps to Group All 1’s Together(會員題) 2107. Number of Unique Flavors After sharing K Candies(會員題) 1.2 進階 2134. Minimum Swaps to Group All 1’s Together II(1748) 2653. Sliding Subarray Beauty(1786) 1888. Minimum Number of Flips to Make the Binary String Alternating(2006) 567. Permutation in String 438. Find All Anagrams in a String 30. Substring with Concatenation of All Words 2156. Find Substring With Given Hash Value(2063) 2953. Count Complete Substrings(2449) 1016. Binary String With Substrings Representing 1 To N 683. K Empty Slots(會員題) 2067. Number of Equal Count Substrings(會員題) 2524. Maximum Frequency Score of a substring(會員題) 1.3 其它 2269. Find the K-Beauty of a Number(1280) 1984. Minimum Difference Between Highest and Lowest of K Scores(1306) 220. Contains Duplicate III 2. 不定長滑動窗口 不定長滑動窗口主要分為三類：求最長子數組、求最短子數組，以及求子數組個數。 ...
科學刷題 Catalog 一、依題號 1-500(45) 1. Two Sum 2. Add Two Numbers 3. Longest Substring Without Repeating Characters 4. Median of Two Sorted Array 5. Longest Palindromic Substring 6. Zigzag Conversion 7. Reverse Integer 8. String to Integer (atoi) 9. Palindrome Number 10. Regular Expression Matching 11. Container With Most Water 12. Integer to Roman 13. Roman to Integer 14. Longest Common Prefix 15. 3Sum 16. 3Sum Closet 17. Letter Combinations of a Phone Number 18. 4Sum 19. Remove Nth Node From End of List 20. Valid Parentheses 21. Merge Two Sorted Lists 22. Generate Parentheses 23. Merge k Sorted Lists 24. Swap Nodes in Pairs 25. Reverse Nodes in k-Group 53. Maximum Subarray 70. Climbing Stairs 79. Word Search 100. Same Tree 124. Binary Tree Maximum Path Sum 132. Palindrome Partitioning II 149. Max Points on a Line 151. Reverse Words in a String 198. House Robber 212. Word Search II 213. House Robber II 223. Rectangle Area 279. Perfect Squares 290. Word Pattern 300. Longest Increasing Subsequence 322. Coin Change 328. Odd Even Linked List 337. House Robber III 347. Top K Frequent Elements 374. Guess Number Higher or Lower II 433. Minimum Genetic Mutation 446. Arithmetic Slices II - Subsequence 452. Minimum Number of Arrows to Burst Balloons ...
分類清單 1. 滑動窗口與雙指針（定長／不定長／單序列／雙序列／三指針／分組循環） 2. 二分演算法（二分答案／最小化最大值／最大化最小值／Kth） 3. 單調棧（基礎／矩形面積／貢獻法／最小字典序） 4. 網格圖（DFS／BFS／綜合應用） 5. 位運算（基礎／性質／拆位／試填／恆等式／思維） 6. 圖論演算法（DFS／BFS／拓撲排序／最短路／最小生成樹／二分圖／基環樹／歐拉路徑） 7. 動態規劃（入門／背包／狀態機／劃分／區間／狀壓／數位／數據結構優化／樹形／博弈／概率期望） 8. 常用數據結構（前綴和／差分／棧／佇列／堆／字典樹／並查集／樹狀樹組／線段樹） 9. 數學演算法（數論／組合／概率期望／博弈／計算幾何／隨機算法） 10. 貪心與思維（基本貪心策略／反悔／區間／字典序／數學／思維／腦筋急轉彎／構造） 11. 鏈表、二叉樹與回溯（前後指針／快慢指針／DFS／BFS／直徑／LCA／一般樹） 12. 字串（KMP／Z函數／Manacher／字串Hash／AC自動機／後綴數組／子序列自動機）
347. Top K Frequent Elements Hardness: \(\color{orange}\textsf{Medium}\) Ralated Topics: Array、Hash Table、Divide and Conquer、Sorting、Heap (Priority Queue)、Bucket Sort、Counting、Quickselect 一、題目 Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order. Example 1: Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2] Example 2: Input: nums = [1], k = 1 Output: [1] Constraints: 1 <= nums.length <= 10^5 -10^4 <= nums[i] <= 10^4 k is in the range [1, the number of unique elements in the array]. It is guaranteed that the answer is unique. Follow up: Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size. ...
題目 題目描述 設計一個類似 stack 的資料結構，實行 push() 跟 pop() 的功能，其中 pop() 會丟出 stack 中出現最多次的元素。 FreqStack class 必須實現： FreqStack() 建構子必須初始化一個空的 FreqStack。 void push(int val) 將 val 推至 stack 的頂端。 int pop() 將 stack 中最頻繁出現的元素移除，並返回。 如果 stack 中最頻繁出現的元素出現平手的狀況，則返回平手的元素中最接近 stack 頂端的元素。 題目範例 輸入 [“FreqStack”, “push”, “push”, “push”, “push”, “push”, “push”, “pop”, “pop”, “pop”, “pop”] [[], [5], [7], [5], [7], [4], [5], [], [], [], []] 輸出 [null, null, null, null, null, null, null, 5, 7, 5, 4] ...