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

tầm 1k1 bài thôi bác.. mình làm chơi chơi thôi chứ ko ham hố cày leetcode cho lắm... kiểu có ngày lên đồng nhìn vào làm được là cứ thế mà gõ thôi, còn bí thì thôi dẹp qua bên từ từ làm tiếp, kiểu vậy.. làm dần nó lên được chừng đó
khủng dữ bác cày mấy năm rồi vậy nếu mỗi ngày 1 bài chắc 3 năm
BdgiW7R.png
 
C++:
class Solution {
public:
    string gcdOfStrings(string s1, string s2) {
        return (s1 + s2 == s2 + s1)  
            ? s1.substr(0, gcd(size(s1), size(s2)))
            : "";
    }
};
 
Bài hôm nay đúng là easy, không hiểu sao mấy bố trong phần discussion còn bảo là medium/hard nữa
Đơn thuần là tính GCD của str1.lengthstr2.length


JavaScript:
function gcdOfStrings(str1: string, str2: string): string {
    const x = str1.length, y = str2.length;
    const gcdNum = x > y ? gcd(x, y): gcd(y, x);
    const gcdStr = str1.substring(0, gcdNum);
    for (let i = 0; i < (x > y ? x/gcdNum : y/gcdNum); i++) {
        str1 = str1.replace(gcdStr, '');
        str2 = str2.replace(gcdStr, '');
    }
    return (str1.length === 0 && str2.length === 0) ? gcdStr : '';
};

function gcd(x: number,y: number) {
    if (y === 0) return x;
    return gcd(y, x % y);
}
 
Last edited:
Bài hôm nay đúng là easy, không hiểu sao mấy bố trong phần discussion còn bảo là medium/hard nữa
Đơn thuần là tính GCD của str1.lengthstr1.length


JavaScript:
function gcdOfStrings(str1: string, str2: string): string {
    const x = str1.length, y = str2.length;
    const gcdNum = x > y ? gcd(x, y): gcd(y, x);
    const gcdStr = str1.substring(0, gcdNum);
    for (let i = 0; i < (x > y ? x/gcdNum : y/gcdNum); i++) {
        str1 = str1.replace(gcdStr, '');
        str2 = str2.replace(gcdStr, '');
    }
    return (str1.length === 0 && str2.length === 0) ? gcdStr : '';
};

function gcd(x: number,y: number) {
    if (y === 0) return x;
    return gcd(y, x % y);
}
Cách của t tính GDC của str1, str2 luôn.
Ý tưởng tương tự cách tính gcd của số tự nhiên. Thằng nào lớn hơn thì trừ đi thằng nhỏ rồi tính tiếp tương tự đến khi = nhau thì là GCD.
Python:
class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        if str1 == str2:
            return str1
        if len(str1) < len(str2):
             str1, str2 = str2, str1
        if str1.startswith(str2):
            return self.gcdOfStrings(str1[len(str2):], str2)
        return ""

Python:
return str1 if str1 == str2 else self.gcdOfStrings(str1[len(str2):], str2) if str1.startswith(str2) else self.gcdOfStrings(str2[len(str1):], str1) if str2.startswith(str1) else ""
 
Last edited:
Bài hôm nay ban đầu nhìn nghĩ hơi phức tạp nhưng sau tiếng hơn em cũng mò ra đc 2 cách khá dễ hiểu các thím nhìn phát hiểu ngay :giggle: em có còm trong codeạ
Java:
class Solution {
    /**
    Iterating through all possible substrings length from len to 1
     */
    public static String gcdOfStrings(String s, String t) {
        int m = s.length(); int n = t.length();
        int len = Math.min(m, n);
        for (int i = len; i >= 1; i--) {
            if (m % i == 0 && n % i == 0) {
                String divisor = s.substring(0, i);
                StringBuilder sb1 = new StringBuilder();
                StringBuilder sb2 = new StringBuilder();
                while (sb1.length() < m) {
                    sb1.append(divisor);
                }
                while (sb2.length() < n) {
                    sb2.append(divisor);
                }
                if (sb1.toString().equals(s) && sb2.toString().equals(t)) {
                    return divisor;
                }
            }
        }
        return "";
    }

    /**
    Use gcd of length vs principle a+b = b+a (if they are multiple of substring)
     */
    public static String gcdOfStrings(String s, String t) {
        return ( (s + t + "").equals(t + s + "") ) ?
            s.substring(0, Math.gcd(s.length(), t.length())) : "";
    }
    public static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }
}
 
hôm nay chưa thấy ai làm nhỉ :doubt:
Java:
class Solution {
    public boolean isAlienSorted(String[] words, String order) {
        int [] position = new int [256];
        for (int i = 0; i < order.length(); ++i) {
            char c = order.charAt(i);
            position[c] = i;
        }
        for (int i = 0; i < words.length-1; ++i) {
            for (int c = 0; c < words[i].length(); ++c) {
                if (words[i].length() > words[i+1].length() && c == words[i+1].length()) return false;
                if (position[words[i].charAt(c)] > position[words[i+1].charAt(c)]) return false;
                else if (position[words[i].charAt(c)] < position[words[i+1].charAt(c)]) break;
            }
        }
        return true;
    }
}
 
