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

cilless said:
luyện leetcode nhiều mai đi làm có dùng nhiều ko các fen
Click to expand...
Thật ra là không, hoặc rất ít... trừ khi bạn làm R&D, phát triển Open Source, làm nghiên cứu chuyên sâu.
Đa số các developer luyện thuật toán ở đây là muốn luyện để tăng khả năng xử lý vấn đề và chủ yếu là để có lợi thế hơn khi đi interview, vì các nhà tuyển dụng ngoài phỏng vấn công nghệ thì sẽ thêm vài câu thuật toán vào để đánh giá trình độ của ứng viên.
 
Hôm nay lại esay à
hkNtitg.png


Code: 
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ì?

Code: 
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ổ said:
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
Click to expand...
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ổ said:
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
Click to expand...

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 said:
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))
Click to expand...
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ổ said:
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
Click to expand...
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ổ said:
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
Click to expand...
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 said:
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
Click to expand...
À 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


Code: 
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ổ said:
À 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
Click to expand...

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.
 

Similar threads

Masterchiefs
8 tờ báo Mỹ kiện OpenAI và Microsoft
Replies
9
Views
616
porpro84
porpro84
T
kiến thức Kèo play to earn miễn phí - Delabs Game
Replies
4
Views
77
Tranviethai98
T
T
kiến thức Kèo play to earn miễn phí - Delabs Games
Replies
4
Views
148
Tranviethai98
T
elementary
Ta thay đổi trước khi Google thay đổi
2 3
Replies
59
Views
4K
ProfessorX
ProfessorX
Masterchiefs
Núi lửa ở Nam Cực phun vàng thật mỗi ngày
2
Replies
24
Views
3K
xuccam2
xuccam2

Share this page

Back
Top