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

Kân team v3 · 21/9/22

Python mà dài thế?

C++:

class Solution {
public:
    vector<int> sumEvenAfterQueries(vector<int>& nums, vector<vector<int>>& queries) {
        vector<int> res; res.reserve(queries.size());
        int sum = 0;
        for (auto i : nums) sum += i & ((i & 1) - 1);
        for (auto &v : queries) {
            auto &n = nums[v[1]];
            sum -= n & ((n & 1) - 1);
            n += v[0];
            res.emplace_back(sum += n & ((n & 1) - 1));
        }
        return res;
    }
};

dân chơi là xài 1 hàm thoy

C++:

struct Solution {
    vector<int> sumEvenAfterQueries(vector<int>& nums, vector<vector<int>>& queries) {
        vector<int> res(queries.size());
        transform(begin(queries), end(queries), begin(res),
                  [&, sum = accumulate(begin(nums), end(nums), 0, [](int sum, int n) {
                          return sum + (n & ((n & 1) - 1));
                      })](const auto& q) mutable {
                      auto& n = nums[q[1]];
                      sum -= n & ((n & 1) - 1);
                      n += q[0];
                      return sum += n & ((n & 1) - 1);
                  });
        return res;
    }
};

thuyduong2007 · 21/9/22

Kân team v3 đã nói:
dân chơi là xài 1 hàm thoy

C++:

struct Solution { vector<int> sumEvenAfterQueries(vector<int>& nums, vector<vector<int>>& queries) { vector<int> res(queries.size()); transform(begin(queries), end(queries), begin(res), [&, sum = accumulate(begin(nums), end(nums), 0, [](int sum, int n) { return sum + (n & ((n & 1) - 1)); })](const auto& q) mutable { auto& n = nums[q[1]]; sum -= n & ((n & 1) - 1); n += q[0]; return sum += n & ((n & 1) - 1); }); return res; } };

Làm chi phức tạp vậy bác kân, 1 dòng là đủ rồi

C++:

        return accumulate(queries.begin(), queries.end(), vector<int>(queries.size()), 
                  [&nums, i = 0, sum = accumulate(nums.begin(), nums.end(), 0, 
                                                  [](auto acc, auto x) {
                                                      return acc + (x & ((x & 1)-1));
                                                  })] (auto &acc, auto &x) mutable {
                            sum -= nums[x[1]] & ((nums[x[1]] & 1) - 1);
                            nums[x[1]] += x[0];
                            sum += nums[x[1]] & ((nums[x[1]] & 1) - 1);
                            acc[i++] = sum;
                            return move(acc);
                        });

Kân team v3 · 21/9/22

thuyduong2007 đã nói:

Làm chi phức tạp vậy bác kân, 1 dòng là đủ rồi

C++:

        return accumulate(queries.begin(), queries.end(), vector<int>(queries.size()), 
                  [&nums, i = 0, sum = accumulate(nums.begin(), nums.end(), 0, 
                                                  [](auto acc, auto x) {
                                                      return acc + (x & ((x & 1)-1));
                                                  })] (auto &acc, auto &x) mutable {
                            sum -= nums[x[1]] & ((nums[x[1]] & 1) - 1);
                            nums[x[1]] += x[0];
                            sum += nums[x[1]] & ((nums[x[1]] & 1) - 1);
                            acc[i++] = sum;
                            return move(acc);
                        });

nick cùi bắp ko like được

Lập Trình Viên Số Khổ · 22/9/22

easy problem :sweet_kiss:

Python:

class Solution:
    def reverseWords(self, s: str) -> str:
        return " ".join([i[::-1] for i in s.split(' ')])

Lập Trình Viên Số Khổ · 22/9/22

dynamic programming đã nói:
Bác hash 1 string thì dù gì hash function cũng phải duyệt qua cả string đó rồi mới gen ra được một số nên ko phải O(nm). Vd như hash("a") với hash("aaaaaaaa") thì thời gian ko giống nhau đâu.
Bác đọc trong này có ví dụ về 1 hàm polynomial rolling hash này
https://cp-algorithms.com/string/string-hashing.html

NudeDuck đã nói:
Ồ hiểu rồi thank you 2 fen nhiều nha

