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

rose_code · 25/11/21

zzchaolegionzz đã nói:
Đâ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 · 25/11/21

rose_code đã nói:
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** · 25/11/21

rose_code đã nói:
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 · 26/11/21

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 · 26/11/21

N.Khanh đã nói:
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 · 27/11/21

N.Khanh đã nói:
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 · 28/11/21

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

Tuấn Mỏ · 28/11/21

and 131 others đã nói:
Xem tệp đính kèm 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 · 28/11/21

Tuấn Mỏ đã nói:
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ỏ · 28/11/21

and 131 others đã nói:
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 · 28/11/21

Tuấn Mỏ đã nói:
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ỏ · 28/11/21

and 131 others đã nói:
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 · 28/11/21

Tuấn Mỏ đã nói:
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ỏ · 28/11/21

and 131 others đã nói:
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 · 28/11/21

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 · 29/11/21

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 · 29/11/21

N.Khanh đã nói:
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 · 29/11/21

N.Khanh đã nói:
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 · 1/12/21

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

thaygiao3 · 7/12/21

cảm giác đầu tiên khi làm đc 1 bài hard trên leetcode khá fun, https://leetcode.com/problems/frog-jump/, bài hard này chắc cx dễ thôi nhưng đối vs em thế là vui r, khoe tí thôi, đây là code của em

C++:

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

Member

Senior Member

Senior Member

Junior Member

Member

Senior Member

Junior Member

Senior Member

Junior Member

Senior Member

Junior Member

Senior Member

Junior Member

Senior Member

Senior Member

Junior Member

Senior Member

Member

Member

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này