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.
Mé đọc đề cứ ngồi code backtracking TLE lòi mắt.
Mà solution khó vãi, sao càng làm Leetcode càng thấy ngu =((
 
Sửa lần cuối:
Ban đầu nghĩ theo cách đếm chữ nhưng nghĩ mãi không biết kiểm tra với tạo chuỗi ntn :cry: bài này medium hơi bịp
 
Rút kinh nghiệm từ bài hôm qua, học cách chia nhỏ vấn đề :D Giải mất khoảng 1 tiếng. Hóng cao nhân có cách giải nào ngắn hơn.
Cách của tui là đếm chữ xong xếp desc theo số lần xuất hiện và đưa toàn bộ số chữ đã sắp xếp đó vào mảng mới (mảng a) nhưng cách ra khoảng trống (a.Length = s.Length * 2 - 1), chỗ những khoảng trống đó dùng để để chèn các chữ cái ở nửa sau vào. Cuối cùng là kiểm tra và cắt ra và trả về nếu chuỗi oke.
C#: 
public class Solution {
    public string ReorganizeString(string s) {
        Dictionary<char, int> charCount = new Dictionary<char, int>();

        foreach (char c in s) {
            if (charCount.ContainsKey(c)) {
                charCount[c]++;
            } else {
                charCount[c] = 1;
            }
        }

        charCount = charCount
            .OrderByDescending(pair => pair.Value)
            .ToDictionary(pair => pair.Key, pair => pair.Value);

        // Create a new array 'a' with length = s.Length * 2 - 1
        char[] a = new char[s.Length * 2 - 1];
        int current = 0;
   
        foreach (var kvp in charCount) {
            char c = kvp.Key;
            int count = kvp.Value;
            for (int i = 0; i < count; i++) {
                a[current] = c; // Fill even indices with characters
                current+=2;
            }
        }

        int sLength = s.Length;
        current = 1;
        for(int i = (s.Length % 2 == 1 ? s.Length + 1 : s.Length); i < a.Length; i+=2) {
            a[current] = a[i];
            current+=2;
        }

        ArraySegment<char> arraySlice = new ArraySegment<char>(a, 0, sLength);

        for(int i = 0; i < arraySlice.Count - 1; i++) {
            if(arraySlice[i] == arraySlice[i+1] || arraySlice[i] == '\u0000') {
                return "";
            }
            if(i == arraySlice.Count - 1) {
                if(arraySlice[i] == '\u0000')
                    return "";
            }
        }

        return string.Join("", arraySlice);
    }
}
 
Sửa lần cuối:
JavaScript: 
var reorganizeString = function(s) {
    let ctr = {}
    for (const ch of s) {
        ctr[ch] ??= 0;
        ctr[ch]++;
    }
    
    const arr = Object.entries(ctr).sort((u, v) => v[1] - u[1]);
    if (arr[0][1] > ~~((s.length + 1) / 2)) {
        return '';
    }
    const ss = arr.flatMap(([ch, cnt]) => [...ch.repeat(cnt)]);
    const sss = [];
    let j = 0;
    for (let i = 0; i < ss.length; i+=2) {
        sss[i] = ss[j++];
    }
    for (let i = 1; i < ss.length; i+=2) {
        sss[i] = ss[j++];
    }
    return sss.join('');
};
 
Priority Queue

Đếm tần số xuất hiện mỗi chữ cái. Dùng PQ để lưu trữ tần số xuất hiện cao nhất đến thấp nhất, mỗi lần append vào String mới sẽ append chữ cái có tần số xuất hiện cao nhất (trừ 1 sau mỗi lần). Nếu 2 chữ cái kế nhau bằng nhau thì append bằng chữ cái có tần số cao thứ hai.

PQ size = 26 -> heapify O(log(26)) = O(1)

TC & SC: O(s.length)

Java: 
class Solution {
    public String reorganizeString(String s) {
        char[] c = s.toCharArray();
        int[] cnt = new int[26];
        for (char i : c) {
            cnt[i - 'a']++;
        }

        Queue<Character> pq = new PriorityQueue<>((a, b) -> {
            return -(cnt[a - 'a'] - cnt[b - 'a']);
        });

        for (int i = 0; i < 26; i++) {
            pq.add((char) (i + 'a'));
        }


        StringBuilder sb = new StringBuilder();
        while(sb.length() < c.length) {
            char temp = pq.poll();
            if (sb.length() > 0 && sb.charAt(sb.length() - 1) == temp) {
                char temp2 = pq.poll();
                if (cnt[temp2 - 'a'] == 0) return "";
                sb.append(temp2);
                cnt[temp2 - 'a']--;
                pq.add(temp2);            
            } else {
                if (cnt[temp - 'a'] == 0) return "";
                sb.append(temp);
                cnt[temp - 'a']--;
            }
            pq.add(temp);
        }

        return sb.toString();
    }
}
 
Sửa lần cuối:
Giải thuật thì chạy vòng lặp. Cứ bốc 2 ký tự xuất hiện nhiều nhất, rồi update lại.

C#: 
public string ReorganizeString(string s)
{
    int n = s.Length, i, j;
    if (n == 1) return s;
    if (n == 2)
        return s[0] == s[1] ? "" : s;

    int[][] nums = new int[26][];
    for (i = 0; i < 26; ++i)
    {
        nums[i] = new int[2];
        nums[i][1] = i;
    }

    foreach (var c in s)
        ++nums[c - 'a'][0];

    j = (n + 1) / 2;
    for (i = 0; i < 26; ++i)
        if (nums[i][0] > j)
            return "";

    string str = "";
    while (n > 0)
    {
        Array.Sort(nums, (a, b) => { return b[0] - a[0]; });
        str += (char)('a' + nums[0][1]);
        --nums[0][0]; --n;

        if (nums[1][0] > 0)
        {
            str += (char)('a' + nums[1][1]);
            --nums[1][0]; --n;
        }
    }

    return str;
}
 
Có cách nào xem code của mấy thằng beat cao cao ko ae nhỉ, làm mấy bài sql đúng sgk mà beat đỏ lè nên muốn xem cách các thánh tối ưu 😰

via theNEXTvoz for iPhone
 
/**
* @param {string} s
* @return {string}
*/
var reorganizeString = function(s) {
let map = {};
for (let c of s) {
map[c] ??= 0;
map[c]++;
}
const arr = Object.entries(map).sort((a, b) => b[1] - a[1]);
if (arr[0][1] > ((s.length + 1) >> 1)) return '';
let index = 0;
const ans = [];
/**
[
[ 'c', 4 ], [ 'm', 3 ],
[ 'o', 2 ], [ 'b', 2 ],
[ 'g', 1 ], [ 'k', 1 ],
[ 'w', 1 ], [ 'x', 1 ],
[ 't', 1 ], [ 's', 1 ],
[ 'z', 1 ], [ 'l', 1 ],
[ 'i', 1 ]
]
*/

for (let i = 0; i < arr.length; i++) {
while (arr[1] > 0) {
if (index >= s.length) index = 1;
ans[index] = arr[0];
index += 2;
arr[1] -= 1;
}
}
return ans.join('');
};
 
Baì hôm nay greedy khá dễ mà, thấy còn dễ nghĩ hơn bài hôm qua.
xjIzSG9.png
 
C++: 
func reorganizeString(s string) string {
  mHeap := maxHeap{}
  heap.Init(&mHeap)
  m := make(map[rune]int)
  for _, c := range s {
    m[c]++
  }
  for k, v := range m {
    heap.Push(&mHeap, CharCount{char: k, count: v})
  }
  var ans strings.Builder
  for len(mHeap) > 1 {
    fChar := heap.Pop(&mHeap).(CharCount)
    sChar := heap.Pop(&mHeap).(CharCount)
    ans.WriteRune(fChar.char)
    ans.WriteRune(sChar.char)
    if fChar.count > 1 {
      heap.Push(&mHeap, CharCount{
        char:  fChar.char,
        count: fChar.count - 1,
      })
    }
    if sChar.count > 1 {
      heap.Push(&mHeap, CharCount{
        char:  sChar.char,
        count: sChar.count - 1,
      })
    }
  }
  if len(mHeap) > 0 {
    c := heap.Pop(&mHeap).(CharCount)
    if c.count > 1 {
      return ""
    }
    ans.WriteRune(c.char)
  }
  return ans.String()
}
type CharCount struct {
  char  rune
  count int
}
type maxHeap []CharCount
func (h maxHeap) Less(i, j int) bool {
  return h[i].count > h[j].count
}
func (h maxHeap) Swap(i, j int) {
  h[i], h[j] = h[j], h[i]
}
func (h maxHeap) Len() int {
  return len(h)
}
func (h *maxHeap) Push(x interface{}) {
  *h = append(*h, x.(CharCount))
}
func (h *maxHeap) Pop() interface{} {
  x := (*h)[len(*h)-1]
  *h = (*h)[:len(*h)-1]
  return x
}
 
Du hoi cham nhung pass tests =))
C++: 
class Solution {
public:
    string reorganizeString(string s) {
        unordered_map<char, int> count;
        for (char c : s) count[c]++;
        
        priority_queue<pair<int, char>> maxHeap;
        for (const auto& it : count) maxHeap.emplace(it.second, it.first);
        
        string res = "";
        while (!maxHeap.empty()){
            auto [cnt, c] = maxHeap.top(); maxHeap.pop();
            if (res.size() == 0 || c != res.back()){
                res += c;
                if (cnt > 1) maxHeap.emplace(cnt - 1, c);
            }else{
                if (!maxHeap.empty()){
                    auto [cnt1, c1] = maxHeap.top(); maxHeap.pop();
                    res += c1;
                    if (cnt1 > 1) maxHeap.emplace(cnt1 - 1, c1);
                    maxHeap.emplace(cnt, c);
                }else return "";
            }
        }
        return res;
    }
};
 
