thảo luận [Học Tập] Topic thuật toán

Yêu em Thu Nga CN12 ptit · Nov 23, 2021

Mới sáng mở mắt ra đớp được bài hard dễ vl, phần palindrome đúng kiểu cứ ốp qhđ là ra, được mấy bài hard phần này rồi, dạng cứ na ná nhau

https://leetcode.com/problems/palindrome-partitioning-iv/

C++:

class Solution {
public:
    bool checkPartitioning(string s) {
        if(s.length()<3) return false;
        vector<vector<bool>>dp(s.length(),vector<bool>(s.length(),false));
        for(int i=0;i<s.length();i++) dp[i][i]=true;
        for(int i=s.length()-2;i>=0;i--){
            for(int j=i+1;j<s.length();j++){
                if((s[i]==s[j])&&(j-i<2||dp[i+1][j-1])) dp[i][j]=true;
            }
        }
        for(int i=1;i<s.length();i++){
            for(int j=i;j<s.length()-1;j++){
                if(dp[0][i-1]&&dp[i][j]&&dp[j+1][s.length()-1]) return true;
            }
        }
        return false;
    }
};

rose_code · Nov 25, 2021

zzchaolegionzz said:
Đây là bài toán tìm đường đi ngắn nhất nhưng không dừng lại khi tìm được đáp án mà tiếp tục chạy cho đến khi tìm được hết các đường đi. Có nhiều giải thuật có thể áp dụng nhưng nếu chịu khó thớt implement cái A* đi, bữa tôi đi phỏng vấn mà họ bắt code A* cho một cái mini game tương tự, kiểu nối các ô có màu giống nhau trong cái đồ thị trên, mà làm trong 30 phút thôi, kết quả là tạch.

thường thì làm ở mảng nào hay đụng đến mấy cái này vậy thím. Mình học bên lập trình web thì thấy chưa thấy đụng đến, toàn là thiết kế cơ sở dữ liệu, viết API rồi hiển thị dữ liệu,

zzchaolegionzz · Nov 25, 2021

rose_code said:
thường thì làm ở mảng nào hay đụng đến mấy cái này vậy thím. Mình học bên lập trình web thì thấy chưa thấy đụng đến, toàn là thiết kế cơ sở dữ liệu, viết API rồi hiển thị dữ liệu,

Làm game, data mining, AI. Còn code application thì chỉ học để đi phỏng vấn

**Doremon** · Nov 25, 2021

rose_code said:
thường thì làm ở mảng nào hay đụng đến mấy cái này vậy thím. Mình học bên lập trình web thì thấy chưa thấy đụng đến, toàn là thiết kế cơ sở dữ liệu, viết API rồi hiển thị dữ liệu,

Web/App có cái Map đó, làm ứng dụng bản đồ cần biết mấy cái đường đi ngắn nhất như A*, làm ứng dụng từ điển thì chắc cần biết qua cái Trie (ko biết nó có đc support sẵn ko), nói chung là lâu lâu cũng có nhưng ít

N.Khanh · Nov 26, 2021

Python:
Nhập vào một chuỗi, hãy tách toàn bộ số trong chuỗi và tính tổng của chuỗi đó (chuỗi chỉ có số nguyên dương)
VD: abc12b4c56d7

>> 12+4+56+7

Các bác cho em hỏi bài này giải theo hướng nào ạ. Em hiện chỉ làm được là thành từng số riêng lẻ cộng với nhau.

>> 1+2+4+5+6+7

Các bác giúp em theo cách ít dùng hàm nhất có thể với ạ tại em mới học nên chưa biết nhiều hàm ạ.

Kân team · Nov 26, 2021

N.Khanh said:
Python:
Nhập vào một chuỗi, hãy tách toàn bộ số trong chuỗi và tính tổng của chuỗi đó (chuỗi chỉ có số nguyên dương)
VD: abc12b4c56d7

Các bác cho em hỏi bài này giải theo hướng nào ạ. Em hiện chỉ làm được là thành từng số riêng lẻ cộng với nhau.

Các bác giúp em theo cách ít dùng hàm nhất có thể với ạ tại em mới học nên chưa biết nhiều hàm ạ.

print(sum(map(int, re.findall(r'[0-9]+', s))))

dagedage · Nov 27, 2021

N.Khanh said:
Python:
Nhập vào một chuỗi, hãy tách toàn bộ số trong chuỗi và tính tổng của chuỗi đó (chuỗi chỉ có số nguyên dương)
VD: abc12b4c56d7

