206 反转链表
思路1:迭代
/**
* 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) {
if(head==null) return head;
ListNode pre=null,cur=head;
while(true){
ListNode temp=cur.next;
cur.next=pre;
pre=cur;
if(temp!=null){
cur=temp;
}
else{
break;
}
}
return cur;
}
}
思路更清晰：
class Solution {
public ListNode reverseList(ListNode head) {
if(head==null) return head;
ListNode pre=null,cur=head;
while(cur!=null){
ListNode temp=cur.next;
cur.next=pre;
pre=cur;
cur=temp;
}
return pre;
}
}
思路2:递归
/**
* 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) {
if(head==null) return head;
return reverseListCore(null,head);
}
ListNode reverseListCore(ListNode pre,ListNode head){
if(head==null) return pre;
ListNode temp=head.next;
head.next=pre;
pre=head;
return reverseListCore(pre,temp);
}
}
128 最长连续序列
思路1:堆
一开始想的是边建堆，边与根节点判断是否连续来更新长度，但是这是不对的，因为一个很大的数会一直是根节点呀。
应该是：先建堆(全部数据都先建好堆)，再一遍遍历。
ps:本题中，出现重复的，并不会中断连续，就算一个即可。
class Solution {
public int longestConsecutive(int[] nums) {
if(nums.length<=1) return nums.length;
PriorityQueue<Integer> queue = new PriorityQueue<>();
for(int num:nums){
queue.add(num);
}
int len=1,max=1,pre=queue.peek();
queue.poll();
while(queue.size()!=0){
if(queue.peek()-1==pre){
len++;
}
else if(queue.peek()==pre){
len=len;
}
else{
max=Math.max(max,len);
len=1;//不是0
}
pre=queue.peek();
queue.poll();
}
return Math.max(max,len);//不是return len，因为有可能一直没进入更新max的代码块
}
}
修改了一下代码
class Solution {
public int longestConsecutive(int[] nums) {
if(nums.length<=1) return nums.length;
PriorityQueue<Integer> queue = new PriorityQueue<>();
for(int num:nums){
queue.add(num);
}
int len=1,max=1,pre=queue.peek();
queue.poll();
while(queue.size()!=0){
int cur=queue.peek();
queue.poll();
if(cur-1==pre){
len++;
max=Math.max(max,len);
pre=cur;
}
else if(cur==pre){
continue;
}
else{
len=1;//不是0
pre=cur;
}
}
return max;
}
}
思路2:集合set
一般，对时间复杂度有要求，就用空间来换，对空间复杂度有要求，就用时间来换。
基于这种思路我们就想要求最长的，就是要记录下有没有相邻的元素，比如遍历到100这个元素，我们需要查看[99, 101]这两个元素在不在序列中，这样去更新最大长度。而记录元素有没有这个事我们太熟悉了，用set这种数据结构，而set这种数据结构是需要o(n)的空间来换取的，这就是我们刚才说的用空间来换时间。
同样也是先建立好set,不可以边建边判断。
照着思路自己写的代码，烂透了，而且非常慢，思考下为什么，你重复了很多操作。
一开始遍历nums
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> numsSet=new HashSet<>();
for(int num:nums){
numsSet.add(num);
}
int ans=0;//默认是0,因为nums中可能无元素
for(int i=0;i<nums.length;i++){
int len=1;
int num=nums[I];
while(numsSet.contains(num-1)){
len++;
num--;
}
num=nums[I];
while(numsSet.contains(num+1)){
len++;
num++;
}
ans=Math.max(len,ans);
}
return ans;
}
}
后来又想遍历set
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> numsSet=new HashSet<>();
for(int num:nums){
numsSet.add(num);
}
int ans=0;//默认是0,因为nums中可能无元素
Iterator it = numsSet.iterator();
while(it.hasNext()){
int num=(int)it.next();
int len=1,temp=num;
while(numsSet.contains(temp-1)){
len++;
temp--;
}
//num=(int)it.next();
temp=num;
//在使用迭代器的时候注意next()方法在同一循环中不能出现俩次
while(numsSet.contains(temp+1)){
len++;
temp++;
}
ans=Math.max(len,ans);
}
return ans;
}
}
别人写的代码
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> numsSet = new HashSet<>();
for (Integer num : nums) {
numsSet.add(num);
}
int longest = 0;
for (Integer num : nums) {
if (numsSet.remove(num)) {//返回值：boolean
// 向当前元素的左边搜索,eg: 当前为100, 搜索：99，98，97,...
int currentLongest = 1;
int current = num;
while (numsSet.remove(current - 1)) current--;
currentLongest += (num - current);
// 向当前元素的右边搜索,eg: 当前为100, 搜索：101，102，103,...
current = num;
while(numsSet.remove(current + 1)) current++;
currentLongest += (current - num);
// 搜索完后更新longest.
longest = Math.max(longest, currentLongest);
}
}
return longest;
}
}
官方题解：
我们考虑枚举数组中的每个数 x，考虑以其为起点，不断尝试匹配 x+1,x+2,⋯ 是否存在，假设最长匹配到了 x+y，那么以 x 为起点的最长连续序列即为
x,x+1,x+2,⋯,x+y，其长度为 y+1，我们不断枚举并更新答案即可。
对于匹配的过程，暴力的方法是 ,在每一次匹配时，以O(n) 遍历数组去看是否存在这个数，但其实更高效的方法是用一个哈希表存储数组中的数，这样查看一个数是否存在即能优化至 O(1) 的时间复杂度。
ps:我们只需知道这个数存在不存在就好，没必要记录下标。所以用set。
仅仅是这样我们的算法时间复杂度最坏情况下还是会达到 O(n^2)（即外层需要枚举 O(n) 个数，内层需要匹配 O(n) 次），无法满足题目的要求。但仔细分析这个过程，我们会发现其中执行了很多不必要的枚举，如果已知有一个 x,x+1,x+2,⋯,x+y 的连续序列，而我们却重新从 x+1，x+2 或者是 x+y 处开始尝试匹配，那么得到的结果肯定不会优于枚举 x 为起点的答案，因此我们在外层循环的时候碰到这种情况跳过即可。
那么怎么判断是否跳过呢？由于我们要枚举的数 x 一定是在数组中不存在前驱数 x−1 的，不然按照上面的分析我们会从 x−1 开始尝试匹配，因此我们每次在哈希表中检查是否存在 x−1 即能判断是否需要跳过了。
增加了判断跳过的逻辑之后，时间复杂度是多少呢？
外层循环需要 O(n) 的时间复杂度，只有当一个数是连续序列的第一个数的情况下才会进入内层循环，然后在内层循环中匹配连续序列中的数，因此数组中的每个数只会进入内层循环一次。根据上述分析可知，总时间复杂度为 O(n)，符合题目要求。
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> num_set = new HashSet<Integer>();
for (int num : nums) {
num_set.add(num);
}
int longestStreak = 0;
for (int num : num_set) {
if (!num_set.contains(num - 1)) {
int currentNum = num;
int currentStreak = 1;
while (num_set.contains(currentNum + 1)) {
currentNum += 1;
currentStreak += 1;
}
longestStreak = Math.max(longestStreak, currentStreak);
}
}
return longestStreak;
}
}
思路3:hash表
没实现 很难理解
本题目要求时间复杂度为O(n)，因此我们在遍历的过程中查找是否有与当前相连的数字需要用到哈希表，这样才能保证每次查找都是O(1)复杂度
！！！核心思想就是拿当前数字去找与其左右相连的数字集合看看能否组成一个更大的集合，并更新两端的最长值，过程中遇到哈希表中已存在的值就跳过，并且维护一个最大值用于返回。
class Solution {
public int longestConsecutive(int[] nums) {
int n=nums.length;
HashMap<Integer,Integer>map = new HashMap<Integer,Integer>();
int res = 0;
for(int num:nums){
//新进来哈希表一个数
if(!map.containsKey(num)){
//获取当前数的最左边连续长度,没有的话就更新为0
int left = map.get(num-1)==null?0:map.get(num-1);
//同理获取右边的数,没有的话就是0
int right = map.get(num+1)==null?0:map.get(num+1);
//更新长度
int cur = 1+left+right;
if(cur>res){
res = cur;
}
// 把当前数加入哈希表，只是代表当前数字出现过 所以用set的也可以，想一想上面就是用set
map.put(num,cur);
//更新 最左端点 的值，如果left=n存在，那么证明当前数的前n个都存在哈希表中 ？
map.put(num-left,cur);
// 更新 最右端点 的值，如果right=n存在，那么证明当前数的后n个都存在哈希表中？
map.put(num+right,cur);
//此时【num-left，num-right】范围的值都连续存在哈希表中了
//即使left或者right=0都不影响结果
}
}
return res;
}
}
详细解释上面的代码：
首先，定义一个哈希表（用于判断某个数是否存在哈希表中）
然后遍历数组
如果当前数num存在哈希表，那么跳过
如果当前数num不存在哈希表中，那么查找num-1和num+1这两个数是不是在哈希表中
比如 num是5
1234 678都在哈希表中
遍历数组的时候，遇到1234678都会掠过
此时哈希表中，1的位置和4存的值都是4（证明1或者4所在的连续长度是4） (因为1和4是端点)
同理 6和8存的值都是3 （同理)
那么此时5进来之后，看看4和6在不在哈希表内，如果在的话，一定是端点，一定能获取到值
所以5进来之后，发现左边有4个连续的，右边有3个连续的，加上自己一个，那么组成一个大连续的
4+1+3 = 8
所以要更新当前最长连续串的端点，也就是1的位置（5-4），8的位置（5+3），更新长度为8
只需要端点存值就行，因为端点中的值在遍历的时候如果在哈希表中就会略过
如果这个时候9又进来，那么它获取到8的位置有8，10的位置有0
更新连续子串长度（8+1+0）
所以更新左端点1（9-8）的值为9，右端点9（9+0）的值为9
为什么只更新区间两端的值？
因为两端的值可能会继续延伸，所以要保存最新的长度，再有中间的值对最大长度是没有影响的，所以只需要更新头和尾的值。
ps：
map.put(num,cur); 这行的意义的一些想法，其实这行的作用不是更新这个区间的长度，而是表示这个元素已经被访问过。
区间长度用两端的元素来确定就可以了。
map.put(num,1); 也是没问题的～！
没看 没实现
思路5:
先sort，然后计数计算最长序列。
但是要求时间复杂度为：o(n)，就不能用sort了。
49 字母异位词分组
思路：对string数组中的每一个string s排序得到sortedS
建立一个map<sortedS,List<string>>,最后遍历获取map的values值！
请认真学习一下别人的代码怎么写的！你很多语法还不会
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
HashMap<String,ArrayList<String>> map=new HashMap<>();
for(String s:strs){
char[] ch=s.toCharArray();//转为char[]
Arrays.sort(ch);
String key=String.valueOf(ch);//转为string
if(!map.containsKey(key)) map.put(key,new ArrayList<>());
map.get(key).add(s);
}
return new ArrayList(map.values());//返回所有values
}
}
或者
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<String, List<String>>();
for (String str : strs) {
char[] array = str.toCharArray();
Arrays.sort(array);
String key = new String(array);
List<String> list = map.getOrDefault(key, new ArrayList<String>());
list.add(str);
map.put(key, list);
}
return new ArrayList<List<String>>(map.values());
}
}
思路2:
计数作为哈希表的键，而不是排序的词组。
具体说来：由于互为字母异位词的两个字符串包含的字母相同，因此两个字符串中的相同字母出现的次数一定是相同的，故可以将每个字母出现的次数使用字符串表示，作为哈希表的键。
由于字符串只包含小写字母，因此对于每个字符串，可以使用长度为 26 的数组记录每个字母出现的次数。
代码：使用stringbuffer
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<String, List<String>>();
for (String str : strs) {
int[] counts = new int[26];
int length = str.length();
for (int i = 0; i < length; i++) {
counts[str.charAt(i) - 'a']++;
}
// 将每个出现次数大于 0 的字母和出现次数按顺序拼接成字符串，作为哈希表的键
StringBuffer sb = new StringBuffer();
for (int i = 0; i < 26; i++) {
if (counts[i] != 0) {
sb.append((char) ('a' + i));
sb.append(counts[I]);
}
}
String key = sb.toString();
List<String> list = map.getOrDefault(key, new ArrayList<String>());
list.add(str);
map.put(key, list);
}
return new ArrayList<List<String>>(map.values());
}
}
221 最大正方形
思路1:暴力 写了20min 想了10min..
遍历每一个元素，并求以它为左上角的最大正方形面(求的过程中需要确定正方形没有越界而且里面全是1)
实际上，你只需要判断新增的一行一列是否都是1就可以了！没有必要又从头开始！
class Solution {
public int maximalSquare(char[][] matrix) {
int max=0;
for(int i=0;i<matrix.length;i++){
for(int j=0;j<matrix[0].length;j++){
//计算最大面积
if(matrix[i][j]!='1') continue;
else{
int w=1,h=1;//w=h 实际上
while(i+h<matrix.length && j+w<matrix[0].length && isOne(i,j,w,matrix)){
w++;h++;
}
max=Math.max(max,w*h);
}
}
}
return max;
}
boolean isOne(int x,int y,int w,char[][] matrix){
for(int i=0;i<=w;i++){
for(int j=0;j<=w;j++){
if(matrix[x+i][y+j]!='1') return false;
}
}
return true;
}
}
修改一下isOne函数
boolean isOne(int x,int y,int w,char[][] matrix){
for(int i=0;i<=w;i++){
if(matrix[x+w][y+i]!='1'||matrix[x+i][y+w]!='1') return false;
}
return true;
}
官方的暴力代码
class Solution {
public int maximalSquare(char[][] matrix) {
int maxSide = 0;
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return maxSide;
}
int rows = matrix.length, columns = matrix[0].length;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {
if (matrix[i][j] == '1') {
// 遇到一个 1 作为正方形的左上角
maxSide = Math.max(maxSide, 1);
// 计算可能的最大正方形边长
int currentMaxSide = Math.min(rows - i, columns - j);
for (int k = 1; k < currentMaxSide; k++) {
// 判断新增的一行一列是否均为 1
boolean flag = true;
if (matrix[i + k][j + k] == '0') {
break;
}
for (int m = 0; m < k; m++) {
if (matrix[i + k][j + m] == '0' || matrix[i + m][j + k] == '0') {
flag = false;
break;
}
}
if (flag) {
maxSide = Math.max(maxSide, k + 1);
} else {
break;
}
}
}
}
}
int maxSquare = maxSide * maxSide;
return maxSquare;
}
}
思路2:动态规划
准确来说，dp(i, j) 是以 matrix(i - 1, j - 1) 为 右下角 的正方形的最大边长。
若某格子值为 1，则以此为右下角的正方形的最大边长为：上面的正方形、左面的正方形或左上的正方形中，最小的那个变长，再加上此格(也就是+1)。
// 伪代码，即：递推公式
if (grid[i - 1][j - 1] == '1') {
dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1;
}
- 从上述分析中，我们似乎得到的只是「动态规划 推进 的过程」，即「如何从前面的 dp 推出后面的 dp」，甚至还只是感性理解
- 我们还缺：dp 具体定义如何，数组多大，初值如何，如何与题目要求的面积相关
- dp 具体定义：dp[i ][j ] 表示 「以第 i -1行、第 j -1列为右下角的正方形的最大边长」
- 因为任何一个正方形，我们都「依赖」当前格 左、上、左上三个方格的情况，但是第一行的上层已经没有格子，第一列左边已经没有格子，需要做特殊 if 判断来处理，为了代码简洁，我们 假设补充 了多一行全 '0'、多一列全 '0'！！！
- 此时 dp 数组的大小也明确为 new dp[height + 1][width + 1]
- 初始值就是将第一列 dp[row][0] 、第一行 dp[0][col] 都赋为 0，相当于已经计算了所有的第一行、第一列的 dp 值
- 题目要求面积。根据 「面积 = 边长 x 边长」可知，我们只需求出 最大边长 即可
/**
dp[i][j]表示以第i行第j列为右下角所能构成的最大正方形边长, 则递推式为:
dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]);
**/
class Solution {
public int maximalSquare(char[][] matrix) {
int r=matrix.length,c=matrix[0].length,max=0;
int[][] dp=new int[r+1][c+1]; // 相当于已经预处理新增第一行、第一列均为0
for(int i=1;i<=r;i++){
for(int j=1;j<=c;j++){
if(matrix[i-1][j-1]=='1'){
dp[i][j]=Math.min(Math.min(dp[i-1][j],dp[i-1][j-1]),dp[i][j-1])+1;
}
max=Math.max(dp[i][j],max);
}
}
return max*max;
}
}
- 其实只需关注"当前格子的周边"，故可二维降一维，优化空间复杂度。
- 由于状态转移方程中的 dp(i,j) 由其上方、左方和左上方的三个相邻位置的 dp 值决定，因此可以使用两个一维数组进行状态转移，空间复杂度优化至O(n)。
class Solution {
public int maximalSquare(char[][] matrix) {
int r=matrix.length,c=matrix[0].length,max=0;
int[] pre=new int[c+1];
int[] cur=new int[c+1];
for(int i=1;i<=r;i++){
for(int j=1;j<=c;j++){
if(matrix[i-1][j-1]=='1'){
cur[j]=Math.min(Math.min(pre[j],pre[j-1]),cur[j-1])+1;
}
max=Math.max(cur[j],max);
}
pre=cur;
cur=new int[c+1];//!!非常重要
}
return max*max;
}
}
其他人写的,为什么可以只用一个数组？
public int maximalSquare(char[][] matrix) {
// base condition
if (matrix == null || matrix.length < 1 || matrix[0].length < 1) return 0;
int height = matrix.length;
int width = matrix[0].length;
int maxSide = 0;
// 相当于已经预处理新增第一行、第一列均为0
// int[][] dp = new int[height + 1][width + 1];
int[] dp = new int[width + 1];
int northwest = 0; // 西北角、左上角
// for (int row = 0; row < height; row++) {
for (char[] chars : matrix) {
northwest = 0; // 遍历每行时，还原回辅助的原值0
for (int col = 0; col < width; col++) {
int nextNorthwest = dp[col + 1];
if (chars[col] == '1') {
// dp[row + 1][col + 1] = Math.min(Math.min(dp[row + 1][col], dp[row][col + 1]), dp[row][col]) + 1;
dp[col + 1] = Math.min(Math.min(dp[col], dp[col + 1]), northwest) + 1;
// maxSide = Math.max(maxSide, dp[row + 1][col + 1]);
maxSide = Math.max(maxSide, dp[col + 1]);
} else {
dp[col + 1] = 0;
}
northwest = nextNorthwest;
}
}
return maxSide * maxSide;
}
还有这个
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
if (matrix.empty() || matrix[0].empty()) return 0;
int m = matrix.size(), n = matrix[0].size(), res = 0;
int pre = 0, tmp;
vector<int> dp(n, 0);
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (i == 0 || j == 0) {
pre=dp[j]; dp[j]=matrix[i][j]-'0';
}
else if(matrix[i][j] == '0') {
pre=dp[j]; dp[j]=0;
}
else {
tmp = dp[j];
dp[j] = min(dp[j - 1], min(dp[j],pre)) + 1;
pre = tmp;
}
res = max(res, dp[j]);
}
}
return res * res;
}
};
为什么不可以只用三个变量呢？
没尝试
时间复杂度 O(height∗width)
空间复杂度 O(width)
总而言之：
当我们判断以某个点为正方形右下角时最大的正方形时，那它的上方，左方和左上方三个点也一定是某个正方形的右下角，否则该点为右下角的正方形最大就是它自己了。这是定性的判断，那具体的最大正方形边长呢？我们知道，该点为右下角的正方形的最大边长，最多比它的上方，左方和左上方为右下角的正方形的边长多1，最好的情况是是它的上方，左方和左上方为右下角的正方形的大小都一样的，这样加上该点就可以构成一个更大的正方形。
但如果它的上方，左方和左上方为右下角的正方形的大小不一样，合起来就会缺了某个角落，这时候只能取那三个正方形中最小的正方形的边长加1了。
假设dpi表示以i,j为右下角的正方形的最大边长，则有 dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1 当然，如果这个点在原矩阵中本身就是0的话，那dp[i]肯定就是0了。
208 实现trie前缀树
将类的实例本身视作一个结点
class Trie {
private boolean isEnd;
private Trie[] next;
/** Initialize your data structure here. */
public Trie() {
next=new Trie[26];//字母映射表
isEnd=false;
}
/** Inserts a word into the trie. */
public void insert(String word) {
Trie cur=this;
for(char c:word.toCharArray()){
if(cur.next[c-'a']==null){
cur.next[c-'a']=new Trie();
}
cur=cur.next[c-'a'];
}
cur.isEnd=true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
Trie cur=this;
for(char c:word.toCharArray()){
if(cur.next[c-'a']==null){
return false;
}
cur=cur.next[c-'a'];
}
return cur.isEnd;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
Trie cur=this;
for(char c:prefix.toCharArray()){
if(cur.next[c-'a']==null){
return false;
}
cur=cur.next[c-'a'];
}
return true;
}
}
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.insert(word);
* boolean param_2 = obj.search(word);
* boolean param_3 = obj.startsWith(prefix);
*/
内部类写法
class Trie {
class TireNode {
private boolean isEnd;
TireNode[] next;
public TireNode() {
isEnd = false;
next = new TireNode[26];
}
}
private TireNode root;
public Trie() {
root = new TireNode();
}
public void insert(String word) {
TireNode node = root;
for (char c : word.toCharArray()) {
if (node.next[c - 'a'] == null) {
node.next[c - 'a'] = new TireNode();
}
node = node.next[c - 'a'];
}
node.isEnd = true;
}
public boolean search(String word) {
TireNode node = root;
for (char c : word.toCharArray()) {
node = node.next[c - 'a'];
if (node == null) {
return false;
}
}
return node.isEnd;
}
public boolean startsWith(String prefix) {
TireNode node = root;
for (char c : prefix.toCharArray()) {
node = node.next[c - 'a'];
if (node == null) {
return false;
}
}
return true;
}
}
官方题解也很不错，解释的很好，代码也不错，只是有点啰嗦
https://leetcode-cn.com/problems/implement-trie-prefix-tree/solution/shi-xian-trie-qian-zhui-shu-by-leetcode/
