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

thằng này đòi ban thằng kia là xao, thoy ban hết 2 thằng đi mod
FY7e6U1.png
irGoYrZ.gif
 
4/8/2022:
  • 1 bài medium khá xàm
  • Vẽ hình ra là sẽ nhận ra tính chất cái gương đầu tiên thu dc sẽ là khi: (số lần bật) * q chia hết cho p
  • Tìm bội chung nhỏ nhất của q, và p, gọi là Lcm
  • số lần bật là Lcm / q, nếu Lcm / q chẵn thì vào gương số 2
  • nếu ko Lcm / p mà chẵn thì vào gương số 0
  • còn lại vào gương số 1
_ vẽ hình ra mất 3 phút để nghĩ
 
Vì tính chất phản xạ nên có thể làm như này: bỏ cạnh trên đi, coi như cái tia nó bật đi bật lại trên 2 cạnh bên (kéo dài vô hạn)
1659576605583.png

Thì mỗi lần chạm 2 cạnh bên, khoảng cách đến đáy là q->2q->3q->...
Giờ bài toán là tìm k đầu tiên sao cho (k*q%p) ==0, nghĩa là k=BCNN(p,q)/q.
Nếu k chẵn thì return 2 (Sẽ ko có trường hợp tia chạm St, vì nếu chạm St thì trc đấy nó chạm 1 rồi)
k lẻ thì là 0 hoặc 1 tùy theo BCNN/p là chẵn hay lẻ. Lẻ thì là 1, chẵn thì là 0

