C++实现LeetCode(38.计数和读法)
[LeetCode] 38. Count and Say 计数和读法
The count-and-say sequence is the sequence of integers with the first five terms as following:
1. 1
2. 11
3. 21
4. 1211
5. 111221
1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.
Given an integer n where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence.
Note: Each term of the sequence of integers will be represented as a string.
Example 1:
Input: 1
Output: "1"
Example 2:
Input: 4
Output: "1211"
这道计数和读法问题还是第一次遇到,看似挺复杂,其实仔细一看,算法很简单,就是对于前一个数,找出相同元素的个数,把个数和该元素存到新的 string 里。代码如下:
class Solution { public: string countAndSay(int n) { if (n <= 0) return ""; string res = "1"; while (--n) { string cur = ""; for (int i = 0; i < res.size(); ++i) { int cnt = 1; while (i + 1 < res.size() && res[i] == res[i + 1]) { ++cnt; ++i; } cur += to_string(cnt) + res[i]; } res = cur; } return res; } };
打印出了前 12 个数字,发现一个很有意思的现象,不管打印到后面多少位,出现的数字只是由 1, 2 和3 组成,前十二个数字如下:
1
1 1
2 1
1 2 1 1
1 1 1 2 2 1
3 1 2 2 1 1
1 3 1 1 2 2 2 1
1 1 1 3 2 1 3 2 1 1
3 1 1 3 1 2 1 1 1 3 1 2 2 1
1 3 2 1 1 3 1 1 1 2 3 1 1 3 1 1 2 2 1 1
1 1 1 3 1 2 2 1 1 3 3 1 1 2 1 3 2 1 1 3 2 1 2 2 2 1
3 1 1 3 1 1 2 2 2 1 2 3 2 1 1 2 1 1 1 3 1 2 2 1 1 3 1 2 1 1 3 2 1 1
到此这篇关于C++实现LeetCode(38.计数和读法)的文章就介绍到这了,更多相关C++实现计数和读法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!
相关推荐
-
C++实现LeetCode(39.组合之和)
[LeetCode] 39. Combination Sum 组合之和 Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target. The same repeated number may b
-
C++实现LeetCode(113.二叉树路径之和之二)
[LeetCode] 113. Path Sum II 二叉树路径之和之二 Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum. For example: Given the below binary tree and sum = 22, 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7
-
C++实现LeetCode(47.全排列之二)
[LeetCode] 47. Permutations II 全排列之二 Given a collection of numbers that might contain duplicates, return all possible unique permutations. Example: Input: [1,1,2] Output: [ [1,1,2], [1,2,1], [2,1,1] ] 这道题是之前那道 Permutations 的延伸,由于输入数组有可能出现重复数字,如果按照之前的
-
C++实现LeetCode(Combinations 组合项)
[LeetCode] Combinations 组合项 Given two integers n and k, return all possible combinations of k numbers out of 1 ... n. For example, If n = 4 and k = 2, a solution is: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ] 这道题让求1到n共n个数字里k个数的组合数的所有情况,还是要用深度优先搜索D
-
C++实现LeetCode(46.全排列)
[LeetCode] 46. Permutations 全排列 Given a collection of distinct integers, return all possible permutations. Example: Input: [1,2,3] Output: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 这道题是求全排列问题,给的输入数组没有重复项,这跟之前的那道 Combinations 和类似,解法基本相同
-
C++实现LeetCode(51.N皇后问题)
[LeetCode] 51. N-Queens N皇后问题 The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other. Given an integer n, return all distinct solutions to the n-queens puzzle. Each solution contains a di
-
C++实现LeetCode(90.子集合之二)
[LeetCode] 90. Subsets II 子集合之二 Given a collection of integers that might contain duplicates, S, return all possible subsets. Note: Elements in a subset must be in non-descending order. The solution set must not contain duplicate subsets. For example
-
C++实现LeetCode(40.组合之和之二)
[LeetCode] 40. Combination Sum II 组合之和之二 Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target. Each number in candidates may only be u
-
C++实现LeetCode(38.计数和读法)
[LeetCode] 38. Count and Say 计数和读法 The count-and-say sequence is the sequence of integers with the first five terms as following: 1. 1 2. 11 3. 21 4. 1211 5. 111221 1 is read off as "one 1" or 11. 11 is read off as "two
-
Redis精确去重计数方法(咆哮位图)
前言 如果要统计一篇文章的阅读量,可以直接使用 Redis 的 incr 指令来完成.如果要求阅读量必须按用户去重,那就可以使用 set 来记录阅读了这篇文章的所有用户 id,获取 set 集合的长度就是去重阅读量.但是如果爆款文章阅读量太大,set 会浪费太多存储空间.这时候我们就要使用 Redis 提供的 HyperLogLog 数据结构来代替 set,它只会占用最多 12k 的存储空间就可以完成海量的去重统计.但是它牺牲了准确度,它是模糊计数,误差率约为 0.81%. 那么有没有一种不怎么
-
两种方法实现mysql分组计数,范围汇总
第一种:常规操作 SELECT SUM(ddd) AS count_days, CASE WHEN aa.days >= 1 AND aa.days < 3 THEN '1-3' WHEN aa.days >= 3 AND aa.days < 5 THEN '5-3' ELSE '5+' END AS groupby_days FROM ( SELECT SUM(1) AS ddd, days FROM tour_group GROUP BY days ) AS aa GROUP
-
Java实现LeetCode(报数)
题目如下: public String countAndSay(int n) { if(n == 1){ return "1"; } //递归调用,然后对字符串处理 String str = countAndSay(n-1) + "*";//为了str末尾的标记,方便循环读数 char[] c = str.toCharArray(); int count = 1; StringBuilder s = new StringBuilder(); for(int i =
-
C++实现LeetCode(倒置链表之二)
[LeetCode] 92. Reverse Linked List II 倒置链表之二 Reverse a linked list from position m to n. Do it in one-pass. Note: 1 ≤ m ≤ n ≤ length of list. Example: Input: 1->2->3->4->5->NULL, m = 2, n = 4 Output: 1->4->3->2->5->NULL 很奇怪为何
-
C++实现LeetCode(23.合并k个有序链表)
[LeetCode] 23. Merge k Sorted Lists 合并k个有序链表 Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. Example: Input: [ 1->4->5, 1->3->4, 2->6 ] Output: 1->1->2->3->4->4->5->6 这
-
C++实现LeetCode(29.两数相除)
[LeetCode] 29. Divide Two Integers 两数相除 Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator. Return the quotient after dividing dividend by divisor. The integer division should truncate
-
C++实现LeetCode(27.移除元素)
[LeetCode] 27. Remove Element 移除元素 Given an array nums and a value val, remove all instances of that value in-place and return the new length. Do not allocate extra space for another array, you must do this by modifying the input array in-place with
-
C++实现LeetCode(75.颜色排序)
[LeetCode] 75. Sort Colors 颜色排序 Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2
-
C++实现LeetCode(104.二叉树的最大深度)
[LeetCode] 104. Maximum Depth of Binary Tree 二叉树的最大深度 Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. Note: A leaf is a node with no child
随机推荐
- 详解Ruby中的循环语句的用法
- VBS For Next循环的一些细节
- VBScript 监控并结束指定进程的代码
- IIS7.5 Error Code 0x8007007e HTTP 错误 500.19的解决方法
- Web.config(应用程序的配置信息)总结
- 详解微信小程序 页面跳转 传递参数
- jquery获取URL中参数解决中文乱码问题的两种方法
- 通过实例认识MySQL中前缀索引的用法
- Mysql删除重复数据保留最小的id 的解决方法
- javascript去除字符串左右两端的空格
- 使用JavaScript判断手机浏览器是横屏还是竖屏问题
- 详解Python当中的字符串和编码
- jQuery拖拽插件gridster使用指南
- jQuery ajax应用总结
- jQuery多级联动下拉插件chained用法示例
- javascript for循环从入门到偏门(效率优化+奇特用法)
- 安全技术—RSA公钥密码体制安全性分析
- 在NodeJS中启用ECMAScript 6小结(windos以及Linux)
- IIS 6.0的web园 最大工作进程数
- java中如何获取时间戳的方法实例