传送门：https://leetcode-cn.com/problems/valid-parenthesis-string 题目描述： 给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则： 1、 任何左括号 ( 必须有相应的右括号 )。 2、任何右括号 ) 必须有相应的左括号 ( 。 3、左括号 ( 必须在对应的右括号之前 )。 4、* 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。 5、一个空字符串也被视为有...
2021年3月21日 73. 矩阵置零 O(1)额外空间写法 简单理解一下： ? 首先我们对于矩阵内所有\(\sum_{i=0}^{m}{\sum_{j=1}^{n}}0\)，记录到第0行和第0列上 ? 那么，我们只需要对于\(\sum_{i=1}^{m}{\sum_{j=1}^{n}}\)，只需要根据第0行和第0列来置0即可 ? 无论第0行和第0列原先是否是0，其对应的列/行，必定变为0 ? 那么，我们考虑第0行对应的行 ? 我们可以发现，它有\(m[0][0]\)来控制，只要是0，那么整行都是0。 ? 我们再考虑第0列对...
题目:给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。 代码如下: class Solution { public int lengthOfLongestSubstring(String s) {// 记录字符上一次出现的位置int[] last = new int[128];for(int i = 0; i < 128; i++) {last[i] = -1;}int n = s.length();int res = 0;int start = 0; // 窗口开始位置for(int i = 0; i < n; i++) {int index = s.charAt(i);start = Math.max(start, last[index] + 1);res ...
Leetcode 题解 - 动态规划 递归和动态规划都是将原问题拆成多个子问题然后求解，他们之间最本质的区别是，动态规划保存了子问题的解，避免重复计算。 斐波那契数列系列 参考文章：labuladong微信公众号#手把手刷动态规划系列文章，很棒的公众号，推荐给大家 动态规划问题的一般形式就是求最值。动态规划其实是运筹学的一种最优化方法，只不过在计算机问题上应用比较多，比如说让你求最长递增子序列呀，最小编辑距离呀等等。 既然是...
There is a hotel with n rooms. The rooms are represented by a 2D integer array rooms where rooms[i] = [roomIdi, sizei] denotes that there is a room with room number roomIdi and size equal to sizei. Each roomIdi is guaranteed to be unique. You are also given k queries in a 2D array queries where queries[j] = [preferredj, minSizej]. The answer to the jth query is the room number id of a room such th...
截止至今LeetCode题目总量已经有1582题，估计将来每年平均增长300题左右，大部分人肯定是刷不完的，所以得有选择地刷LeetCode。一种公认的刷题策略是按类别刷题，可是每个类别也有许多题，在有限的时间里到底该刷哪些题呢？个人根据LeetCode官方给出的每个题目的出现频率，整理并收录了每个类别里高频出现的题目，对于官方统计频率太低的题目，不予收录，最终得到了这个高频题目表格。例如，对于下图中题号#275与#270的题目将被收录...
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/ class BSTIterator { public:vector<int> num;int i;BSTIterator(Tr...
给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。最高位数字存放在数组的首位， 数组中每个元素只存储一个数字。你可以假设除了整数 0 之外，这个整数不会以零开头。示例 1:输入: [1,2,3] 输出: [1,2,4] 解释: 输入数组表示数字 123。 示例 2:输入: [4,3,2,1] 输出: [4,3,2,2] 解释: 输入数组表示数字 4321。//章节 - 数组和字符串 //一、数组简介 //3. 加一 /*算法思想：代码注释即可,注意审题！ *///算法...
、Duplicate Emails Write a SQL query to find all duplicate emails in a table named Person. +----+---------+ | Id | Email | +----+---------+ | 1 | a@b.com | | 2 | c@d.com | | 3 | a@b.com | +----+---------+For example, your query should return the following for the above table: +---------+ | Email | +---------+ | a@b.com | +---------+Note: All emails are in lowercase. 分析：编写一个SQL查询从P...
题目描述： 二进制手表顶部有 4 个 LED 代表 小时（0-11），底部的 6 个 LED 代表 分钟（0-59）。 每个 LED 代表一个 0 或 1，最低位在右侧。例如，上面的二进制手表读取 “3:25”。 给定一个非负整数 n 代表当前 LED 亮着的数量，返回所有可能的时间。 示例： 输入: n = 1 返回: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]题解1： 直接暴力 从0:00到11:59 直接判断小时位出现的1个数和分...
题目描述 给定 N 个人的出生年份和死亡年份，第 i 个人的出生年份为 birth[i]，死亡年份为 death[i]，实现一个方法以计算生存人数最多的年份。 你可以假设所有人都出生于 1900 年至 2000 年（含 1900 和 2000 ）之间。如果一个人在某一年的任意时期处于生存状态，那么他应该被纳入那一年的统计中。例如，生于 1908 年、死于 1909 年的人应当被列入 1908 年和 1909 年的计数。 如果有多个年份生存人数相同且均为最大值，输出其中最小...
Consider all the leaves of a binary tree, from left to right order, the values of those leaves form a leaf value sequence.For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8). Two binary trees are considered leaf-similar if their leaf value sequence is the same. Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar. Example 1:...
https://leetcode-cn.com/problems/shortest-bridge/ 给定一个数组。数组中包含两个岛屿。求两个岛屿之间的最短距离。 采用找岛屿的方式（DFS），把其中的一个岛屿全部标记为2。并且用一个queue来存储上，此时采用BFS根据queue中的每一个节点逐步向外扩，直到遇到第一个数字1，也就找到了最短的距离。 class Solution { public int shortestBridge(int[][] A) {int len1 = A.length;int len2 = A[0].length;Queue<int[]> q = new L...
AnagramsGiven an array of strings, return all groups of strings that are anagrams.Note: All inputs will be in lower-case.思路：什么是anagrams？傻逼了，百度吧。一百度全是别人的方法，看到了有map存在，正是这个提示导致此题并没有用很长的时间。方法很简单，将vector中的每个string先排序，然后在map中寻找是否已经有排序后的string，如果有则说明找到了一个anagrams，如果没有则把排序后的string作为key存在map中，对应...
典型的搜索问题。694是200的拓展，多了怎么保存岛屿的特征的问题。两道题既可以用DFS做，也可以用BFS做。解题中用到了 pair<int, int> 和 make_pair(i, j) 来记录坐标，相较于自己创建一个结构体，更加方便。auto关键字，用于申明类型，类型会自动推断，如果类型比较复杂，用auto申明会方便不少。DFS和BFS结构都比较固定，DFS的写法与之前总结的框架结构保持一致，熟能生巧。 200. Number of IslandsDFS:class Solution { public:i...