Leetcode 算法面试冲刺 热题 HOT 100 刷题（253 279 283 287 297）（六十六）

• 253. 会议室 II
• 279. 完全平方数
• 283. 移动零
• 287. 寻找重复数
• 297. 二叉树的序列化与反序列化

没写出来：

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        if not intervals or len(intervals) == 0:
            return 0
        cnt = 1
        new_intervals = sorted(intervals)
        n = len(new_intervals)
        for i in range(1, n):
            for j in range(i):
                if new_intervals[i][0] < new_intervals[j][1]:
                    cnt += 1
        return cnt
            

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:

        # If there is no meeting to schedule then no room needs to be allocated.
        if not intervals:
            return 0

        # The heap initialization
        free_rooms = []

        # Sort the meetings in increasing order of their start time.
        intervals.sort(key= lambda x: x[0])

        # Add the first meeting. We have to give a new room to the first meeting.
        heapq.heappush(free_rooms, intervals[0][1])

        # For all the remaining meeting rooms
        for i in intervals[1:]:

            # If the room due to free up the earliest is free, assign that room to this meeting.
            if free_rooms[0] <= i[0]:
                heapq.heappop(free_rooms)

            # If a new room is to be assigned, then also we add to the heap,
            # If an old room is allocated, then also we have to add to the heap with updated end time.
            heapq.heappush(free_rooms, i[1])

        # The size of the heap tells us the minimum rooms required for all the meetings.
        return len(free_rooms)

二刷回来。

不会

class Solution {
public:
    int numSquares(int n) {
        vector f(n + 1);
        for (int i = 1; i <= n; i++) {
            int minn = INT_MAX;
            for (int j = 1; j * j <= i; j++) {
                minn = min(minn, f[i - j * j]);
            }
            f[i] = minn + 1;
        }
        return f[n];
    }
};

import math
class Solution:
    def numSquares(self, n: int) -> int:
        dp = [0] * (n + 1)
        for i in range(1, n + 1):
            dp[i] = i
            tmp = i
            for j in range(1, int(math.sqrt(tmp)) + 1):
                dp[i] = min(dp[i], dp[i - j ** 2] + 1)
        return dp[n]

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        z, nz = 0, 0
        n = len(nums)
        while z < n and nz < n:
            while z < n and nums[z] != 0:
                z += 1
            if nz < z:
                nz = z + 1
            while nz < n and nums[nz] == 0:
                nz += 1
            if z < n and nz < n:
                nums[z], nums[nz] = nums[nz], nums[z]
            z += 1
            nz += 1
       

和我想的一样

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        n = len(nums)
        left = right = 0
        while right < n:
            if nums[right] != 0:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
            right += 1

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            for j in range(i+ 1, n):
                if nums[i] == nums[j]:
                    return nums[i]

超时了

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        nums.sort()
        for i in range(len(nums) - 1):
            if nums[i] == nums[i + 1]:
                return nums[i]

不会