[Swift]LeetCode779. 第K个语法符号 | K-th Symbol in Grammar

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★➤微信公众号：山青咏芝（shanqingyongzhi）➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）➤GitHub地址：https://github.com/strengthen/LeetCode➤原文地址： https://www.cnblogs.com/strengthen/p/10541751.html ➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

On the first row, we write a 0. Now in every subsequent row, we look at the previous row and replace each occurrence of 0 with 01, and each occurrence of 1 with 10.

Given row N and index K, return the K-th indexed symbol in row N. (The values of K are 1-indexed.) (1 indexed).

Examples: Input: N = 1, K = 1 Output: 0 Input: N = 2, K = 1 Output: 0 Input: N = 2, K = 2 Output: 1 Input: N = 4, K = 5 Output: 1 Explanation: row 1: 0 row 2: 01 row 3: 0110 row 4: 01101001

Note:

N will be an integer in the range [1, 30].K will be an integer in the range [1, 2^(N-1)].

---

在第一行我们写上一个 0。接下来的每一行，将前一行中的0替换为01，1替换为10。

给定行数 N 和序数 K，返回第 N 行中第 K个字符。（K从1开始）

例子:

输入: N = 1, K = 1 输出: 0 输入: N = 2, K = 1 输出: 0 输入: N = 2, K = 2 输出: 1 输入: N = 4, K = 5 输出: 1 解释: 第一行: 0 第二行: 01 第三行: 0110 第四行: 01101001

注意：

N 的范围 [1, 30].K 的范围 [1, 2^(N-1)].

---

Runtime: 4 ms Memory Usage: 18.4 MB 1 class Solution { 2 func kthGrammar(_ N: Int, _ K: Int) -> Int { 3 if N == 1{ 4 return 0 5 } 6 7 return K % 2 == 0 ? (kthGrammar(N-1,K/2) == 0 ? 1 : 0 ):(kthGrammar(N-1,(K+1)/2) == 1 ? 1 : 0) 8 } 9 }

---

Runtime: 4 ms Memory Usage: 18.4 MB 1 class Solution { 2 func kthGrammar(_ N: Int, _ K: Int) -> Int { 3 var K = K 4 var res:Int = 0 5 while (K > 1) 6 { 7 K = (K % 2 == 1) ? K + 1 : K / 2 8 res ^= 1 9 } 10 return res 11 } 12 }

---

4ms

1 class Solution { 2 func kthGrammar(_ N: Int, _ K: Int) -> Int { 3 var s = pow(Double(2), Double(N - 1)) 4 var flips = 0 5 var K = K 6 while (s > 2){ 7 if K > Int(s / 2) { 8 K -= Int(s / 2) 9 flips += 1 10 } 11 s /= 2 12 } 13 K -= 1 // K is either 2 or 1 14 if flips % 2 == 1 { 15 K = 1 - K 16 } 17 return K 18 } 19 }

---

8ms

1 class Solution { 2 func kthGrammar(_ N: Int, _ K: Int) -> Int { 3 if K == 1 { 4 return 0 5 } 6 let halfCount = Int(pow(2.0, Double(N-2))) 7 let rm = K%halfCount 8 if K <= halfCount { 9 return kthGrammar(N-1, rm == 0 ? halfCount : rm) 10 } else { 11 return kthGrammar(N-1, rm == 0 ? halfCount : rm) == 0 ? 1 : 0 12 } 13 } 14 }

 

转载于:https://www.cnblogs.com/strengthen/p/10541751.html