「38.外观数列」题解

4/11/2021 LeetCodeAlgorithm

# 38. 外观数列 (opens new window)

# 题目描述

给定一个正整数 n ,输出外观数列的第 n 项。

「外观数列」是一个整数序列,从数字 1 开始,序列中的每一项都是对前一项的描述。

你可以将其视作是由递归公式定义的数字字符串序列:

  • countAndSay(1) = "1"
  • countAndSay(n) 是对 countAndSay(n-1) 的描述,然后转换成另一个数字字符串。

前五项如下:

1.     1
2.     11
3.     21
4.     1211
5.     111221
第一项是数字 1
描述前一项,这个数是 1 即 “ 一 个 1 ”,记作 "11"
描述前一项,这个数是 11 即 “ 二 个 1 ” ,记作 "21"
描述前一项,这个数是 21 即 “ 一 个 2 + 一 个 1 ” ,记作 "1211"
描述前一项,这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ,记作 "111221"

描述 一个数字字符串,首先要将字符串分割为 最小 数量的组,每个组都由连续的最多 相同字符 组成。然后对于每个组,先描述字符的数量,然后描述字符,形成一个描述组。要将描述转换为数字字符串,先将每组中的字符数量用数字替换,再将所有描述组连接起来。

例如,数字字符串 "3322251" 的描述如下图:

img

示例 1:

输入:n = 1
输出:"1"
解释:这是一个基本样例。

示例 2:

输入:n = 4
输出:"1211"
解释:
countAndSay(1) = "1"
countAndSay(2) = 读 "1" = 一 个 1 = "11"
countAndSay(3) = 读 "11" = 二 个 1 = "21"
countAndSay(4) = 读 "21" = 一 个 2 + 一 个 1 = "12" + "11" = "1211"

提示:

  • 1 <= n <= 30

相关信息

  • 难度:简单
  • 标签:字符串

# 题目解释

由于本题目的描述相对复杂,我在读题的时候就没有很好地理解题意,现给出一个相对简洁的题目描述:

  1. 1
    
  2. 11
    
  3. 21
    
  4. 1211
    
  5. 111221
    

一步一步来

  1. 给一个数,这个数是 1
  2. 描述上一步的数,这个数是 1 即一个 1,故写作 11
  3. 描述上一步的数,这个数是 11 即两个 1,故写作 21
  4. 描述上一步的数,这个数是 21 即一个 2 一个 1,故写作 12-11
  5. 描述上一步的数,这个数是 1211 即一个 1 一个 2 两个 1,故写作 11-12-21

-----来自原题评论区的精华评论。

# 题解

根据上边的题目解释,不知你有没有觉得有些眼熟?是否有想起斐波拉契数列?这计算过程可以说几乎一致,只是详细的计算方法不同而已。既然与斐波拉契数列相似,那么大体的解答方法也是一样的,通过递归或者迭代的方法来完成。但是由于本题主要的操作数据对象是字符串,所以信息的计算过程也涉及到使用字符的统计,可以考虑使用正则表达式。

# 方法一:递归

# JavaScript 实现

# 递归+双指针版本:
/*
执行用时: 88 ms
内存消耗: 40.6 MB
*/

var countAndSay = function (n) {
  if (n == 1) return "1";
  let temp = countAndSay(n - 1); //递归调用
  let out = "",
    right = 0,
    left = 0;
  while (right < temp.length) {
    while (temp[right] === temp[left] && right < temp.length) {
      right++;
    }
    //使用双指针来统计相邻相同字符的数量
    out += (right - left).toString() + temp[left];
    left = right;
  }
  return out;
};
# 递归+正则表达式版本:
# String.match() + for(){}
/*
执行用时: 92 ms
内存消耗: 41.1 MB
*/
var countAndSay = function (n) {
  if (n == 1) return "1";
  let temp = countAndSay(n - 1).match(/(\d)\1*/g); //递归且对返回值使用正则表达式匹配
  //String.match(RegEx):会返回一个包含所有匹配值的数组。
  // /(\d)\1*/g 这个正则表示,全局匹配,匹配一位数字或者匹配相同的多位数字,
  let out = "";
  for (let i = 0; i < temp.length; i++) {
    //这段循环是用于积累描述,返回新的描述值。
    //可以考虑使用Array.forEach() API 替代。
    out += temp[i].length + temp[i][0];
  }
  return out;
};
# String.match() + Array.reduce()
/*
执行用时: 88 ms
内存消耗: 40.7 MB
*/
var countAndSay = function (n) {
  if (n == 1) return "1";
  let temp = countAndSay(n - 1).match(/(\d)\1*/g);
  return temp.reduce((pre, val, index) => pre + val.length + val[0], "");
  //由于循环累计,所以可以使用 reduce 替代。
};
/*
执行用时: 92 ms
内存消耗: 40.9 MB
*/
//一行代码搞定版本
var countAndSay = function (n) {
  return n === 1
    ? "1"
    : countAndSay(n - 1)
        .match(/(\d)\1*/g)
        .reduce((pre, val, index) => pre + val.length + val[0], "");
};
# String.replace()

