Re: [閒聊] 每日leetcode

作者: JerryChungYC (JerryChung)   2024-07-22 13:37:10
https://leetcode.com/problems/minimum-number-of-moves-to-seat-everyone
6/13的 解完今天的按隨機剛好出這題easy就順便解了
※ 引述《sustainer123 (caster )》之銘言:
: ※ 引述《SecondRun (南爹摳打)》之銘言:
: : 2037. Minimum Number of Moves to Seat Everyone
: : 有 n 個座位和 n 個學生在一個房間裡。給你一個長度為 n 的 seats 陣列,其中 seats[i] 是第 i 個座位的位置。同樣地,給你一個長度為 n 的 students 陣列,其中 students[j] 是第 j 個學生的位置。
: : 你可以進行以下任意次數的移動:
: : 增加或減少第 i 個學生的位置 1 (即,將第 i 個學生從位置 x 移動到 x + 1 或 x - 1)
: : 返回將每個學生移動到一個座位的最小移動次數,使得沒有兩個學生在同一個座位上。
: : 請注意,一開始可能有多個座位或學生位於相同位置。
: : Example 1:
: : Input: seats = [3,1,5], students = [2,7,4]
: : Output: 4
: : Explanation: The students are moved as follows:
: : - The first student is moved from from position 2 to position 1 using 1 move.
: : - The second student is moved from from position 7 to position 5 using 2 moves.
: : - The third student is moved from from position 4 to position 3 using 1 move.
: : In total, 1 + 2 + 1 = 4 moves were used.
: : 思考: 貪婪
: : C# code:
: : public class Solution {
: : public int MinMovesToSeat(int[] seats, int[] students) {
: : Array.Sort(seats);
: : Array.Sort(students);
: : int result = 0;
: : int len = seats.Length;
: : for (int i=0; i<len; i++)
: : {
: : result += Math.Abs(seats[i] - students[i]);
: : }
: : return result;
: : }
: : }
: 思路:
: 差不多
: Python Code:
: class Solution:
: def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:
: seats.sort()
: students.sort()
: result = 0
: for i in range(len(seats)):
: result += abs(seats[i] - students[i])
: return result
思考:
發現總和的絕對值就是答案
Python Code:
class Solution:
def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:
return abs(sum(seats) - sum(students))
然後就錯了
看了一下 應該是排序後個別相減的絕對值相加後才是答案
順便用剛用過的zip
Python Code:
class Solution:
def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:
return sum(abs(_[0] - _[1]) for _ in zip(sorted(seats), sorted(students)))

Links booklink

Contact Us: admin [ a t ] ucptt.com