Các bác cho em hỏi bài này giải theo hướng nào ạ. Em hiện chỉ làm được là thành từng số riêng lẻ cộng với nhau.

Các bác giúp em theo cách ít dùng hàm nhất có thể với ạ tại em mới học nên chưa biết nhiều hàm ạ.

stack

and 131 others · Nov 28, 2021

fen nào giúp e với ạ nếu đc e xin hậu tạ

Tuấn Mỏ · Nov 28, 2021

and 131 others said:
View attachment 892922
fen nào giúp e với ạ nếu đc e xin hậu tạ

Gọi F(n, m) là số lần chơi lớn nhất với n Mana m mantra.
công thức đệ quy F(n, m) = max(F(n + x1, m+y1), F(n + x2, m+y2), F(n+x3, m+y3))

and 131 others · Nov 28, 2021

Tuấn Mỏ said:
Gọi F(n, m) là số lần chơi lớn nhất với n Mana m mantra.
công thức đệ quy F(n, m) = max(F(n + x1, m+y1), F(n + x2, m+y2), F(n+x3, m+y3))

fen cho e hỏi thêm để tính tổng tất cả các số không phải lũy thừa của 2 từ 0 đến n thì mình làm thế nào?

Tuấn Mỏ · Nov 28, 2021

and 131 others said:
fen cho e hỏi thêm để tính tổng tất cả các số không phải lũy thừa của 2 từ 0 đến n thì mình làm thế nào?

đơn giản nhất là chạy vòng lặp 0-> n và check các số x & (x - 1) != 0

and 131 others · Nov 28, 2021

Tuấn Mỏ said:
Gọi F(n, m) là số lần chơi lớn nhất với n Mana m mantra.
công thức đệ quy F(n, m) = max(F(n + x1, m+y1), F(n + x2, m+y2), F(n+x3, m+y3))

#include <iostream>
#include <algorithm>

using namespace std;

int x1, x2, x3, y1, y2, y3;
int F(int n, int m){
return max(F(n + x1, m+y1), F(n + x2, m+y2), F(n+x3, m+y3));
}
int main()
{
int n, m;
cin >> n >>m;
cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
int t = F(n,m);
cout << t;
return 0;
}

e sai chỗ nào fen chỉ e với ạ

Tuấn Mỏ · Nov 28, 2021

and 131 others said:
e sai chỗ nào fen chỉ e với ạ

Nếu đang đứng ở vị trí x1, y1 thì ko thể nhảy lại vào x1,y1

and 131 others · Nov 28, 2021

Tuấn Mỏ said:
Nếu đang đứng ở vị trí x1, y1 thì ko thể nhảy lại vào x1,y1

fen sửa giúp e đc ko ạ e ko hiểu lắm

Tuấn Mỏ · Nov 28, 2021

and 131 others said:
fen sửa giúp e đc ko ạ e ko hiểu lắm

tự sửa đi fen

Yêu em Thu Nga CN12 ptit · Nov 28, 2021

https://leetcode.com/problems/wiggle-subsequence/
bài này có solution trong phần discuss khá hay.
Đây là cách ban đầu của em, discuss không thằng nào làm theo hướng này

dpt O(n^2), ý tưởng thì na ná LCS, thêm mảng để lưu hiệu của nó rồi dùng tích để check điều kiện đề bài

C++:

class Solution {
public:
  
int wiggleMaxLength(vector<int>& nums) {
        int n=nums.size();
        if(n<2) return 1;
        vector<int>dp(n,1);
        vector<int>mark(n);
        mark[1]=nums[1]-nums[0];
        mark[0]=0;
        int res=1;
        for(int i=1;i<nums.size();i++){
            for(int j=i-1;j>=0;j--){
                int val=nums[i]-nums[j];
                if(val*mark[j]<0||(val*mark[j]<=0&&val!=0)){
                    if(dp[j]+1>dp[i]){
                        mark[i]=val;
                        dp[i]=dp[j]+1;
                    }
                }
            }
            res=max(res,dp[i]);
        }
        return res;
    }
};

sau khi tối ưu:
Y hệt như trên, nhưng dùng thằng i-1 để tính toán luôn nên giảm đpt về O(n)