Python: 
class Solution:
    def mirrorReflection(self, p: int, q: int) -> int:
        x=lcm(p,q)
        k=x//q
        if k%2==0:      # left edge
            return 2
        else:           # right edge
            if (x//p)%2:
                return 1
            else:
                return 0
 
Arik97 said:
Vì tính chất phản xạ nên có thể làm như này: bỏ cạnh trên đi, coi như cái tia nó bật đi bật lại trên 2 cạnh bên (kéo dài vô hạn)
View attachment 1302089
Thì mỗi lần chạm 2 cạnh bên, khoảng cách đến đáy là q->2q->3q->...
Giờ bài toán là tìm k đầu tiên sao cho (k*q%p) ==0, nghĩa là k=BCNN(p,q)/q.
Nếu k chẵn thì return 2 (Sẽ ko có trường hợp tia chạm St, vì nếu chạm St thì trc đấy nó chạm 1 rồi)
k lẻ thì là 0 hoặc 1 tùy theo BCNN/p là chẵn hay lẻ. Lẻ thì là 1, chẵn thì là 0

Python: 
class Solution:
    def mirrorReflection(self, p: int, q: int) -> int:
        x=lcm(p,q)
        k=x//q
        if k%2==0:      # left edge
            return 2
        else:           # right edge
            if (x//p)%2:
                return 1
            else:
                return 0
Click to expand...
Hay phết em chưa nghĩ ra cách kéo dài 2 cạnh ra như bác :D
 
code điêu 1 dòng
return p / gcd(p, q) % 2 ? q / gcd(p, q) % 2 : 2;
RPOxGRd.gif


C++: 
int mirrorReflection(int p, int q) {
    for (int a = p, b = q;; a = std::exchange(b, a % b))
        if (a % b == 0) return p / b % 2 ? q / b % 2 : 2;
}
 
Bài hôm nay tôi nghĩ đến tam giác đồng dạng => tính được điểm tiếp xúc ở cạnh hình vuông kế tiếp => lặp đi lặp lại đến khi trùng với các điểm góc hình vuông.

Nhưng khi nhào vô code thì nó xảy ra trường hợp điểm tiếp xúc kế tiếp có thể nằm ở cạnh bên, cũng có thể nằm ở cạnh đối diện... => quá phức tạp để code được.

Vào xem discuss thì thấy phương pháp lặp các cạnh hình vuông đến vô tận => quá hay và sáng tạo :p

Sent from Samsung SM-A528B using vozFApp
 
tdat00 said:
Bài hôm nay tôi nghĩ đến tam giác đồng dạng => tính được điểm tiếp xúc ở cạnh hình vuông kế tiếp => lặp đi lặp lại đến khi trùng với các điểm góc hình vuông.

Nhưng khi nhào vô code thì nó xảy ra trường hợp điểm tiếp xúc kế tiếp có thể nằm ở cạnh bên, cũng có thể nằm ở cạnh đối diện... => quá phức tạp để code được.

Vào xem discuss thì thấy phương pháp lặp các cạnh hình vuông đến vô tận => quá hay và sáng tạo :p

Sent from Samsung SM-A528B using vozFApp
Click to expand...
lúc đầu cũng nghĩ tính lại q sau mỗi lần phản xạ ở corner ==> quá phức tạp
cũng vào discuss thấy hình mấy cái ô vuông lặp lại mới nhớ đến ảnh ảo của gương rồi mới làm ra :beat_brick: ngáo quá thế mà xưa được thi quốc gia lý :beat_brick:
 
Mình mới làm cái Assement của AMZ nó có bài thế này:
Cho 1 mảng gồm các string thế này: a=["abc","bcd","cgh","hdg","bkv"]. Đếm số chuỗi là family trong mảng.
Định nghĩa 2 chuỗi family với nhau là như sau: So sánh 2 chuỗi nếu từng ký tự của chuỗi 1 là ký tự nối tiếp của chuỗi 2 thì nó là family. Ví dụ: "abc" và "bcd" là family do b là nối tiếp của a, c là nối tiếp của b, và d là nối tiếp của c... "abc" và "abc" không phải family.
Bạn nào gặp dạng bài này rồi chỉ mình với
 
thieugiatri4492 said:
Mình mới làm cái Assement của AMZ nó có bài thế này:
Cho 1 mảng gồm các string thế này: a=["abc","bcd","cgh","hdg","bkv"]. Đếm số chuỗi là family trong mảng.
Định nghĩa 2 chuỗi family với nhau là như sau: So sánh 2 chuỗi nếu từng ký tự của chuỗi 1 là ký tự nối tiếp của chuỗi 2 thì nó là family. Ví dụ: "abc" và "bcd" là family do b là nối tiếp của a, c là nối tiếp của b, và d là nối tiếp của c... "abc" và "abc" không phải family.
Bạn nào gặp dạng bài này rồi chỉ mình với
Click to expand...
Chắc dịch sai rồi chứ đề bài sao thế này được.
Chắc đề bài là:
1. Đếm số cặp chuỗi (a,b) mà a là family của b
2. Đếm số lượng phần tử trong family có nhiều chuỗi nhất.
Nghe thấy kỳ kỳ
 
thieugiatri4492 said:
Mình mới làm cái Assement của AMZ nó có bài thế này:
Cho 1 mảng gồm các string thế này: a=["abc","bcd","cgh","hdg","bkv"]. Đếm số chuỗi là family trong mảng.
Định nghĩa 2 chuỗi family với nhau là như sau: So sánh 2 chuỗi nếu từng ký tự của chuỗi 1 là ký tự nối tiếp của chuỗi 2 thì nó là family. Ví dụ: "abc" và "bcd" là family do b là nối tiếp của a, c là nối tiếp của b, và d là nối tiếp của c... "abc" và "abc" không phải family.
Bạn nào gặp dạng bài này rồi chỉ mình với
Click to expand...
  • theo mình nghĩ, mỗi từ trong mảng chỉ thuộc trong 1 chuỗi family thôi, nên đầu tiên bác cho các từ vào trong 1 cái hash map.
  • Tạo 1 cái mảng visited nữa (mảng này đánh dấu 1 từ đã trong 1 chuỗi family nào chưa)
  • Sau đó duyệt lần lượt các từ:
  • nếu visited từ đó thì continue
  • nếu ko thì tìm từ bên trái và bên phải của từ đang xét trong chuỗi family
  • VD: xét từ "cgh" thì từ bên phải trong chuỗi family là "dei" và từ bên trái là "beg".
  • nếu 1 trong 2 từ thuộc cái hash map thì tiếp tục duyệt tiếp và đánh dấu visited .
Cơ bản là thế
 
randomA said:
Chắc dịch sai rồi chứ đề bài sao thế này được.
Chắc đề bài là:
1. Đếm số cặp chuỗi (a,b) mà a là family của b
2. Đếm số lượng phần tử trong family có nhiều chuỗi nhất.
Nghe thấy kỳ kỳ
Click to expand...
Nó không phải cặp chuỗi đâu, tại đề nó đưa cái mảng mà các chuỗi lúc nào cũng 3 ký tự hết, so lần lượt từng char của chuỗi này vs chuỗi kia, nếu tất cả char của chuỗi này lần lượt là nối tiếp với các char chuỗi kia theo thứ tự chữ cái alphabet thì nó là family
 
thieugiatri4492 said:
Mình mới làm cái Assement của AMZ nó có bài thế này:
Cho 1 mảng gồm các string thế này: a=["abc","bcd","cgh","hdg","bkv"]. Đếm số chuỗi là family trong mảng.
Định nghĩa 2 chuỗi family với nhau là như sau: So sánh 2 chuỗi nếu từng ký tự của chuỗi 1 là ký tự nối tiếp của chuỗi 2 thì nó là family. Ví dụ: "abc" và "bcd" là family do b là nối tiếp của a, c là nối tiếp của b, và d là nối tiếp của c... "abc" và "abc" không phải family.
Bạn nào gặp dạng bài này rồi chỉ mình với
Click to expand...
https://leetcode.com/discuss/interv...Screen-September-2021-or-SDE-(Reject)/1070371
tra google thì khá giống ông này, chắc là nâng cấp từ 1 chữ thành 1 từ :LOL::LOL:
 
Violet_7 said:
  • theo mình nghĩ, mỗi từ trong mảng chỉ thuộc trong 1 chuỗi family thôi, nên đầu tiên bác cho các từ vào trong 1 cái hash map.
  • Tạo 1 cái mảng visited nữa (mảng này đánh dấu 1 từ đã trong 1 chuỗi family nào chưa)
  • Sau đó duyệt lần lượt các từ:
  • nếu visited từ đó thì continue
  • nếu ko thì tìm từ bên trái và bên phải của từ đang xét trong chuỗi family
  • VD: xét từ "cgh" thì từ bên phải trong chuỗi family là "dei" và từ bên trái là "beg".
  • nếu 1 trong 2 từ thuộc cái hash map thì tiếp tục duyệt tiếp và đánh dấu visited .
Cơ bản là thế
Click to expand...
Cái family của chuỗi "cgh" là "dhi" mới đúng nhỉ? À mà trong cái input, chuỗi có khả năng lặp lại nhe, nên nó cũng có tính chuỗi lặp lại nếu cùng family
 
thieugiatri4492 said:
Nó không phải cặp chuỗi đâu, tại đề nó đưa cái mảng mà các chuỗi lúc nào cũng 3 ký tự hết, so lần lượt từng char của chuỗi này vs chuỗi kia, nếu tất cả char của chuỗi này lần lượt là nối tiếp với các char chuỗi kia theo thứ tự chữ cái alphabet thì nó là family
Click to expand...
Vừa đọc cái link của @Violet_7 xong. Dịch sai rồi bác. Cái bài này là đếm số lượng families được tạo nên trong cái mảng các chuỗi đó.
Nhìn qua thì cách giải là cứ build graph thôi xong rồi DFS để đếm số families
 
randomA said:
Vừa đọc cái link của @Violet_7 xong. Dịch sai rồi bác. Cái bài này là đếm số lượng families được tạo nên trong cái mảng các chuỗi đó.
Nhìn qua thì cách giải là cứ build graph thôi xong rồi DFS để đếm số families
Click to expand...
Bài này như bài miền liên thông thôi nhỉ, dùng union find là ok rồi.
 
randomA said:
Vừa đọc cái link của @Violet_7 xong. Dịch sai rồi bác. Cái bài này là đếm số lượng families được tạo nên trong cái mảng các chuỗi đó.
Nhìn qua thì cách giải là cứ build graph thôi xong rồi DFS để đếm số families
Click to expand...
Cái link đó đề khác mà còn cái của mình đề nó khác nữa, không giống nhau đâu
 

Similar threads

buiduchanh1995
thắc mắc Cách thiết kế database cho hệ thống lớn
2
Replies
37
Views
3K
khonganhit19
khonganhit19
meekoo
thắc mắc [Hỏi AI] Cách làm sao để train AI hiểu một task nào đấy?
Replies
9
Views
976
weed_bông
weed_bông
IM LANG
thắc mắc Cần cao nhân giúp đỡ về WordPress (có sử dụng custom theme bằng HTML, CSS)
Replies
3
Views
295
zaizai_vjp
zaizai_vjp
quangpt12345
kiến thức Join Anchor Consortium trading crypto sàn Odyssey kiếm lợi nhuận 2-3% mỗi ngày
Replies
2
Views
131
quangpt12345
quangpt12345
J
kiến thức Mod Mộng Liêu Trai mới nhất
Replies
0
Views
87
jivrus
J

Share this page

Back
Top