Leetcode

100. Same Tree Hardness: \(\color{green}\textsf{Easy}\) Ralated Topics: Tree、Depth-First Search、Breadth-First Search、Binary Tree 一、題目 Given the roots of two binary tree p and q, write a function to check if they are the same or not. Two binary tree are considered the same if they are structurally iedntical, and the nodes have the same value. Example 1: Input: p = [1,2,3], q = [1,2,3] Output: true Example 2: Input: p = [1,2], q = [1,null,2] Output: false Example 3: ...

149. Max Points on a Line Hardness: \(\color{red}\textsf{Hard}\) Ralated Topics: Array、Hash Table、Math、Geometry 一、題目 Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line. Example 1: Input: points = [[1,1],[2,2],[3,3]] Output: 3 Example 2: Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]] Output: 4 Constraints: 1 <= points.length <= 300 points[i].length == 2 -10^4 <= xi, yi <= 10^4 All the points are unique. 二、分析 若干點在同一條線上，表示這些點的斜率都相同，注意題目有提示不會有相同的點，故兩點間必定有斜率。 特別注意當分母為 0 時要特別處理。 題目有限制 -10^4 <= xi, yi <= 10^4，故斜率最大 10^8，所以我們可以將分母為零的斜率暫定為 INT_MAX(2147483647)。 遍歷每個點，並統計該點與其它點之間的斜率，將斜率用 unordered_map 記錄下來，其每個斜率的直線上總共會有 m+1 (加上自己)。 三、解題 1. Time complexity: \(O(n^2)\) Space complexity: \(O(n)\) int maxPoints(vector<vector<int>>& points) { int n = points.size(); int res = 0; for (int i = 0; i < n; i++) { int& x0 = points[i][0]; int& y0 = points[i][1]; unordered_map<double,int> map; for (int j = 0; j < n; j++) { if (i == j) continue; // 若等於自己則跳過 int& x1 = points[j][0]; int& y1 = points[j][1]; if (x0 == x1) { // 當分母為 0 時特別處理 int& cnt = ++map[INT_MAX]; res = max(res, cnt); } else { double m = (y1-y0)/(1.0*(x1-x0)); // 注意將斜率轉成 double int& cnt = ++map[m]; res = max(res, cnt); } } } return res + 1; // 答案記得加 1，加上自己 } 回目錄 Catalog ...

452. Minimum Number of Arrows to Burst Balloons Hardness: \(\color{orange}\textsf{Medium}\) Ralated Topics: Array,Greedy,Sorting 一、題目 There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [x_start, x_end] denotes a balloon whose horizontal diameter stretches between x_start and x_end. You do not know the exact y-coordinates of the balloons. Arrows can be shot up directly vertically (in the positive y-direction) from different points along the x-axis. A balloon with x_start and x_end is burst by an arrow shot at x if x_start <= x <= x_end. There is no limit to the number of arrows that can be shot. A shot arrow keeps traveling up infinitely, bursting any balloons in its path. Given the array points, return the minimum number of arrows that must be shot to burst all balloons. ...

944. Delete Columns to Make Sorted Hardness: \(\color{green}\textsf{Easy}\) Ralated Topics: Array、String 一、題目 You are given an array of n string strs, all of the same length. The string s can be arranged such that there is one on each line, making a grid. For example, strs = ["abc", "bce", "cae" can be arranged as : abc bce cae You want to delete the columns that are not sorted lexicographically. In the aove example (0-indexed), columns 0('a','b','c') and 2('c','e','e') are sorted while column 1('b','c','a') is not, so you would delete column 1. Return the number of columns that you will delete. ...

2522. Partition String Into Substrings With Values at Most K Hardness: \(\color{orange}\textsf{Medium}\) Ralated Topics: \(\color{blue}\textsf{Weekly Contest 323}\) 一、題目 You are given a string s consisting of digits from 1 to 9 and an integer k. A partition of a string s is called good if: Each digit of s is part of exactly one substring. The value of each substring is less than or equal to k. Return the minimum number of substrings in a good partition of s. If no good partition of s exists, return -1. Note that: The value of a string is its result when interpreted as an integer. For example, the value of "123" is 123 and the value of "1" is 1. A substring is a contiguous sequence of characters within a string. Example 1: ...

2523. Closest Prime Numbers in Range Hardness: \(\color{orange}\textsf{Medium}\) Ralated Topics: \(\color{blue}\textsf{Weekly Contest 323}\) 一、題目 Given two positive integers left and right, find the two integers num1 and num2 such that: left <= nums1 < nums2 <= right. nums1 and nums2 are both prime numbers. nums2 - nums1 is the minimum amongst all other pairs satisfying the above conditions. Return the positive integer array ans = [nums1, nums2]. If there are multiple pairs satisfying these conditions, return the one with the minimum nums1 value or [-1, -1] if such numbers do not exist. A number greater than 1 is called prime if it is only divisible by 1 and itself. Example 1: ...

520. Detect Capital Hardness: \(\color{green}\textsf{Easy}\) Ralated Topics: String 一、題目 We define the usage of capitals in a word to be right when one of the following cases holds: All letters in this word are capitals, like "USA". All letters in this word are not capitals, like "leetcode". Only the first letter in this word is capital, like "Google". Given a string word, return true if the usage of capitals in it is right. Example 1: ...

2521. Distinct Prime Factors of Product of Array Hardness: \(\color{orange}\textsf{Medium}\) Ralated Topics: \(\color{blue}\textsf{Weekly Contest 323}\) 一、題目 Given an array of positive integers nums, return the number of distinct prime factors in the product of the elements of nums. Note that: A number greater than 1 is called prime if it is divisible by only 1 and itself. An integer val1 is a factor of another integer val2 if val2 / val1 is an integer. Example 1: ...

2520. Count the Digits That Divide a Number Hardness: \(\color{green}\textsf{Easy}\) Ralated Topics: \(\color{blue}\textsf{Weekly Contest 323}\) 一、題目 Given an integer num, return the number of digits in num that divide num. An integer val divides nums if nums % val == 0. Example 1: Input: num = 7 Output: 1 Explanation: 7 divides itself, hence the answer is 1. Example 2: Input: num = 121 Output: 2 Explanation: 121 is divisible by 1, but not 2. Since 1 occurs twice as a digit, we return 2. Example 3: ...

290. Word Pattern Hardness: \(\color{green}\textsf{Easy}\) Ralated Topics: Hash Table、String 一、題目 Given a pattern and a string s, find if s follows the same pattern. Here follow means a full match, such that there is a bijection between a letter in pattern and non-empty word in s. Example 1: Input: pattern = “abba”, s = “dog cat cat dog” Output: true Example 2: Input: pattern = “abba”, s = “dog cat cat fish” Output: false Example 3: ...