leetcode 30-Day LeetCoding Challenge Week2

概述

第二周, 题目来自LeetCode一个30天挑战。第二周难度比第一周略显提升，题目不再是单纯的静态问题，存在一些动态操作在其中，下面将自己的理解记录在下来，望大家相互交流，学习备忘之用。

题目地址

思路分析

Middle of the Linked List

给定一个链表, 返回中位数，如果为偶数，返回第二个节点

思路1. 朴素的做法为, 先遍历一次计算链表长度, 根据长度, 再遍历一次获取中位数的node。
该方法时间复杂度O(N) + O(N)

思路2. 进一步思考, 中间节点, 随着链表长度而变化, 注意关注节点间的递推变化，其中关系为len=1, mid=head; len=2, mid=mid->next; len=3, mid = mid; len=4, mid=mid->next。我们不难发现每当长度逐渐+1时, 中间节点会在偶数时进行下一步跳远，奇数时保持不变。因此关键代码路径为mid = head, mid= mid->next if len % 2 == 0
该方式时间复杂度为O(N)

总结.

1) 关注局部与整体, 即中位数与长度的协同变化
2) 关注递推变化

Backspace String Compare

给定两个字符串, #代表退格键, 比较完整操作后, 两个字符串是否相等。如

Input: S = "ab#c", T = "ad#c"
Output: true

思路1. 首先字符串, 本质上为一字符数组, 回退操作, 意味着删除。那么一种朴素的做法为, 利用双指针, 第一个指针对input的字符串进行循环遍历，第二个指针用于指向当可用的位置。如此循环后，第二指针指向新串的结尾，而后以新结尾进行比较即可得到答案。
该方法时间复杂度为O(N)

思路2. 对于回退操作可以理解为对上一个操作的删除，而且是严格的t-1的删除。那么意味着可以利用栈的性质进行处理。PS：此种做法相比于第一种，好处在于对原串无修改；坏处在于需要额外的空间与操作。
该方法的时间复杂度O(N), 常数略大于前者。

总结.

1) 思路一、思路二，在week1中均有体现。这里要强调的是，对input数据是否修改，生产环境中一般会选择后者，信息完整度更高；如果对性能有极致追求，则会选择前者。
2) 原地/非原地，是优化的常见考察点。

Min Stack

在基础栈的功能上，支持返回当前栈中最小元素的操作，即getMin。

思路1. 对于功能性问题, 一定不是单一结构可以解决的。同时这种功能性问题，通常是一个动态的规程，因此我们可以一般的思路是，当n=1时,情况如何、当n=2时,情况如何、当n=n时,情况如何。对于此题来说, 当插入第i个元素时, 最小的元素为min(cur_value, last_min)。可以采用增加一个镜像stack, 用于存放当前的最小min，所有操作同步进行。

stack_raw = [1,0,3,7,2,5]
stack_min = [1,0,0,0,0,0]

总结.

1) 在基础功能之上增加新功能，必然意味着要有额外的数据结构或者操作。因为需要提供更多的信息量。
2) 对于功能性问题而言，要动态的观察问题，如pop/push是一组动态交互操作。

Diameter of Binary Tree

给定一棵二叉树，返回左右子树叶子节点间的最大距离，如下所示

          1
         / \
        2   3
       / \     
      4   5
output:  3
explain: [4,2,1,3] or [5,2,1,3]

思路1. 对于树的题目, 一般性的考虑就是, 任意一个node都是相同的，相同是指，左右节点。那么站在这个角度，这道题可以理解为，对于任意一个node，计算其到左右子树的path和，并取最大。
该方法时间复杂度O(2^N)

总结.

1) 此题当前的解法比较朴素, 直觉上还能更好 cue作者

Last Stone Weight

给定一个数组, nums[i]代表石头的重量, 每次处理重量最大的两个石头, 令x <= y, 则有如下操作

if x == y, x=y=0
if x !=y,  y-x放到nums中

输出数组中最后一个元素, 或zero.

思路1. 考虑每次需要处理最大重量的两个，因此需要待处理的数据有序。此题的处理过程, 重点在维护数据的序上，同时整个过程是一个动态的过程。因此通用办法为，大顶堆/小顶堆，进一步考虑，若数据自身有特点，可以考虑如桶排序这种结构，利用空间交换时间。
该方法的复杂度为O(Nlog(N)

总结.

1) 主要考虑了序与动态交互式操作的处理。

Contiguous Array

给定一个数组，数组中的元素只有0,1，找到一个最长的连续子数组，使得其中的0,1 个数相同

思路1. 朴素的做法, 分别对0,1的个数做前缀数量的计算。那么当给定[i, j]后，利用前缀数组，可以快速求出区间内的one的数量与zero的数量。
该算法时间复杂度为O(N^2)

总结

1) O(N^2)解法非最优, 利用减枝, 勉强AC
2) 最优解, cue作者

Perform String Shifts

给定一个字符串, 定义操作数, 操作数为对strings[i], 进行了左移or右移一个例子如下

Input: s = "abc", shift = [[0,1],[1,2]]
Output: "cab"
Explanation: 
[0,1] means shift to left by 1. "abc" -> "bca"
[1,2] means shift to right by 2. "bca" -> "cab"

思路1. 首先对于操作数的题目而言, 是存在周期性的。其次, 对任意某一个字符的操作，等价于对所有字符进行了移动。最后，题干中的操作数有左右两种，这两种操作是可以互相抵消的。基于上述的讨论，我们对题目的操作数进行简化后，则变成了字符串的拼接操作，e.g. 令[0, n]为原串, 向左移动2个单位则新串表示为 [2, n] + [0, 2]

总结

1) 这里的周期性，和mod是相似的，同时字符串的循环移动等操作，也是字符串的基础操作。