nay fix bug sml, sáng nhìn qua là nghĩ sẽ xài cái priorityqueue r
Python: 
class Solution:
    def reorganizeString(self, s: str) -> str:

        map = defaultdict(int)
        for c in s:
            map[c] += 1
        possible = True
        result = ""
        n = len(s)

        q = []
        
        for c in map:
            q.append((-map[c], c))

        heapq.heapify(q)
        valid = True
        while q:
            # print(q)
            curr = heapq.heappop(q)
            m, max_char_1 = -curr[0], curr[1]
            if len(result) == 0 or result[-1] != max_char_1:
                result += max_char_1
                m -= 1
                if m > 0:
                    heapq.heappush(q, (-m, max_char_1))
                continue
            else:
                if len(q) == 0:
                    return ""
                curr = heapq.heappop(q)
                n, max_char_2 = -curr[0], curr[1]
                result += max_char_2
                n -= 1
                if n > 0:
                    heapq.heappush(q, (-n, max_char_2))
                heapq.heappush(q, (-m, max_char_1))
        
        return result
 
Hover đã nói:
Baì hôm nay greedy khá dễ mà, thấy còn dễ nghĩ hơn bài hôm qua.
xjIzSG9.png
Nhấp để mở rộng...
Mấy bài greedy ảo lắm. Trc làm contest t làm đc câu q4 greedy hard nhưng ko làm đc câu q3. Xong vẫn top 400. :haha:
Nói chung mấy bài này tâm trạng tốt thì nghĩ rất nhanh. Còn lờ đờ như t sáng nay phải mất cả tiếng ms nghĩ ra pq. Còn ko nghĩ ra cách O(n), mặc dù nó cx ko phức tạp gì :too_sad:
 
