Leetcode

2463. Minimum Total Distance Traveled Hardness: \(\color{red}\textsf{Hard}\) Ralated Topics: Array、Dynamic Programming、Sorting \(\color{blue}\textsf{Weekly Contest 318}\) 一、題目 There are some robots and factories on the X-axis. You are given an integer array robot where robot[i] is the position of the ith robot. You are also given a 2D integer array factory where factory[j] = [positionj, limitj] indicates that positionj is the position of the jth factory and that the jth factory can repair at most limitj robots. ...

2462. Total Cost to Hire K Hardness: \(\color{orange}\textsf{Medium}\) Ralated Topics: Array、Two Pointer、Heap (Priority Queue)、Simulation \(\color{blue}\textsf{Weekly Contest 318}\) 一、題目 You are given a 0-indexed integer array costs where costs[i] is the cost of hiring the ith worker. You are also given two integers k and candidates. We want to hire exactly k workers according to the following rules: You will run k sessions and hire exactly one worker in each session. In each hiring session, choose the worker with the lowest cost from either the first candidates workers or the last candidates workers. Break the tie by the smallest index. For example, if costs = [3,2,7,7,1,2] and candidates = 2, then in the first hiring session, we will choose the 4th worker because they have the lowest cost [3,2,7,7,1,2]. In the second hiring session, we will choose 1st worker because they have the same lowest cost as 4th worker but they have the smallest index [3,2,7,7,2]. Please note that the indexing may be changed in the process. If there are fewer than candidates workers remaining, choose the worker with the lowest cost among them. Break the tie by the smallest index. A worker can only be chosen once. Return the total cost to hire exactly k workers. Example 1: ...

2461. Maximum Sum of Distinct Subarrays With Length K Hardness: \(\color{orange}\textsf{Medium}\) Ralated Topics: Array、Hash Table、Sliding Window \(\color{blue}\textsf{Weekly Contest 318}\) 一、題目 You are given an integer array nums and an integer k. Find the maximum subarray sum of all the subarrays of nums that meet the following conditions: The length of the subarray is k, and All the elements of the subarray are distinct. Return the maximum subarray sum of all the subarrays that meet the conditions. If no subarray meets the conditions, return 0. A subarray is a contiguous non-empty sequence of elements within an array. Example 1: ...

2460. Apply Operations to an Array Hardness: \(\color{green}\textsf{Easy}\) Ralated Topics: Array、Simulation \(\color{blue}\textsf{Weekly Contest 318}\) 一、題目 You are given a 0-indexed array nums of size n consisting of non-negative integers. You need to apply n - 1 operations to this array where, in the ith operation (0-indexed), you will apply the following on the ith element of nums: If nums[i] == nums[i + 1], then multiply nums[i] by 2 and set nums[i + 1] to 0. Otherwise, you skip this operation. After performing all the operations, shift all the 0’s to the end of the array. For example, the array [1,0,2,0,0,1] after shifting all its 0’s to the end, is [1,2,1,0,0,0]. Return the resulting array. Note that the operations are applied sequentially, not all at once. Example 1: ...

1323. Maximum 69 Number Hardness: \(\color{green}\textsf{Easy}\) Ralated Topics: Math、Greedy 一、題目 You are given a positive integer num consisting only of digits 6 and 9. Return the maximum number you can get by changing at most one digit (6 becomes 9, and 9 becomes 6). Example 1: Input: num = 9669 Output: 9969 Explanation: Changing the first digit results in 6669. Changing the second digit results in 9969. Changing the third digit results in 9699. Changing the fourth digit results in 9666. The maximum number is 9969. Example 2: ...

79. Word Search Hardness: \(\color{orange}\textsf{Medium}\) Ralated Topics: Array、Backtracking、Matrix 一、題目 Given an m x n grid of characters board and a string word, return true if word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once. Example 1: Input: board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED” Output: true Example 2: ...

212. Word Search II Hardness: \(\color{red}\textsf{Hard}\) Ralated Topics: Array、String、Backtracking、Trie、Matrix 一、題目 Given an m x n board of characters and a list of strings words, return all words on the board. Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word. Example 1: Input: board = [[“o”,“a”,“a”,“n”],[“e”,“t”,“a”,“e”],[“i”,“h”,“k”,“r”],[“i”,“f”,“l”,“v”]], words = [“oath”,“pea”,“eat”,“rain”] Output: [“eat”,“oath”] Example 2: ...

2131. Longest Palindrome by Concatenating Two Letter Words Hardness: \(\color{orange}\textsf{Medium}\) Ralated Topics: Array、Hash Table、String、Greedy、Counting 一、題目 You are given an array of strings words. Each element of words consists of two lowercase English letters. Create the longest possible palindrome by selecting some elements from words and concatenating them in any order. Each element can be selected at most once. Return the length of the longest palindrome that you can create. If it is impossible to create any palindrome, return 0. ...

433. Minimum Genetic Mutation Hardness: \(\color{orange}\textsf{Medium}\) Ralated Topics: Hash Table、String、Breadth-First Search 一、題目 A gene string can be represented by an 8-character long string, with choices from A, C, G, and T. Suppose we need to investigate a mutation from a gene string start to a gene string end where one mutation is defined as one single character changed in the gene string. For example, "AACCGGTT" --> "AACCGGTA" is one mutation. There is also a gene bank bank that records all the valid gene mutations. A gene must be in bank to make it a valid gene string. Given the two gene strings start and end and the gene bank bank, return the minimum number of mutations needed to mutate from start to end. If there is no such a mutation, return -1. Note that the starting point is assumed to be valid, so it might not be included in the bank. Example 1: ...

這一題的兩個關鍵點是 轉成角度，使用 atan2(dy, dx) 這個函式，並將 rad 轉成 degree。 要考慮座標 0 == 360，頭尾要相接。我的做法是將負數 +360 重覆放一遍。(或是只需要放小於 -180 + angle) 剩下的就是 sliding window 了。 class Solution { public: int visiblePoints(vector<vector<int>>& points, int angle, vector<int>& location) { vector<double> angles; int on = 0; for (const auto& p : points) { int dy = p[1] - location[1]; int dx = p[0] - location[0]; if (dx == 0 && dy == 0) { on++; continue; } double ang = atan2(dy, dx) * 180 / std::numbers::pi; if (ang < 180 + angle) angles.push_back(ang + 360); angles.push_back(ang); } sort(angles.begin(), angles.end()); int left = 0, right = 0, res = 0, n = angles.size(); while (right < n) { double curr = angles[right++]; while (curr - angles[left] > angle) left++; res = max(res, right - left); } return res + on; } };