Number Problem

โจทย์ที่ 1: Two Sum

อ่านโจทย์จากต้นทาง https://leetcode.com/problems/two-sum/description/

แนะนำการใช้งาน LeetCode โดยประมาณ

ทีนี้ เนื่องจากข้อนี้เป็นข้อแรก เราจะขอแนะนำพื้นที่หน้าจอแต่ละส่วนก่อนว่ามันคืออะไรบ้าง

ฝั่งของ leetcode นั้นจะประกอบของไปด้วยทั้งหมด 3 ส่วนคือ

1. ฝั่งซ้ายมือ จะเป็นโจทย์ที่จะบอกมาว่า โจทย์จะให้ทำอะไรและมีตัวอย่างข้อมูลส่งแบบไหนบ้าง
2. ฝั่งขวาบน เป็นส่วนของการส่ง code สังเกตตรง c++ จะเป็น dropdown (บางเครื่องเริ่มต้นอาจจะไม่ใช้ C++ ให้ปรับมาเป็น C++) นี่คือ code function เริ่มต้นที่ LeetCode จะทำการส่งข้อมูลเข้ามา
3. ฝั่งขวาล่าง เป็นส่วนของ Test case ที่ทาง LeetCode จะเตรียมมาให้เพื่อให้สามารถทดสอบการส่งข้อมูลผ่านชุด code ที่เราทำมาได้

ทีนี้ เพื่อให้เกิดความเข้าใจที่มากขึ้น เราจะขออธิบายของเพิ่ม 2 อย่างคือ

1. จากภาพ LeetCode ได้เตรียม function ชื่อ twoSum(vector<int>& nums, int target) มาให้ โดยจะเป็นการรับ parameter 2 ตัวเข้ามาคือ nums เป็นประเภท vector (ที่เดี๋ยวเราจะอธิบายอีกที) และ target เป็น interger

2. function นี้จะเป็น function ที่ LeetCode จะนำไป run บน system ของ LeetCode ดังนั้นตัวนี้จะเป็น function หลักที่ “ไม่สามารถเปลี่ยนได้” และผลลัพธ์ที่ return ผ่าน function นี้ก็จะเป็นการตอบคำถาม (ส่วนของ Output) ในแต่ละ Test case ที่ LeetCode เตรียมมาให้

เพื่อเติมเต็มความเข้าใจ เดี๋ยวเราจะลอง debug code กัน ผมจะขออธิบายตัวแปรประเภท Vector ก่อนว่ามันคืออะไร

Vector เป็นหนึ่งใน data structure ที่ใช้เก็บรวบรวมข้อมูลหลายๆ อันในรูปแบบของลำดับหรือ Array แต่มีความยืดหยุ่นและความสามารถในการจัดการข้อมูลที่เหนือกว่า Array แบบธรรมดา นั่นคือ สามารถเพิ่มหรือลดจำนวนสมาชิกใน Array ได้ รวมถึงสามารถเพิ่ม, ลบข้อมูลภายใน Vector ได้

นี่คือตัวอย่างของ Code Vector

#include <iostream>
#include <vector>
using namespace std;

int main() {
  vector<int> myVector = {1, 2, 3, 4, 5};
  cout << "Vector elements: " << endl;
  for (int i = 0; i < myVector.size(); ++i) {
    cout << myVector[i] << " " << endl;
  }

  return 0;
}

ผลลัพธ์

Vector elements: 
1 
2 
3 
4 
5

จะสังเกตเห็นว่า ผลลัพธ์จะเหมือนกับเวลาวน loop array ออกมาเลย ดังนั้น สำหรับโจทย์นี้เราสามารถใช้ Vector เป็นเหมือน Array ตัวหนึ่งได้เลย

** เดี๋ยวเรื่อง Vector เราจะอธิบายแบบเจาะลึกอีกทีในหัวข้อ Data Structure หัวข้อหลังๆสำหรับหัวข้อนี้ให้เข้าใจว่ามันสามารถใช้งานแบบ Array ออกมาได้ก่อน

