121. Thời gian tốt nhất để mua và bán cổ phiếu
Giải thích và mã giả:
Để giải quyết vấn đề này, trước tiên, chúng tôi sử dụng cách tiếp cận thuật toán vũ phu. Chúng tôi sẽ thử tất cả các lợi nhuận có thể mà chúng tôi có thể nhận được từ các giá trị đã cho và chọn giá trị cao nhất. Để tính toán lợi nhuận tối đa bạn có thể đạt được từ mỗi giao dịch.Brute force algorithm approach. we will try all possible profits we can get from the given values and pick the highest one. To calculate the maximum profit you can achieve from each transaction.
- Tạo một biến maxProfit để lưu trữ lợi nhuận tối đa
- Vòng lặp qua mảng hai lần để nhận giá mua và giá bán
- Tính lợi nhuận bằng cách trừ buyPrice từ sellPrice
- Nếu giá trị lợi nhuận lớn hơn giá trị MaxProfit, hãy đặt MaxProfit thành bằng lợi nhuận
- Trả lại maxProfit
Ở đây, một sự cố về cách mã tính toán và trả lại lợi nhuận tối đa bằng hai vòng lặp;
Phân tích độ phức tạp
- Độ phức tạp về thời gian: O (N²) trong đó n là độ dài của mảng giá
- Độ phức tạp không gian: O (1). Chỉ có hai biến được tạo ra. MaxProfit và lợi nhuận
Một cách tiếp cận tốt hơn sử dụng một cho vòng lặp;
Từ lời giải thích ở trên, bạn sẽ nhận thấy có một mẫu được sử dụng để tính lợi nhuận tối đa. Thay vì phải tính toán lại tất cả các giá trị với nhau, thay vào đó chúng ta có thể theo dõi mức giá tối thiểu và trừ nó khỏi giá bán như vậy
Giải thích và mã giả:
- Tạo một biến để lưu trữ giá tối đa
- Tạo một biến khác để theo dõi giá tối thiểu và đặt nó thành giá trị đầu tiên trong mảng
- Vòng lặp qua mảng giá bắt đầu từ Chỉ số 1 là giá bán của bạn
- Để nhận được lợi nhuận, bạn đã trừ minPrice từ SellPrice
- Nếu lợi nhuận lớn hơn lợi nhuận tối đa, hãy thay thế giá trị của maxProfit bằng giá trị lợi nhuận
Mặt khác để tính lợi nhuận cho các giá trị khác, hãy kiểm tra xem giá trị hiện tại là SellingPrice nhỏ hơn giá trị minPrice. Nếu có, hãy đặt giá trị hiện tại là giá bán cho minPrice.
- trả về MaxProfit
Ở đây, một sự cố về cách mã tính toán và trả lại lợi nhuận tối đa bằng cách sử dụng một foroop;
Phân tích độ phức tạp
- Độ phức tạp về thời gian: O (N²) trong đó n là độ dài của mảng giá
- Độ phức tạp không gian: O (1). Chỉ có hai biến được tạo ra. MaxProfit và lợi nhuận
Tôi hy vọng bạn tìm thấy lời giải thích này dễ hiểu. Mã hóa hạnh phúc!
Ngày 16 tháng 5 năm 2022 • 4 phút đọc4 min read
Lời nhắc
Bạn được cung cấp một mảng & nbsp; ________ 12 & nbsp; trong đó & nbsp; ____ 13 & nbsp; là giá của một cổ phiếu nhất định trên & nbsp; ____ 14 & nbsp; ngày.
Bạn muốn tối đa hóa lợi nhuận của mình bằng cách chọn A & NBSP; một ngày & nbsp; để mua một cổ phiếu và chọn A & NBSP; ngày khác nhau trong tương lai & nbsp; để bán cổ phiếu đó.single day to buy one stock and choosing a different day in the future to sell that stock.
Trả lại & nbsp; lợi nhuận tối đa bạn có thể đạt được từ giao dịch này. Nếu bạn không thể đạt được bất kỳ lợi nhuận nào, return & nbsp; ________ 15.
Ví dụ 1:
Input: prices = [7,1,5,3,6,4] Output: 5 Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.Phân tích vấn đề
Như với các vấn đề trước đây, giải pháp rõ ràng đầu tiên là đi cho giải pháp vũ lực. Ở đây chúng tôi sẽ lặp lại trên mảng hai lần kiểm tra mọi phép trừ giữa mọi giá trị tiếp theo và chỉ lấy lợi nhuận cao nhất.
Một ví dụ trực quan về điều này có thể trông như thế này:
Giải pháp đầu tiên
Hãy tiếp tục và viết mã cho những gì chúng tôi đã đề cập ở trên.
JavaScript
function maxProfit(prices) { let profit = 0; for (let i = 0; i < prices.length - 1; i++) { for (let j = i + 1; j < prices.length; j++) { const currentProfit = prices[j] - prices[i]; if (currentProfit > profit) { profit = currentProfit; } } } return profit; }Ở đây chúng tôi so sánh giá của yếu tố tiếp theo trong mảng với dòng điện. Cách tốt nhất để khái niệm hóa điều này là
JavaScript
function maxProfit(prices) { let profit = 0; for (let i = 0; i < prices.length - 1; i++) { for (let j = i + 1; j < prices.length; j++) { const currentProfit = prices[j] - prices[i]; if (currentProfit > profit) { profit = currentProfit; } } } return profit; } 6 là chỉ mục của chúng tôi vàJavaScript
function maxProfit(prices) { let profit = 0; for (let i = 0; i < prices.length - 1; i++) { for (let j = i + 1; j < prices.length; j++) { const currentProfit = prices[j] - prices[i]; if (currentProfit > profit) { profit = currentProfit; } } } return profit; } 7 là con trỏ của chúng tôi luôn lặp đi lặp lại.Chúng tôi sử dụng hai vòng
JavaScript
function maxProfit(prices) { let profit = 0; for (let i = 0; i < prices.length - 1; i++) { for (let j = i + 1; j < prices.length; j++) { const currentProfit = prices[j] - prices[i]; if (currentProfit > profit) { profit = currentProfit; } } } return profit; } 8 để tìm lợi nhuận tối đa. Điều này sẽ có sự phức tạp của O (n^2). Đây là một vấn đề khá lớn vì nó rất chậm! Tuy nhiên, chúng tôi có thể tối ưu hóa điều này bằng cách lặp lại trên mảng một lần.Giải pháp thứ hai
Nhưng một lần lặp duy nhất sẽ trông như thế nào?
Với mã, nó sẽ trông giống như thế này:
JavaScript
var maxProfit = function (prices) { let profit = 0; let stockToBuy = prices[0]; for (let i = 1; i < prices.length; i++) { if (stockToBuy > prices[i]) { stockToBuy = prices[i]; } const currentProfit = prices[i] - stockToBuy; if (currentProfit > profit) { profit = currentProfit; } } return profit; };Chúng tôi lấy
JavaScript
function maxProfit(prices) { let profit = 0; for (let i = 0; i < prices.length - 1; i++) { for (let j = i + 1; j < prices.length; j++) { const currentProfit = prices[j] - prices[i]; if (currentProfit > profit) { profit = currentProfit; } } } return profit; } 9 ban đầu từ phần tử đầu tiên trong mảng. Sau đó, chúng ta có thể bắt đầu lặp lại trên mảng (bỏ qua đầu tiên). Chúng tôi so sánh nếu cổ phiếu tiếp theo có giá cao hơn cổ phiếu hiện được chọn của chúng tôi. Nếu vậy, nó sẽ mang lại cho chúng tôi lợi nhuận cao hơn để chúng tôi chuyển nó ra.Tuy nhiên, điều này cũng phục vụ như một cơ chế thiết lập lại. Nếu cổ phiếu có giá trị cao hơn, chúng ta biết rằng từ thời điểm này trở đi, nó sẽ không có lợi nhuận cao hơn so với với cổ phiếu được chọn trước đó.
JavaScript
stockToBuy = prices[i];Sau đó, chúng tôi tính toán
JavaScript
var maxProfit = function (prices) { let profit = 0; let stockToBuy = prices[0]; for (let i = 1; i < prices.length; i++) { if (stockToBuy > prices[i]) { stockToBuy = prices[i]; } const currentProfit = prices[i] - stockToBuy; if (currentProfit > profit) { profit = currentProfit; } } return profit; }; 0 mới của chúng tôi, đây chỉ là một giá trị tạm thời trong lần lặp hiện tại của chúng tôi.JavaScript
const currentProfit = prices[i] - stockToBuy;Sau đó, chúng tôi so sánh nó với giá trị chúng tôi đã lưu bên ngoài vòng lặp
JavaScript
function maxProfit(prices) { let profit = 0; for (let i = 0; i < prices.length - 1; i++) { for (let j = i + 1; j < prices.length; j++) { const currentProfit = prices[j] - prices[i]; if (currentProfit > profit) { profit = currentProfit; } } } return profit; } 8 của chúng tôi. Nếu nó cao hơn thì đó chính xác là những gì chúng ta muốn.Lưu ý rằng chúng tôi đã tạo biến với
JavaScript
function maxProfit(prices) { let profit = 0; for (let i = 0; i < prices.length - 1; i++) { for (let j = i + 1; j < prices.length; j++) { const currentProfit = prices[j] - prices[i]; if (currentProfit > profit) { profit = currentProfit; } } } return profit; } 5 lúc đầu để nếu chúng tôi không tìm thấy bất kỳ lợi nhuận nào, chúng tôi có thể trả lại như vậy.Thuật toán tham lam
Nhưng cái này được gọi là gì?
Những gì chúng tôi làm ở đây là chọn tùy chọn tốt nhất trên mỗi lần lặp và quên đi các lựa chọn trong quá khứ, đây được gọi là thuật toán tham lam.
Đây là một bài viết Wikipedia nếu bạn muốn đọc thêm về nó (bạn nên).
Hãy kết nối
Nếu bạn thích điều này, hãy kết nối với tôi trên LinkedIn hoặc Twitter
Kiểm tra lộ trình phát triển miễn phí của tôi và tin tức ngành công nghệ hàng tuần trong bản tin của tôi.
Nếu bạn thấy bất kỳ lỗi chính tả hoặc lỗi nào, bạn có thể chỉnh sửa bài viết trực tiếp trên GitHub
Hãy đứng đầu ngành công nghệ và phát triển như một nhà phát triển với một lựa chọn các bài báo và tin tức cùng với lời khuyên cá nhân, quan sát và hiểu biết. 🚀developer with a curated selection of articles and news alongside personal advice, observations, and insight. 🚀
Không có thư rác 🙅♂. Hủy đăng ký
bất cứ khi nào.
Đặt mua