设计与思考

改变世界的力量

0%

发表于 分类于

题目

LeetCode 14. Longest Common Prefix

思路

  1. index从0开始, 每个字符串取第index个元素, 判断是否相等, 相等则index递增继续计算, 直到不相等为止
  2. 个人觉得问题比较简单, 但是各种边界条件必须考虑到位
    • 数组为空, 数组只有一个字符串, 数组包含””
    • 因为是求前缀, 当index == 0 的元素不相等, 代表不存在最长公共前缀, 可以直接返回 “”
    • 注意 str.charAt(index) 越界问题
      阅读全文 »

发表于 分类于

题目

leetcode 350. Intersection of Two Arrays II

思路

  1. 最原始的想法就是判断数组1的元素, 是否出现在数组2中.
  2. 但如果有重复的元素会导致结果错误, 所以要忽略掉已经判断属于交集的两个数组中的元素
  3. 在这里借用map来协助计算, map结构: <元素, 出现次数>, 遍历数组1并存入map中
  4. 遍历数组2, 判断是否在map中, 存在则value–
  5. 这里并没有新建数组存储结果, 而是直接存到了数组2中, 因为移动计算过的数据不再需要

进阶问题

  1. 若两个数组有序, 算法能否优化?
    阅读全文 »

发表于 分类于

  1. 开闭原则(Open-Closed Principle, OCP)

    对扩展开放, 对修改关闭. 强调用抽象构建框架, 用实现扩展细节.

  2. 单一职责原则(Simple Responsebility Principle, SRP)

    一个类、接口、方法只做一件事.
    假设我们有一个 Class 负责两个职责，一旦发生需求变更，修改其中一个职责的逻辑代码，有可能会导致另一个职责的功能发生故障.
    最好的方式给两个职责分别用两个 Class 来实现, 降低类的复杂度，提高类的 可读性，提高系统的可维护性，降低变更引起的风险.

  3. 依赖倒置原则(Dependence Inversion Principle, DIP)

    设计代码结构时, 高层模块不应该依赖于底层模块, 二者都应该依赖其抽象.

    阅读全文 »

发表于 分类于

题目

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

1
2
3
4
5
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶
阅读全文 »

发表于 分类于

题目

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:

必须在原数组上操作，不能拷贝额外的数组.
尽量减少操作次数.

思路

  • 最初想法:
    1. 遍历数组, 维护首尾两指针, 若当前元素为0, 则与尾指针指向的元素互换位置
    2. 每次循环, 头指针加一, 尾指针指向元素若不为0则一直减一
    3. 当头指针+1=尾指针, 循环结束.

但是这样得到的数组并不能保证原来顺序.

  • 实现:
    1. 遍历两次, 第一次获取到不为0的元素并按照顺序放到数组
    2. 第二次将剩余置空

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void moveZeroes(int[] nums) {
    if (nums == null || nums.length == 0) {
      return;
    }
    int j = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != 0) {
            nums[j++] = nums[i];
        }
    }
    while (j < nums.length) {
        nums[j++] = 0;
    }
}

发表于 分类于

题目

实现一个函数, 可以删除单链表中倒数第K个节点.
要求:
如果链表长度为N, 时间复杂度达到O(N),额外空间复杂度达到O(1)

思路

假设让链表从头开始走到尾, 每移动一步就让K值减一,则当链表走到结尾时:

  • K > 0, 代表K - N > 0, 则K > N,说明链表不存在倒数第K个节点, 不用调整链表
  • K = 0, 代表K = N, 倒数第K个节点就是头节点, 删除头节点即可
  • K < 0, 代表存在该节点, 单链表已经遍历过了, 那么怎么找到要删除的节点的前驱节点呢? (通过node.next = node.next.next来删除)
    1. 重新从头节点遍历, 每移动一步让K加一
    2. 当K等于0时, 移动停止, 移动到的节点就是要删除节点的前驱节点
      阅读全文 »