ดังนั้น เมื่อลองเอามาประยุกต์กับ code ของ LeetCode เราก็จะใส่ code เป็นลักษณะประมาณนี้ไปเพื่อทดสอบผลลัพธ์ออกมา

class Solution {
public:
  vector<int> twoSum(vector<int> &nums, int target) {
    for (int i = 0; i < nums.size(); ++i) {
      cout << nums[i] << endl;
    }
    return {1};
  }
};

นำไปวางไว้ในตำแหน่งของ code ใน LeetCode และลองทดสอบ Run ดู

ก็จะได้ผลลัพธ์ประมาณนี้ออกมา

สังเกตว่า

• หลังจาก Run เสร็จ ผลลัพธ์ตอน cout จะโผล่มาที่ stdout ออกมา ซึ่งเป็นจุดที่ทำให้เราสามารถ debug ข้อมูลออกมาได้

• และตรงตำแหน่ง return หากมีการเปลี่ยนแปลงอะไรเข้าไป ก็จะสามารถเปลี่ยนแปลงตรง Output (ตัวที่เราจะต้องส่งคำตอบ) ออกไปได้

  

และนี่ก็คือการใช้งาน LeetCode รวมถึงหากเราต้องการนำ solution มา run ที่เครื่องเราเอง เราก็สามารถ copy function ของ LeetCode มาที่ code ของเรา และทำการเรียกใช้ function ตาม Test case นั้นๆออกมาได้ลักษณะแบบนี้

#include<iostream>
#include<vector>

using namespace std;

class Solution {
public:
  vector<int> twoSum(vector<int> &nums, int target) {
    for (int i = 0; i < nums.size(); ++i) {
      cout << nums[i] << endl;
    }
    return {1};
  }
};

// call twoSum with input [2,7,11,15] and output 9
int main() {
  Solution s;
  vector<int> nums = {2, 7, 11, 15};
  int target = 9;
  vector<int> result = s.twoSum(nums, target);
  for (int i = 0; i < result.size(); ++i) {
    cout << result[i] << endl;
  }
  return 0;
}

ผลลัพธ์

เพิ่มเติม การใช้งาน Vector (init vector ด้วย =) จะสามารถใช้งานได้ผ่าน C++11 standard compiler ซึ่งเป็น feature ที่เพิ่มมาใหม่ในภายหลังจากตัว c++ original ดังนั้นจึงต้องมีการเพิ่ม -std=c++11 เข้าไปตามภาพนี้เพื่อให้สามารถใช้งานการ init vector ได้ แบบนี้

g++ -std=c++11 test.cpp -o test

เกี่ยวกับ C++11 standard compiler เราจะมีอธิบายเพิ่มเติมอีกทีในหัวข้อ Data Structure เช่นเดียวกัน

ทีนี้เราก็พร้อมสำหรับการลุยโจทย์ปัญหาและ

วิเคราะห์โจทย์และแก้ปัญหา

อธิบายโจทย์แบบสั้นๆ มี array (vector) ของตัวเลข และต้องหา “ตัวเลข 2 ตัว” ที่บวกกันแล้วเท่ากับ target ที่กำหนดมา โดยจะต้องคืนผลลัพธ์ (Output) ออกมาเป็น index ใน vector

จากข้อมูลที่โจทย์ให้มา

Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]

เราจะต้องตามหา Index ของ Array ที่ให้ผลลัพธ์รวมเท่ากับ Target ออกมาได้ ดังนั้นหากเราคิดแบบตรงไปตรงมา ไอเดียของการแก้ปัญหานี้

• สร้าง ตัวแปร 2 ตัวขึ้นมา ไล่หาข้อมูลที่อยู่ใน Array โดยใช้ loop
• หาก ผลลัพธ์ใน Array ที่กำลังค้นหาอยู่ = ให้คืน index ของ Array นั้นออกมาเป็น คู่ของ index ที่ค้นหาเจอ