cái code cũ hôm chủ nhật nó vẫn cho pass nè fen, ảo thiệt đó, tự nhiên sáng nay thấy nó update giải đc 4 bài lun :byebye:

dangson · 22/9/22

Thấy bài dễ là phải nhoi lên ngay. =]]

Python:

return ' '.join([w[::-1] for w in s.split()])

Legolas1618 · 22/9/22

C#:

public class Solution {
    public string ReverseWords(string s) {
        List<string> result = new List<string>();
        string[] arr = { s };

        if (s.Contains(" "))
            arr = s.Split(" ");

        foreach (string aWord in arr)
        {
            char[] charArray = aWord.ToCharArray();
            Array.Reverse(charArray);
            result.Add(new string(charArray));
        }
        return string.Join(" ", result);
    }
}

Aristides · 22/9/22

thằng Java không có methods reverse cho string, cũng không có reverse substring cho StringBuilder nhỉ?

Java:

class Solution {
    public String reverseWords(String s) {
        if(s.length() == 0)
        {
            return s;
        }
        StringBuilder ans = new StringBuilder(s);
        StringBuilder tmp = new StringBuilder();
        int j = 0;
        for(int i = 0; i < ans.length(); i++)
        {
            if(ans.charAt(i) != ' ')
            {
                continue;
            }
            tmp.append(ans.substring(j, i)).reverse();
            ans.replace(j, i, tmp.toString());
            tmp.delete(0, tmp.length());
            j = i + 1;
        }
        tmp.append(ans.substring(j, ans.length())).reverse();
        ans.replace(j, ans.length(), tmp.toString());
        tmp.delete(0, tmp.length());
        return ans.toString();
    }
}

nhân vật phụ · 22/9/22

Aristides đã nói:
thằng Java không có methods reverse cho string, cũng không có reverse substring cho StringBuilder nhỉ?

Java:

class Solution { public String reverseWords(String s) { if(s.length() == 0) { return s; } StringBuilder ans = new StringBuilder(s); StringBuilder tmp = new StringBuilder(); int j = 0; for(int i = 0; i < ans.length(); i++) { if(ans.charAt(i) != ' ') { continue; } tmp.append(ans.substring(j, i)).reverse(); ans.replace(j, i, tmp.toString()); tmp.delete(0, tmp.length()); j = i + 1; } tmp.append(ans.substring(j, ans.length())).reverse(); ans.replace(j, ans.length(), tmp.toString()); tmp.delete(0, tmp.length()); return ans.toString(); } }

sao lại không

PHP:

class Solution {
    public String reverseWords(String s) {
        String[] words = s.split(" ");
        
        for (int i = 0; i < words.length; i++) {
            words[i] = new StringBuilder(words[i]).reverse().toString();
        }
        
        return String.join(" ", words);
    }
}

bribnt · 22/9/22

Mã:

object Solution {
    def reverseWords(s: String): String = {
        s split ' ' map (_.reverse) mkString " "
    }
}

crushkydvn · 22/9/22

dangson đã nói:
Thấy bài dễ là phải nhoi lên ngay. =]]

Python:

return ' '.join([w[::-1] for w in s.split()])

Em cũng python mà dài vch :")) có khoá nào học để viết code gọn lại không thím.

Python:

class Solution:
    def reverseWords(self, s: str) -> str:
        a=s.split()
        ans=""
        for i in range(len(a)):
            a[i]=a[i][::-1]
            if (i<len(a)-1):
                ans+=a[i]+" ";
            else:
                ans+=a[i]
        return ans

Kân team v3 · 22/9/22

1 dòng C++

C++:

struct Solution {
    string reverseWords(string s) {
        return [&] { for (auto it = begin(s), jt = begin(s); reverse(it, jt = find(it, end(s), ' ')), jt != end(s);) it = jt + 1; }(), s;
    }
};

nhoccoi96vp · 22/9/22

Mã:

func reverseWords(s string) string {
    arrayS := make([]string, 0)
    arrayS = strings.Split(s, " ")
    for index, value := range arrayS {
        arrayS[index] = reverseWord(strings.Split(value, ""))
    }
    return strings.Join(arrayS, " ")
}

