Skip to main content

ประยุกต์กับ leetcode

Problem 55 - Jump Game​

https://leetcode.com/problems/jump-game/description/

ปัญหาแบบสั้นๆ: ให้ array nums มา แทนตัวเลขที่สามารถกระโดดข้ามได้เมื่อถึงช่องนั้น โดยเริ่มต้นจากช่องแรกสุดของ nums เป็นไปได้หรือไม่ ที่สามารถกระโดดจนถึงช่องสุดท้ายของ array nums ได้

นี่คือวิธีแก้ปัญหา Jump Game (LeetCode 55) ด้วยภาษา C++ แบบง่ายๆ:

class Solution {
public:
  bool canJump(vector<int> &nums) {
    int n = nums.size();
    int maxReach = 0;

    for (int i = 0; i <= maxReach; i++) {
      maxReach = max(maxReach, i + nums[i]);
      if (maxReach >= n - 1) {
        return true;
      }
    }

    return false;
  }
};

วิธีนี้ใช้แนวคิดแบบ Greedy algorithm โดยมีขั้นตอนดังนี้:

  1. กำหนดตัวแปร maxReach เพื่อเก็บตำแหน่งไกลสุดที่เราสามารถไปถึงได้ในขณะนั้น โดยเริ่มต้นที่ 0

  2. วนลูปตั้งแต่ตำแหน่ง 0 ถึง maxReach (รวมทั้งสองค่า) โดยในแต่ละรอบ:

  • อัปเดต maxReach เป็นค่ามากสุดระหว่าง maxReach ปัจจุบันกับ i + nums[i] (ตำแหน่งปัจจุบัน + ระยะกระโดดสูงสุดที่ตำแหน่งนั้น)
  • ถ้า maxReach มากกว่าหรือเท่ากับ n - 1 (ตำแหน่งสุดท้าย) แสดงว่าเราสามารถไปถึงตำแหน่งสุดท้ายได้ ให้คืนค่า true
  1. ถ้าวนลูปจบแล้วยังไม่สามารถไปถึงตำแหน่งสุดท้าย ให้คืนค่า false
    ความซับซ้อนของเวลา (Time Complexity) คือ O(n) เนื่องจากเราวนลูปเพียงครั้งเดียว ความซับซ้อนของพื้นที่ (Space Complexity) คือ O(1) เนื่องจากเราใช้พื้นที่เพิ่มเติมคงที่ ไม่ขึ้นกับขนาดอินพุต
    สรุปสั้นๆ คือเราจะพยายามไปให้ไกลที่สุดเท่าที่จะทำได้ในแต่ละก้าว ถ้าสามารถไปถึงตำแหน่งสุดท้ายได้ก็แสดงว่าเราสามารถกระโดดไปถึงจุดหมายปลายทางได้

Problem 134 - Gas Station​

https://leetcode.com/problems/gas-station/description/

ปัญหา: มีปั๊มน้ำมัน n แห่งตามเส้นทางวงกลม โดยที่ปั๊มน้ำมันที่ i มีน้ำมันอยู่ gas[i] ลิตร
คุณมีรถยนต์ที่มีถังน้ำมันไม่จำกัดขนาด และต้องใช้น้ำมัน cost[i] ลิตร ในการเดินทางจากปั๊มที่ i ไปยังปั๊มถัดไป (i + 1) คุณเริ่มต้นการเดินทางด้วยถังน้ำมันที่ว่างเปล่าที่ปั๊มน้ำมันแห่งใดแห่งหนึ่ง กำหนดอาร์เรย์จำนวนเต็มสองอาร์เรย์ gas และ cost ให้คืนค่าดัชนีของปั๊มน้ำมันเริ่มต้น หากคุณสามารถเดินทางรอบวงจรได้ครบรอบในทิศทางตามเข็มนาฬิกา ไม่เช่นนั้นให้คืนค่า -1 ถ้ามีคำตอบ จะรับประกันว่าคำตอบนั้นจะมีเพียงคำตอบเดียว

นี่คือวิธีแก้ปัญหา Gas Station (LeetCode 134) ด้วยภาษา C++

class Solution {
public:
  int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
    int n = gas.size();
    int totalGas = 0, totalCost = 0;
    int currentGas = 0, startStation = 0;

    for (int i = 0; i < n; i++) {
      totalGas += gas[i];
      totalCost += cost[i];
      currentGas += gas[i] - cost[i];

      if (currentGas < 0) {
        startStation = i + 1;
        currentGas = 0;
      }
    }

    return (totalGas < totalCost) ? -1 : startStation;
  }
};

วิธีนี้ใช้แนวคิดแบบ Greedy algorithm โดยมีขั้นตอนดังนี้:

  1. กำหนดตัวแปร totalGas และ totalCost เพื่อเก็บผลรวมของก๊าซและค่าใช้จ่ายทั้งหมดตามลำดับ

  2. กำหนดตัวแปร currentGas เพื่อเก็บปริมาณก๊าซสะสมในขณะนั้น และ startStation เพื่อเก็บสถานีเริ่มต้นที่เป็นไปได้

  3. วนลูปตั้งแต่ 0 ถึง n-1 (จำนวนสถานี) โดยในแต่ละรอบ:

  • เพิ่มค่า gas[i] ลงใน totalGas และ cost[i] ลงใน totalCost
  • เพิ่มค่า gas[i] - cost[i] ลงใน currentGas (ปริมาณก๊าซสะสมหลังจากเติมและใช้ไปที่สถานีปัจจุบัน)
  • ถ้า currentGas ติดลบ แสดงว่าเราไม่สามารถไปต่อจากสถานีปัจจุบันได้ ให้อัปเดต startStation เป็น i+1 (สถานีถัดไป) และรีเซ็ต currentGas เป็น 0
  1. หลังจบลูป ถ้า totalGas น้อยกว่า totalCost แสดงว่าไม่มีจุดเริ่มต้นที่ทำให้เดินทางรอบวงได้ ให้คืนค่า -1 ถ้าไม่ใช่ ให้คืนค่า startStation
    ความซับซ้อนของเวลา (Time Complexity) คือ O(n) เนื่องจากเราวนลูปเพียงครั้งเดียว ความซับซ้อนของพื้นที่ (Space Complexity) คือ O(1) เนื่องจากเราใช้พื้นที่เพิ่มเติมคงที่ ไม่ขึ้นกับขนาดอินพุต
    สรุปสั้นๆ คือเราจะลองเริ่มต้นจากแต่ละสถานีและดูว่าปริมาณก๊าซสะสมเป็นลบหรือไม่ ถ้าเป็นลบแสดงว่าเริ่มจากสถานีนั้นไม่ได้ ต้องข้ามไปเริ่มที่สถานีถัดไป สุดท้ายถ้ามีก๊าซมากพอจะวนรอบได้ก็จะได้คำตอบเป็นสถานีเริ่มต้นที่เป็นไปได้