Leetcode

766. Toeplitz Matrix Hardness: \(\color{green}\textsf{Easy}\) Ralated Topics: Array、Matrix 一、題目 Given an m x n matrix, return true if the matrix is Toeplitz. Otherwise, return false. A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same elements. Example 1: Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]] Output: true Explanation: In the above grid, the diagonals are: “[9]”, “[5, 5]”, “[1, 1, 1]”, “[2, 2, 2]”, “[3, 3]”, “[4]”. In each diagonal all elements are the same, so the answer is True. Example 2: ...

19. Remove Nth Node From End of List Hardness: \(\color{orange}\textsf{Medium}\) Ralated Topics: Linked List、Two Pointers 一、題目 Given the head of a linked list, remove the nth node from the end of the list and return its head. Example 1: Input: head = [1,2,3,4,5], n = 2 Output: [1,2,3,5] Example 2: Input: head = [1], n = 1 Output: [] Example 3: Input: head = [1,2], n = 1 Output: [1] Constraints: ...

1293. Shortest Path in a Grid with Obstacles Elimination Hardness: \(\color{red}\textsf{Hard}\) Ralated Topics: Array、Breadth-First Search、Matrix 一、題目 You are given an m x n integer matrix grid where each cell is either 0 (empty) or 1 (obstacles). You can move up, down, left, or right from and to an empty cell in one step. Return the minimum number of steps to walk from the upper left corner (0, 0) to the lower right conrer m-1, n-1 given that you can eliminate at most k obstacles. If it is not possible to find such walk return -1. ...

2136. Earliest Possible Day of Full Bloom Hardness: \(\color{red}\textsf{Hard}\) Ralated Topics: Array、Greedy、Sorting 一、題目 You have n flower seeds. Every seed must be planted first before it can begin to grow, then bloom. Planting a seed take time and so does the growth of a seed. You are given two 0-indexed integer arrays plantTime and growTime, of length n each: plantTime[i] is the number of full days it takes you to plant the ith seed. Every day, you can work on planting exactly one seed. You do not have to work on planting the same seed on consecutive days, but the planting of a seed is not complete until you have worked plantTime[i] days on planting it in total. growTime[i] is the number of full days it takes the ith seed to grow after being completely planted. After the last day of its growth, the flower blooms and stays bloomed forever. From the beginning of day 0, you can plant the seeds in any order. Return the earliest possible day where all seeds are blooming. Example 1: ...

18. 4Sum Hardness: \(\color{orange}\textsf{Medium}\) Ralated Topics: Array、Two Pointer、Sorting 一、題目 Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that: 0 <= a, b, c, d < n a, b, c and d are distinct. nums[a] + nums[b] + nums[c] + nums[d] == target You may return the answer in any order. Example 1: Input: nums = [1,0,-1,0,-2,2], target = 0 Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]] Example 2: ...

17. Letter Combinations of a Phone Number Hardness: \(\color{orange}\textsf{Medium}\) Ralated Topics: Hash Table,String,Backtracking 一、題目 Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters. Example 1: Input: digits = “23” Output: [“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”] Example 2: ...

no. </strong> <ul> <li>Hardness: \(\color{orange}\textsf{Medium}\)</li> <li>Ralated Topics: <code>Array</code>、<code>Two Pointers</code>、<code>Sorting</code></li> </ul> <hr> <h3 id="一題目">一、題目</h3> <p>Given an integer array <code>nums</code> of length <code>n</code> and an integer <code>target</code>, find three integers in <code>nums</code> such that the sum is closet to <code>target</code>. Return *the sum of the three integers`. You may assume that each input would have exactly one solution. <p><strong>Example 1:</strong> <ul> <li><strong>Input:</strong> nums = [-1,2,1,-4], target = 1</li> <li><strong>Output:</strong> 2</li> <li><strong>Explanation:</strong> The sum that is closet to the target is 2. (-1 + 2 + 1 = 2).</li> </ul> <p><strong>Example 2:</strong> ...

15. 3Sum Hardness: \(\color{orange}\textsf{Medium}\) Ralated Topics: Array、Two Pointer、Sorting 一、題目 Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets. Example 1: Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]] Explanation: nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0. nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0. nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0. The distinct triplets are [-1,0,1] and [-1,-1,2]. Notice that the order of the output and the order of the triplets does not matter. Example 2: ...

14. Longest Common Prefix Hardness: \(\color{green}\textsf{Easy}\) Ralated Topics: String 一、題目 Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string "". Example 1: Input: strs = [“flower”, “flow”, “flight”] Output: “fl” Example 2: Input: strs = [“dog”, “racecar”, “car”] Output: "" Explanation: There is no common prefix among the input strings. Constraints: 1 <= strs.length <= 200 0 <= strs[i].length <= 200 strs[i] consists of only lowercase English letters. 二、分析 簡單的字串比對問題。 需熟悉 string 的函數 substr() 的使用方式，常用以下兩種 s.substr(int start, int len)，從 start 起取長度為 len 的子字串。 s.substr(int start) 從 start 起取到字串的結尾。 三、解題 1. String Time complexity: \(O(m\times n)，\text{m }為\text{ strs }的長度，\text{n }為\text{ strs[i] }的長度\)， Space complexity: \(O(1)\) string longestCommonPrefix(vector<string>& strs) { string res = strs[0]; for (int i = 1; i < strs.size(); i++) { int j = 0; for (; j < min(strs[i].length(), res.length()); j++) { if (strs[i][j] != res[j]) break; } res = res.substr(0, j); } return res; } 回目錄 Catalog ...

13. Roman to Integer Hardness: \(\color{green}\textsf{Easy}\) Ralated Topics: Hash Table、Math、String 一、題目 Roman numerals are represented by seven different symbols: I, V, X, L, C, D, and M. \(\boxed{\begin{array}{ll} \textbf{Symbol}&\textbf{Value}\\ \texttt{I}&1\\ \texttt{V}&5\\ \texttt{X}&10\\ \texttt{L}&50\\ \texttt{C}&100\\ \texttt{D}&500\\ \texttt{M}&1000\\ \end{array}}\) For example, 2 is written as II in Roman numeral, just two one’s added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II. Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used: ...