Java实现 LeetCode 481 神奇字符串
2023-09-14 08:58:04 时间
481. 神奇字符串
神奇的字符串 S 只包含 ‘1’ 和 ‘2’,并遵守以下规则:
字符串 S 是神奇的,因为串联字符 ‘1’ 和 ‘2’ 的连续出现次数会生成字符串 S 本身。
字符串 S 的前几个元素如下:S = “1221121221221121122 …”
如果我们将 S 中连续的 1 和 2 进行分组,它将变成:
1 22 11 2 1 22 1 22 11 2 11 22 …
并且每个组中 ‘1’ 或 ‘2’ 的出现次数分别是:
1 2 2 1 1 2 1 2 2 1 2 2 …
你可以看到上面的出现次数就是 S 本身。
给定一个整数 N 作为输入,返回神奇字符串 S 中前 N 个数字中的 ‘1’ 的数目。
注意:N 不会超过 100,000。
示例:
输入:6
输出:3
解释:神奇字符串 S 的前 6 个元素是 “12211”,它包含三个 1,因此返回 3。
class Solution {
public int magicalString(int n) {
List<Integer> s2=new ArrayList<Integer>();
s2.add(1);s2.add(-1);s2.add(-1);
int key=1;
for (int i = 2; i < n; i++) {
if(s2.get(i)==1)
s2.add(key);
if(s2.get(i)==-1){
s2.add(key);
s2.add(key);
}
key=-key;
}
key = 0;
for (int i = 0;i<n;i++) {
if(s2.get(i)==1)
key++;
}
return key;
}
}
相关文章
- Java实现 LeetCode 813 最大平均值和的分组 (DFS+DP记忆化搜索)
- Java实现 LeetCode 806 写字符串需要的行数 (暴力模拟)
- Java实现 LeetCode 721 账户合并(并查集)
- Java实现 LeetCode 690 员工的重要性(简易递归)
- Java实现 LeetCode 687 最长同值路径(递归)
- Java实现 LeetCode 609 在系统中查找重复文件(阅读理解+暴力大法)
- Java实现 LeetCode 583 两个字符串的删除操作(求最长公共子序列问题)
- Java实现 LeetCode 575 分糖果(看看是你的长度小还是我的种类少)
- Java实现 LeetCode 551 学生出勤记录 I(暴力大法好)
- Java实现 LeetCode 522 最长特殊序列 II(查找最长的非子序列的长度)
- Java实现 LeetCode 513 找树左下角的值
- Java实现 LeetCode 452 用最少数量的箭引爆气球
- Java实现 LeetCode 416 分割等和子集
- Java实现 LeetCode 378 有序矩阵中第K小的元素
- Java实现 LeetCode 328 奇偶链表
- Java实现 LeetCode 292 Nim游戏
- Java实现 LeetCode 224 基本计算器
- Java实现 LeetCode 200 岛屿数量
- Java实现 LeetCode 173 二叉搜索树迭代器
- Java实现 LeetCode 119 杨辉三角 II
- Java实现 LeetCode 63 不同路径 II(二)
- Java实现 LeetCode 60 第k个排列
- Java实现 LeetCode 37 解数独
- Java实现 LeetCode 29 两数相除
- Java实现 LeetCode 140 单词拆分II
- Java实现 LeetCode 242 有效的字母异位词
- 【JAVA】java中split以"." 、""、“|”分隔字符串
- Simple Logging Facade for Java (SLF4J)作用(java日志框架)