swzxsyh

--笔记

0%

LeetCode 记录

发表于 更新于
  • 记录刷题记录相关
  • Base Structure
  • Algorithm
  • LeetCode
  • Other

Base Structure

Algorithm

BFS与DFS区别

字符串移动

  • 给定一个字符串，这个字符串为号和26个字母的任意组合。现在需要把字符串的号都移动到最左侧，而把字符串中的字母移动到最右侧并保持相对顺序不变，要求时间复杂度和空间复杂度最小。

约瑟夫环

  • 想象 0 到 n-1 个人围成一个圈，每个人中的距离是相等的，试求出第 firstNumber 号对面的人是几号

  • 对于n个人围成一圈，第 i个人对面的人的编号为 (i + n/2) % n。这个公式基于的原理是，在一个环中，每个人与对面的人的编号之和都是环的大小的一半。因此，我们可以将i的编号加上n/2，然后对 n 取模，就可以得到i对面的人的编号。

    1
    2
    3
    public int oppositePerson(int n, int firstNumber) {
        return (firstNumber + n / 2) % n;
    }

二叉树

1
2
3
4
5
6
     A
   /   \
  B     C
 / \   / \
D   E F   G

二叉树前序遍历

  • 先访问当前节点，然后依次访问当前节点的左子树和右子树。即先根节点，再左子树，最后右子树的顺序。

  • 前序遍历结果：A B D E C F G

    1
    2
    3
    4
    5
    6
    7
    8
    public void preOrder(TreeNode treeNode) {
        if (Objects.isNull(treeNode)) {
            return;
        }
        log.info((String) treeNode.val);
        preOrder(treeNode.left);
        preOrder(treeNode.right);
    }

二叉树中序遍历

  • 先访问当前节点的左子树，然后访问当前节点，最后访问当前节点的右子树。即先左子树，再根节点，最后右子树的顺序。

  • 中序遍历结果：D B E A F C G

    1
    2
    3
    4
    5
    6
    7
    8
    public void inOrder(TreeNode treeNode) {
        if (Objects.isNull(treeNode)) {
            return;
        }
        inOrder(treeNode.left);
        log.info((String) treeNode.val);
        inOrder(treeNode.right);
    }

二叉树后序遍历

  • 先访问当前节点的左子树和右子树，然后访问当前节点。即先左子树，再右子树，最后根节点的顺序。

  • 后序遍历结果：D E B F G C A

    1
    2
    3
    4
    5
    6
    7
    8
    public void postOrder(TreeNode treeNode) {
      if (Objects.isNull(treeNode)) {
          return;
      }
      postOrder(treeNode.left);
      postOrder(treeNode.right);
      log.info((String) treeNode.val);
    }

