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

zzchaolegionzz

Senior Member
https://leetcode.com/problems/jump-game-ii/

ai giải thích bài này quy hoạch động với
Giải thích bằng cái ví dụ của nó nhé
Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.
  • Bạn bắt đầu nhảy ở vị trí đầu tiên trong array, có giá trị là 2, nghĩa là bạn được chọn 2 ô tiếp theo để nhảy tới, bạn có quyền nhảy vào một trong hai ô phía trước, không bắt buộc là ô nào cả.
  • Hai ô tiếp theo có giá trị lần lượt là 3, và 1. Bạn chỉ được chọn một giá trị để làm bước nhảy tiếp theo.
    • Nếu chọn 3: bạn được phép nhảy tới một trong ba ô kế tiếp có giá trị là 1, 1, 4
    • Nếu chọn 1: bạn được quyền nhảy tới một ô kế tiếp là có giá trị là 1
  • Dễ thấy nếu chọn giá trị 3, bạn nhảy được tới 3 ô kế tiếp, tới hết array luôn => giá trị cần chọn là 3, còn nếu chọn 1, bạn phải nhảy thêm một vài lần nữa mới tới hết array. => bạn chỉ nhảy 2 lần, từ vị trí số 0 (chứa 2), tới vị trí số 1 (chứa 3) => output = 2

Code của mình đây
C#:
public class Solution {
    public int Jump(int[] nums) {
     
      var count = 0;
      var farthest = 0;
      var jumpEnd = 0;
       
      for(var i = 0; i < nums.Length - 1; i++){
        farthest = Math.Max(farthest,  i + nums[i]);
        if(i == jumpEnd){
          jumpEnd = farthest;
          count++;
        }
      }
     
      return count;
    }
}
 
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
UO1H3Fn.gif

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

Junior Member
Đâ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. :feel_good:
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

Senior Member
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 :p
 

**Doremon**

Senior Member
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

Junior Member
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

Senior Member
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))))

GYA3x5J.gif
 

dagedage

Senior Member
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

Junior Member
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?
 

and 131 others

Junior Member
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 ạ
 
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
BdgiW7R.png

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)
1BW9Wj4.png

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
BdgiW7R.png

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

Junior Member
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

Senior Member
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
 
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.
 
Top