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

  • Người tạo chủ đề Người tạo chủ đề unknowpc90
  • Ngày bắt đầu Ngày bắt đầu
Mình đoán là bạn chưa search đúng keyword hoặc có thể đọc lời giải không hiểu nên mình code hộ bạn vậy
:big_smile:

JavaScript:
function median(a, b, c, d, e) {
  if (a >= b) { /* 1st comparision */
    a = a + b; b = a - b; a = a - b; // swap
  }
  if (c >= d) { /* 2nd comparision */
    c = c + d; d = c - d; c = c - d;
  }
  // now we have: a < b, c < d
  if (b >= d) { /* 3rd comparision */
    a = a + c; c = a - c; a = a - c;
    b = b + d; d = b - d; b = b - d;
  }
  // now d > (a and b and c) => d is not median
  if (c >= e) { /* 4th comparision */
    c = c + e; e = c - e; c = c - e;
  }
  // now we have: a < b, c < e
  if (b > e) { /* 5th comparision */
    if (a > e) return a; else return e; /* 6th comparision */
  } else { // => e is not median
    if (b > c) return b; else return c; /* 6th comparision */
  }
}

Còn đây là link lời giải https://cs.stackexchange.com/a/45
sao cái so sánh b>c ở dòng cuối vận là so sánh lần thứ 6 vậy ạ, e tưởng nó phải là so sánh lần thứ 7 rồi chứ :(
 
Làm bài dễ dễ lấy động lực học tập

1634204585366.png


1634204612039.png
 
https://leetcode.com/problems/target-sum/
Ai có hướng giải bài Target Sum không ạ? Pick 1 bài trong list này mà không giải được
làm rồi này, tất nhiên là lên youtube nghe ý tưởng của mấy anh Ấn. Chia dãy làm 2 phần s1,s2. s1 gồm các phần tử mang dấu +, s2 mang dấu -. Có s1+s2=sum; s1-s2=target. Suy ra s1=(sum+target)/2
quy về bài toán qhđ điển hình tìm tất cả dãy con có tổng bằng s1
nhớ mang máng vậy
 
https://leetcode.com/problems/target-sum/
Ai có hướng giải bài Target Sum không ạ? Pick 1 bài trong list này mà không giải được
Bài này dùng dynamic programing nhé. Mặc dù đang nhậu xỉn cũng giải trong vòng 1 nốt nhạc nhé. Tuy nhiên solution chưa thực sự tối ưu.

Python:
class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        self.nums = nums
        return self.findTargetSumWaysRecursive(target)
   
    @cache
    def findTargetSumWaysRecursive(self, target, pos = 0):
        if pos >= len(self.nums):
            return 1 if target == 0 else 0
        return self.findTargetSumWaysRecursive(target - self.nums[pos], pos+1) + self.findTargetSumWaysRecursive(target + self.nums[pos], pos+1)
 
Lấy hiệu 2 mảng số mũ là như thế nào thím nhỉ, em nghĩ mãi không ra
Là phân tích 2 số ra thành thừa số nguyên tố đó thím.

Ví dụ 5! = 2^3 * 3 * 5 thì có mảng số mũ là [3, 1, 1]. 6 = 2 * 3 là [1, 1, 0]. Hiệu 2 mảng số mũ là [2, 0, 1] (tương ứng với 5!/6 = 2^2 * 5)
 
Xem tệp đính kèm 823133
Các thím có ý tưởng không ạ? Em đọc còn không hiểu đề

bài này quen lắm, kiểu hành trình có khả năng bỏ có khả năng lấy như này hay dùng priority queue. Không thì sử dụng hàm đệ quy chọn giữa nghỉ và chạy tiếp (backtracking)

Bessie với cow này là usaco rồi. Bài này quy hoạch động O(MxN - 10k x 5k thì vẫn ok). Gọi f[j] [j] là quãng đường mà bò bessie có thể chạy tối đa ở phút thứ i và thể lực là j. Theo đề bài sẽ có 2 lữa chọn.

Giả sử đang có f[j] [j] = quãng đường tối đa mà bò chạy được phút thứ i và có thể lục là j
*) Nếu j > 0 thì có thể chạy được thêm 1 phút (theo đề bài và tốn 1 thể lực)
-> f[i + 1][j - 1] = f[j] [j] + D[i + 1] (D[i + 1] là quãng đường chạy ở phút thứ i + 1
*) Nếu nghỉ thì phút i + 1 sẽ hồi được 1 thể lực
-> f[i + 1][j + 1] = f[j];
 
Bessie với cow này là usaco rồi. Bài này quy hoạch động O(MxN - 10k x 5k thì vẫn ok). Gọi f[j] [j] là quãng đường mà bò bessie có thể chạy tối đa ở phút thứ i và thể lực là j. Theo đề bài sẽ có 2 lữa chọn.

Giả sử đang có f[j] [j] = quãng đường tối đa mà bò chạy được phút thứ i và có thể lục là j
*) Nếu j > 0 thì có thể chạy được thêm 1 phút (theo đề bài và tốn 1 thể lực)
-> f[i + 1][j - 1] = f[j] [j] + D[i + 1] (D[i + 1] là quãng đường chạy ở phút thứ i + 1
*) Nếu nghỉ thì phút i + 1 sẽ hồi được 1 thể lực
-> f[i + 1][j + 1] = f[j];
hay quá fen, tui mới học cái quy hoạch động này mà không nghĩ đến, quê quá
 

Thống kê chủ đề

Ngày tạo
unknowpc90,
Người trả lời cuối
Spaghetti Code,
Trả lời
1.460
Lượt xem
154.039
Quay lại
Lên đầu trang