二叉树层序遍历

  • 从二叉树的根节点开始，按照从上到下、从左到右的顺序，依次遍历二叉树的每一层节点。也就是按照树的深度，从上到下逐层遍历，同一层的节点按照从左到右的顺序访问。

  • 常用的实现方法是使用队列，先将根节点加入队列中，然后从队列中取出节点进行访问，同时将该节点的左子节点和右子节点加入队列中，再重复这个过程直到队列为空。这样就可以实现二叉树的层序遍历。

  • 层序遍历结果： A B C D E F G

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    @Override
    public void sequenceOrder(TreeNode treeNode) {
        if (treeNode == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        //根节点入队
        queue.add(treeNode);
        while (!queue.isEmpty()) {
            //节点出队
            TreeNode node = queue.poll();
            log.info((String) node.val);
            //节点左子树入队
            if (node.left != null) {
                queue.add(node.left);
            }
            //节点右子树入队
            if (node.right != null) {
                queue.add(node.right);
            }
        }
    }

二分查找

查找比某个数字数大的最小数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * 查找比某个数字数大的最小数
 *
 * @return 数组下标
 */
public int searchMax(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return left;
}

查找比某个数字数小的最大数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
   * 查找比某个数字数小的最大数
   *
   * @return 数组下标
   */
  public int searchMin(int[] nums, int target) {
      // 定义左右指针
      int left = 0, right = nums.length - 1;
      // 当左指针小于等于右指针时，继续查找
      while (left <= right) {
          // 计算中间位置
          int mid = left + (right - left) / 2;
          // 如果中间位置的数大于等于目标数
          if (nums[mid] >= target) {
              // 将右指针移动到中间位置的左边
              right = mid - 1;
              // 如果中间位置的数小于目标数
          } else {
              // 将左指针移动到中间位置的右边
              left = mid + 1;
          }
      }
      // 返回比目标数小的最大数的下标
      return right;
  }

LeetCode

LeetCode 21 合并两个有序链表

LeetCode 77 组合

LeetCode 94 二叉树的中序遍历

LeetCode 102 输出一个二叉树的宽度

LeetCode 121 买卖股票的最佳时机

  • 贪心算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static int maxProfit(int[] prices) {

    int minPrice = prices[0];
    int maxProfit = 0;

    for (int i = 0; i < prices.length; i++) {
        if (prices[i] < minPrice) {
            minPrice = prices[i];
        }

        if ((i + 1) < prices.length && prices[i + 1] > minPrice) {
            if (prices[i + 1] - minPrice > maxProfit) {
                maxProfit = prices[i + 1] - minPrice;
            }
        }
    }
    return maxProfit;
}

LeetCode 122 买卖股票的最佳时机 II

  • 贪心算法
1
2
3
4
5
6
7
8
9
10
11
12
public static int maxProfit(int[] prices) {
    int maxProfit = 0;
    int currentProfit;

    for (int i = 0; i < prices.length; i++) {
        if (i + 1 < prices.length && prices[i] < prices[i + 1]) {
            currentProfit = -prices[i] + prices[i + 1];
            maxProfit += currentProfit;
        }
    }
    return maxProfit;
}

LeetCode 144 二叉树的前序遍历

LeetCode 145 二叉树的后序遍历

LeetCode 165 版本号比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public int compareVersion(String version1, String version2) {
    String[] splitV1 = version1.split("\\.");
    String[] splitV2 = version2.split("\\.");

    if (splitV1.length == splitV2.length) {
        for (int i = 0; i < splitV1.length; i++) {
            if (Integer.parseInt(splitV1[i]) > Integer.parseInt(splitV2[i])) {
                return 1;
            }
            if (Integer.parseInt(splitV1[i]) < Integer.parseInt(splitV2[i])) {
                return -1;
            }
        }
        return 0;
    }


    int shortLength = Math.min(splitV1.length, splitV2.length);

    StringBuilder sbV1 = new StringBuilder();
    StringBuilder sbV2 = new StringBuilder();
    for (int i = 0; i < shortLength; i++) {
        sbV1.append(Integer.valueOf(splitV1[i]));
        sbV2.append(Integer.valueOf(splitV2[i]));
    }

    int result = sbV1.toString().compareTo(sbV2.toString());
    if (result == 0) {
        if (splitV1.length == shortLength) {
            for (int i = shortLength; i < splitV2.length; i++) {
                if (Integer.parseInt(splitV2[i]) > 0) {
                    return -1;
                }
            }
        }
        for (int i = shortLength; i < splitV1.length; i++) {
            if (Integer.parseInt(splitV1[i]) > 0) {
                return 1;
            }
        }
    }
    return result;
}

LeetCode 179 最大数

  • 重点方法：自定义比较器Comparator
1
2
3
4
5
6
7
8
9
10
11
12
public String largestNumber(int[] nums) {
    StringBuilder sb = new StringBuilder();

    Arrays.stream(nums).mapToObj(String::valueOf).sorted((o1, o2) -> {
        String str1 = o1 + o2;
        String str2 = o2 + o1;

        return str2.compareTo(str1);
    }).map(sb::append).collect(Collectors.joining());

    return sb.charAt(0) == '0' ? "0" : sb.toString();
}

LeetCode 206 单链表反转

LeetCode 300 最长上升子序列

输入: [10,9,2,5,3,7,101,18]

输出: 4 ，最长的上升子序列是 [2,3,7,101]，它的长度是 4。

  • DP算法

剑指Offer

剑指offer42

TODO

剑指offer43

TODO

Other

数组中找出最长连续序列

TODO

判断一个输入宇符串（只考虑宇母，不区分大小写）是否是回文串

TODO

从一个字符串中找到第一个不重复的字符，返回它的索引。如果不存在，则返回-1

TODO

100个元素的数组中找出长度为3的出现次数最多的元素

TODO

用代码实现两个数字宇符串相加，不限制长度

TODO

主要是将字符串拆分成char数组，从个位开始相加，满十进一，其中代码需要注意char向 int转换的问题。

LeetCode 上合并 区间的题

TODO

二叉树的最近公共祖先

TODO

有序数组合并

TODO

什么是平衡二叉树、最小堆

TODO

字符串消消乐

TODO

链表如何快速查找到两个相关的值

阿拉伯数字转汉字

思路：将“零一二三四五六七八九”、“十百千万亿”这些结果用到的字符存到数组，然后将阿拉伯数字转字符串，遍历拼接结果。

字符串的全排列

输入：s = “abc”

输出：[“abc”,”acb”,”bac”,”bca”,”cab”,”cba”]

有序列表，找出所有两数之和为10000的组合

可以用 HashMap 来存遍历过的数字，每次遍历时检查下 HashMap 里是否有目标数字，时间复杂度O(n)，空间复杂度为O(n)。

用双指针，从列表的两边向中间扫，和小于10000，则左指针右移，和大于10000，则右指针左移，双指针理论上没有使用额外的空间。

链表倒数第N个节点算法

单链表奇数节点移动到最前面

输入：a1->a2->a3->a4->a5

输出：a1->a3->a5->a2->a4

打印文件目录结构树

TODO

扑克牌游戏：给5张牌计算牛牛个数

TODO

(o/1/2） 其实是比较简单的两数之和

无向图：找出孤立节点

TODO

虽然是图，但给的数据格式很简单，找到规则遍历即可

获得最优推荐路径 热力值最大

TODO

是道应用题，考的知识点其实是树、最长路径、动态规划。
在参加笔试的时候因为关于树我没有复习，直接卡在数据处理上，稍微骗了点分就提交了

判断2个单链是否有交叉

TODO

2个栈实现一个队列

TODO

最小覆盖子串

TODO

判断链表是否有环

TODO

Java如何实现一个阻塞队列

TODO

手写HashMap

TODO

质量不同的球体中，最快最少次数找出质量最轻的球

分治法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int getLightestBall(int[] balls) {
      int mid = balls.length / 2;
      int arrayLeft = compare(balls, 0, mid);
      int arrayRight = compare(balls, mid + 1, balls.length - 1);
      log.info("left: {} ,right: {}", arrayLeft, arrayRight);
      return Math.min(arrayLeft, arrayRight);
  }

  private int compare(int[] array, int start, int end) {
      if (array.length < 2) {
          return array[0];
      }

      int lightest = array[start];

      for (int i = start; i < end; i++) {
          int tmp = Math.min(array[i], array[i + 1]);
          if (tmp < lightest) {
              lightest = tmp;
          }
      }
      return lightest;
  }

锦标赛算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private int compare(int[] array, int start, int end) {
    // 当前比较区间只有一个元素时，直接返回该元素
    if (start == end) {
        return array[start];
    }

    // 将当前比较区间分为两个子区间，分别进行递归比较
    int mid = (start + end) / 2;
    // 比较左子区间
    int leftLightest = compare(array, start, mid);
    // 比较右子区间
    int rightLightest = compare(array, mid + 1, end);

    // 比较左右子区间的最轻元素，返回最轻元素
    return Math.min(leftLightest, rightLightest);
}

兔子跳下台阶，一次只能跳2阶台阶或3阶台阶，n个台阶至少要跳几次能跳下去，如果跳不下去返回-1

  • 纯计算

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    private int calculate(int fullSteps) {
        int count = fullSteps / 3;

        int remainStep = fullSteps - count * 3;

        if (remainStep > 0) {
            int i = remainStep / 2;
            count = count + i;

            remainStep = remainStep - i * 2;

            if (remainStep > 0) {
                return -1;
            }
        }
        return count;
    }

  • 递归

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    public int jump(int n) {
          if (n == 2 || n == 3) {
              return 1;
          } else if (n < 2) {
              return -1;
          } else {
              int twoSteps = jump(n - 2);
              int threeSteps = jump(n - 3);
              if (twoSteps == -1 && threeSteps == -1) {
                  return -1;
              } else if (twoSteps == -1) {
                  return threeSteps + 1;
              } else if (threeSteps == -1) {
                  return twoSteps + 1;
              } else {
                  return Math.min(twoSteps, threeSteps) + 1;
              }
          }
      }

  • DP

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    public int calculate(int fullSteps) {
          if (fullSteps < 2) {
              return -1; // Impossible to traverse the staircase
          }

          int[] dp = new int[fullSteps + 1];
          dp[0] = 0;
          dp[1] = 1;

          for (int i = 2; i <= fullSteps; i++) {
              dp[i] = Integer.MAX_VALUE;
              if (i - 2 >= 0) {
                  dp[i] = Math.min(dp[i], dp[i-2] + 1);
              }
              if (i - 3 >= 0) {
                  dp[i] = Math.min(dp[i], dp[i-3] + 1);
              }
          }

          if (dp[fullSteps] == Integer.MAX_VALUE) {
              return -1; // Impossible to traverse the staircase
          } else {
              return dp[fullSteps];
          }
      }

螺旋打印二维数组

  • 给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。

    1

日期之差，多少天，需要计算闰月

查找单入口空闲区域

时间限制：1s空间限制：256MB 限定语言：不限
题目描述：
给定一个m x n的矩阵，由若干字符X和O构成，X表示该处已被占据，O表示该处空闲，请找到最大的单入口空闲区域。
解释：
空闲区域是由连通的O组成的区域，位于边界的O可以构成入口，单入口空闲区域即有且只有一个位于边界的O作为入口的由连通的O组成的区域
如果两个元素在水平或垂直方向相邻，则称它们是“连通”的，

输入描述：
第一行输入为两个数字，第一个数宇为行数m，第二个数宇列数n，两个数字以空格分隔，1<=m,n <=200,
剩余各行为矩阵各行元素，元素为X或O，各元素间以空格分隔。
输出描述：
若有唯一符合要求的最大单入口空闲区域，输出三个数字，第一个数宇为入口行坐标(范围为0-行数-1），第二个数
字为入口列坐标（范国为0~列数-1），第三个数宇为区域大小，三个数宇以空格分隔;
若有多个符合要求的最大单入口空闲区域，输出一个数字，代表区域的大小；
若没有，输出NUL。

给定两个字符串string1和Istring2.

string1是一个被加扰的宇符串。string1由小写英文宇母(‘a’‘z’)和数字字符(‘0’‘9’)组成，而加扰宇符串由‘0’‘9’、’af’组成。string1里面可能包含0个或多个加扰子串，剩下可能有0个或多个有效子串，这些有效子串被加扰子串隔开。

string2是一个参考字符串，仅由小写英文字母(‘a’~’z’)组成。
你需要在string1字符串里找到一个有效子串，这个有效子串要同时满足下面两个条件：
(1)这个有效子串里不同字母的数量不超过且最接近于string2里 不同宇母的数量，即小于或等于string2里 不同宇母的数量的同时且最大。
(2)这个有效子串是满足条件(1)里的所有子串(如果有多个的话)里宇典序，最大的一个。
如果没有找到合适条件的子串的话，请输出”Not Found”

快递投放问题

有N个快递站点用字符串标识，某些站点之间有道路连接。
每个站点有一些包裹要运输，每个站点间的包裹不重复，路上有检查站会导致部分货物无法通行，计算哪些货物无法正常投递？

输入描述

第一行输入M N，M个包裹N个道路信息.
后面M行分别输入包裹名、包裹起点、包裹终点
后面N行分别表示两个站点之间不能通过的包裹名。检查站禁止通行的包裹如果有多个以空格分开
检查站禁止通行的包裹如果有名个以空格公开

快递员问题

提供一个数组，数组各项代表一个地址，内容为1或者0，1代表此地有包裹需要快递员配送，0代表此地没有包裹需要配送
每个快递员可以配送指定位置及其左右相邻三个地方，问至少需要多少快递员可以把快递送完

岛屿数量

手写LRU

页面置换？淘汰算法？ LRU用基础数据结构的实现思路？

字符串序列化

动态规划

求字符串中最大不重复的子串并输出