func reverseWord(s []string) string {
    left, right := 0, len(s) - 1
    for left < right {
        temp := s[right]
        s[right] = s[left]
        s[left] = temp
        left++
        right--
    }
    return strings.Join(s, "")
}

Đoạn reverse thì dùng two pointer

sau_tim_thiep_hong · 23/9/22

Python:

class Solution:
    def reverseWords(self, s: str) -> str            :
        return " ".join(s[::-1].split(" ")[::-1])

thuyduong2007 · 23/9/22

23/09:

Python:

return reduce(lambda acc, x: ((acc << x.bit_length()) | x)%int(1e9+7), range(1,n+1))

dangson · 23/9/22

crushkydvn đã nói:
Em cũng python mà dài vch :")) có khoá nào học để viết code gọn lại không thím.

Python:

class Solution: def reverseWords(self, s: str) -> str: a=s.split() ans="" for i in range(len(a)): a[i]=a[i][::-1] if (i<len(a)-1): ans+=a[i]+" "; else: ans+=a[i] return ans

Thôi cứ viết dài đi cho dễ đọc.
Mình code dưỡng sinh nghịch ngợm thì mới thế thôi.

https://github.com/dangsonbk/1linePython

Kân team v3 · 23/9/22

bài hôm nay khó thặc, search oeis mới ra được 1 dòng

C++:

struct Solution {
    int concatenatedBinary(int n) {
        return n == 1 ? 1 : (concatenatedBinary(n - 1) * (1ULL << (1 + static_cast<int>(log2(n)))) + n) % 1'000'000'007;
    }
};

bribnt · 23/9/22

Thuật toán O(log^2 n). Nguyên tắc cơ bản là dựa vào việc có thể tính nhanh tổng dãy cấp số nhân 2^k phần tử.
Có ai rảnh thử code xem:

Xét nửa khoảng từ [2^k, 2^(k+1) ), ta thấy tất cả số j trong này đều có k bit trong biểu diễn nhị phân. Như vậy khi ghép lại có thể tách làm 2 phân so le k bit như sau (i = 2^k)

s(0) = i 0^k (i+2) 0^k ... i+2^k-2 0^k
s(1) = 0^k (i+1) 0^k i+3 ... 0^k i+2^k-1

Để ý thấy các thành phần tương ứng trong 2 nửa chỉ sai khác nhau 1. Tức là có thể tính một nửa dựa trên nửa còn lại:

s(0) = 2^k * [ s(1) - 1 - 2^2k - 2^4k - ... - 2^(k*(2^k-2)) ]
= 2^k * [ s(1) - (1 + (4^k) + (4^k)^2 + ... + (4^k)^(2^(k-1)-1) )]
= 2^k * [ s(1) - ((4^k)^(2^(k-1)) - 1) / (4^k - 1)]

Thuật toán sẽ là:

Tính riêng tổng cho những đoạn có cùng số bit. Có tất cả log n đoạn,
Với mỗi đoạn thì dùng phương pháp chia hai như trên. Đệ quy mất O( k)

sau_tim_thiep_hong · 23/9/22

Python:

class Solution:
    def concatenatedBinary(self, n: int) -> int:
        res=0
        M=1000000007
        for i in range(1,n+1,1):
            res = (res << (len(bin(i))-2) | i) % M
        return res

Aristides · 23/9/22

loz Leetcode không import sẵn cho cái Big integer class, làm mình húy hoáy coi sai syntax chỗ nào

Java:

import java.math.BigInteger;
class Solution {
    public final long mod = (long)(Math.pow(10,9) + 7);
    public int concatenatedBinary(int n) {
        if(n <= 0)
        {
            throw new IllegalArgumentException();
        }
        if(n == 1)
        {
            return 1;
        }
        long ans = 1;
        for(int i = 2; i <= n; i++)
        {
            long currentBitLength = (long)(BigInteger.valueOf(i).bitLength());
            ans = ((ans << currentBitLength) % mod + i) % mod;
        }
        return (int)ans;
    }
}

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

Senior Member

Member

Senior Member

Senior Member

Senior Member

Đã tốn tiền

Junior Member

Senior Member

Senior Member

Đã tốn tiền

Senior Member

Senior Member

Member

Member

Member

Đã tốn tiền

Senior Member

Đã tốn tiền

Member

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này