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.
Cơm lưu vào cái list kia lại bị trường hợp là link nền tảng khác không được các bác ơi, có file tổng hợp nào chung không nhỉ các bác.
 
Ko medium lắm :|
C#: 
public class Solution
{
    public int[] XorQueries(int[] arr, int[][] queries)
    {
        int[] prefix = new int[arr.Length];
        prefix[0] = arr[0];
        for (int i = 1; i < arr.Length; i++)
        {
            prefix[i] = prefix[i - 1] ^ arr[i];
        }

        int[] result = new int[queries.Length];
        for (int i = 0; i < queries.Length; i++)
        {
            int[] query = queries[i];
            if (query[0] == 0)
            {
                result[i] = prefix[query[1]];
                continue;
            }
            result[i] = prefix[query[1]] ^ prefix[query[0] - 1];
        }

        return result;
    }
}
 
Cho cơm khô mới không dễ nhai, nhưng mà nó hay
FY7e6U1.gif


via theNEXTvoz for iPhone
 
garanphomai đã nói:
Cơm khê Additive Number :(
Nhấp để mở rộng...
làm thêm cái follow up nữa cơm này ngậm từ trưa tới h, hận python, js có sẵn big int
g9qSbBf.png
.

Java: 
import java.math.BigInteger;
class Solution {
    public boolean isAdditiveNumber(String num) {
        BigInteger bNum = new BigInteger(num);
        for(int i = 1 ;i<=num.length()/2;i++){
            BigInteger first = new BigInteger(num.substring(0,i));
            if(first.toString().length()!=i) return false;
            if(backtrack(num, i,first)) return true;
        }
        return false;
    }
    public boolean backtrack(String num, int start, BigInteger firstNum){
        for(int i = start+1;i<=num.length()-start;i++){
            BigInteger tryNum = new BigInteger(num.substring(start,i));
            if(tryNum.toString().length()!=i-start) return false;
            if(isTrue(num.substring(i), firstNum, tryNum)) return true;
        }
        return false;
    }
    public boolean isTrue(String remain, BigInteger preNum,BigInteger nextOne){
        if(remain.length()==0) return true;
        BigInteger sum = preNum.add(nextOne);
        int sumLength = sum.toString().length();
        if(sumLength>remain.length()) return false;
        if(!remain.substring(0,sumLength).equals(sum.toString())) return false;
        return isTrue(remain.substring(sumLength), nextOne, sum);
    }
}
 
MasonMaoSuVuong đã nói:
làm thêm cái follow up nữa cơm này ngậm từ trưa tới h, hận python, js có sẵn big int
g9qSbBf.png
.

Java: 
import java.math.BigInteger;
class Solution {
    public boolean isAdditiveNumber(String num) {
        BigInteger bNum = new BigInteger(num);
        for(int i = 1 ;i<=num.length()/2;i++){
            BigInteger first = new BigInteger(num.substring(0,i));
            if(first.toString().length()!=i) return false;
            if(backtrack(num, i,first)) return true;
        }
        return false;
    }
    public boolean backtrack(String num, int start, BigInteger firstNum){
        for(int i = start+1;i<=num.length()-start;i++){
            BigInteger tryNum = new BigInteger(num.substring(start,i));
            if(tryNum.toString().length()!=i-start) return false;
            if(isTrue(num.substring(i), firstNum, tryNum)) return true;
        }
        return false;
    }
    public boolean isTrue(String remain, BigInteger preNum,BigInteger nextOne){
        if(remain.length()==0) return true;
        BigInteger sum = preNum.add(nextOne);
        int sumLength = sum.toString().length();
        if(sumLength>remain.length()) return false;
        if(!remain.substring(0,sumLength).equals(sum.toString())) return false;
        return isTrue(remain.substring(sumLength), nextOne, sum);
    }
}
Nhấp để mở rộng...
Dùng string luôn ko phải concern about overflow issue nữa.
Bài hard hận đời quá
osCpCsi.png
Mới ngày đầu beta test mà đã vầy rồi @freedom.9
 
freedom.9 đã nói:
Cuối tuần mà mai fen phải upsolve mới có dopamine
BdgiW7R.gif


via theNEXTvoz for iPhone
Nhấp để mở rộng...
osCpCsi.png
Hôm qua cuối cùng cũng hiểu Tarjan mà trễ quá ko thức làm được, hôm nay ưu tiên cơm thêm nên chưa kịp làm nốt
Java: 
class Solution {
    int ans;
    int k;
    public int distributeCookies(int[] cookies, int k) {
        this.k = k;
        ans = Integer.MAX_VALUE;
        backtrack(0, new int[k], cookies);
        return ans;
    }

    private void backtrack(int idx, int[] distributions, int[] cookies) {
        int n = cookies.length;

        if (idx == n) {
            int max = 0;
            for (int c: distributions) {
                max = Math.max(c, max);
            }

            ans = Math.min(ans, max);
            return;
        }

        for (int i = 0; i < k; i++) {
            distributions[i] += cookies[idx];
            backtrack(idx + 1, distributions, cookies);
            distributions[i] -= cookies[idx];
        }
    }
}

Java: 
class Solution {
    public boolean isAdditiveNumber(String num) {
        int n = num.length();

        for (int i = 1; i <= n/2; i++) {
            if (num.charAt(0) == '0' && i > 1) return false;
            for (int j = i + 1; j < n; j++) {
                if (num.charAt(i) == '0' && j - i > 1) break;
                String num1 = num.substring(0, i);
                String num2 = num.substring(i, j);
                String rest = num.substring(j, n);
                if (isValid(num1, num2, rest)) return true;
            }
        }

        return false;
    }

    private boolean isValid(String num1, String num2, String rest) {
        while (!rest.isEmpty()) {
            String sum = add(num1, num2);

            if (!rest.startsWith(sum)) return false;

            num1 = num2;
            num2 = sum;
            rest = rest.substring(sum.length());
        }

        return true;
    }

    private String add(String num1, String num2) {
        int i = num1.length() - 1, j = num2.length() - 1, carry = 0;
        StringBuilder sb = new StringBuilder();

        while (i >= 0 || j >= 0 || carry > 0) {
            int x = i >= 0 ? num1.charAt(i--) - '0' : 0;
            int y = j >= 0 ? num2.charAt(j--) - '0' : 0;
            int sum = x + y + carry;
            sb.append(sum % 10);
            carry = sum / 10;
        }

        return sb.reverse().toString();
    }
}

Java: 
class Solution {
    int n, target;
    List<String> ans;
    String num;
    public List<String> addOperators(String num, int target) {
        this.target = target;
        this.n = num.length();
        this.ans = new ArrayList<>();
        this.num = num;

        backtrack(0, 0L, 0L, "");

        return ans;
    }

    private void backtrack(int idx, long curVal, long lastVal, String expression) {
        if (idx == n) {
            if (curVal == target) {
                ans.add(expression);
            }
            return;
        }

        for (int i = idx; i < n; i++) {

            if (i > idx && num.charAt(idx) == '0') break;

            String curStr = num.substring(idx, i + 1);
            long curNum = Long.parseLong(curStr);

            if (idx == 0) {
                backtrack(i + 1, curNum, curNum, curStr);
            } else {
                backtrack(i + 1, curVal + curNum, curNum, expression + "+" + curStr);
                backtrack(i + 1, curVal - curNum, -curNum, expression + "-" + curStr);
                backtrack(i + 1, curVal - lastVal + lastVal * curNum, lastVal * curNum, expression + "*" + curStr);
            }
        }
    }
}
 
Cố Trường Ca đã nói:
osCpCsi.png
Hôm qua cuối cùng cũng hiểu Tarjan mà trễ quá ko thức làm được, hôm nay ưu tiên cơm thêm nên chưa kịp làm nốt
Java: 
class Solution {
    int ans;
    int k;
    public int distributeCookies(int[] cookies, int k) {
        this.k = k;
        ans = Integer.MAX_VALUE;
        backtrack(0, new int[k], cookies);
        return ans;
    }

    private void backtrack(int idx, int[] distributions, int[] cookies) {
        int n = cookies.length;

        if (idx == n) {
            int max = 0;
            for (int c: distributions) {
                max = Math.max(c, max);
            }

            ans = Math.min(ans, max);
            return;
        }

        for (int i = 0; i < k; i++) {
            distributions[i] += cookies[idx];
            backtrack(idx + 1, distributions, cookies);
            distributions[i] -= cookies[idx];
        }
    }
}

Java: 
class Solution {
    public boolean isAdditiveNumber(String num) {
        int n = num.length();

        for (int i = 1; i <= n/2; i++) {
            if (num.charAt(0) == '0' && i > 1) return false;
            for (int j = i + 1; j < n; j++) {
                if (num.charAt(i) == '0' && j - i > 1) break;
                String num1 = num.substring(0, i);
                String num2 = num.substring(i, j);
                String rest = num.substring(j, n);
                if (isValid(num1, num2, rest)) return true;
            }
        }

        return false;
    }

    private boolean isValid(String num1, String num2, String rest) {
        while (!rest.isEmpty()) {
            String sum = add(num1, num2);

            if (!rest.startsWith(sum)) return false;

            num1 = num2;
            num2 = sum;
            rest = rest.substring(sum.length());
        }

        return true;
    }

    private String add(String num1, String num2) {
        int i = num1.length() - 1, j = num2.length() - 1, carry = 0;
        StringBuilder sb = new StringBuilder();

        while (i >= 0 || j >= 0 || carry > 0) {
            int x = i >= 0 ? num1.charAt(i--) - '0' : 0;
            int y = j >= 0 ? num2.charAt(j--) - '0' : 0;
            int sum = x + y + carry;
            sb.append(sum % 10);
            carry = sum / 10;
        }

        return sb.reverse().toString();
    }
}

Java: 
class Solution {
    int n, target;
    List<String> ans;
    String num;
    public List<String> addOperators(String num, int target) {
        this.target = target;
        this.n = num.length();
        this.ans = new ArrayList<>();
        this.num = num;

        backtrack(0, 0L, 0L, "");

        return ans;
    }

    private void backtrack(int idx, long curVal, long lastVal, String expression) {
        if (idx == n) {
            if (curVal == target) {
                ans.add(expression);
            }
            return;
        }

        for (int i = idx; i < n; i++) {

            if (i > idx && num.charAt(idx) == '0') break;

            String curStr = num.substring(idx, i + 1);
            long curNum = Long.parseLong(curStr);

            if (idx == 0) {
                backtrack(i + 1, curNum, curNum, curStr);
            } else {
                backtrack(i + 1, curVal + curNum, curNum, expression + "+" + curStr);
                backtrack(i + 1, curVal - curNum, -curNum, expression + "-" + curStr);
                backtrack(i + 1, curVal - lastVal + lastVal * curNum, lastVal * curNum, expression + "*" + curStr);
            }
        }
    }
}
Nhấp để mở rộng...
Tuyệt vời, mai thi thố rồi kiểu này rank 3k đổ xuống
zFNuZTA.gif


via theNEXTvoz for iPhone
 
MasonMaoSuVuong đã nói:
làm thêm cái follow up nữa cơm này ngậm từ trưa tới h, hận python, js có sẵn big int
g9qSbBf.png
.

Java: 
import java.math.BigInteger;
class Solution {
    public boolean isAdditiveNumber(String num) {
        BigInteger bNum = new BigInteger(num);
        for(int i = 1 ;i<=num.length()/2;i++){
            BigInteger first = new BigInteger(num.substring(0,i));
            if(first.toString().length()!=i) return false;
            if(backtrack(num, i,first)) return true;
        }
        return false;
    }
    public boolean backtrack(String num, int start, BigInteger firstNum){
        for(int i = start+1;i<=num.length()-start;i++){
            BigInteger tryNum = new BigInteger(num.substring(start,i));
            if(tryNum.toString().length()!=i-start) return false;
            if(isTrue(num.substring(i), firstNum, tryNum)) return true;
        }
        return false;
    }
    public boolean isTrue(String remain, BigInteger preNum,BigInteger nextOne){
        if(remain.length()==0) return true;
        BigInteger sum = preNum.add(nextOne);
        int sumLength = sum.toString().length();
        if(sumLength>remain.length()) return false;
        if(!remain.substring(0,sumLength).equals(sum.toString())) return false;
        return isTrue(remain.substring(sumLength), nextOne, sum);
    }
}
Nhấp để mở rộng...
E mới optimize lại còn 1ms, mà code hơi ẹ. Hình như bài này có pattern phải k, thấy mấy thím code struct giống giống nhau.

Java: 
class Solution {
    StringBuilder s;
    String sub;
    long curNum;
    int size;
    List<Long> list = new ArrayList<>();
    public boolean isAdditiveNumber(String num) {
        if (num.length() <= 2) return false;
        s = new StringBuilder(num);
        return backtrack(0, 1);
    }
    boolean backtrack(int curIndex, int num) {
        if (curIndex >= s.length()) {
            if (list.size() < 3)
                return false;
            return true;
        }
        if (curIndex + num > s.length()) {
            return false;
        }
        sub = s.substring(curIndex, curIndex+num).toString();
        // can't be true if number length is half of s
        if (sub.length() > s.length() / 2 + 1) {
            return false;
        }
        curNum = Long.parseLong(sub);
        size = list.size();
        
        if (size < 2 || list.get(size - 1) + list.get(size - 2) == curNum) {
            list.add(curNum);
            if (backtrack(curIndex + num, 1)) {
                return true;
            }
            list.removeLast();
        }
        // handle zeros
        if (s.charAt(curIndex) == '0') {
            return false;
        }
        return backtrack(curIndex, num + 1);
    }
}
 
Sửa lần cuối:
garanphomai đã nói:
E mới optimize lại còn 1ms, mà code hơi ẹ. Hình như bài này có pattern phải k, thấy mấy thím code struct giống giống nhau.

Java: 
class Solution {
    StringBuilder s;
    String sub;
    long curNum;
    int size;
    List<Long> list = new ArrayList<>();
    public boolean isAdditiveNumber(String num) {
        if (num.length() <= 2) return false;
        s = new StringBuilder(num);
        return backtrack(0, 1);
    }
    boolean backtrack(int curIndex, int num) {
        if (curIndex >= s.length()) {
            if (list.size() < 3)
                return false;
            return true;
        }
        if (curIndex + num > s.length()) {
            return false;
        }
        sub = s.substring(curIndex, curIndex+num).toString();
        // can't be true if number length is half of s
        if (sub.length() > s.length() / 2 + 1) {
            return false;
        }
        curNum = Long.parseLong(sub);
        size = list.size();
      
        if (size < 2 || list.get(size - 1) + list.get(size - 2) == curNum) {
            list.add(curNum);
            if (backtrack(curIndex + num, 1)) {
                return true;
            }
            list.removeLast();
        }
        // handle zeros
        if (s.charAt(curIndex) == '0') {
            return false;
        }
        return backtrack(curIndex, num + 1);
    }
}
Nhấp để mở rộng...
ubyRVAQ.png
e đọc tag thấy ghi backtracking nên đặt tên hàm là backtrack đấy chứ cũng ko biết nó là pattern j đâu bác.
sự thặc nổ não phải ko
YLJ4h33.png
 
MasonMaoSuVuong đã nói:
ubyRVAQ.png
e đọc tag thấy ghi backtracking nên đặt tên hàm là backtrack đấy chứ cũng ko biết nó là pattern j đâu bác.
sự thặc nổ não phải ko
YLJ4h33.png
Nhấp để mở rộng...
mấy bài backtrack này e thấy bản chất nó cũng chỉ là BF nên cũng ko có nhiều pattern gì, khó là phải biết điểm exist, base case của hàm ở đâu, và input đầu vào như nào cho hiệu quả, thêm 1 vài cái nó cần memoi để giảm computation ...
 
Cố Trường Ca đã nói:
osCpCsi.png
Hôm qua cuối cùng cũng hiểu Tarjan mà trễ quá ko thức làm được, hôm nay ưu tiên cơm thêm nên chưa kịp làm nốt
Java: 
class Solution {
    int ans;
    int k;
    public int distributeCookies(int[] cookies, int k) {
        this.k = k;
        ans = Integer.MAX_VALUE;
        backtrack(0, new int[k], cookies);
        return ans;
    }

    private void backtrack(int idx, int[] distributions, int[] cookies) {
        int n = cookies.length;

        if (idx == n) {
            int max = 0;
            for (int c: distributions) {
                max = Math.max(c, max);
            }

            ans = Math.min(ans, max);
            return;
        }

        for (int i = 0; i < k; i++) {
            distributions[i] += cookies[idx];
            backtrack(idx + 1, distributions, cookies);
            distributions[i] -= cookies[idx];
        }
    }
}

Java: 
class Solution {
    public boolean isAdditiveNumber(String num) {
        int n = num.length();

        for (int i = 1; i <= n/2; i++) {
            if (num.charAt(0) == '0' && i > 1) return false;
            for (int j = i + 1; j < n; j++) {
                if (num.charAt(i) == '0' && j - i > 1) break;
                String num1 = num.substring(0, i);
                String num2 = num.substring(i, j);
                String rest = num.substring(j, n);
                if (isValid(num1, num2, rest)) return true;
            }
        }

        return false;
    }

    private boolean isValid(String num1, String num2, String rest) {
        while (!rest.isEmpty()) {
            String sum = add(num1, num2);

            if (!rest.startsWith(sum)) return false;

            num1 = num2;
            num2 = sum;
            rest = rest.substring(sum.length());
        }

        return true;
    }

    private String add(String num1, String num2) {
        int i = num1.length() - 1, j = num2.length() - 1, carry = 0;
        StringBuilder sb = new StringBuilder();

        while (i >= 0 || j >= 0 || carry > 0) {
            int x = i >= 0 ? num1.charAt(i--) - '0' : 0;
            int y = j >= 0 ? num2.charAt(j--) - '0' : 0;
            int sum = x + y + carry;
            sb.append(sum % 10);
            carry = sum / 10;
        }

        return sb.reverse().toString();
    }
}

Java: 
class Solution {
    int n, target;
    List<String> ans;
    String num;
    public List<String> addOperators(String num, int target) {
        this.target = target;
        this.n = num.length();
        this.ans = new ArrayList<>();
        this.num = num;

        backtrack(0, 0L, 0L, "");

        return ans;
    }

    private void backtrack(int idx, long curVal, long lastVal, String expression) {
        if (idx == n) {
            if (curVal == target) {
                ans.add(expression);
            }
            return;
        }

        for (int i = idx; i < n; i++) {

            if (i > idx && num.charAt(idx) == '0') break;

            String curStr = num.substring(idx, i + 1);
            long curNum = Long.parseLong(curStr);

            if (idx == 0) {
                backtrack(i + 1, curNum, curNum, curStr);
            } else {
                backtrack(i + 1, curVal + curNum, curNum, expression + "+" + curStr);
                backtrack(i + 1, curVal - curNum, -curNum, expression + "-" + curStr);
                backtrack(i + 1, curVal - lastVal + lastVal * curNum, lastVal * curNum, expression + "*" + curStr);
            }
        }
    }
}
Nhấp để mở rộng...
Bài hard thực ra làm 1 pass thế này hơi khó, mình có cách tiếp cận là generate ra hết các possible string. Time complexity sẽ là 2^10*10*3, rồi dùng 1 pass tiếp theo để khử phép *, 1 pass nữa để khử phép +- bằng stack.
Time complexity sẽ là 2^10*10*10*6 chắc chắn vẫn sẽ pass

via theNEXTvoz for iPhone
 
freedom.9 đã nói:
Bài hard thực ra làm 1 pass thế này hơi khó, mình có cách tiếp cận là generate ra hết các possible string. Time complexity sẽ là 2^10*10, rồi dùng 1 pass tiếp theo để khử phép *, 1 pass nữa để khử phép +- bằng stack.
Time complexity sẽ là 2^10*10*10*2 chắc chắn vẫn sẽ pass

via theNEXTvoz for iPhone
Nhấp để mở rộng...
cái toán phụ đó hình như cũng tầm medium cứng đó
meoqQpA.png
Cũng trầy da tróc vẩy chứ k đơn giản hơn trư làm bao nhiêu
Với cả trong trí nhớ của trư bài đó cũng cơ bắp lắm
KgmQHtR.png
 
MasonMaoSuVuong đã nói:
ubyRVAQ.png
e đọc tag thấy ghi backtracking nên đặt tên hàm là backtrack đấy chứ cũng ko biết nó là pattern j đâu bác.
sự thặc nổ não phải ko
YLJ4h33.png
Nhấp để mở rộng...
:choler::beat_brick:
noobdev đã nói:
mấy bài backtrack này e thấy bản chất nó cũng chỉ là BF nên cũng ko có nhiều pattern gì, khó là phải biết điểm exist, base case của hàm ở đâu, và input đầu vào như nào cho hiệu quả, thêm 1 vài cái nó cần memoi để giảm computation ...
Nhấp để mở rộng...
:love:
 
MasonMaoSuVuong đã nói:
đoán 6ms là xài hashmap còn 2ms là xài array biểu diễn map đúng ko :big_smile:
Nhấp để mở rộng...

Cố Trường Ca đã nói:
Bác mới nên không biết chứ chỉ nên khen @MasonMaoSuVuong thôi chứ bác ấy giấu nghề kinh lắm ko trả lời theo lẽ thường đâu. Gặp là khen nhiều vô, bác ấy vui bác ấy share cho mấy kinh nghiệm cao siêu mà học hỏi.
Nhấp để mở rộng...
Đọc sol của mấy thím cũng vỡ ra nhiều :p. Còn thím @MasonMaoSuVuong thì cao thủ rồi, liếc runtime phát là biết sol của mình optimize chỗ nào =((.
Ráng đu cơm thêm theo mấy thím lụm 2k rating :hungry:
 
Trạng thái
Không mở để trả lời thêm.
AD · 970×250

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
2K
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
894
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.214.659

Chia sẻ trang này

Quay lại
Lên đầu trang