thảo luận Leetcode mỗi ngày

  • Người tạo chủ đề Người tạo chủ đề _Gia_Cat_Luong_
  • Ngày bắt đầu Ngày bắt đầu
Trạng thái
Không mở để trả lời thêm.
Hôm nay lại esay à
hkNtitg.png


Mã: 
defmodule Solution do
  @spec can_construct(ransom_note :: String.t(), magazine :: String.t()) :: boolean
  def can_construct(ransom_note, magazine) do
    ransom = ransom_note |> String.to_charlist() |> Enum.frequencies()
    mag = magazine |> String.to_charlist() |> Enum.frequencies()

    ransom
    |> Enum.all?(fn {ch, c} ->
      case Map.get(mag, ch) do
        nil -> false
        v -> v >= c
      end
    end)
  end
end
 
Bài hôm nay mức easy mà sao thấy 57% submit pass nhỉ? Thấy là lạ mà đọc đề không có yêu cầu về time hay space gì?

Mã: 
func canConstruct(ransomNote string, magazine string) bool {
    mapMagazine := make(map[rune]int)
    for _, value := range magazine {
        mapMagazine[value]++
    }
    for _, value := range ransomNote {
        mapMagazine[value]--
        if mapMagazine[value] < 0 {
            return false
        }
    }
    return true
}
 
Lập Trình Viên Số Khổ đã nói:
Python: 
class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
       
        ransomNote_count = defaultdict(int)
        for i in ransomNote:
            ransomNote_count[i] += 1
           
        magazine_count = defaultdict(int)
        for i in magazine:
            magazine_count[i] += 1

       
        for i in ransomNote:
            if magazine_count[i] < ransomNote_count[i]:
                return False
       
        return True
Nhấp để mở rộng...
Bài này tạo 1 mapMagazine thôi thím rồi for ransomNote. Nếu mapMagazine < 0 thì false
 
Sao dùng cái permutation tự viết nó bị TLE, còn dùng itertools.permutations thì lại pass nhỉ


Python: 
def permutation(lst):

    # If lst is empty then there are no permutations
    if len(lst) == 0:
        return []

    # If there is only one element in lst then, only
    # one permutation is possible
    if len(lst) == 1:
        return [lst]

    # Find the permutations for lst if there are
    # more than 1 characters

    l = []  # empty list that will store current permutation

    # Iterate the input(lst) and calculate the permutation
    for i in range(len(lst)):
        m = lst[i]

        # Extract lst[i] or m from the list.  remLst is
        # remaining list
        remLst = lst[:i] + lst[i+1:]

        # Generating all permutations where m is first
        # element
        for p in permutation(remLst):
            l.append([m] + p)
    return l


Python: 
class Solution:
    def reorderedPowerOf2(self, n: int) -> bool:
        l = permutations(list(str(n)))
        l = [int("".join(arr)) for arr in l if arr[0] != '0']
        for num in l:
                if not num & (num-1):
                    return True
        return False
 
Lập Trình Viên Số Khổ đã nói:
bác nào giải thích giúp mình tại sao mà

(n != 0 and n & (n-1)) == True => n is power of 2
Nhấp để mở rộng...

Giả sử n là số power of 2 thì biểu diễn binary sẽ có dạng 1000...0, cái này khỏi giải thích nhé.
n - 1 sẽ có dạng binary 111..1 => lúc đó n & (n-1) sẽ có dạng binary 0000...0 = 0

Tôi không biết ngôn ngữ nào mà 0 = True
 
thuyduong2007 đã nói:
Bài hôm nay cũng chỉ cần 1 dòng là đủ, :p
Python: 
return sorted(str(n)) in (sorted(str(pow(2,x))) for x in range(0,32))
Nhấp để mở rộng...
Mai dậy muộn tí nhé fen. Hôm nào cũng post trước t. T.T
Python: 
return next((True for i in range(30) if Counter(str(n)) == Counter(str(pow(2, i)))), False)
 
Lập Trình Viên Số Khổ đã nói:
Sao dùng cái permutation tự viết nó bị TLE, còn dùng itertools.permutations thì lại pass nhỉ


Python: 
def permutation(lst):

    # If lst is empty then there are no permutations
    if len(lst) == 0:
        return []

    # If there is only one element in lst then, only
    # one permutation is possible
    if len(lst) == 1:
        return [lst]

    # Find the permutations for lst if there are
    # more than 1 characters

    l = []  # empty list that will store current permutation

    # Iterate the input(lst) and calculate the permutation
    for i in range(len(lst)):
        m = lst[i]

        # Extract lst[i] or m from the list.  remLst is
        # remaining list
        remLst = lst[:i] + lst[i+1:]

        # Generating all permutations where m is first
        # element
        for p in permutation(remLst):
            l.append([m] + p)
    return l


Python: 
class Solution:
    def reorderedPowerOf2(self, n: int) -> bool:
        l = permutations(list(str(n)))
        l = [int("".join(arr)) for arr in l if arr[0] != '0']
        for num in l:
                if not num & (num-1):
                    return True
        return False
Nhấp để mở rộng...
Vì cái hàm built-in nó tối ưu hơn chứ sao. Cụ thể thì cái implementation của ông dùng nhiều phép nối mảng, việc này rất tốn chi phí trong việc cấp phát / giải phóng vùng nhớ. Nên dễ bị TLE.
 
Lập Trình Viên Số Khổ đã nói:
Sao dùng cái permutation tự viết nó bị TLE, còn dùng itertools.permutations thì lại pass nhỉ