String.replace 方法可以直接完成从正则匹配到替换的过程,就像是 replace 替代了上边的 match 和 reduce 两个 APi, 详细用法可以参考 MDN 文档 (opens new window)

/*
执行用时: 108 ms
内存消耗: 41.2 MB
*/
var countAndSay = function (n) {
  return n === 1
    ? "1"
    : countAndSay(n - 1).replace(
        /(\d)\1*/g,
        (item) => `${item.length}${item[0]}`
      ); //这里用了 ES6 的模板字符串语法
};

等价于

/**
执行用时: 88 ms
内存消耗: 41.2 MB
*/
//不用模板字符串,运行时间还显著提升了,玄学。
var countAndSay = function (n) {
  return n === 1
    ? "1"
    : countAndSay(n - 1).replace(
        /(\d)\1*/g,
        (item) => "" + item.length + item[0]
      );
};

# 方法二:循环

# JavaScript 实现
# 循环+双指针
/**
执行用时: 96 ms
内存消耗: 41 MB
*/
var countAndSay = function (n) {
  let out = "1";
  while (--n) {
    let outTemp = "";
    let right = 0,
      left = 0;
    while (right < out.length) {
      while (out[right] === out[left] && right < out.length) {
        right++;
      }
      outTemp += (right - left).toString() + out[left];
      left = right;
    }
    out = outTemp;
  }
  return out;
};
# 循环+ replace()
/*
执行用时: 84 ms
内存消耗: 41.3 MB
*/
var countAndSay = function (n) {
  let out = "1";
  for (let i = 1; i < n; i++) {
    out = out.replace(/(\d)\1*/g, (item) => `${item.length}${item[0]}`);
  }
  return out;
};

# 总结

由此可见,本题的关键在于两个地方:

  1. 如何处理上一种情况和下一种情况的转换关系?使用递归还是循环?

  2. 如何统计相邻相同数字的长度?使用双指针还是正则匹配?

最后,如果本文对你有所帮助的话,不要忘了给我点赞三连嗷~感谢

# 全部代码

