头像

bmdxyn0725


访客:3113

离线:1天前



开始习惯刷题

最近一段时间, 几乎每天都想刷刷题,不刷有点难以入睡。

假如你有一个目标, 达成的期望时间如果太短, 这会导致遇到困难时陷入焦虑, 自我怀疑。
反之, 则会享受每日或每周的稳定积累, 久而久之形成习惯, 目标也能逐渐被逼近, 同时规避了违背内心的自律式强迫症。

凡事预则立, 不预则废。欲速则不达。其实在讲同一件事情。两句放一起更能互相佐证。

重点其实是, 即预需远远早于, 如两年, 三年, 五年不等。




/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null) return head;

        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode tail = head.next;

        while(tail != null){
            if(head.val != tail.val) {
                head = tail;
                tail = tail.next;
            }else{
                head.next = tail.next;
                tail = head.next;
            }
        }

        return dummy.next;
    }
}



/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null) return head;

        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy, tail = head.next;

        while(tail != null){
            int len = 0;
            while(tail != null && head.val == tail.val) {len++; tail = tail.next;}

            if(len == 0){
                pre = pre.next;
                head = head.next;
                tail = tail.next;
            }else{
                if(tail == null){
                    pre.next = tail;
                }else{
                    head = tail;
                    tail = tail.next;
                    pre.next = head;
                }
            }
        }

        return dummy.next;
    }
}


活动打卡代码 LeetCode 78. 子集

class Solution {

    List<List<Integer>> res = new ArrayList();

    public List<List<Integer>> subsets(int[] nums) {
        if(nums == null || nums.length < 1) return res;
        // 每个长度对应一棵dfs递归树
        for(int i = 0; i <= nums.length; i++){
            Stack<Integer> path = new Stack();
            dfs(i, 0, nums, path);
        }
        return res;
    }

    public void dfs(int len, int start, int[] a, Stack<Integer> path){
        if(path.size() == len){
            res.add(new ArrayList(path));
            return;
        }

        for(int i = start; i < a.length; i++){
            path.push(a[i]);
            dfs(len, i+1, a, path);
            path.pop();
        }
    }
}


活动打卡代码 LeetCode 77. 组合

class Solution {

    List<List<Integer>> res = new ArrayList();
    Stack<Integer> path = new Stack();

    public List<List<Integer>> combine(int n, int k) {
        dfs(1, n, k);
        return res;
    }

    public void dfs(int start, int n, int k){
        if(path.size() == k) {
            res.add(new ArrayList(path));
            return;
        }
        for(int i = start; i <= n; i++){
            path.push(i);
            dfs(i + 1, n, k);
            path.pop();
        }
    }

}


活动打卡代码 LeetCode 75. 颜色分类

class Solution {
    public void sortColors(int[] nums) {
        if(nums == null || nums.length < 2) return;


    }
            //两个指针, 左指针l指向0,1的分界点, 右指针r指向1,2的分界点;
        //即l左边的数全部小于nums[l], r右边的数全部大于nums[r];
        int l = -1, r = nums.length;
        int i = 0;
        while(i < r) {
            if(nums[i] < 1) {l++; swap(nums, i, l); i++;} 
            else if(nums[i] == 1){
                i++;
            }else{
                r--;
                swap(nums, i, r);
            }
        }
    public void swap(int[] a, int i, int j){
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
}


活动打卡代码 LeetCode 74. 搜索二维矩阵

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix == null || matrix.length < 1 || matrix[0].length < 1) return false;

        // 来两次二分
        // 第一次对矩阵的第一列进行二分, 找到目标值所在的行, 这里需要将r设置为matrix.length, 原因是没找到时, 统一都返回比target大的值所在行
        // 00,10,20,30
        int l = 0, r = matrix.length;
        while(l < r){
            int mid = l + r >> 1;
            if(target <= matrix[mid][0]) r = mid;
            else l = mid + 1;
        }

        //如果目标值在第一列已经找到, 直接返回true
        if(l < matrix.length && target == matrix[l][0]) return true;
        //搜索结束时, 由于使用target<=matrix[mid],如果找到, 则是最后一个>target的数;否则,边界停在第一个比target大的数处
        int row = l > 0 ? l - 1 : 0;
        // 第二次对矩阵的第l-1行进行二分, 找到目标值所在的列
        l = 0; r = matrix[0].length-1;
        while(l < r){
            int mid = l + r >> 1;
            if(target <= matrix[row][mid]) r = mid;
            else l = mid + 1;
        }

        if(l < matrix[0].length && target == matrix[row][l]) return true;
        else return false;
    }
}



DP

  1. LeetCode 10. 正则表达式匹配
  2. LeetCode 32. 最长有效括号
  3. LeetCode 42. 接雨水
  4. LeetCode 44. 通配符匹配
  5. LeetCode 45. 跳跃游戏 II
  6. LeetCode 53. 最大子序和
  7. LeetCode 55. 跳跃游戏
  8. LeetCode 62. 不同路径
  9. LeetCode 63. 不同路径 II
  10. LeetCode 64. 最小路径和
  11. LeetCode 70. 爬楼梯
  12. LeetCode 72. 编辑距离
  13. LeetCode 87. 扰乱字符串

滑动窗口

  1. LeetCode 3. 无重复字符的最长子串
  2. LeetCode 76. 最小覆盖子串

