Linked List

对于一个有一个next指针和一个数字的一个node,他的大小是8个字节
next指针4个字节,数字4个字节。
如果一个指针,指向这个node.这个指针占用4个字节

  • 指针问题,因为node1, node2, node3都是指向真正的数据的指针而已。所以无论如何操作不会改变这个链表的结构。如下面的代码
1
2
3
4
5
6
7
8
9
10
11
ListNode *node1 = ListNode.new();
ListNode *node2 = ListNode.new();
ListNode *node3 = ListNode.new();
node1.next = node2;
node2.next = node3;

ListNode *head = node1;
print(head);

node1 = node2;
print(head);
  • Dummy Node,当头部节点会发生变化的时候就需要使用dummy node.
    RemoveDuplicates from sorted list II: 因为删除之后head可能就变化了。所以加了一个dummy先指向最前面,返回也是返回dummy.next.然后如果 current.next.val == current.next.next.val,这个时候记录下val,然后将等于val的都删掉
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def deleteDuplicates(self, head):
# write your code here
# node = head
dummy = ListNode(-1)
dummy.next = head
current = dummy
while current.next and current.next.next:
if current.next.val == current.next.next.val:
val = current.next.val
while current.next and current.next.val == val:
current.next = current.next.next
else:
current = current.next
return dummy.next

有一个链表。每走n布就需要翻转一下前n个

1
2
3
4
5
6
7
8
9
10
先画一个图,这样可以更清楚的理论清楚思路
head -> n1->n2->...nk->nk+1...
=>
head -> nk->nk-1....n1->nk+1...
因为第一个节点会发生变化,如果做一个reverse的函数,返回的是新的head,老的就跑到别的地方去了。所以这个时候最好创建一个dummyNode

ListNode *dummy = [ListNode new];
dummy.next = head;
// 调用reverse函数
之后返回dummy.next;
  • 翻转一个链表(四句话)
    1->2->3->4->..N->
    None<- 1 <-2 <-3 <-4…<-N
1
2
3
4
5
6
7
8
9
prev = None
current = head;
while(current!=None){
#一根指针指向prev,一根指针指向current
tmp = current.next #临时存一下
current.next = prev #真正改变当前的next
prev = current #改变prev
current = tmp #改变current
}
  • 翻转链表的从m到n(reverse linked list 2)
    分了三部分,一个是findkth, 一个是reverse,另外就是把整个的逻辑接上
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
from lintcode import ListNode
class Solution:

def reverse(self, head):
prev = None
while head != None:
next = head.next
head.next = prev
prev = head
head = next
return prev

def findkth(self, head, k):
for i in xrange(k):
if head is None:
return None
head = head.next
return head

def reverseBetween(self, head, m, n):
dummy = ListNode(-1, head) # 以为有可能会影响到第一个,所以也需要dummynode
mth_prev = self.findkth(dummy, m - 1)
mth = mth_prev.next
nth = self.findkth(dummy, n)
nth_next = nth.next
nth.next = None

self.reverse(mth) # 其实可以用返回值也可以不用,因为改的是值
mth_prev.next = nth
mth.next = nth_next
return dummy.next
  • Insert into a Cyclic Sorted List :这个注意,有几个特殊条件,一个是none的时候,一个是正常>=prev <= next的时候,还有就是,当插入的值是最大值或者最小值。 或者当回到原点(判断指针)。这几个条件,都终止。用whileTrue
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
class Solution:
"""
@param: node: a list node in the list
@param: x: An integer
@return: the inserted new list node
"""

def insert(self, node, x):
# write your code here
if node is None:
node = ListNode(x)
node.next = node
return node

p = node
prev = None
while True:
prev = p
p = p.next
if x <= p.val and x >= prev.val:
break
if (prev.val > p.val) and (x < p.val or x > prev.val):
break;
if p is node:
break
newNode = ListNode(x)
newNode.next = p
prev.next = newNode
return newNode
  • 翻转链表的k个点,多少个点的next会受到影响?(k+1),比如n0->n1->n2->n3->n4->, reverse n1到n3那么n0这个时候也会受到影响。

  • High Frequency

Array

  • Subarray
  • Sorted Array
x quick sort merge sort heep sort
时间 O(nlog n) O(nlogn) O(n log n)
空间 O(1) O(n + logn)(O(n)) O(1)
稳定

merge sort空间复杂度为什么是O(n+logn)?因为归并排序需要存放于原始记录同等数量的存储空间存放归并结果,并且递归深度为logn的栈空间,所以空间复杂度为O(n+logn).

  • subarray sum:这个思路比较奇怪,当然dfs也是可以做。但是这个方法就是,首先,计算每一个数当时的sum是多少,另外,如果同样出现了相同的sum,那么则表示,之前那个sum到现在的sum,中间的和是0
1
2
3
4
5
6
7
8
9
10
11
def subarraySum(nums):
hs = {0:-1}
all_sum = 0
for i in range(len(nums)):
all_sum = all_sum + nums[i]
print all_sum, hs
if all_sum in hs:
print all_sum, hs, 'bingo'
return [hs[all_sum] + 1, i]
hs[all_sum] = i
return
  • subarray多用到前缀和(prefixsum),构造前缀和的话耗费O(n)时间和O(n)的空间,这个时候可以用任意O(1)的时间来计算i,j之间的和。如maximsum那个题,首先知道那个是miminumsum,然后用当前的减去minimumsum如果是更大,那么就替换。