LeetCode学习计划：LeetCode 75-Level-1
DAY1
1480. 一维数组的动态和
问题描述
给你一个数组 nums 。数组「动态和」的计算公式为：runningSum[i] = sum(nums[0]…nums[i])。
请返回 nums 的动态和。
示例
输入：nums = [1,2,3,4]
输出：[1,3,6,10]
解释：动态和计算过程为 [1, 1+2, 1+2+3, 1+2+3+4] 。
解题思路
模拟法求解即可。
代码示例（JAVA）
class Solution {
public int[] runningSum(int[] nums) {
for (int i = 1; i < nums.length; i++) {
nums[i] += nums[i - 1];
}
return nums;
}
}
724. 寻找数组的中心下标
问题描述
给你一个整数数组 nums ，请计算数组的 中心下标 。
数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。
示例
示例1
输入：nums = [1, 7, 3, 6, 5, 6]
输出：3
解释：
中心下标是 3 。
左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，
右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。
解题思路
找到第一个中心位置，使得左边之和等于右边之和即可；可以算出左边之和后再算右边之和，右边之和=数组总和-中心位置的数-左边之和。
代码示例（JAVA）
class Solution {
public int pivotIndex(int[] nums) {
int total = 0;
for (int i = 0; i < nums.length; i++) {
total += nums[i];
}
int left = 0;
for (int i = 0; i < nums.length; i++) {
left = i == 0 ? 0 : left + nums[i - 1];
int right = total - nums[i] - left;
if (left == right) {
return i;
}
}
return -1;
}
}
DAY2
205. 同构字符串
问题描述
给定两个字符串 s 和 t ，判断它们是否是同构的。
如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。
每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。
示例
输入：s = "egg", t = "add"
输出：true
输入：s = "foo", t = "bar"
输出：false
解题思路
遍历字符串，将第一次出现的映射关系存到两个map中，一个是s映射到t，另一个是t映射到s；
如果遇到已处理过的映射字符，校验映射关系。
代码示例（JAVA）
class Solution {
public boolean isIsomorphic(String s, String t) {
Map<Character, Character> map1 = new HashMap<>(), map2 = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
char char1 = s.charAt(i);
char char2 = t.charAt(i);
if ((map1.get(char1) != null && map1.get(char1) != char2) || (map2.get(char2) != null && map2.get(char2) != char1)) {
return false;
}
map1.put(char1, char2);
map2.put(char2, char1);
}
return true;
}
}
392. 判断子序列
问题描述
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，ace是abcde的一个子序列，而aec不是）。
示例
输入：s = "abc", t = "ahbgdc"
输出：true
输入：s = "axc", t = "ahbgdc"
输出：false
解题思路
遍历一遍字符串s，并遍历一遍字符串t即可。
代码示例（JAVA）
class Solution {
public static boolean isSubsequence(String s, String t) {
char[] arrS = s.toCharArray();
char[] arrT = t.toCharArray();
int i = 0, j = 0;
for (; i < arrS.length; i++) {
for (; j < arrT.length; j++) {
if (arrS[i] == arrT[j]) {
break;
}
}
// j未超范围，说明找到了匹配的字符；超出范围，说明未找到
if (j < arrT.length) {
j++;
} else {
return false;
}
}
// s没验证完
if (i != arrS.length) {
return false;
}
return true;
}
}
DAY3
21. 合并两个有序链表
问题描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例
解题思路
这题很简单，就是简单的操作链表。
代码示例（JAVA）
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode preHead = new ListNode();
ListNode node = preHead;
while (list1 != null || list2 != null) {
if (list1 == null) {
node.next = list2;
break;
} else if (list2 == null) {
node.next = list1;
break;
} else {
int val1 = list1.val;
int val2 = list2.val;
if (val1 <= val2) {
node.next = list1;
node = node.next;
list1 = list1.next;
} else {
node.next = list2;
node = node.next;
list2 = list2.next;
}
}
}
return preHead.next;
}
}
206. 反转链表
问题描述
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例
解题思路
基本功，简单的指针、链表操作即可。
代码示例（JAVA）
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode cur = head;
ListNode newNode = null;
while (cur != null) {
ListNode nextNode = cur.next;
cur.next = newNode;
newNode = cur;
cur = nextNode;
}
return newNode;
}
}
DAY4
876. 链表的中间结点
问题描述
给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例
输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
解题思路
遍历一遍链表，获取链表的长度，算出中心节点的位置；再遍历一遍列表，找出中心节点。
代码示例（JAVA）
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode middleNode(ListNode head) {
int count = 0;
ListNode node = head;
while (node != null) {
count++;
node = node.next;
}
int index = count / 2;
node = head;
while (--index >= 0) {
node = node.next;
}
return node;
}
}
142. 环形链表 II
问题描述
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
示例
解题思路
这个问题分为两部分：证明环、找到环的入口。
之前用纯指针的方式解决过一次，“找寻环的入口”需要进行一定数学分析：
LeetCode：142. 环形链表 II
这次用一个取巧的方法，把链表中的结点都保存下来，如果发生了第一次重复保存，该结点就是环入口；如果遍历完了也没有发生重复保存，说明不是环。
代码示例（JAVA）
public class Solution {
public ListNode detectCycle(ListNode head) {
Set<ListNode> set = new HashSet<>();
ListNode node = head;
while (node != null) {
boolean res = set.add(node);
if (!res) {
return node;
}
node = node.next;
}
return null;
}
}
DAY5
121. 买卖股票的最佳时机
问题描述
给定一个数组 prices ，它的第i个元素 prices[i] 表示一支给定股票第i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
解题思路
可以模拟这样的场景进行求解：
如果你是一个一遇到高利润就抛的人；
在这个时间段内，当你得知了当日的价格比之前的最低价还低，你可以将最低价记录下来；
当你得知今日的价格较高，如果你在当时最低价买入并在此时卖出，获得的利润比之前抛售更高，开始emo~
我们的算法就是允许你反悔......
hhhhhhhhhhhh~
代码示例（JAVA）
class Solution {
public int maxProfit(int[] prices) {
int profit = 0, minPrice = prices[0];
for (int i = 1; i < prices.length; i++) {
if (prices[i] < minPrice) {
minPrice = prices[i];
} else if (prices[i] - minPrice > profit) {
profit = prices[i] - minPrice;
}
}
return profit;
}
}
409. 最长回文串
问题描述
给定一个包含大写字母和小写字母的字符串 s ，返回 通过这些字母构造成的 最长的回文串 。
在构造过程中，请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。
示例
输入:s = "abccccdd"
输出:7
解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
解题思路
核心：贪心法
这道题很简单，首先统计字符的种类以及每个种类的个数，然后计算回文字符串的最大长度：
当某种字符的个数正好被2整除时，那么这种字符可以全部出现；
当某种字符不能被2整除时，可以被整除的部分是可以全部出现的，但是剩下的1个不一定能出现在字符串中，因为只允许出现一次孤零零的一个字符。
代码示例（JAVA）
class Solution {
public int longestPalindrome(String s) {
Map<Character, Integer> map = new HashMap<>();
char[] chars = s.toCharArray();
for (char c : chars) {
map.put(c, map.get(c) == null ? 1 : map.get(c) + 1);
}
int count = 0;
boolean oneFlag = false;
for (char c : map.keySet()) {
if (map.get(c) % 2 == 1 && !oneFlag) {
count++;
oneFlag = true;
}
count = count + (map.get(c) / 2) * 2;
}
return count;
}
}
DAY6
589. N 叉树的前序遍历
问题描述
给定一个 n 叉树的根节点 root ，返回 其节点值的 前序遍历 。
n 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。
示例
解题思路
这道题很简单，属于树的基本功，不做赘述。
代码示例（JAVA）
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List<Integer> preorder(Node root) {
List<Integer> arr = new ArrayList<>();
preOrder(root, arr);
return arr;
}
public void preOrder(Node root, List<Integer> arr) {
if (root == null) {
return;
}
arr.add(root.val);
if (root.children != null) {
for (Node node : root.children) {
preOrder(node, arr);
}
}
}
}
102. 二叉树的层序遍历
问题描述
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例
解题思路
这道题很简单，遍历的时候传一下节点所在层数，然后存入相应的list中即可。
代码示例（JAVA）
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> arr = new ArrayList<>();
order(root, arr, 0);
return arr;
}
public void order(TreeNode root, List<List<Integer>> arr, int n) {
if (root == null) {
return;
}
if (arr.size() < n + 1) {
arr.add(new ArrayList<>());
}
List<Integer> list = arr.get(n);
list.add(root.val);
order(root.left, arr, n + 1);
order(root.right, arr, n + 1);
}
}
DAY7
704. 二分查找
问题描述
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
解题思路
二分查找属于基本功，在此不做赘述；
有一个要注意的地方就是计算mid时，由于一些数据很大的测试用例，直接计算mid = (left + right) / 2可能会溢出，可以用mid = left + (right - left) / 2进行计算。
代码示例（JAVA）
class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1, mid = left + (right - left) / 2;
while (target != nums[mid]) {
if (target > nums[mid]) {
left = mid + 1;
} else if (target < nums[mid]) {
right = mid - 1;
}
if (left > right) {
return -1;
} else {
mid = left + (right - left) / 2;
}
}
return mid;
}
}
278. 第一个错误的版本
问题描述
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本[1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例
输入：n = 5, bad = 4
输出：4
解释：
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。
解题思路
这道题应该用二分查找缩小查找的区间，直到找到第一个错误的版本；和我们平常写的二分查找有一点不同的是，当mid是错误版本时，right = mid，而不是right = mid - 1，因为它可能是第一个错误版本，不能把它舍弃掉。
代码示例（JAVA）
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
int left = 1, right = n;
while (left < right) {
int mid = left + (right - left) / 2;
if (isBadVersion(mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
DAY8
98. 验证二叉搜索树
问题描述
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例
解题思路
这道题，我第一个想法就是直接中序遍历获取一个list，然后判断list的有序性；但是，其实不需要这么麻烦，放一个变量pre在外面即可，每次遍历和这个pre做比较。
另外，有一些测试数据很恶心，这里用long。
代码示例（JAVA）
class Solution {
long pre = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
if (!isValidBST(root.left)) {
return false;
}
if (pre >= root.val) {
return false;
}
pre = root.val;
return isValidBST(root.right);
}
}
235. 二叉搜索树的最近公共祖先
问题描述
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例
解题思路
我们可以利用二叉搜索树的有序性来解题：
遍历树，
如果当前节点比两个指定节点的值都大，说明这两个节点在左子树上，遍历左节点；
如果当前节点比两个指定节点的值都小，说明这两个节点在右子树上，遍历右节点；
如果以上两种情况都不满足，说明这两个节点不在同一子树上，返回当前节点。
代码示例（JAVA）
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
TreeNode node = root;
while (node != null) {
if (p.val < node.val && q.val < node.val) {
node = node.left;
} else if (p.val > node.val && q.val > node.val) {
node = node.right;
} else {
break;
}
}
return node;
}
}
DAY9
733. 图像渲染
问题描述
有一幅以 m x n 的二维整数数组表示的图画 image ，其中 image[i][j] 表示该图画的像素值大小。
你也被给予三个整数 sr , sc 和 newColor 。你应该从像素 image[sr][sc] 开始对图像进行 上色填充 。
为了完成 上色工作 ，从初始像素开始，记录初始坐标的 上下左右四个方向上 像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应 四个方向上 像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为 newColor 。
最后返回 经过上色渲染后的图像 。
示例
解题思路
遍历二维数组，找到需要上色的位置，同时将满足条件的周围位置一起上色。
代码示例（JAVA）
class Solution {
int[] arrX = {-1, 1, 0, 0};
int[] arrY = {0, 0, -1, 1};
public int[][] floodFill(int[][] image, int sr, int sc, int color) {
int target = image[sr][sc];
fill(target, image, sr, sc, color);
return image;
}
public void fill(int target, int[][] image, int sr, int sc, int color) {
// 处理过的直接结束
if (image[sr][sc] != target || image[sr][sc] == color) {
return;
}
image[sr][sc] = color;
for (int i = 0; i < 4; i++) {
if (sr + arrX[i] >= 0 && sr + arrX[i] <= image.length - 1
&& sc + arrY[i] >= 0 && sc + arrY[i] <= image[0].length - 1) {
fill(target, image, sr + arrX[i], sc + arrY[i], color);
}
}
}
}
200. 岛屿数量
问题描述
给你一个由 1（陆地）和 0（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例
解题思路
这题和上面一题思路是一样的，不再赘述。
代码示例（JAVA）
class Solution {
int[] arrX = {-1, 1, 0, 0};
int[] arrY = {0, 0, -1, 1};
public int numIslands(char[][] grid) {
int count = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == '1') {
count++;
changeSurrounding(grid, i, j);
}
}
}
return count;
}
public void changeSurrounding(char[][] grid, int x, int y) {
int n = grid.length - 1, m = grid[0].length - 1;
// 上
for (int i = 0; i < arrX.length; i++) {
if (x + arrX[i] >= 0 && x + arrX[i] <= n && y + arrY[i] >= 0 && y + arrY[i] <= m) {
if (grid[x + arrX[i]][y + arrY[i]] == '1') {
grid[x + arrX[i]][y + arrY[i]] = 0;
changeSurrounding(grid, x + arrX[i], y + arrY[i]);
}
}
}
}
}
DAY10
509. 斐波那契数
问题描述
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。
示例
解题思路
斐波那契数闭着眼睛都能写，这里用递推。
代码示例（JAVA）
class Solution {
public int fib(int n) {
int[] arr = {0, 1};
if (n <= 1) {
return arr[n];
}
for (int i = 2; i <= n; i++) {
arr[i % 2] = arr[0] + arr[1];
}
return arr[n % 2];
}
}
70. 爬楼梯
问题描述
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
解题思路
这道题，寻找数学规律，会发现本质是一道“斐波那契数列”。
代码示例（JAVA）
class Solution {
public int climbStairs(int n) {
int[] arr = {1, 2};
if (n - 1 <= 1) {
return arr[n - 1];
}
for (int i = 2; i <= n - 1; i++) {
arr[i % 2] = arr[0] + arr[1];
}
return arr[(n - 1) % 2];
}
}
DAY11
746. 使用最小花费爬楼梯
问题描述
给你一个整数数组 cost ，其中 cost[i]是从楼梯第i个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。 你可以选择从下标为0或下标为1` 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
示例
输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。
输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。
- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
- 支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。
解题思路
核心：动态规划
计算到每一个台阶需要的花费:
代码示例（JAVA）
class Solution {
public int minCostClimbingStairs(int[] cost) {
int[] arr = new int[cost.length + 1];
arr[0] = 0;
arr[1] = 0;
for (int i = 2; i < arr.length; i++) {
arr[i] = Math.min(arr[i - 2] + cost[i - 2], arr[i - 1] + cost[i - 1]);
}
return arr[arr.length - 1];
}
}
62. 不同路径
问题描述
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 Start ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 Finish ）。
问总共有多少条不同的路径？
示例
解题思路
核心：动态规划
计算到每一个格子的不同路径即可。
代码示例（JAVA）
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (i == 0 && j == 0) {
dp[i][j] = 1;
} else {
dp[i][j] = (i - 1 >= 0 ? dp[i - 1][j] : 0) + (j - 1 >= 0 ? dp[i][j - 1] : 0);
}
}
}
return dp[n - 1][m - 1];
}
}
DAY12
438. 找到字符串中所有字母异位词
问题描述
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
s 和 p 仅包含小写字母。
示例
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
解题思路
核心：滑动窗口
用一个长度为p的窗口从s的开始位置向右滑动，比较p和窗口中的字符串是否相同。
代码示例（JAVA）
class Solution {
public List<Integer> findAnagrams(String s, String p) {
if (s.length() < p.length()) {
return new ArrayList<>();
}
int[] arrP = str2Arr(p);
int[] arrS = str2Arr(s.substring(0, p.length()));
List<Integer> result = new ArrayList<>();
for (int i = 0; i <= s.length() - p.length(); i++) {
if (i != 0) {
arrS[s.charAt(i - 1) - 'a']--;
arrS[s.charAt(i + p.length() - 1) - 'a']++;
}
if (Arrays.equals(arrP, arrS)) {
result.add(i);
}
}
return result;
}
public int[] str2Arr(String str) {
int[] arr = new int[26];
for (char c : str.toCharArray()) {
arr[c - 'a']++;
}
return arr;
}
}
424. 替换后的最长重复字符
问题描述
给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符，并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。
在执行上述操作后，返回包含相同字母的最长子字符串的长度。
s 仅由大写英文字母组成。
示例
输入：s = "ABAB", k = 2
输出：4
解释：用两个'A'替换为两个'B',反之亦然。
输入：s = "AABABBA", k = 1
输出：4
解释：
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。
解题思路
核心：滑动窗口
用left、right表示窗口的起始位置，right向右滑动，当满足条件sum(所有字符的出现次数) - max(出现次数最多的字符的出现次数）= other(其他字符的出现次数) <= k时，更新最大长度，right继续右滑；如果不满足条件时，left以及right同时右滑。
代码示例（JAVA）
class Solution {
public int characterReplacement(String s, int k) {
int max = 0;
// arr表示窗口数据
int[] arr = new int[26];
for (int left = 0, right = 0; right < s.length(); right++) {
arr[s.charAt(right) - 'A']++;
int curMax = 0;
int sum = 0;
for (int i = 0; i < 26; i++) {
curMax = Math.max(curMax, arr[i]);
sum += arr[i];
}
if (sum - curMax <= k) {
max = sum;
} else {
// left右滑
arr[s.charAt(left) - 'A']--;
left++;
}
}
return max;
}
}
DAY13
1. 两数之和
问题描述
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
输入：nums = [3,2,4], target = 6
输出：[1,2]
解题思路
枚举数组中的每一个x，寻找target-x，可以借助哈希表快速查找。
代码示例（JAVA）
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; ++i) {
if (hashtable.containsKey(target - nums[i])) {
return new int[]{hashtable.get(target - nums[i]), i};
}
hashtable.put(nums[i], i);
}
return new int[0];
}
}
299. 猜数字游戏
问题描述
你在和朋友一起玩 猜数字（Bulls and Cows）游戏，该游戏规则如下：
写出一个秘密数字，并请朋友猜这个数字是多少。朋友每猜测一次，你就会给他一个包含下述信息的提示：
猜测数字中有多少位属于数字和确切位置都猜对了（称为 "Bulls"，公牛），
有多少位属于数字猜对了但是位置不对（称为 "Cows"，奶牛）。也就是说，这次猜测中有多少位非公牛数字可以通过重新排列转换成公牛数字。
给你一个秘密数字 secret 和朋友猜测的数字 guess ，请你返回对朋友这次猜测的提示。
提示的格式为 xAyB ，x 是公牛个数， y 是奶牛个数，A 表示公牛，B 表示奶牛。
请注意秘密数字和朋友猜测的数字都可能含有重复数字。
提示：
- 1 <= secret.length, guess.length <= 1000
- secret.length == guess.length
- secret 和 guess 仅由数字组成
示例
输入：secret = "1807", guess = "7810"
输出："1A3B"
输入：secret = "1123", guess = "0111"
输出："1A1B"
注意，两个不匹配的 1 中，只有一个会算作奶牛（数字猜对位置不对）。通过重新排列非公牛数字，其中仅有一个 1 可以成为公牛数字。
解题思路
同时遍历两个字符串，将相同位置相同字符的记入公牛个数，如果不同，把这两个字符分别放入map；将两个map进行比对，计算奶牛个数。
因为数字只可能是0~9，这里如果用new int[10]的数组代替map，效率更高。
代码示例（JAVA）
class Solution {
public String getHint(String secret, String guess) {
Map<Character, Integer> sMap = new HashMap<>();
Map<Character, Integer> gMap = new HashMap<>();
char[] sArr = secret.toCharArray();
char[] gArr = guess.toCharArray();
int bulls = 0, cows = 0;
for (int i = 0; i < sArr.length; i++) {
if (sArr[i] == gArr[i]) {
bulls++;
} else {
sMap.put(sArr[i], sMap.get(sArr[i]) == null ? 1 : sMap.get(sArr[i]) + 1);
gMap.put(gArr[i], gMap.get(gArr[i]) == null ? 1 : gMap.get(gArr[i]) + 1);
}
}
for (Character c : sMap.keySet()) {
if (gMap.get(c) != null) {
cows += Math.min(sMap.get(c), gMap.get(c));
}
}
return bulls + "A" + cows + "B";
}
}
DAY14
844. 比较含退格的字符串
问题描述
给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
注意：如果对空文本输入退格字符，文本继续为空。
示例
输入：s = "ab#c", t = "ad#c"
输出：true
解释：s 和 t 都会变成 "ac"。
输入：s = "ab##", t = "c#d#"
输出：true
解释：s 和 t 都会变成 ""。
解题思路
先构建字符串，后比较。
代码示例（JAVA）
class Solution {
public boolean backspaceCompare(String s, String t) {
s = generate(s);
t = generate(t);
return s.equals(t);
}
public String generate(String str) {
StringBuilder builder = new StringBuilder();
char[] arr = str.toCharArray();
for (char c : arr) {
if (c != '#') {
builder.append(c);
} else if (builder.length() > 0) {
builder.deleteCharAt(builder.length() - 1);
}
}
return builder.toString();
}
}
394. 字符串解码
问题描述
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
提示：
- 1 <= s.length <= 30
- s 由小写英文字母、数字和方括号 '[]' 组成
- s 保证是一个 有效 的输入。
- s 中所有整数的取值范围为 [1, 300]
示例
输入：s = "3[a]2[bc]"
输出："aaabcbc"
输入：s = "3[a2[c]]"
输出："accaccacc"
输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"
输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"
解题思路
方法一（不推荐）
我原来是准备简单的将数字和字母分开，存入两个栈后进行求解；在处理过程中，发现“[”、“]”在嵌套和并列的时候，处理起来比较麻烦，虽然最后还是能解出来。
方法二（推荐）
用两个栈数字栈以及结果栈进行求解，具体看下面代码示例。
代码示例（JAVA）
方法一
class Solution {
public static String decodeString(String s) {
// 数字栈
Stack<Integer> dStack = new Stack<>();
// 字符栈
Stack<Character> cStack = new Stack<>();
// 将数据存入栈
int digit = 0;
for (char c : s.toCharArray()) {
if (!Character.isDigit(c)) {
cStack.push(c);
if (digit != 0) {
dStack.push(digit);
digit = 0;
}
} else {
digit = digit * 10 + (c - '0');
}
}
// 从字符栈里取出数据，当取出"["时，从数字栈弹出一个数
StringBuilder str = new StringBuilder();
Integer repeatCount = 0;
List<StringBuilder> repeatList = new ArrayList<>();
while (!cStack.isEmpty()) {
char c = cStack.pop();
if (c >= 'a' && c <= 'z') {
if (repeatList.size() != 0) {
repeatList.get(repeatList.size() - 1).insert(0, c);
} else {
str.insert(0, c);
}
} else if (c == ']') {
repeatList.add(new StringBuilder());
} else {
// c == [
repeatCount = Integer.parseInt(String.valueOf(dStack.pop()));
while (repeatCount-- > 0) {
if (repeatList.size() == 1) {
str.insert(0, repeatList.get(repeatList.size() - 1));
} else {
repeatList.get(repeatList.size() - 2).insert(0, repeatList.get(repeatList.size() - 1));
}
}
repeatList.remove(repeatList.size() - 1);
}
}
return str.toString();
}
}
方法二
class Solution {
public static String decodeString(String s) {
// 数字栈
Stack<Integer> dStack = new Stack<>();
// 结果栈
Stack<StringBuilder> resultStack = new Stack<>();
StringBuilder result = new StringBuilder();
// 遍历字符串
int digit = 0;
for (char c : s.toCharArray()) {
if (Character.isDigit(c)) {
digit = digit * 10 + (c - '0');
} else if (c == '[') {
dStack.push(digit);
digit = 0;
resultStack.push(result);
result = new StringBuilder();
} else if (Character.isAlphabetic(c)) {
result.append(c);
} else {
// c == ]
StringBuilder resultTemp = resultStack.pop();
int count = dStack.pop();
for (int i = 0; i < count; i++) {
resultTemp.append(result);
}
result = resultTemp;
}
}
return result.toString();
}
}
DAY15
1046. 最后一块石头的重量
问题描述
有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。
示例
输入：[2,7,4,1,8,1]
输出：1
解释：
先选出 7 和 8，得到 1，所以数组转换为 [2,4,1,1,1]，
再选出 2 和 4，得到 2，所以数组转换为 [2,1,1,1]，
接着是 2 和 1，得到 1，所以数组转换为 [1,1,1]，
最后选出 1 和 1，得到 0，最终数组转换为 [1]，这就是最后剩下那块石头的重量。
解题思路
这道题简单使用优先队列即可。
代码示例（JAVA）
class Solution {
public int lastStoneWeight(int[] stones) {
// 优先队列
PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
for (int stone : stones) {
queue.offer(stone);
}
while (!queue.isEmpty()) {
Integer x = queue.poll();
Integer y = queue.poll();
if (y == null) {
return x;
}
if (x - y > 0) {
queue.offer(x - y);
}
}
return 0;
}
}
692. 前K个高频单词
问题描述
给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。
示例
输入: words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
输出: ["i", "love"]
解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
注意，按字母顺序 "i" 在 "love" 之前。
输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
输出: ["the", "is", "sunny", "day"]
解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词，
出现次数依次为 4, 3, 2 和 1 次。
解题思路
遍历数组，将字符串以及出现的次数存入哈希表；然后根据哈希表中的次数对字符串进行排序。
代码示例（JAVA）
class Solution {
public List<String> topKFrequent(String[] words, int k) {
Map<String, Integer> map = new HashMap<>();
for (String word : words) {
map.put(word, map.getOrDefault(word, 0) + 1);
}
List<String> result = new ArrayList<>();
for (String str : map.keySet()) {
result.add(str);
}
// 排序
Collections.sort(result, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return map.get(o1) == map.get(o2) ? o1.compareTo(o2) : map.get(o2) - map.get(o1);
}
});
return result.subList(0, k);
}
}
