โจทย์
ภาพหนึ่งภาพคือตารางของพิกเซล และแต่ละพิกเซลเก็บเป็นจำนวนเต็มหนึ่งตัวที่รวมสีไว้ด้วยกัน คือ red × 65536 + green × 256 + blue โดยแต่ละช่องสีมีค่า 0 ถึง 255 (สีฐานสิบหก #FF8000 คือจำนวนเต็ม 16744448) หากต้องการทำให้ภาพเป็นสีเทา ให้ทุกพิกเซลมีค่า g เท่ากันทั้งสามช่องสี โดย g คือความสว่างของพิกเซลนั้น
g = (299 × red + 587 × green + 114 × blue) / 1000 ปัดเป็นจำนวนเต็มที่ใกล้ที่สุด โดยถ้าเป็นครึ่งพอดีให้ปัดขึ้น
ถ้าใช้แต่จำนวนเต็ม จะเขียนได้ว่า g = (299 × red + 587 × green + 114 × blue + 500) / 1000 โดยใช้การหารแบบปัดเศษทิ้ง (integer division)
จงเขียน grayscale_filter(pixels)
อินพุต
pixels: ภาพ แถวละหนึ่งลิสต์ แต่ละแถวอาจยาวไม่เท่ากัน
เอาต์พุต
คืนค่าตารางที่มีรูปร่างเหมือนเดิม โดยแต่ละพิกเซลเป็น g × 65536 + g × 256 + g ถ้าภาพว่าง ให้คืนค่าตารางว่าง
เงื่อนไข
0 ≤ จำนวนแถว ≤ 50, 0 ≤ จำนวนพิกเซลต่อแถว ≤ 50
0 ≤ แต่ละพิกเซล ≤ 16,777,215
ตัวอย่าง
อินพุต:
pixels = [
[16744448, 255]
]
ผลลัพธ์ที่คาดหวัง:
expected = [
[9934743, 1907997]
]
อินพุต:
std::vector<std::vector<long long>> pixels = {
{16744448, 255}
};
ผลลัพธ์ที่คาดหวัง:
std::vector<std::vector<long long>> expected = {
{9934743, 1907997}
};
อินพุต:
long[][] pixels = new long[][] {
new long[] {16744448, 255}
};
ผลลัพธ์ที่คาดหวัง:
long[][] expected = new long[][] {
new long[] {9934743, 1907997}
};
คำอธิบาย
#FF8000 มีแดง 255 เขียว 128 น้ำเงิน 0 คำนวณได้ (76245 + 75136 + 0 + 500) / 1000 = 151 จึงได้ 151 × 65793 = 9934743 ส่วนน้ำเงินล้วน 255 ได้ (29070 + 500) / 1000 = 29 จึงได้ 1907997
อินพุต:
pixels = [
[0, 16777215],
[8421504, 65280]
]
ผลลัพธ์ที่คาดหวัง:
expected = [
[0, 16777215],
[8421504, 9868950]
]
อินพุต:
std::vector<std::vector<long long>> pixels = {
{0, 16777215},
{8421504, 65280}
};
ผลลัพธ์ที่คาดหวัง:
std::vector<std::vector<long long>> expected = {
{0, 16777215},
{8421504, 9868950}
};
อินพุต:
long[][] pixels = new long[][] {
new long[] {0, 16777215},
new long[] {8421504, 65280}
};
ผลลัพธ์ที่คาดหวัง:
long[][] expected = new long[][] {
new long[] {0, 16777215},
new long[] {8421504, 9868950}
};
คำอธิบาย
สีดำยังคงเป็น 0 และสีขาวยังคงเป็น 16777215 สีเทา #808080 ยังคงเป็น 128 (8421504) ส่วนเขียวล้วนได้ (149685 + 500) / 1000 = 150 จึงได้ 9868950
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
สีแดงคือ (pixel / 65536) % 256 สีเขียวคือ (pixel / 256) % 256 และสีน้ำเงินคือ pixel % 256 หรือจะใช้การเลื่อนบิตกับการมาสก์ก็ได้
คำใบ้ 2
การบวก 500 ก่อนหารด้วย 1000 จะทำให้กรณีครึ่งพอดีถูกปัดขึ้น
คำใบ้ 3
ใส่ค่าสีเทาเดียวกันทั้งสามช่องสีเมื่อรวมกลับเป็นจำนวนเต็ม
ความซับซ้อนที่คาดหวัง
เวลา O(rows × columns), หน่วยความจำเพิ่ม O(rows × columns)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน