LeetCode实战:子问题分析

主要推送关于对算法的思考以及应用的消息。培养思维能力,注重过程,挖掘背后的原理,刨根问底。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎您的关注。

记录下,LeetCode Contest 56 题1,包括题目意思,和解题思路。 这个题目上来读了好几遍才理解它的意思,理解意思后,这个题目就比较简单了。 不过为了提升算法效率,进一步做了一些优化,优化后 beat 100% submission,重点看下优化思路吧。

01

原题解读

We have two special characters. The first character can be represented by one bit 0. The second character can be represented by two bits (10 or 11).

Now given a string represented by several bits. Return whether the last character must be a one-bit character or not. The given string will always end with a zero.

Example 1:

Input: bits = [1, 0, 0]
Output: True
Explanation: 
The only way to decode it is two-bit character and one-bit character. 
So the last character is one-bit character.

Example 2:

Input: bits = [1, 1, 1, 0] 
Output: False
Explanation: 
The only way to decode it is two-bit character and two-bit character. 
So the last character is NOT one-bit character.

题目的中文意思:

我们有两个特殊的字符,第一个字符可以用一位来表达:0;第二个字符用两位表达,要么为10,要么为11。

给出一个字符串,判断最后一位(位于最右侧的位)是不是一定为0。

LeetCode一般给出的例子不是瞎举的,而是非常有代表性的2个例子。

第一个例子 [1 0 0],显然 第一个字符必须为1和0搭配为10(这是题目中第二个字符),所以第二个字符也就是最后一个字符必然为 0;

第一个例子 [1 1 1 0],显然 第一个字符必须为1和1搭配为11,并且第二个字符必须为10,所以最后一个字符是10,而不是0 。

02

分析题目

设 bits为 n 位, 则如果判断最后一位是0的话,即bits[n-1]=0,那么

bits[n-2] 只可能为两种情况:

  1. 如果bits.length=1,则只含有一个0字符,一定是;
  2. bits[n-2] = 0,即 ...00,则这种结构表明一定是以0结尾;
  3. bits[n-2]=1bits[n-3]=0,即 ...010,这种结构一定不是最后一位为0;
  4. bits[n-2]=1bits[n-3]=1,即 ...110,这种情况不能确定最后一位一定是0 ,像题目中给出的例子 1110 便是其中一个最后一位不为0的代表,因此只有这种情况才需要遍历

遍历情况分析,如果遍历时,i 能等于 n-1,表示最后一位为0,并且 return;等遍历结束时,还没返回,表明已经越过最后一位,返回 false 。

经过上述分析后,代码如下所示:

public class Solution { public bool IsOneBitCharacter(int[] bits) { int i=0; if(bits.Length==1) //情况1 return true; if(bits[bits.Length-2]==0) //情况2 return true; if(bits.Length >2 && bits[bits.Length-2]==1 && bits[bits.Length-3]==0) //情况3 return false; //情况4 while(i<bits.Length){ if(bits[i]==1){ i+=2; } else i++; if(i==bits.Length-1) return true; } return false; } }

算法的时间复杂度为 O(n),空间复杂度为 O(1) 。

Beat 100% submission

请记住:每天一小步,日积月累一大步!

主要推送关于对算法的思考以及应用的消息。培养思维能力,注重过程,挖掘背后的原理,刨根问底。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎您的关注。

原文发布于微信公众号 - 算法channel(alg-channel)

原文发表时间:2017-11-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏从流域到海域

Python 函数

Python的函数与其他语言的函数概念上是一致的,只是形式上有所不同。在面向过程的编程语言中(C语言),函数是代码的基本组成形式,是功能的基本模块;在面向...

21770
来自专栏菩提树下的杨过

as3:Function以及call,apply

Function类在as3中是直接从Object继承下来的,通常开发者定义的每一个function,均可以认为是Function类的一个实例。  如果硬要跟c#...

21290
来自专栏chenjx85的技术专栏

leetcode-561-Array Partition I

19670
来自专栏开源优测

Python3快速排序

Python3快速排序 概述 快速排序(Quicksort)是对冒泡排序的一种改进。 快速排序由C. A. R. Hoare在1962年提出。 通过一趟排序将要...

43060
来自专栏Brian

C++11基础学习系列一

---- 概述 C++11标准越来越趋于稳定和成熟,国外c++11如火如荼而国内却依然处于观望期。每当提到C++很多程序员都很抵触,特别是学术界的呼声更高一些。...

28240
来自专栏猿人谷

常见排序算法分析

一.常见排序算法的实现 1.冒泡排序 冒泡排序是非常容易理解和实现,,以从小到大排序举例: 设数组长度为N。 1.比较相邻的前后二个数据,如果前面数据大于后面...

20780
来自专栏程序员互动联盟

【编程基础】Java面向对象基础知识

前言: 前面一系列文章讲了Java的一些语法基础知识、Java中的数据类型和Java中的运算符,基本上都是学习Java语言的基础知识,从这一讲开始将会逐步介绍J...

35250
来自专栏大闲人柴毛毛

剑指offer——年龄排序问题

题目:对某公司所有员工的年龄进行排序,要求时间复杂度为O(n) 分析:         在已有的排序算法中,性能最好的是快速排序,但是他在最好的情况下时间复杂度...

31860
来自专栏大闲人柴毛毛

剑指 offer代码解析——面试题29数组中出线次数超过一半的数字

题目:数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。 分析:本题最直观的思路就是分别统计数组中每个数出现的次数,然后求出最大值,判断是否超过...

34760
来自专栏追不上乌龟的兔子

介绍一些Python str类的方法

上面的代码正确的返回了'0.333333',但是当x = 1 / 2时,由于小数只有一位,这个方案的结果就是'0.5'了,而不是预期中的'0.500000'。

19540

扫码关注云+社区

领取腾讯云代金券