SJCHEN

时光，不会辜负每一个平静努力的人

0%

发表于 分类于 ， Waline： 本文字数： 1.4k 阅读时长 ≈ 1 分钟

LC最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例1:

输入：["flower","flow","flight"]

输出：[fl]

示例2:

输入：["dog","racecar","car"]

输出：""

解释：输入不存在公共前缀

说明：

所有人输入只包含小写字母a-z。

阅读全文 »

发表于 分类于 ， Waline： 本文字数： 3.9k 阅读时长 ≈ 4 分钟

[[toc]]

115. 不同的子序列

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）

题目数据保证答案符合 32 位带符号整数范围。

示例1：

输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下图所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit

示例2:

输入：s = "babgbag", t = "bag"
输出：5
解释：
如下图所示, 有 5 种可以从 s 中得到 "bag" 的方案,
babgbag
babgbag
babgbag
babgbag
babgbag

阅读全文 »

发表于 分类于 ， Waline： 本文字数： 728 阅读时长 ≈ 1 分钟

118. 杨辉三角

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例1:

输入：numRows = 5
输出：[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

阅读全文 »

发表于 分类于 ， Waline： 本文字数： 2.4k 阅读时长 ≈ 2 分钟

[[toc]] # 91. 解码方法

一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：

"AAJF" ，将消息分组为 (1 1 10 6) "KJF" ，将消息分组为 (11 10 6) 注意，消息不能分组为  (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。

给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。

题目数据保证答案肯定是一个 32 位 的整数。

示例1:

输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。

输入：s = "226"
输出：3
解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

阅读全文 »

发表于 分类于 ， Waline： 本文字数： 3.1k 阅读时长 ≈ 3 分钟

62. 不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例：

输入：m = 3, n = 7 输出：28

输入：m = 3, n = 2 输出：3 解释： 从左上角开始，总共有 3 条路径可以到达右下角。 1. 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 3. 向下 -> 向右 -> 向下

阅读全文 »

发表于 分类于 ， Waline： 本文字数： 3.8k 阅读时长 ≈ 3 分钟

[[toc]]

差分数组

前面我们了解了前缀和

前缀和主要适用于原始数组不会被修改的情况下，频繁查询某个区间的累加和

差分数组主要适用于频繁对原始数组的某个区间的元素进行增减

比如我们给定一个数组nums

0 1 2 3 4
nums 8 2 6 3 1

要求给区间nums[2..6]全部加1，再给nums[3..9]全部减3，再给nums[0..4]全部加2，最后问nums数组的值为多少？

常规做法就是每次在所给区间循环加上或者减去给定的值，时间复杂度为：O(m)，效率比较低。

这时就需要用到差分数组，我们先对nums数组构造一个diff差分数组，diff[i] = nums[i] - nums[i-1]

阅读全文 »

发表于 更新于 分类于 Waline： 本文字数： 1.7k 阅读时长 ≈ 2 分钟

寻找数组的中心索引

题目链接

给定一个整数类型的数组 nums，请编写一个能够返回数组 “中心索引” 的方法。

我们是这样定义数组 中心索引 的：数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。

如果数组不存在中心索引，那么我们应该返回 -1。如果数组有多个中心索引，那么我们应该返回最靠近左边的那一个。

阅读全文 »

发表于 更新于 分类于 ， Waline： 本文字数： 2.6k 阅读时长 ≈ 2 分钟

题目链接

题目描述

有一个仅由数字0与1组成的n×n格迷宫。若你位于一格0上，那么你可以移动到相邻44格中的某一格1上，同样若你位于一格1上，那么你可以移动到相邻44格中的某一格0上。

你的任务是：对于给定的迷宫，询问从某一格开始能移动到多少个格子（包含自身）。

输入输出格式

输入格式：

第1行为两个正整数n,m。

下面n行，每行n个字符，字符只可能是0或者1，字符之间没有空格。

接下来m行，每行2个用空格分隔的正整数i,j，对应了迷宫中第i行第j列的一个格子，询问从这一格开始能移动到多少格。

输出格式：

m行，对于每个询问输出相应答案。

阅读全文 »