C++:

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n=nums.size();
        if(n<2) return 1;
        vector<int>dp(n,1);
        vector<int>mark(n);
        mark[0]=0;
        int res=1;
        for(int i=1;i<nums.size();i++){
            int val=nums[i]-nums[i-1];
            if(val*mark[i-1]<0||(val*mark[i-1]<=0&&val!=0)){
                if(dp[i-1]+1>dp[i]){
                    mark[i]=val;
                    dp[i]=dp[i-1]+1;
                }
            }
            else{
                dp[i]=dp[i-1];
                mark[i]=val+mark[i-1];
            }
            res=max(res,dp[i]);
        }
        return res;
    }
};

thấy solution của mình có ý tưởng đỉnh nhất cmnr nhưng đhs faster được hơn có 6x% nên vào check discuss, đây là code của họ, cùng là O(n) nhưng đơn giản vl

C++:

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n=nums.size();
        if(n<2) return 1;
        int up=1,down=1;
        for(int i=1;i<n;i++){
            if(nums[i]>nums[i-1]) up=down+1;
            else if(nums[i]<nums[i-1]) down=up+1;
        }
        return max(down,up);
    }
};

N.Khanh · Nov 29, 2021

Python:

Nhập vào 2 tọa độ là 2 đỉnh của một hình chữ nhật

Sau đó

Nhập vào tọa độ tâm đường tròn và bán kính R

Hãy vẽ hình hình chữ nhật và đường tròn trên

Viết hàm kiểm tra xem đường tròn trên và hình chữ nhật cắt nhau tại bao nhiêu điểm
---------------------------------------------------------------------
Các bác cho em hỏi có công thức nào để tính số lần giao nhau của hình tròn và hình chữ nhật không ạ. Em có tìm kiếm trên google cả bằng tiếng anh và tiếng việt mà mơ hồ quá ạ.
Kỹ năng tìm kiếm của em còn óc chó mong các bác thông cảm

bmskyline · Nov 29, 2021

N.Khanh said:
Python:

Nhập vào 2 tọa độ là 2 đỉnh của một hình chữ nhật

Sau đó

Nhập vào tọa độ tâm đường tròn và bán kính R

Hãy vẽ hình hình chữ nhật và đường tròn trên

Viết hàm kiểm tra xem đường tròn trên và hình chữ nhật cắt nhau tại bao nhiêu điểm
---------------------------------------------------------------------
Các bác cho em hỏi có công thức nào để tính số lần giao nhau của hình tròn và hình chữ nhật không ạ. Em có tìm kiếm trên google cả bằng tiếng anh và tiếng việt mà mơ hồ quá ạ.
Kỹ năng tìm kiếm của em còn óc chó mong các bác thông cảm

Mình nghĩ bài này bạn tính từng cạnh của hcn thôi , bạn search circle line intersection là ra công thức số điểm cắt nhau

thuyduong2007 · Nov 29, 2021

N.Khanh said:
Python:

Nhập vào 2 tọa độ là 2 đỉnh của một hình chữ nhật

Sau đó

Nhập vào tọa độ tâm đường tròn và bán kính R

Hãy vẽ hình hình chữ nhật và đường tròn trên

Viết hàm kiểm tra xem đường tròn trên và hình chữ nhật cắt nhau tại bao nhiêu điểm
---------------------------------------------------------------------
Các bác cho em hỏi có công thức nào để tính số lần giao nhau của hình tròn và hình chữ nhật không ạ. Em có tìm kiếm trên google cả bằng tiếng anh và tiếng việt mà mơ hồ quá ạ.
Kỹ năng tìm kiếm của em còn óc chó mong các bác thông cảm

Bạn quy về bài toán tìm điểm giao của đường tròn với 4 đường thẳng được tạo ra bởi 4 cạnh. Nếu có điểm giao thì kiểm tra tiếp xem điểm giao đó có nằm trên cạnh của hình chữ nhật không. 2 bài này đều có công thức hết rồi.

KimSoHyunGoddness · Dec 1, 2021

Giờ có thời gian rảnh. Lại quay về cày leetcode. Hehehe. Lại gặp mấy bác rồi

thảo luận [Học Tập] Topic thuật toán

Senior Member

Senior Member

Member

Senior Member

Junior Member

Senior Member

Senior Member

Junior Member

Senior Member

Junior Member

Senior Member

Junior Member

Senior Member

Junior Member

Senior Member

Senior Member

Junior Member

Junior Member

Member

Member

Similar threads

Share this page