/*
 * @lc app=leetcode.cn id=38 lang=javascript
 *
 * [38] 外观数列
 *
 * https://leetcode-cn.com/problems/count-and-say/description/
 *
 * algorithms
 * Medium (57.92%)
 * Likes:    734
 * Dislikes: 0
 * Total Accepted:    208.5K
 * Total Submissions: 360K
 * Testcase Example:  '1'
 *
 * 给定一个正整数 n ,输出外观数列的第 n 项。
 * 
 * 「外观数列」是一个整数序列,从数字 1 开始,序列中的每一项都是对前一项的描述。
 * 
 * 你可以将其视作是由递归公式定义的数字字符串序列:
 * 
 * 
 * countAndSay(1) = "1"
 * countAndSay(n) 是对 countAndSay(n-1) 的描述,然后转换成另一个数字字符串。
 * 
 * 
 * 前五项如下:
 * 
 * 
 * 1.     1
 * 2.     11
 * 3.     21
 * 4.     1211
 * 5.     111221
 * 第一项是数字 1 
 * 描述前一项,这个数是 1 即 “ 一 个 1 ”,记作 "11"
 * 描述前一项,这个数是 11 即 “ 二 个 1 ” ,记作 "21"
 * 描述前一项,这个数是 21 即 “ 一 个 2 + 一 个 1 ” ,记作 "1211"
 * 描述前一项,这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ,记作 "111221"
 * 
 * 
 * 要 描述 一个数字字符串,首先要将字符串分割为 最小 数量的组,每个组都由连续的最多 相同字符
 * 组成。然后对于每个组,先描述字符的数量,然后描述字符,形成一个描述组。要将描述转换为数字字符串,先将每组中的字符数量用数字替换,再将所有描述组连接起来。
 * 
 * 例如,数字字符串 "3322251" 的描述如下图:
 * 
 * 
 * 
 * 
 * 
 * 
 * 示例 1:
 * 
 * 
 * 输入:n = 1
 * 输出:"1"
 * 解释:这是一个基本样例。
 * 
 * 
 * 示例 2:
 * 
 * 
 * 输入:n = 4
 * 输出:"1211"
 * 解释:
 * countAndSay(1) = "1"
 * countAndSay(2) = 读 "1" = 一 个 1 = "11"
 * countAndSay(3) = 读 "11" = 二 个 1 = "21"
 * countAndSay(4) = 读 "21" = 一 个 2 + 一 个 1 = "12" + "11" = "1211"
 * 
 * 
 * 
 * 
 * 提示:
 * 
 * 
 * 1 
 * 
 * 
 */

// @lc code=start
/**
 * @param {number} n
 * @return {string}
 */
var countAndSay = function(n) {
    let prev = '1'
    for(let i = 1; i < n; i++){
        prev = prev.replace(/(\d)\1*/g, item =>`${item.length}${item[0]}`)
    }
    return prev
}
// @lc code=end

var countAndSay = function(n) {
    if(n==1)return'1';
    let temp=countAndSay(n-1)//递归调用
    let out='',right=0,left=0;
    while(right<temp.length){
        while(temp[right]===temp[left]&&right<temp.length){
            right++;
        }
      //使用双指针来统计相邻相同字符的数量
        out+=(right-left).toString()+temp[left];
        left=right;
    }
    return out;
};
var countAndSay = function(n) {
    if(n==1)return'1';
    let temp=countAndSay(n-1).match(/(\d)\1*/g)//递归且对返回值使用正则表达式匹配
//String.match(RegEx):会返回一个包含所有匹配值的数组。
// /(\d)\1*/g 这个正则表示,全局匹配,匹配一位数字或者匹配相同的多位数字,
    let out='';
    for(let i=0;i<temp.length;i++){
      //这段循环是用于积累描述,返回新的描述值。
      //可以考虑使用Array.forEach() API 替代。
        out+=temp[i].length+temp[i][0];
    }
    return out;
};

var countAndSay = function(n) {
    if(n==1)return'1';
    let temp=countAndSay(n-1).match(/(\d)\1*/g);
    return temp.reduce((pre,val,index)=>pre+val.length+val[0],''); 
  //由于循环累计,所以可以使用 reduce 替代。
};

//一行代码搞定版本
var countAndSay = function(n) {
    return n===1?'1':countAndSay(n-1).match(/(\d)\1*/g).reduce((pre,val,index)=>pre+val.length+val[0],'');
};

var countAndSay = function (n) {
    return n === 1 ? '1' : countAndSay(n - 1).replace(/(\d)\1*/g, item => `${item.length}${item[0]}`);//这里用了 ES6 的模板字符串语法
};

//不用模板字符串,运行时间还显著提升了,玄学。
var countAndSay = function (n) {
    return n === 1 ? '1' : countAndSay(n - 1).replace(/(\d)\1*/g, item => ""+item.length+item[0]);
};

var countAndSay = function(n) {
    let out='1'
        while(--n){
                let outTemp=''
                let right=0,left=0;
                while(right<out.length){
                    while(out[right]===out[left]&&right<out.length){
                        right++;
                    }
                    outTemp+=(right-left).toString()+out[left];
                    left=right;
                }
                out=outTemp
            }
        return out;
    };


