Java C++题解leetcode672灯泡开关示例

目录
  • 题目要求
  • 思路：找规律
    • Java
    • C++
    • Rust
  • 总结

题目要求

思路：找规律

找到尽可能最精简的通项表达，今日参考：京城打工人

首先，归纳每个开关会影响的灯，其中(k=0,1,2,…)：

开关 反转灯编号
一 k
二 2k
三 2k+1
四 3k+1

可见灯以6盏为周期具有相同变化，所以以下只需要推导第一个周期里的6盏灯即可。

观察前6盏灯：

灯 开关
1 一、三、四
2 一、二
3 一、三
4 一、二、四
5 一、三
6 一、二

发现灯2、6和3、5分别受同样的开关影响，所以状态相同；

观察前4盏灯，发现灯1、3与灯2、4存在规律：

  • 当开关四按动次数为偶数时，两组灯状态分别相同；
  • 当开关四按动次数为奇数时，两组灯状态分别不同；
  • 所以根据其中一组灯的状态即可判断另一组。

因此，选择一组+另一组中的一盏，即可涵盖所有灯的状态。

因此选择观察前三盏灯即可预知所有明暗状态：

前三盏灯在不同按动次数中的状态如下：

发现在一次按动时会出现四种状态，两次按动时出现七种状态【缺少011状态】，三次及以上按动即可出现所有状态，共2^3=8种。

此时仅需枚举一盏灯和两盏灯时的状态即可，后续都与三盏相同：

  • 一盏灯仅可能有两种状态；
  • 两盏灯可能有四种状态；

但按动一次时仅会出现三种情况【缺少11状态】：

  • 将上述规律归纳为代码即可！

Java

class Solution {
    public int flipLights(int n, int presses) {
        if (presses == 0)
            return 1;
        if (n == 1)
            return 2;
        else if (n == 2)
            return presses == 1 ? 3 : 4;
        else
            return presses == 1 ? 4 : presses == 2 ? 7 : 8;
    }
}
  • 时间复杂度：O(1)O(1)O(1)
  • 空间复杂度：O(1)O(1)O(1)

C++

class Solution {
public:
    int flipLights(int n, int presses) {
        if (presses == 0)
            return 1;
        if (n == 1)
            return 2;
        else if (n == 2)
            return presses == 1 ? 3 : 4;
        else
            return presses == 1 ? 4 : presses == 2 ? 7 : 8;
    }
};
  • 时间复杂度：O(1)
  • 空间复杂度：O(1)

Rust

  • 浅学一下rust的match~
impl Solution {
    pub fn flip_lights(n: i32, presses: i32) -> i32 {
        if presses == 0 {
            return 1;
        }
        match n {
            1 => 2,
            2 => {
                match presses {
                    1 => 3,
                    _ => 4
                }
            },
            _ => {
                match presses {
                    1 => 4,
                    2 => 7,
                    _ => 8
                }
            },
        }
    }
}
  • 时间复杂度：O(1)
  • 空间复杂度：O(1)

总结

本来以为要DP或者生模拟，结果是数学思维找规律。

一道代码无敌简单，思路究极绕的题目，以至于推导完思路感觉就结束了【代码都没啥区别……】