Hover đã nói:
Baì hôm nay greedy khá dễ mà, thấy còn dễ nghĩ hơn bài hôm qua.
xjIzSG9.png
Nhấp để mở rộng...
suy nghĩ theo đúng hướng thì dễ, sai hướng thì mất thời gian hơn nên thấy khó
aVgiONl.png
Lịt pẹ toy xài tham lam nhưng trật hướng, cũng theo kiểu lớn nhất rồi lớn nhì nhưng append hết lớn nhất và hết lớn nhì luôn chứ ko push lại vào pq, thế đéo nào tới test 64/70 mới oẳng. Như kiểu "aaaabbcc" thì "a*a*a*a" rồi "ababa*a" rồi "ababaca", nhưng đụng "aaabbcc" thì lại thành "a*a*a" rồi "ababa" rồi "ababac*c" thì oẳng. 1 lúc sau mới nghĩ ra được xài pq pop 2 char lớn nhất nhì rồi -1 tần suất của 2 char đó

C++: 
struct Solution {
    string reorganizeString(string s) {
        priority_queue<pair<int, char>> maxPq;
        int freq[256]{};
        for (char c : s) ++freq[c];
        for (int c = 'a'; c <= 'z'; ++c)
            if (freq[c] > 0) maxPq.emplace(freq[c], c);
        string res;
        while (maxPq.size() > 1) {
            auto [f1, c1] = maxPq.top(); maxPq.pop();
            res += c1;
            auto [f2, c2] = maxPq.top(); maxPq.pop();
            res += c2;
            if (f1 > 1) maxPq.emplace(f1 - 1, c1);
            if (f2 > 1) maxPq.emplace(f2 - 1, c2);
        }
        return maxPq.empty() ? res : maxPq.top().first > 1 ? "" : res + maxPq.top().second;
    }
};
 