//不得不说,这时间和空间都吊打前面的方法,真牛。
var countAndSay = function(n) {
    const dic = [
           "",
           "1",
           "11",
           "21",
           "1211",
           "111221",
           "312211",
           "13112221",
           "1113213211",
           "31131211131221",
           "13211311123113112211",
           "11131221133112132113212221",
           "3113112221232112111312211312113211",
           "1321132132111213122112311311222113111221131221",
           "11131221131211131231121113112221121321132132211331222113112211",
           "311311222113111231131112132112311321322112111312211312111322212311322113212221",
           "132113213221133112132113311211131221121321131211132221123113112221131112311332111213211322211312113211",
           "11131221131211132221232112111312212321123113112221121113122113111231133221121321132132211331121321231231121113122113322113111221131221",
           "31131122211311123113321112131221123113112211121312211213211321322112311311222113311213212322211211131221131211132221232112111312111213111213211231131122212322211331222113112211",
           "1321132132211331121321231231121113112221121321132122311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213122112311311123112111331121113122112132113213211121332212311322113212221",
           "11131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113121113123112112322111213211322211312113211",
           "311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122211311122122111312211213211312111322211213211321322113311213212322211231131122211311123113223112111311222112132113311213211221121332211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221131112311311121321122112132231121113122113322113111221131221",
           "132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113213221133122112231131122211211131221131112311332211211131221131211132221232112111312111213322112132113213221133112132113221321123113213221121113122123211211131221222112112322211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321322113311213211331121113122122211211132213211231131122212322211331222113112211",
           "111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122211331121321232221121113122113121113222123112221221321132132211231131122211331121321232221123113112221131112311332111213122112311311123112112322211211131221131211132221232112111312211322111312211213211312111322211231131122111213122112311311221132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322212321121113122123211231131122113221123113221113122112132113213211121332212311322113212221",
           "3113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213213211221113122113121113222112132113213221232112111312111213322112132113213221133112132123123112111311222112132113311213211221121332211231131122211311123113321112131221123113112221132231131122211211131221131112311332211213211321223112111311222112132113212221132221222112112322211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211132221121311121312211213211312111322211213211321322113311213212322211231131122211311123113321112131221123113112211121312211213211321222113222112132113223113112221121113122113121113123112112322111213211322211312113211",
           "132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132132211231232112311321322112311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133112132123123112111312111312212231131122211311123113322112111312211312111322111213122112311311123112112322211211131221131211132221232112111312111213111213211231132132211211131221232112111312212221121123222112132113213221133112132123123112111311222112132113213221132213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121132211332113221122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321231231121113112221121321132122311211131122211211131221131211322113322112111312211322132113213221123113112221131112311311121321122112132231121113122113322113111221131221",
           "1113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121113222112131112131221121321131211132221121321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121113222123211211131211121311121321123113111231131122112213211321322113311213212322211231131122211311123113223112111311222112132113311213211221121332211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122113221122112133221121113122113121113222123211211131211121311121321123113213221121113122113121113222113221113122113121113222112132113213221232112111312111213322112311311222113111221221113122112132113121113222112311311222113111221132221231221132221222112112322211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331121321232221123123211231132132211231131122211331121321232221123113112221131112311332111213122112311311123112112322211211131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112211322212322211231131122211322111312211312111322211213211321322113311213211331121113122122211211132213211231131122212322211331222113112211",
           "31131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321322123211211131211121332211231131122211311122122111312211213211312111322211231131122211311123113322112111331121113112221121113122113111231133221121113122113121113222123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221123113112221131112311332111213122112311311123112111331121113122112132113311213211321222122111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132122211322212221121123222112311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122211311123113322113223113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331221122311311222112111312211311123113322112132113213221133122211332111213112221133211322112211213322112111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122211331121321232221121113122113121122132112311321322112111312211312111322211213111213122112132113121113222112132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212311222122132113213221123113112221133112132123222112111312211312111322212321121113121112133221121311121312211213211312111322211213211321322123211211131211121332211213211321322113311213212312311211131122211213211331121321122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311222113111221221113122112132113121113222112132113213221133122211332111213322112132113213221132231131122211311123113322112111312211312111322212321121113122123211231131122113221123113221113122112132113213211121332212311322113212221",
           "13211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331121321232221123123211231132132211231131122211331121321232221123113112221131112311332111213122112311311123112112322211211131221131211132221232112111312211322111312211213211312111322211231131122111213122112311311221132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221232112111312211312113211223113112221131112311332111213122112311311123112112322211211131221131211132221232112111312211322111312211213211312111322211231131122111213122112311311221132211221121332211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321322113311213212322211322132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212311222122132113213221123113112221133112132123222112111312211312111322212311322123123112111321322123122113222122211211232221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112311311222113111231133211121321321122111312211312111322211213211321322123211211131211121332211231131122211311123113321112131221123113111231121123222112111331121113112221121113122113111231133221121113122113121113221112131221123113111231121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132132211331221122311311222112111312211311123113322112111312211312111322212311322123123112112322211211131221131211132221132213211321322113311213212322211231131122211311123113321112131221123113112211121312211213211321222113222112132113223113112221121113122113121113123112112322111213211322211312113211",
           "11131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211132221121311121312211213211312111322211213211321322113311213212322211231131122211311123113223112111311222112132113311213211221121332211211131221131211132221231122212213211321322112311311222113311213212322211211131221131211132221232112111312111213322112131112131221121321131211132221121321132132212321121113121112133221121321132132211331121321231231121113112221121321133112132112211213322112311311222113111231133211121312211231131122211322311311222112111312211311123113322112132113212231121113112221121321132122211322212221121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122111213122112311311222113111221131221221321132132211331121321231231121113112221121321133112132112211213322112311311222113111231133211121312211231131122211322311311222112111312211311123113322112132113212231121113112221121321132122211322212221121123222112311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122111213122112311311222112111331121113112221121113122113121113222112132113213221232112111312111213322112311311222113111221221113122112132113121113222112311311222113111221132221231221132221222112112322211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312111322212321121113121112133221132211131221131211132221232112111312111213322112132113213221133112132113221321123113213221121113122123211211131221222112112322211231131122211311123113321112132132112211131221131211132221121321132132212321121113121112133221123113112221131112311332111213211322111213111213211231131211132211121311222113321132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331121321232221123123211231132132211231131122211331121321232221123113112221131112311332111213122112311311123112112322211211131221131211132221232112111312211322111312211213211312111322211231131122111213122112311311221132211221121332211213211321322113311213212312311211131211131221223113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331121321231231121113112221121321133112132112211213322112312321123113213221123113112221133112132123222112311311222113111231132231121113112221121321133112132112211213322112311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122111213122112311311221132211221121332211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312111322212311222122132113213221123113112221133112132123222112311311222113111231133211121321132211121311121321122112133221123113112221131112311332211322111312211312111322212321121113121112133221121321132132211331121321231231121113112221121321132122311211131122211211131221131211322113322112111312211322132113213221123113112221131112311311121321122112132231121113122113322113111221131221",
           "3113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112311311222113111231133211121321321122111312211312111322211213211321322123211211131211121332211231131122211311123113321112131221123113111231121123222112111331121113112221121113122113111231133221121113122113121113221112131221123113111231121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321223112111311222112132113213221133122211311221122111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331222113321112131122211332113221122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213122112311311123112112322211322311311222113111231133211121312211231131112311211232221121113122113121113222123211211131221132211131221121321131211132221123113112211121312211231131122113221122112133221121321132132211331121321231231121113121113122122311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133112132123123112111312211322311211133112111312211213211311123113223112111321322123122113222122211211232221121113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121113222112131112131221121321131211132221121321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121113222123112221221321132132211231131122211331121321232221121113122113121113222123211211131211121332211213111213122112132113121113222112132113213221232112111312111213322112132113213221133112132123123112111311222112132113311213211221121332211231131122211311123113321112131221123113112221132231131122211211131221131112311332211213211321223112111311222112132113212221132221222112112322211211131221131211132221232112111312111213111213211231131112311311221122132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121311121312211213211312111322211213211321322123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132122311211131122211213211321222113222122211211232221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213213211221113122113121113222112132113213221232112111312111213322112132113213221133112132123123112111312211322311211133112111312212221121123222112132113213221133112132123222113223113112221131112311332111213122112311311123112112322211211131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112211322212322211231131122211322111312211312111322211213211321322113311213211331121113122122211211132213211231131122212322211331222113112211"
       ]
       return dic[n]
   };