以上就是Java C++题解leetcode672灯泡开关示例的详细内容，更多关于Java C++题解灯泡开关的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • Java C++ 算法题解leetcode145商品折扣后最终价格单调栈

    Java C++ 算法题解leetcode145商品折扣后最终价格单调栈

    目录 题目要求 思路一:暴力模拟 Java C++ Rust 思路二:单调栈 Java C++ Rust 题目要求 思路一:暴力模拟 由于数据范围不算离谱,所以直接遍历解决可行. Java class Solution { public int[] finalPrices(int[] prices) { int n = prices.length; int[] res = new int[n]; for (int i = 0; i < n; i++) { int discount = 0; fo

  • Java C++ 题解leetcode1619删除某些元素后数组均值

    Java C++ 题解leetcode1619删除某些元素后数组均值

    目录 题目要求 思路:模拟 Java C++ Rust 题目要求 思路:模拟 根据题意模拟即可: 排序然后只取中间符合条件的数加和然后计算均值: 根据给出的数组长度n为20的倍数,5%可直接取n/20: 两边各去除5%,则剩余长度为0.9n. Java class Solution { public double trimMean(int[] arr) { Arrays.sort(arr); int n = arr.length, tot = 0; for (int i = n / 20; i

  • Java C++题解leetcode消失的两个数字实例

    Java C++题解leetcode消失的两个数字实例

    目录 题目要求 思路:数学推导 Java C++ Rust 总结 题目要求 思路:数学推导 不重复的数组序列可以根据高斯公式计算所有元素的总和: 用当前数组长度加上两个缺失的数字可以得到所有数字长度,即可应用公式. 减去当前数组和即可得到缺失数字和sumsumsum: 两个缺失的数字分别位于m=sum2m=\frac{sum}{2}m=2sum两边: 遍历当前数组中所有小于(或大于)mmm的值,找到缺失的一个: 同样利用两个“和”的差值得到: 利用sumsumsum即可得到另一个. Java c

  • Java C++ 算法题解leetcode1582二进制矩阵特殊位置

    Java C++ 算法题解leetcode1582二进制矩阵特殊位置

    目录 题目要求 思路:模拟 Java C++ Rust 题目要求 思路:模拟 直接按题意模拟,先算出每行每列中“111”的个数,然后判断统计行列值均为111的位置即可. Java class Solution { public int numSpecial(int[][] mat) { int n = mat.length, m = mat[0].length; int res = 0; int[] row = new int[n], col = new int[m]; for (int i =

  • Java C++算法题解leetcode1592重新排列单词间的空格

    Java C++算法题解leetcode1592重新排列单词间的空格

    目录 题目要求 思路:模拟 Java C++ Rust 题目要求 思路:模拟 模拟就完了 统计空格数量和单词数量,计算单词间应有的空格数,将它们依次放入结果字符串,若有余数则在末尾进行填补. Java class Solution { public String reorderSpaces(String text) { int n = text.length(), spcnt = 0; List<String> words = new ArrayList<>(); for (int

  • Java C++题解leetcode判定是否为字符重排

    Java C++题解leetcode判定是否为字符重排

    目录 题目要求 思路一:排序 Java C++ Rust 思路二:词频统计 Java C++ Rust 总结 题目要求 思路一:排序 Java class Solution { public boolean CheckPermutation(String s1, String s2) { if(s1.length() != s2.length()) return false; char[] sort1 = s1.toCharArray(); Arrays.sort(sort1); char[]

  • Java C++题解leetcode672灯泡开关示例

    Java C++题解leetcode672灯泡开关示例

    目录 题目要求 思路:找规律 Java C++ Rust 总结 题目要求 思路:找规律 找到尽可能最精简的通项表达,今日参考:京城打工人 首先,归纳每个开关会影响的灯,其中(k=0,1,2,…): 开关 反转灯编号 一 k 二 2k 三 2k+1 四 3k+1 可见灯以6盏为周期具有相同变化,所以以下只需要推导第一个周期里的6盏灯即可. 观察前6盏灯: 灯 开关 1 一.三.四 2 一.二 3 一.三 4 一.二.四 5 一.三 6 一.二 发现灯2.6和3.5分别受同样的开关影响,所以状态相同

  • Java C++题解leetcode817链表组件示例

    Java C++题解leetcode817链表组件示例

    目录 题目要求 思路:模拟 Java C++ Rust 总结 题目要求 思路:模拟 Java class Solution { public int numComponents(ListNode head, int[] nums) { int res = 0; Set<Integer> set = new HashSet<>(); for (int x : nums) set.add(x); // 转存nums while (head != null) { if (set.cont

  • Java C++题解leetcode915分割数组示例

    目录 题目要求 思路一:两次遍历 Java C++ Rust 思路二:一次遍历 Java C++ Rust 题目要求 题目链接 思路一:两次遍历 题目的意思也就是左半边数组的最大值小于等于右半边数组的最小值,那么就找这个分界点就好: 首先从后向前遍历,找[i,n−1]里最小的值: 然后从前向后遍历,找[0,i]里最大的值: 然后找满足max[i]<=min[i+1]的分割点i: 可以将2.3两步结合为一步完成,由于iii从前向后不断增大,所以用后面(较大)的值覆盖更新之前的值. 找到分界点的索引

  • Java C++题解leetcode816模糊坐标示例

    目录 题目 思路:枚举 Java C++ Rust 总结 题目 题目要求 思路:枚举 既然要输出每种可能了,那必然不能“偷懒”,就暴力枚举咯: 在每个间隔处添加逗号: 定义函数decPnt(sta, end)分别列举逗号左右两边的数能构成的可能性: 同样在每个间隔添加小数点: 注意两种不合法的结构——前导0和后缀0: 不要忘记无小数点的整数版本, 分别组合两边的不同可能性,根据要求各式加入答案. Java class Solution { String str; public List<Stri

  • Java C++题解leetcode1441用栈操作构建数组示例

    目录 题目要求 思路:模拟[双指针] Java C++ Rust 题目要求 思路:模拟[双指针] 按题意模拟即可: 一个指针cur依次指向target中的每个元素,另一个指针i依次指向1∼n的数字: 对i所指向的每个数字进行Push操作,然后判断当前数字与target[cur]是否相等: 相等则判断下一个数字,同时将cur指向下一个元素: 否则需进行Pop操作. 过程中需注意cur的越界,当其越界则target构造完毕. Java class Solution { public List<Str

  • Java C++题解leetcode 1684统计一致字符串的数目示例

    目录 题目 思路:模拟 Java C++ Rust 题目 题目要求 思路:模拟 用一个哈希表记录可出现的字母,然后逐一遍历每个单词每个字母,符合条件则结果加一. Java class Solution { public int countConsistentStrings(String allowed, String[] words) { boolean[] hash = new boolean[26]; for (var a : allowed.toCharArray()) hash[a -

  • java算法题解牛客BM99顺时针旋转矩阵示例

    目录 题目描述 解题思路 实践代码 解法1 解法2 题目描述 BM99 顺时针旋转矩阵 描述 有一个NxN整数矩阵,请编写一个算法,将矩阵顺时针旋转90度. 给定一个NxN的矩阵,和矩阵的阶数N,请返回旋转后的NxN矩阵. 数据范围:0<n<300,矩阵中的值满足0≤val≤1000 要求:空间复杂度 O(N^2),时间复杂度 O(N^2) 进阶:空间复杂度 O(1),时间复杂度 O(N^2) 示例1输入:[[1,2,3],[4,5,6],[7,8,9]],3返回值:[[7,4,1],[8,5

  • Java使用桥接模式实现开关和电灯照明功能详解

    Java使用桥接模式实现开关和电灯照明功能详解

    本文实例讲述了Java使用桥接模式实现开关和电灯照明功能.分享给大家供大家参考,具体如下: 一.模式定义 桥接模式,也称桥梁模式,在软件系统中,由于自身的逻辑,具有两个或多个维度的变化,如何应对这种多维度的变化,桥接模式使得软件系统能够轻松地沿着多个方向进行变化,而又不引入额外的复杂度. 桥接模式三个关键词为:抽象化,实现化,脱耦 二.模式举例 1 桥接模式分析方法 我们借用电灯照明来说明该模式. 不使用继承,使用对象组合的方式,将开关和电灯的强关联关系变成弱关联关系. 2 桥接模式静态类模型

  • java开发RocketMQ生产者高可用示例详解

    目录 引言 1 消息 1.1 topic 1.2 Body 1.3 tag 1.4 key 1.5 延迟级别 2 生产者高可用 2.1 客户端保证生产者高可用 2.1.1 重试机制 2.1.2 客户端容错 2.2 Broker端保证生产者高可用 引言 前边两章说了点基础的,从这章开始,我们挖挖源码.看看RocketMQ是怎么工作的. 首先呢,这个生产者就是送孩子去码头的家长,孩子们呢,就是消息了. 我们看看消息孩子们都长啥样. 1 消息 public class Message implemen

  • 后端算法题解LeetCode前缀和示例详解

    目录 面试题 01.09. 字符串轮转 方法一:模拟 思路 题解 方法二:搜索子字符串 思路 题解 1480. 一维数组的动态和 方法一:前缀和 思路 题解 724. 寻找数组的中心下标 方法一:前缀和 思路 解题 面试题 01.09. 字符串轮转 面试题 01.09. 字符串轮转 难度:easy 字符串轮转.给定两个字符串 s1 和 s2,请编写代码检查 s2 是否为 s1 旋转而成(比如,waterbottle 是 erbottlewat 旋转后的字符串). 示例1: 输入:s1 = "wa

随机推荐