code hoi xau nhung em follow gcd algo cua euclid :LOL:
Code:
class Solution {
    public String gcdOfStrings(String str1, String str2) {
        if (str1.length() >= str2.length()) return helper(str1, str2);
        return helper(str2, str1);
    }

    public String helper(String a, String b) {
        if (a.equals(b)) return a;
        if (b.length() == 0) return "";
        if (!a.substring(a.length() - b.length()).equals(b)) return "";
        String newS = a.substring(0, a.length() - b.length());
        if(newS.length() >= b.length()) return helper(newS, b);
        return helper(b, newS);
    }
}
 
C++:
class Solution {
public:
bool isAlienSorted(vector<string>& words, string order) {
 vector<string> result = words;
 sort(words.begin(), words.end(), [&order](const string& a, const    string& b) {
 int i = 0, j = 0;
  while (i < a.length() && j < b.length()) {
    int a_pos = order.find(a[i]);
    int b_pos = order.find(b[j]);
    if (a_pos != string::npos && b_pos == string::npos) {
      return true;
    } else if (a_pos == string::npos && b_pos != string::npos) {
      return false;
    } else {
      if (a_pos < b_pos) {
        return true;
      } else if (a_pos > b_pos) {
        return false;
      }
    }
    ++i;
    ++j;
  }
  return a.length() < b.length();
  });
  if (equal(result.begin(), result.end(), words.begin())) return true;
  else return false;
    }
};
Bài hôm này với hôm qua em nhận định thấy nó ở mức medium thì đúng hơn:doubt:
 
Kiểu design system đồ, hoặc là hiểu sâu về máy tính á, hiểu rõ bản chất mọi cái... Mình thấy cái đó có ich hơn nhiều vì nó thực tiễn và giúp mình giải quyết vấn đề nhiều hơn...
Thường vòng 1 cty họ hay cho test data structure & algorithms . Theo thím những thứ nào cần nắm vững để khoanh vùng cho gọn lại xíu. Vì mấy cái system design mới giúp mình nhiều trong công việc nhưng bài test vòng 1 không qua thì khỏi nói đến system :D

Mình cày những thứ này:
  • Greedy
  • Graph
  • Tree
  • String
  • Cuối cùng mới đến DP

Theo thím đủ chưa :extreme_sexy_girl:
 
bài hôm nay 2/2. Viết kiểu đơn giản, k tối ưu thì mấy dòng là xong thôi, :p.
ý tưởng là transform words về words_normal theo thứ tự alphabet, sort, rồi compare

Python:
class Solution:
    def isAlienSorted(self, words: List[str], order: str) -> bool:
        dict_word = { a : b for a, b in zip(order, sorted(order))}
        words_normal = ["".join([dict_word[x] for x in word]) for word in words]    
        return words_normal == sorted(words_normal)
 
Code:
class Solution {
    public boolean isAlienSorted(String[] words, String order) {
        int[] map = new int[26];
        for (int i = 0; i < 26; i++) {
            map[order.charAt(i) - 'a'] = i;
        }

        for (int i = 0; i < words.length - 1; i++) {
            char[] a = words[i].toCharArray();
            char[] b = words[i+1].toCharArray();

            for (int j = 0; j < a.length; j++) {
                if (j == b.length) return false;
                if (map[a[j] - 'a'] < map[b[j] - 'a']) break;
                if (map[a[j] - 'a'] > map[b[j] - 'a']) return false;
            }
        }

        return true;
    }
}
 
Last edited:
Thường vòng 1 cty họ hay cho test data structure & algorithms . Theo thím những thứ nào cần nắm vững để khoanh vùng cho gọn lại xíu. Vì mấy cái system design mới giúp mình nhiều trong công việc nhưng bài test vòng 1 không qua thì khỏi nói đến system :D

Mình cày những thứ này:
  • Greedy
  • Graph
  • Tree
  • String
  • Cuối cùng mới đến DP

Theo thím đủ chưa :extreme_sexy_girl:

Thật ra vậy cũng đúng mà, data structures mà còn không biết thì design system kiểu gì. Mình học về system design càng đào sâu càng đụng vô data structures nhiều. Thấy các building blocks của system design toàn data structures không thôi, tùm lum data structures.
 
Bài hôm này với hôm qua em nhận định thấy nó ở mức medium thì đúng hơn:doubt:
bài hôm nay biết vài hàm trong <algorithm> như is_sortedlexicographical_compare thì dễ thoy
uq1dgnk.png


C++:
struct Solution {
    bool isAlienSorted(const vector<string>& words, string_view order) {
        array<int, 26> p{};
        for (size_t i = 0; i < order.size(); ++i) p[order[i] - 'a'] = i;
        return is_sorted(begin(words), end(words), [&](const auto& a, const auto& b){
            return lexicographical_compare(begin(a), end(a), begin(b), end(b), [&](char x, char y){
                return p[x - 'a'] < p[y - 'a'];
            });
        });
    }
};
 