เพียงเท่านี้เราก็จะสามารถแก้ปัญหานี้ได้

• Solution

  class Solution {
  public:
      vector<int> twoSum(vector<int>& nums, int target) {
          for (int i = 0; i < nums.size(); ++i) {
              for (int j = i + 1; j < nums.size(); ++j) {
                  if (nums[i] + nums[j] == target) {
                      return {i, j};
                  }
              }
          }
          // As per the problem statement, this line should never be reached
          return {};
      }
  };

เนื่องจากนี้เป็นข้อแรก เราจะขอแนะนำวิธีการ submit เพิ่มเติมหลังจากที่ได้ solution มา ให้นำ code ของ solution วางไว้ตรงตำแหน่งของ code ใน LeetCode และลองกด Run ดูรอบหนึ่งก่อนว่าผ่านครบทุก Test case หรือไม่

หากไม่มีปัญหาอะไรในตัว code จะต้องขึ้นลักษณะนี้

หากเจอปัญหาอะไรก็ตาม มันจะขึ้นเป็นสีแดงให้ตรวจสอบให้ดีก่อนว่า Output และ Expected มีจุดไหนที่แตกต่างกัน แก้ปัญหาก่อนเพื่อให้ผ่านครบทั้ง 3 เคสก่อนที่จะ Submit จริง

เมื่อไม่มีปัญหาอะไรแล้ว ให้กด Submit เพื่อทำการส่ง code

หากแสดงคำว่า Accepted ตอนท้ายออกมาได้ = เราทำถูกต้องแล้ว เป็นอันผ่านข้อนี้เป็นที่เรียบร้อย

สำหรับข้ออื่นๆ เราจะขอแนะนำเป็น Guideline และมี code Solution (ที่เราซ่อนไว้) แนบไว้ให้ โดยขอแนะนำให้ลองทำเองก่อนทุกข้อ ก่อนที่จะอ่าน Guideline และดู code Solution

รวมถึงใน web LeetCode เองจะมี tab Solutions อยู่ หากตันๆอย่างไรสามารถเข้าไปดู Solution เพื่อหาไอเดียเพิ่มเติมได้เช่นกัน

โจทยที่ 2: Palindrome

โจทย์ https://leetcode.com/problems/palindrome-number/description/

อธิบายโจทย์แบบสั้นๆ มีตัวเลขส่งมาให้ (x) จงบอกว่าตัวเลขนั้นเป็น Palindrome หรือไม่ ?

• Palindrome เป็นคำหรือวลีที่อ่านจากหน้าไปหลังหรือจากหลังไปหน้าแล้วมีความหมายเหมือนกัน
  • ตัวอย่าง Palindrome เช่น 1221, racecar, “No lemon, no melon”
  • ตัวอย่าง ไม่ใช่ Palindrome เช่น 12345 (54321), hello (olleh)

จากข้อมูลที่โจทย์ให้มา

Example 1:
Input: x = 121
Output: true
Explanation: 121 reads as 121 from left to right and from right to left.

Example 2:
Input: x = -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:
Input: x = 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

จากตัวอย่างนี้ค่อนข้างชัดว่า

• ตัวเลขติดลบ (น้อยกว่า 0) ไม่มีทางเป็น palindrome ได้เลย เพราะ เมื่ออ่านกลับกัน จะเจอลบกลับมาเสมอ = สามารถตัดเคส น้อยกว่า 0 ว่าไม่ใช่ palindrome ออกมาก่อนได้
• รวมถึงถ้าเคสไหนลงท้ายด้วย 0 เช่น 10, 200, 250, 3250 จะไม่มีทางเป็น palindrome ได้เช่นเดียวกัน เนื่องจากตัวเลข integer ไม่สามารถนำหน้าด้วย 0 ได้ = ไม่สามารถเขียนกลับเป็น palindrome ที่มีจำนวน digit เท่ากันได้ เช่น 250 เมื่อเขียนกลับจะกลายเป็น 52 ออกมาแทน (0 จะหายไปเนื่องจากเป็นตำแหน่งแรกสุด)
• ที่เหลือสามารถทำได้โดยการสร้างตัวเลขใหม่ที่กลับกัน และนำมาเทียบกันว่าเหมือนกันหรือไม่
  • ถ้าเหมือน = Palindrome
  • ถ้าไม่เหมือน = ไม่ใช่ Palindrome

