设计与思考

题目

LeetCode 53. 最大子序和

思路

• 对数组进行遍历，当前最大连续子序列和为 sum，缓存结果为 ans
• 如果 sum > 0，则说明 sum 结果是好的, 累加当前遍历的值
• 如果 sum <= 0，则sum结果是坏的, 需要舍弃，则 sum 直接更新为当前遍历的值
• 每次比较 sum 和 ans的大小，将最大值置为ans，遍历结束返回结果
  阅读全文 »

题目

LeetCode 2. Add Two Numbers

思路

1. 两个逆序存储数值的链表, 要求返回数值相加结果并且逆序存储的链表.

2. 就两个链表一起遍历, 每一位相加:

   • 若小于10直接拼接到新链表中
   • 若大于10, 则个位数拼接到新链表, 十位数加入到下一个链表节点的计算中(实际就是进位)

其实就是两数相加, 链表的头节点就是个位, 依此类推.

题目:

LeetCode 141. Linked List Cycle

思路:

1. 最先想到的是遍历链表, 并将结点的内存地址存在HashSet中.如果当前结点的内存地址已经存在,则表示存在环,直接返回true
2. 还可以用双指针(快慢指针)来解决, 如果两个指针相遇(套圈), 则代表存在环.
   阅读全文 »

题目:

LeetCode 21. Merge Two Sorted Lists

思路:

基本思想就是新建一个链表, 然后从两个列表的头结点分别依次比较大小, 并将较小的插入新链表中.
实现1: 递归实现
实现2: 两个链表依次遍历插入新链表

题目

LeetCode 19. Remove Nth Node From End of List

思路

思路一:

1. 单链表, 无法从尾结点往前遍历. 那么可以将倒数第N个结点转为第L-N+1个正数节点
2. 长度L可以提前遍历一次来求值
3. 移除第L - N + 1个节点

思路二:

1. 利用双指针
2. 先让两个指针相隔N - 1的位置
3. 然后双指针同步后移
4. 当第二个指针到了尾部, 第一个指针恰好在倒数第N个节点的前驱位置.
   阅读全文 »

题目

LeetCode 6. ZigZag Conversion

思路

1. 最开始想的就是一个二维数组, 它把原字符串, 按照规律放入固定位置, 最后再拼接
2. 那么又分为两个问题
   • 二维数组要考虑越界和合并判断问题
   • 这个Z(明明是N!)的规律是什么
3. 关于Z的规律只能说, 在纸上画一下2行,3行的情况, 发现规律是2n-2个字母为一个循环周期, 再拿4行验证一下
4. 另外选用了字符串来替代一维数组, 直接拼接保存该行
   阅读全文 »

题目

LeetCode 15. 3Sum

思路

1. 采用固定一个数, 双指针寻找另外两个数
2. 排序后开始处理, 注意几个情况:
   1. nums[i] > 0, 代表后面的数都会大于0, 没必要计算了
   2. 跳过固定数值重复的情况
   3. 跳过left指针、right指针重复的情况
      阅读全文 »

题目

LeetCode 66. Plus One

思路

难度在于要考虑到所有情况:

1. 末位 ≠ 9, 直接++, 返回数组
2. 末位 == 9, 且存在某位 ≠ 9, 在该位 ++ , 返回数组
3. 末位 == 9 , 前面所有位都是9, 新建一个数组, 首位置为1, 返回
   阅读全文 »

题目

LeetCode 27. Remove Element

思路

这道题目, 把题意读明白就好做了.
预定义的方法中要求返回int类型长度len, 但代码提交时, 却是按照 nums中[0, len)的区间输出判断的.
所以最终需要注意的是:

1. O(1) 空间复杂度
2. nums中跟val不等的元素, 要往前移
   阅读全文 »

题目

LeetCode 189. Rotate Array

思路

实现1: 利用一个额外的数组

1. 目标: 将数组1中每一个元素, 移动到额外数组目标索引位置
2. 目标索引 = (现在位置 + 步数) % 长度
3. 最终将额外数组元素再复制回原数组
   PS: 这里要注意 java中 Arrays.copyOf(), System.arraycopy(), clone() (对象是深拷贝, 对数组是浅拷贝) 几种浅拷贝

实现2: 分析数组翻转后的元素排列, 使用位置互换