Sửa lần cuối:
https://leetcode.com/problems/substring-with-concatenation-of-all-words
Ae ai rảnh cho mình hỏi sao bài này test case này ra [] nhỉ, phải ra 8 mới đúng chứ.
Lúc đầu bài này mình nghĩ là giải bằng backtracking.

Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []
Explanation: Since words.length == 4 and words.length == 4, the concatenated substring has to be of length 16.
There is no substring of length 16 is s that is equal to the concatenation of any permutation of words.
We return an empty array.
 
freedom.9 đã nói:
https://leetcode.com/problems/substring-with-concatenation-of-all-words
Ae ai rảnh cho mình hỏi sao bài này test case này ra [] nhỉ, phải ra 8 mới đúng chứ.
Lúc đầu bài này mình nghĩ là giải bằng backtracking.

Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []
Explanation: Since words.length == 4 and words.length == 4, the concatenated substring has to be of length 16.
There is no substring of length 16 is s that is equal to the concatenation of any permutation of words.
We return an empty array.
Nhấp để mở rộng...
8 là ["good", "good", "best", "word"] chứ đâu phải ["word","good","best","word"]
TG0OxM9.gif
 
JavaScript: 
function reorganizeString(s: string): string {
    const strLen = s.length
    let index = 0;
    const result:string[] = Array(strLen);

    const characterCountMap = buildCharacterCountMap(s);
    const charactersSortedByCount = Object.keys(characterCountMap).sort((ch1,ch2)=> characterCountMap[ch2]-characterCountMap[ch1])

    const hasNoResult = charactersSortedByCount.some((char)=>{
        const numberOfCharacter = characterCountMap[char];
        // No arrangement available if characterCount > (length+1)/2
        if(numberOfCharacter > (strLen+1)/2){
            return result;
        }

        for(let i=0;i<numberOfCharacter;i++){
            if (index >= strLen) index = 1;
            result[index] = char;
            index +=2;
        }

        return false;
    })

    return hasNoResult ? '' : result.join('');
};

function buildCharacterCountMap(s:string){
    const charArray = s.split('');
    return charArray.reduce((acc,char)=>{
        if (acc[char]) acc[char]+=1;
        else acc[char] = 1;
        return acc;
    },{}
        )
}
 
freedom.9 đã nói:
https://leetcode.com/problems/substring-with-concatenation-of-all-words
Ae ai rảnh cho mình hỏi sao bài này test case này ra [] nhỉ, phải ra 8 mới đúng chứ.
Lúc đầu bài này mình nghĩ là giải bằng backtracking.

Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []
Explanation: Since words.length == 4 and words.length == 4, the concatenated substring has to be of length 16.
There is no substring of length 16 is s that is equal to the concatenation of any permutation of words.
We return an empty array.
Nhấp để mở rộng...

Có permutation nào tạo ra được substring bắt đầu ở vị trí 8 đâu bro.
 
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.566

Chia sẻ trang này

Quay lại
Lên đầu trang