Leetcode

5. Longest Substring Without Repeating Characters Hardness: \(\color{orange}\textsf{Medium}\) Ralated Topics: String、Dynamic Programming 一、題目 Given a string s, return the longest palindromic substring in s. A string is called a palindrome string if the reverse of that string is the same of the original string. Example 1: Input: s = “babad” Output: “bab” Explanation: “aba” is also a valid answer. Example 2: Input: s = “cbbd” Output: “bb” Constraints: 1 <= s.length <= 1000 s consists of only digits and English letters. 二、分析 注意 palindrome string 的特性： 當長度為 1 時，必為 palindrome string 當長度為 2 時，兩個字元必須相同才為 palindrome string 當長度 >2 時，palindrome string 必須滿足 最左邊的字元等於最右邊的字元，即 s[left] == s[right] 除去最左邊的字元跟最右邊的字元，必須為 palindrome string， 即 s.substr(left+1, len-2) 為 palindromic。 三、解題 1. Dynamic Prograimming Time complexity: \(O(n^2)\) Space complexity: \(O(n^2)\) string longestPalindrome(string s) { int n = s.length(); string res; bool dp[n][n]; memset(dp, false, sizeof(dp)); int len = 0; for (int j = 0; j < n; j++) { for (int i = 0; i <= j; i++) { if (i == j) { // 長度為 1 dp[i][j] = true; } else if (j - i == 1) { // 長度為 2 dp[i][j] = s[i] == s[j]; } else { // 長度 > 2 dp[i][j] = s[i] == s[j] && dp[i+1][j-1]; } if (dp[i][j] && j - i + 1 > len) { // 比較長度 len = j - i + 1; res = s.substr(i, len); } } } return res; } 回目錄 Catalog ...

4. Median of Two Sorted Arrays Hardness: \(\color{red}\textsf{Hard}\) Ralated Topics: Array、Binary Search、Divide and Conquer 一、題目 Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the sorted arrays. The overall run time complexity should be O(log (m+n)). Example 1: Input: nums1 = [1,3], nums2 = [2] Output: 2.00000 Explanation: merged array = [1,2,3] and median is 2. Example 2: Input: nums1 = [1,2], nums2 = [3,4] Output: 2.50000 Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5. Constraints: ...

3. Longest Substring Without Repeating Characters Hardness: \(\color{orange}\textsf{Medium}\) Ralated Topics: Hash Table、String、Sliding Window 一、題目 Given a string s, find the length of the longest substring without repeating characters. Example 1: Input: s = “abcabcbb” Output: 3 Explanation: The answer is “abc”, with the length of 3. Example 2: Input: s = “bbbbb” Output: 1 Explanation: The answer is “b”, with the length of 1. Example 3: Input: s = “pwwkew” Output: 3 Explanation: The answer is “wke”, with the length of 3. Notice that the answer must be a substring, “pwke” is a subsequence and not a substring. Constraints: ...

2. Add Two Numbers Hardness: \(\color{orange}\textsf{Medium}\) Ralated Topics: Linked List、Math、Recursion 一、題目 You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself. Example 1: ...

1. Two Sum Hardness: \(\color{green}\textsf{Easy}\) Ralated Topics: Array、Hash Table 一、題目 Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order. Example 1: Input: nums = [2,7,11,15], taget = 9 Output: [0,1] Explanation: Because nums[0] + nums[1] == 9, we return [0,1]. Example 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 ...

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] ...