leetcode剑指Offer第十天
把数字翻译成字符串medium 原题连接：把数字翻译成字符串
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
示例：
输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
限制：
0 <= num < 231
解题思路从尾到头进行动态规划，如果最后两位符合26以内的值F(N) = F(N-1)+F(N-2) 否则就只有 F(N) = F(N-1)
将0-25的数字编码为a-z的字符，既可以尝试单个数字去编码，又可以判断是否满足一定条件使得两个数字作为一个参数去编码
要求遍历完整个数字后看看有多少种编码手段。
初见题目的时候，我就觉得很像之前的青蛙跳台阶问题，可以选择一步步走， ...
leetcode剑指Offer第九天
连续子数组的最大和Easy 原题连接：连续子数组的最大和
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
示例：
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
限制：
1 <= arr.length <= 10^5
-100 <= arr[i] <= 100
解题思路将连续子数组视为一个数，这个数如果为负，加上后续的和一定小于后续，所以更新；如果为正，直接将后续值填入子数组再判断
循环判断完整个数组，在遍历时判断更新最大值
Java代码class Solution {
public int maxSubArray(int[] nums) {
int ans = Integer.MIN_VALUE;
int mid = 0;
for(int num : nums) {
...
leetcode剑指Offer第八天
斐波那契数列Easy 原题连接：斐波那契数列
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1F(N) = F(N - 1) + F(N - 2), 其中 N > 1.斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例：
输入：n = 2
输出：1
输入：n = 5
输出：5
限制：
0 <= n <= 100`
解题思路按照题目要求来，设定好最初的 0 和 1对象，对接下来的递归使用F(N) = F(N-1) + F(N-2)
Java代码class Solution {
public int fib(int n) {
if(n == 0) return 0;
if(n == 1) retur ...
leetcode剑指Offer第七天
树的子结构medium 原题连接：树的子结构
输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构， 即 A中有出现和B相同的结构和节点值。
例如:给定的树 A:
3 / \
4 5 / 1 2给定的树 B：
4 / 1返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。
示例：
输入：A = [1,2,3], B = [3,1]
输出：false
输入：A = [3,4,5,1,2], B = [4,1]
输出：true
限制：
0 <= 节点个数 <= 10000
解题思路证明一个树B是另一棵树A的子结构，按顺序要证明两点：
找到 B 的根节点在 A 中的位置
在根节点正确的前提下，只要 B 不为null的地方，A 都应该与其值相同
接下来就是分析遍历：
明确一个rootNode函数，作用是判断传入的B节点是否是A的子结构，与主方法不同的是，前者只要判断根节点这一个节点，后者需要遍历判断整个B子树。
...
leetcode剑指Offer第六天
了解今天的题目前，可以去我的博客看看二叉树和BFS（宽度优先遍历）知识：二叉树 | IT蛋的个人博客 (xcscx.github.io)
从上到下打印二叉树medium 原题连接：从上到下打印二叉树
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
示例：
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回 [3,9,20,15,7]
限制：
节点总数 <= 1000
解题思路二叉树的广度优先算法，因为输出时不需要考虑节点之间的关系，所以按照从上至下，从左至右的顺序存储输出即可
二叉树的BFS（宽度优先遍历）最常见的实现方式是利用队列进行存储，因为队列是先进先出，所以在遍历每一节点时将全部子节点填入队列，这样，在子节点全部遍历完成前，子节点的子节点不会被遍历到，依次类推，直到队列为空
Java代码/**
* Definition for a binary tree node.
* public class TreeNode {
* i ...
leetcode剑指Offer第五天
二维数组中的查找medium 原题连接：二维数组中的查找
在一个 n * m 的二维数组中，每一行都按照从左到右 非递减 的顺序排序，每一列都按照从上到下 非递减 的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
示例：
现有数组：
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。
限制：
0 <= n <= 10000 <= m <= 1000
解题思路在遍历数组时，需要注意遍历顺序和要求，如本题而言，如果总左上角开始遍历，你会发现其左侧和下侧都是大于本数，是一种暴力遍历
但是如果从右上角开始遍历，你会发现其左侧是小于自己的数，下面是大于自己的数，这就将数组划为了两个部分，取满足条件的一 ...
leetcode剑指Offer第四天
从数组中重复的数字Easy 原题连接：数组中重复的数字
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例：
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
提示：
2 <= n <= 100000
解题思路 方法一：已知总数组长度和数范围，直接创建对应大小的空数组，遍历总数组，增加空数组中对应位值，判断值是否到2，到2返回（简单，空数组浪费空间）
方法二：遍历总数组，利用HashSet存储以及查看过的数据，在每次遍历时查看HashSet是否已经存储，已存储就返回
方法三：遍历数组，将nums[n] 的位置放入 n 值，如果已经放过了却还需要放（重复）就返回该值。（时间复杂：O( N ), 空间复杂：O( 1 ) ）
方法三思路：数组长度为n，数字范围为1-n，因为存在重复项，所以数组与数字是存在一对多的关系。对于一个nums[ i ]，只有两种可能：nums[ i ] = i ...
leetcode剑指Offer第三天
替换空格Esay 原题连接：替换空格
请实现一个函数，把字符串 s 中的每个空格替换成”%20”。
示例：
输入：s = "We are happy."
输出："We%20are%20happy."
提示：
0 <= s 的长度 <= 10000
解题思路将字符对象转变为char[]类型对象，再遍历替换目标子字符串
最后组合成StringBuilder类型返回toString
不过，有现成方法就不用再重复造轮子了，理解万岁
// String中的replace方法
public String replace(char oldChar, char newChar) {
// 替换前后字符串一致就不用转换了
if (oldChar != newChar) {
// 判断对象是否是拉丁文（就是好不好转码）调用不同编码的实现方式做转换
String ret = isLatin1() ? StringLatin1.replace(value, oldC ...
leetcode剑指Offer第二天
从尾到头打印链表Easy 原题连接：剑指 Offer 06. 从尾到头打印链表
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）
示例：
输入：head = [1,3,2]
输出：[2,3,1]
提示：
0 <= 链表长度 <= 10000
解题思路 从尾到头输出，也就是遍历，时间复杂度最小为O(n)，那么空间复杂度越小越好
首先想到的是反转链表，空间复杂度为O(1)，时间复杂度O(n)
反转列表需要三个Node变量，记录上一个节点方便向前连接，记录当前节点用于改变next、指向第一个节点代表的前节点、记录原本的后续节点
先记录下一个节点的信息，再将next指向前节点，以此类推，反转链表
Java代码/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
* ...