Ý tưởng: Mình tạo map để lưu order của bảng chữ cái mới sau đó so sánh từng cặp giá trị thôi
Viết nhanh nên toàn early return:D
JavaScript:
function isAlienSorted(words: string[], order: string): boolean {
    const map: Map<string, number> = new Map();
    let isSorted = true;
    for (let i = 0; i <= order.length; i++) {
        map.set(order[i], i);
    }
    if (words.length < 2) {
        return true;
    }
    let i = 0, j = 1;
    while (j < words.length) {
        if (compareWord(words[i], words[j], map)) {
            i++;
            j++;
        } else {
            isSorted = false;
            break;
        }
    }
    return isSorted
};

function compareWord(x: string, y: string, map: Map<string, number>) {
    for (let i = 0; i < (x.length > y.length ? x.length : y.length); i++) {
        if (x.length > y.length && (x[i] && !y[i])) {
            return false;
        }
        if (x.length < y.length && (!x[i] && y[i])) {
            return true;
        }
        if (x[i] === y[i]) {
            continue
        }
        if (map.get(x[i]) > map.get(y[i])) {
            return false;
        } else return true;
    }
    return true;
}
 
C++:
class Solution {
public:
bool isAlienSorted(vector<string>& words, string order) {
 vector<string> result = words;
 sort(words.begin(), words.end(), [&order](const string& a, const    string& b) {
 int i = 0, j = 0;
  while (i < a.length() && j < b.length()) {
    int a_pos = order.find(a[i]);
    int b_pos = order.find(b[j]);
    if (a_pos != string::npos && b_pos == string::npos) {
      return true;
    } else if (a_pos == string::npos && b_pos != string::npos) {
      return false;
    } else {
      if (a_pos < b_pos) {
        return true;
      } else if (a_pos > b_pos) {
        return false;
      }
    }
    ++i;
    ++j;
  }
  return a.length() < b.length();
  });
  if (equal(result.begin(), result.end(), words.begin())) return true;
  else return false;
    }
};
Bài hôm này với hôm qua em nhận định thấy nó ở mức medium thì đúng hơn:doubt:
bài hnay thì medium thiệt, bài hqua mình nghĩ nó khá clear là tính gcd rồi thím, ez thôi hehe:D
 
JavaScript:
var isAlienSorted = function(words, order) {
    const dict = {};
    order.split('').forEach((ch, idx) => {
        dict[ch] = String.fromCharCode(97 + idx);
    });
    const trans = s => {
        return s.split('').map(ch => dict[ch]).join('');
    };
    for (let i = 0; i < words.length; i++) {
        words[i] = trans(words[i]);
        if (i>0 && words[i] < words[i-1]) {
            return false;
        }
    }
    return true;
};
 
vs ruby thì 1 dòng.
ý tưởng map ailen_order về person_order sau đó sort lại.

Ruby:
def is_alien_sorted(words, order)
  words == words.sort_by {|word| word.tr(order, 'abcdefghijklmnopqrstuvwxyz') }
end
 
order có 26 chữ nên order.find(x) là O(1) nhóe
MjfezZB.png


C++:
struct Solution {
    bool isAlienSorted(const vector<string>& words, string_view order) {
        return is_sorted(begin(words), end(words), [&](const auto& a, const auto& b){
            return lexicographical_compare(begin(a), end(a), begin(b), end(b), [&](char x, char y){
                return order.find(x) < order.find(y);
            });
        });
    }
};
 
Mình biết hơi loằng ngoằng các bác góp ý giúp nhé
JavaScript:
function isAlienSorted(words: string[], order: string): boolean {
  let objDecode = {};

  for (let i = 0; i < 26; i++) {
    objDecode = { ...objDecode, [order[i]]: String.fromCharCode(97 + i) };
  }

  const getHumanWord = (word: string): string => {
    let score = "";
    const lWord = word.length;
    for (let i = 0; i < lWord; i++) {
      score = `${score}${objDecode[word[i]]}`;

    }
    return score;
  };
  
  const l = words.length;
  const humanWords: string[] = [];
  let result = true
  for (let i = 0; i < l - 1; i++) {
    const humanWord1 = getHumanWord(words[i]);
    const humanWord2 = getHumanWord(words[i + 1]);
    if (humanWord1.localeCompare(humanWord2) > 0) {
      result = false;
      break
    } 
  }

  return result;
}
 
Last edited:
Lúc đầu hiểu nhầm đề, đã correct :)

JavaScript:
var isAlienSorted = function(words, order) {
    pass = true
    for (cur=0; cur<words.length -1; cur++){
       currentWord = words[cur]
       nextWord = words[cur+1]
       console.log("\n",currentWord, " ", nextWord)
       
       for (i=0; i<currentWord.length; i++){
           first = -1
           second = -1
           for(j=0; j<order.length; j++){
               if (currentWord[i] === order[j]) first = j
               if (nextWord[i] === order[j]) second = j
           }
           console.log(currentWord[i], " ",first, " ",nextWord[i], " ",second, " ")
           if (first <second) break
           if (first >second) {
               pass = false
               break
           }
       }

    }
    return pass
};
 
Back
Top