Python: 
def permutation(lst):

    # If lst is empty then there are no permutations
    if len(lst) == 0:
        return []

    # If there is only one element in lst then, only
    # one permutation is possible
    if len(lst) == 1:
        return [lst]

    # Find the permutations for lst if there are
    # more than 1 characters

    l = []  # empty list that will store current permutation

    # Iterate the input(lst) and calculate the permutation
    for i in range(len(lst)):
        m = lst[i]

        # Extract lst[i] or m from the list.  remLst is
        # remaining list
        remLst = lst[:i] + lst[i+1:]

        # Generating all permutations where m is first
        # element
        for p in permutation(remLst):
            l.append([m] + p)
    return l


Python: 
class Solution:
    def reorderedPowerOf2(self, n: int) -> bool:
        l = permutations(list(str(n)))
        l = [int("".join(arr)) for arr in l if arr[0] != '0']
        for num in l:
                if not num & (num-1):
                    return True
        return False
Nhấp để mở rộng...
Chưa xem giải thuật, nhưng xem qua thì hàm permutation fen viết tạo cả 1 list, tính toán hết xong trả về, hàm của itertools nó yield giá trị về, dùng đến đâu tính đến đó.
Python: 
# https://docs.python.org/3/library/itertools.html#itertools.permutations
def permutations(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = list(range(n))
    cycles = list(range(n, n-r, -1))
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return
 
tdat00 đã nói:
Giả sử n là số power of 2 thì biểu diễn binary sẽ có dạng 1000...0, cái này khỏi giải thích nhé.
n - 1 sẽ có dạng binary 111..1 => lúc đó n & (n-1) sẽ có dạng binary 0000...0 = 0

Tôi không biết ngôn ngữ nào mà 0 = True
Nhấp để mở rộng...
À chỗ 0 == True viết thiếu, Nhưng đấy là chiều thuận, tui đang hỏi chiều ngược cơ, tại sao n & (n-1) == 0 suy ra là power of 2
 
Bài hôm nay lại dễ, chắc để bắt thóp những ai tự làm permutation
cgE9MkI.gif


Mã: 
defmodule Solution do
  @power_of_2 0..29
              |> Stream.map(fn x ->
                :math.pow(2, x)
                |> trunc()
                |> Integer.digits()
                |> Enum.frequencies()
              end)
              |> MapSet.new()

  @spec reordered_power_of2(n :: integer) :: boolean
  def reordered_power_of2(n) do
    n
    |> Integer.digits()
    |> Enum.frequencies()
    |> (fn f -> MapSet.member?(@power_of_2, f) end).()
  end
end
 
Lập Trình Viên Số Khổ đã nói:
À chỗ 0 == True viết thiếu, Nhưng đấy là chiều thuận, tui đang hỏi chiều ngược cơ, tại sao n & (n-1) == 0 suy ra là power of 2
Nhấp để mở rộng...

Phản chứng: giả sử n không phải là power of 2, suy ra trong biểu diễn nhị phân của n có ít nhất 2 bit 1.
Ta chỉ cần quan tâm số 1 đầu tiên từ phải sang, gọi là LSB:
n = 1xxx100
n -1 = 1xxx011

n & (n - 1) = 1xxx000 != 0, mâu thuẫn với điều kiện.
 
Lập Trình Viên Số Khổ đã nói:
Giờ thế này, fen chứng minh các số không phải power of 2, ví dụ số 37
tại sao 37 & 36 != 0
Nhấp để mở rộng...
Cái này cũng dễ, thiết nghĩ fen có thể tự suy nghĩ và chứng minh được. Mình có vài gợi ý:

1. Nghĩ thêm về bản chất của phép trừ một trên số nhị phân, bit nào sẽ bị đổi thành 0 và bit nào sẽ bị đổi thành 1
2. Nhận thấy nếu số n không phải là power of 2 thì phép trừ 1 chắc chắn sẽ để lại ít nhất 1 bit = 1 không đổi.
3. Chính vì cả n và n - 1 đều có bit 1 không đổi này nên n & (n - 1) chắc chắn sẽ lớn hơn 0
 
Trạng thái
Không mở để trả lời thêm.

Chủ đề tương tự

Thach Sanh Mat Riu
Điều gì xảy ra nếu bạn uống nước chè xanh mỗi ngày?
2
Trả lời
22
Lượt xem
1K
dattenmoi
D
megume
thảo luận Hôm nay, buổi bình minh của AI robot đã đến
Trả lời
4
Lượt xem
1K
Toc Hong
Toc Hong
Lộc Tục
(Dịch) Cuộc điều tra của CBC/Radio-Canada tiết lộ công ty Việt Nam nhắm vào người Canada bằng tin giả AI để kiếm lời
2
Trả lời
30
Lượt xem
5K
dukeng995
dukeng995
Ti Amo
[Dịch] Công ty Việt Nam dùng tin giả do AI tạo ra để kiếm tiền — nhắm vào độc giả Canada
Trả lời
0
Lượt xem
1K
Ti Amo
Ti Amo
Gấu Ted
Độc giả ngày càng tin nhà báo hơn thương hiệu báo chí
Trả lời
10
Lượt xem
838
giayasics
giayasics

Thống kê chủ đề

Ngày tạo
_Gia_Cat_Luong_,
Người trả lời cuối
Vipluckystar,
Trả lời
17.755
Lượt xem
1.212.745

Chia sẻ trang này

Quay lại
Lên đầu trang