นี่คือ flowchart idea โดยประมาณของข้อนี้

Solution

class Solution {
public:
  bool isPalindrome(int x) {
    // น้อยกว่า 0 หรือลงท้ายด้วย 0 = คือไม่ใช่ palindrome
    if (x < 0 || (x % 10 == 0 && x != 0)) {
      return false;
    }

		// ที่เหลือค่อยๆสร้างเลขย้อนกลับจากการดึง digit สุดท้ายมาสร้างเป็นตัวเลขใหม่
    int reversedHalf = 0;
    while (x > reversedHalf) {
      reversedHalf = reversedHalf * 10 + x % 10;
      x /= 10;
    }
    return x == reversedHalf || x == reversedHalf / 10;
  }
};

นี่คือ Solution ของข้อนี้

1. ตัวเลขที่น้อยกว่า 0 และ ตัวเลขที่ลงท้ายด้วย 0 (ใช้ % ในการหารเอาเศษเพื่อหาตำแหน่งสุดท้ายออกมา) และที่สำคัญต้องเว้น “0” ไว้ด้วย เนื่องจาก 0 เป็น palindrome นั่นเอง
2. ทำการสร้างตัวแปร reversedHalf เพื่อทำการเก็บตัวเลขย้อนกลับออกมาโดยเช็คก่อนว่า ค่า original (x) มีค่ามากกว่า reversedHalf แล้วหรือยัง ถ้าใช่ = reverse ครบแล้วเรียบร้อย
3. ในทุกๆการ reversed ให้นำตัวเลข original หารเอาเศษ (เพื่อดึงตำแหน่งสุดท้ายออกมา) และ ค่อยๆ * 10 ตัวเลข reversedHalf เพื่อเป็นการเขยิบ digit ขึ้นมาเรื่อยๆ เช่น
   1. หากตัวเลข original คือ 252 จะทำการดึง 2 ออกมาจาก 252 และนำไปใส่ใน reversedHalf ตอนนี้ reversedHalf = 2 และลด เลข original เหลือ 25 (จากการหาร 10 ออกในทุกๆรอบ)
   2. ต่อมาจาก 25 ดึง 5 ออกมา และนำไปใส่ใน reversedHalf โดยจะต้อง shift 2 ที่เคยเก็บไว้กลายเป็นหลักสิบแทน ดังนั้น reversedHalf จึง * 10 เข้าตัวเอง (2 เป็น 20) และบวกกับเลขท้าย 5 ที่ดึงออกมา reversedHalf ก็จะกลายเป็น 25 ออกมา และ ลด เลข original เหลือ 2
   3. และสุดท้ายก็ทำเหมือนเดิม ก็จะได้ reversedHalf เป็น 252 ออกมาได้
4. คำตอบก็ตรงไปตรงมาว่า หาก x == reversedHalf แปลว่า ตัวเลขนี้คือ palindrome
5. ที่ต้องดักเคส x == reversedHalf / 10 เนื่องจากเป็นการป้องกันเลขหลักหน่วยที่มีเพียงตัวเลขเดียว แต่ยังมีคุณสมบัติ palindrome อยู่ ให้ code ยังสามารถตอบออกมาได้ว่าเป็นตัวเลข palindrome เช่นกัน (ลองนำตัวเลข x = 8 ไล่ตาม code ดูได้)