สมมติว่าในแถวแรก เรามี 0 ทีนี้ ในทุกแถวต่อๆ มา เราจะดูที่แถวก่อนหน้าและแทนที่การเกิดขึ้นของ 0 ด้วย 01 และแต่ละการเกิดขึ้นของ 1 คูณ 10 สมมติว่าเรามี N แถวและดัชนี K เรา ต้องหาสัญลักษณ์ที่ดัชนี K-th ในแถว N. (ค่าของ K คือ 1-indexed.) (ดัชนี 1 รายการ) ดังนั้นหาก N =4 และ K =5 ผลลัพธ์จะเป็น 1 เนื่องจาก −
- แถว 1:0
- แถว 2:01
- แถว 3:0110
- แถวที่ 4:01101001
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- สมมติว่าชื่อของเมธอดคือ kthGrammar ต้องใช้ N และ K
- ถ้า N เป็น 1 ให้คืนค่า 0
- ถ้า k เป็นเลขคู่ ให้คืนค่า 1 เมื่อ kthGrammar(N – 1, K/2) เป็น 0 มิฉะนั้น 0
- มิฉะนั้นให้คืนค่า kthGrammar(N – 1, (K + 1)/2)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int kthGrammar(int N, int K) {
if(N == 1) return 0;
if(K % 2 == 0){
return kthGrammar(N - 1, K / 2) == 0 ? 1 : 0;
}else{
return kthGrammar(N - 1, (K + 1) / 2);
}
}
};
main(){
Solution ob;
cout << (ob.kthGrammar(4, 5));
} อินพุต
4 5
ผลลัพธ์
1
