thảo luận Leetcode mỗi ngày
- Thread starter _Gia_Cat_Luong_
- Start date
Sunday_Sunday
Junior Member
Cứ filter theo mức
Easy rồi nhấn Pick One để nó random ra 1 bài làm thôi thím. Đừng làm theo topic, vì làm được 1 bài qua bài sau nó sẽ ná ná như vậy => chưa chắc sẽ giúp thím nhớ lâu
cmmmmmmmm
Member
e cam on a.
_Gia_Cat_Luong_
Senior Member
Công nhận, đọc xong bài đó phải mất 15p nghĩ mãi đ ra, bài ez méo gì khó vl.cái not contiguous subsequence chí mạng thật, đọc hồi mới ngẫm ra
Tức quá nhấn vào hint thì chết cười
). Lừa vl
ngoctan_95
Senior Member
Java ảo vãi cả nồi
Ý tưởng là:
- Nếu rỗng, return 0
- Tạo StringBuilder để reverse string input
Bài này same same bài số 5 và 9, xài lại
Last edited:
ngoctan_95
Senior Member
Ơ bài này trước pvan ở cty ở HCM nè
))
Java:
public int minPartitions(String n) {
int max = -1;
int length = n.length();
for (int i = 0; i < length; i++) {
// Check the gaps
int tempNumWithCharAt = n.charAt(i) - '0';
max = Math.max(tempNumWithCharAt, max);
}
return max;
}
Violet_7
Senior Member
28/6/2022:
- 1 câu medium nhẹ nhàng
- 1 string tốt khi ko có 2 kí tự nào cùng tần số, bỏ ít nhất các kí tự để string thành 1 string tốt -> chỉ cần quan tâm số lần lặp của mỗi kí tự.
- tạo 1 mảng lưu số lần lặp các kí tự, vì kí tự thường nên mảng chỉ cần 26 phần tử
- Như vậy thấy lúc này đề bài tương đương số lần giảm 1 đơn vị cho mỗi số sao cho dãy ko có 2 số nào giống nhau. Dãy ở đây chính là dãy lưu các lần lặp của kí tự
- VD {4, 2, 5, 4, 2} -> {3, 1, 5, 4, 2}, cần giảm 2 đơn vị
- Để làm vậy, sort mảng: {4, 2, 5, 4, 2} -> {5, 4, 4, 2, 2}
- xét từ lớn nhất -> bé nhất, giảm số tại vị trí i sao cho nó phải nhỏ hơn số trước, lấy cái số giảm đó cộng vào result
- Time: O(n) + O(26log26)
- Code: https://leetcode.com/submissions/detail/732992116/
- Hôm qua thức đến 1h30 sáng nên sáng dậy hơi bê, mất 10p để nghĩ ra ý tưởng, lúc đầu còn đọc đề sai, mất thêm 10p nữa để code và 1 lần submit sai
Cũng làm gần giống như thím Violet nhưng dùng HashSet để check cho nó nhẹ nhàng đơn giản
C#:
public class Solution {
public int MinDeletions(string s) {
int[] count = new int['z'-'a'+1];
foreach (char c in s)
count[c-'a']++;
Array.Sort(count);
HashSet<int> frequency = new ();
int ret = 0;
for (var i = 0; i < count.Length; i++)
{
while (count[i] > 0 && frequency.Contains(count[i]))
{
count[i]--;
ret++;
}
frequency.Add(count[i]);
}
return ret;
}
}Tương tự cách của bác Violet. Beat 97,72%
Code Java: https://leetcode.com/submissions/detail/733042952/
Code Java: https://leetcode.com/submissions/detail/733042952/
Sunday_Sunday
Junior Member
cùng idea với thímCũng làm gần giống như thím Violet nhưng dùng HashSet để check cho nónhẹ nhàngđơn giản
C#:public class Solution { public int MinDeletions(string s) { int[] count = new int['z'-'a'+1]; foreach (char c in s) count[c-'a']++; Array.Sort(count); HashSet<int> frequency = new (); int ret = 0; for (var i = 0; i < count.Length; i++) { while (count[i] > 0 && frequency.Contains(count[i])) { count[i]--; ret++; } frequency.Add(count[i]); } return ret; } }
Blue Amethyst
Junior Member
Em thấy cái của bác không cần phải sort ấyCũng làm gần giống như thím Violet nhưng dùng HashSet để check cho nónhẹ nhàngđơn giản
C#:public class Solution { public int MinDeletions(string s) { int[] count = new int['z'-'a'+1]; foreach (char c in s) count[c-'a']++; Array.Sort(count); HashSet<int> frequency = new (); int ret = 0; for (var i = 0; i < count.Length; i++) { while (count[i] > 0 && frequency.Contains(count[i])) { count[i]--; ret++; } frequency.Add(count[i]); } return ret; } }
em cũng tương tự bác, Java 100% https://leetcode.com/submissions/detail/733055071/
Sunday_Sunday
Junior Member
em nghĩ sort thì là nlognEm thấy cái của bác không cần phải sort ấy
em cũng tương tự bác, Java 100% https://leetcode.com/submissions/detail/733055071/
còn không sort thì là n*n
do em hiểu k sai thì hàm gọi n lần hàm contains thì độ phức tạp là n*n
Blue Amethyst
Junior Member
hàm .contains() của HashSet thì độ phức tạp O(1) thôi bác
Không sort thì tạch cái testEm thấy cái của bác không cần phải sort ấy
em cũng tương tự bác, Java 100% https://leetcode.com/submissions/detail/733055071/
"bbcebab" thím ơi À tự gạch, test đó tôi sai bởi chưa check
count[i] > 0 chứ không phải do chưa sort https://leetcode.com/submissions/detail/733011400/
Sunday_Sunday
Junior Member
sorry bác, em quên đấy.hàm .contains() của HashSet thì độ phức tạp O(1) thôi bác
cứ đinh ninh là list
Nhưng trong trường hợp n nhỏ thì dùng HashSet sẽ đỡ phải sort cái mảng 26 phần tử có khi sẽ tốt hơn.
Violet_7
Senior Member
- dùng hashset chỉ tốt hơn khi ít các phần tử trùng lặp, vd mảng 26 số 100 -> mất 100*99/2 lần đếm-> còn cách sort thì time luôn luôn là 26log26 lần.
- câu này cx khá giống câu hôm nay, nhưng giá trị phần tử lớn hơn và size cx lớn hơn: https://leetcode.com/problems/minimum-increment-to-make-array-unique/.
qhai_2009
Junior Member
Instead of learning solutions of LeetCode questions, understand patterns! 
For ex.
If input array is sorted then
If asked for all permutations/subsets then
- Backtracking
If given a tree then
If given a graph then
If given a linked list then
- Two pointers
If recursion is banned then
- Stack
If must solve in-place then
If asked for maximum/minimum subarray/subset/options then
- Dynamic programming
If asked for top/least K items then
- Heap
If asked for common strings then
Else
For ex.
If input array is sorted then
- Binary search
- Two pointers
If asked for all permutations/subsets then
- Backtracking
If given a tree then
- DFS
- BFS
If given a graph then
- DFS
- BFS
If given a linked list then
- Two pointers
If recursion is banned then
- Stack
If must solve in-place then
- Swap corresponding values
- Store one or more different values in the same pointer
If asked for maximum/minimum subarray/subset/options then
- Dynamic programming
If asked for top/least K items then
- Heap
If asked for common strings then
- Map
- Trie
Else
- Map/Set for O(1) time & O(n) space
- Sort input for O(nlogn) time and O(1) space
Similar threads