二分

  1. LeetCode 4. 寻找两个正序数组的中位数
  2. LeetCode 33. 搜索旋转排序数组
  3. LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置
  4. LeetCode 35. 搜索插入位置
  5. LeetCode 69. x 的平方根
  6. LeetCode 74. 搜索二维矩阵
  7. LeetCode 74. 搜索二维矩阵

DFS

  1. LeetCode 17. 电话号码的字母组合
  2. LeetCode 31. 下一个排列
  3. LeetCode 36. 有效的数独
  4. LeetCode 37. 解数独
  5. LeetCode 39. 组合总和
  6. LeetCode 40. 组合总和 II
  7. LeetCode 46. 全排列
  8. LeetCode 47. 全排列 II
  9. LeetCode 51. N皇后
  10. LeetCode 52. N皇后 II
  11. LeetCode 77. 组合
  12. LeetCode 78. 子集

模板题

  1. KMP LeetCode 28. 实现 strStr()
  2. 卡特兰数 LeetCode 32. 最长有效括号
  3. 快速幂 LeetCode 50. Pow(x, n)
  4. 区间合并 LeetCode 56. 合并区间
  5. 二进制版高精度加法 LeetCode 67. 二进制求和
  6. 快速排序的partition思想 LeetCode 75. 颜色分类

数组(链表)翻转

  1. LeetCode 7. 整数反转
  2. LeetCode 25. K 个一组翻转链表
  3. LeetCode 48. 旋转图像
  4. LeetCode 61. 旋转链表

观察找规律

  1. LeetCode 6. Z 字形变换
  2. LeetCode 11. 盛最多水的容器
  3. LeetCode 12. 整数转罗马数字
  4. LeetCode 13. 罗马数字转整数
  5. LeetCode 38. 外观数列
  6. LeetCode 42. 接雨水
  7. LeetCode 55. 跳跃游戏

使用方向向量

  1. LeetCode 54. 螺旋矩阵
  2. LeetCode 59. 螺旋矩阵 II

数据结构

优先队列

  1. LeetCode 23. 合并K个排序链表

哈希

  1. 原地哈希 LeetCode 41. 缺失的第一个正数


活动打卡代码 LeetCode 72. 编辑距离

class Solution {
    public int minDistance(String s, String p) {
        int m = s.length(), n = p.length();
        if(s == null && p == null) return 0;
        s = " " + s;
        p = " " + p;
        int[][] f = new int[m+1][n+1];
        // f[0][i]表示空串S到p[i]需要操作的最小次数
        for(int i = 1; i <= n; i++){
            f[0][i] = i;
        }
        // f[i][0]表示串S到空串P需要操作的最小次数
        for(int i = 1; i <= m; i++){
            f[i][0] = i;
        }
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                //如果s的第i个==p的第j个字符, f[i][j]意味着s[0,i] == p[0,j], 即s[0,i-1] == p[0,j-1],
                if(s.charAt(i) == p.charAt(j)) {f[i][j] = f[i-1][j-1]; continue;}
                f[i][j] = Math.min(Math.min(f[i-1][j], f[i][j-1]),f[i-1][j-1]) + 1;
            }
        }
        return f[m][n];
    }
}



思路

通过观察发现标准路径就是不带任何"..", ".", "//"这类相对路径的标识的字符串.
".."具有返回上层的作用, 栈的pop操作可以实现这个作用.
"."具有保持当前目录的作用, 不压栈不弹栈可以实现这个作用.
"/home", 将home压入栈中还是/home压入栈中? 可以考虑将"/"作为分界点, 只将home压入栈中.

代码框架

  1. 初始化空栈
  2. 所有路径以"/"开始,
  3. 所以遍历path时, 从下标1开始
  4. 打针i,j遍历path, 从下标1开始, 对于每个字符
    • 3.1 如果是连续的"/", i++ , j=i;
    • 3.2 如果指针j指向非"/", 持续右移j
    • 3.3 j将停留的位置要么是path遍历结束, 要么是"/"
      • 3.3.1 如果j将path遍历结束, 可以直接substring(i,j)
      • 3.3.2 如果j停留在"/"处, 也可以直接substring(i,j)
    • 3.4 比较substring(i,j) == "..", 栈弹出,相当于回到上一层目录
    • 3.5 比较substring(i,j) == ".", 让i指向j指向的"/", 否则, 表示substring(i,j)是一个合法目录,将其压栈
  5. 边界处理
    • 4.1 所有路径以"/"开始, 因此i,j指针下标从1开始
    • 4.2 遇到".."时, 需要保证栈不为空
    • 4.3 遇到非".", ".."时, 才需要压栈
    • 4.4 所有情况都需要将i更新为j, 让i始终指向分界字符 "/"

java代码

class Solution {
    public String simplifyPath(String path) {
        if(path == null || path.length() < 1) return path;

        Stack<String> stk = new Stack();
        // 主要是边界问题
        for(int i = 1, j = 1; i < path.length(); i++, j = i){
            if(path.charAt(i-1) == '/' && path.charAt(i) == '/') { continue;}
            while(j < path.length() && path.charAt(j) != '/') j++;

            String tmp = path.substring(i, j);
            if("..".equals(tmp) && stk.size() > 0){
                stk.pop();
            }else if(!".".equals(tmp) && !"..".equals(tmp)){
                stk.push(tmp);
            }
            i = j;
        }

        if(stk.size() == 0) return "/";

        StringBuilder sb = new StringBuilder();
        while(stk.size() > 0){
            sb.insert(0, "/"+stk.pop());
        }
        return sb.toString();
    }
}