KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode 127 Word Ladder



Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

1. Only one letter can be changed at a time.
2. Each transformed word must exist in the word list.

Note:

Return 0 if there is no such transformation sequence. All words have the same length.
All words contain only lowercase alphabetic characters. You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

Input:
beginWord = “hit”,
endWord = “cog”,
wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]

Output: 5

Explanation: As one shortest transformation is “hit” -> “hot” -> “dot” -> “dog” -> “cog”,
return its length 5.


Example 2:

Input:
beginWord = “hit”
endWord = “cog”
wordList = [“hot”,”dot”,”dog”,”lot”,”log”]

Output: 0

*Explanation: The endWord “cog” is not in wordList, therefore no possibletransformation.


题目大意：

给定一个字典和两个单词。每次变换一个字母的得到新单词且该词要在字典中。求最少变换次数。

解题思路：

这题是最短路径题，第一时间想到BFS。这是一条典型的单源最短路径问题。

  1. 这是图，所以要有visited记录是否重复访问。
  2. 字典的实现两个作用： 快速查找，以及记录距离可以省下一轮循环。总共两重循环。
  3. getNextWords的实现。通过变换每位上字母，比较巧妙。

解题步骤：

这题是最短路径题，第一时间想到BFS。这是一条典型的单源最短路径问题。

  1. 建字典。
  2. BFS访问。
  3. 求所有距离为1的相邻单词getNextWords。

注意事项：

  1. 注意题目条件，开始词不在字典中(终结词默认在，否则无结果），要将它加入字典中且距离为1。
  2. 用Map来记录解(儿子节点，参考按层搜索)，visited用于记录父节点
  3. getNextWords的实现不含自己。
  4. Python中用popleft出列，不是pop

Python代码：

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
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
	if not beginWord or not endWord:
		return 0
	distance = {}
	for word in wordList:
		distance[word] = 0
	distance[beginWord] = 1
	return self.bfs(beginWord, endWord, distance, set())

def bfs(self, beginWord, endWord, dict, visited):
	queue = deque([beginWord])
	visited.add(beginWord)
	while queue:
		word = queue.popleft()
		if word == endWord:
			return dict[word]

		neighbors = self.get_next_words(word, dict)
		for neighbor in neighbors:
			if neighbor not in visited:
				queue.append(neighbor)
				visited.add(neighbor)
				dict[neighbor] = dict[word] + 1

	return 0

def get_next_words(self, word, dict):
	res = []
	for i in range(len(word)):
		for c in string.ascii_lowercase: # or use 'abcdefghijklmnopqrstuvwxyz'
			if c == word[i]:
				continue
			new_word = word[:i] + c + word[i + 1:]
			if new_word in dict:
				res.append(new_word)
	return res

Java代码：

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
44
45
46
47
48
49
50
51
52
53
54
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
	// This is a dict and also keeps track of distance
	Map<String, Integer> dict = getDict(wordList);
	// Make sure endWord is in the dict and can be the next word 
	//dict.put(endWord, 0);
	dict.put(beginWord, 1);
	
	Set<String> visited = new HashSet<>();
	Queue<String> q = new LinkedList<>();
	q.offer(beginWord);
	visited.add(beginWord);
	while(!q.isEmpty()) {
		String word = q.poll();
		if(endWord.equals(word))
			return dict.get(word);
		
		List<String> nextWords = getNextWords(word, dict);
		for(String s : nextWords) {
			if(visited.contains(s))
				continue;
			
			q.offer(s);
			visited.add(s);
			dict.put(s, dict.get(word) + 1);
			
		}
	}
	return 0;
}

Map<String, Integer> getDict(List<String> wordList) {
	Map<String, Integer> map = new HashMap<>();
	for(String word : wordList) {
		map.put(word, 0);
	}
	return map;
}

List<String> getNextWords(String word, Map<String, Integer> dict) {
	List<String> result = new ArrayList<>();
	for(int i = 0; i < word.length(); i++) {
		for(int j = 0; j < 26; j++) { 
			char newChar = (char)('a' + j);
			if(word.charAt(i) == newChar) // exclude itself
				continue;
			String newWord = word.substring(0, i) + 
					newChar + word.substring(i + 1, word.length());
			if(dict.containsKey(newWord))
				result.add(newWord);
			
		}
	}
	return result;
}

算法分析：

getNextWords是L26L=O(L2)产生新字符串需要L
时间复杂度为O(n*L2)，空间复杂度O(n)，n为单词数。

算法II解题思路：

利用双向BFS，参考双向BFS概念
如果搜索不够广的话(例如类似于一条直线)，BFS会较慢，用双向BFS可解决此问题。双向BFS就是同时从起点和终点两个方向开始搜索，结果分存在map中，如果节点在另一个map中，
就意味着找到了一条连接起点和终点的最短路径。若任一queue为空，表明不会存在路径。如下图，前向BFS找到了结果。

搜索方式分为同步搜索和队列容量较少的先搜。本法采取前者

解题步骤：

  1. 与单向BFS类似，但由于现在是双向，所以将BFS的通用部分提取出来，变量为queue, visited, distance, target_distance, target_distance是查找本方向
    的节点是否在对方搜索过的路径上代替endWord，距离为本方向的路径+对方的路径。while循环移到调用函数中。
  2. while循环用两个queue不为空
  3. 为了优化get_next_words重复调用，将结果存在graph中形成邻接表。这样的话，distance不用初始化为0，还可以用于记录重复节点代替visited。
  4. 其他初始化步骤给endWord的BFS复制一次。

注意事项：

  1. graph = collections.defaultdict(list)避免NPE，dict都尽量用此法

Python代码：

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
def ladderLength2(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
	if not beginWord or not endWord:
		return 0
	wordList.append(beginWord)
	graph, word_dict = collections.defaultdict(list), set(wordList)
	for word in wordList:
		graph[word] = self.get_next_words(word, word_dict)
	forward_distance, backward_distance = collections.defaultdict(int), collections.defaultdict(int)
	forward_distance[beginWord], backward_distance[endWord] = 1, 0

	forward_queue, backward_queue = deque([beginWord]), deque([endWord])
	forward_visited, backward_visited = set([beginWord]), set([endWord])
	while forward_queue and backward_queue:
		total_dis = self.bfs_from_start_or_end(graph, forward_queue, forward_distance, backward_distance)
		if total_dis > 0:
			return total_dis
		total_dis = self.bfs_from_start_or_end(graph, backward_queue, backward_distance, forward_distance)
		if total_dis > 0:
			return total_dis
	return 0

def bfs_from_start_or_end(self, graph, queue, distance, target_dict):
	word = queue.popleft()
	if word in target_dict and target_dict[word] > 0:  # the forward distance has all words initially
		return distance[word] + target_dict[word]

	neighbors = graph[word]
	for neighbor in neighbors:
		#if neighbor in visited:
		if neighbor in distance:
			continue
		queue.append(neighbor)
		# visited.add(neighbor)
		distance[neighbor] = distance[word] + 1
	return 0

Posted on Edited on Disqus:

LeetCode



You have a queue of integers, you need to retrieve the first unique integer in the queue.

Implement the FirstUnique class:

FirstUnique(int[] nums) Initializes the object with the numbers in the queue. int showFirstUnique() returns the value of the first unique integer of the queue, and returns -1 if there is no such integer.
void add(int value) insert value to the queue.

Example 1:

Input:
[“FirstUnique”,”showFirstUnique”,”add”,”showFirstUnique”,”add”,”showFirstUnique”,”add”,”showFirstUnique”]
[[[2,3,5]],[],[5],[],[2],[],[3],[]]
Output:
[null,2,null,2,null,3,null,-1]
Explanation:
FirstUnique firstUnique = new FirstUnique([2,3,5]);
firstUnique.showFirstUnique(); // return 2
firstUnique.add(5);            // the queue is now [2,3,5,5]
firstUnique.showFirstUnique(); // return 2
firstUnique.add(2);            // the queue is now [2,3,5,5,2]
firstUnique.showFirstUnique(); // return 3
firstUnique.add(3);            // the queue is now [2,3,5,5,2,3]
firstUnique.showFirstUnique(); // return -1


Example 2:

Input:
[“FirstUnique”,”showFirstUnique”,”add”,”add”,”add”,”add”,”add”,”showFirstUnique”]
[[[7,7,7,7,7,7]],[],[7],[3],[3],[7],[17],[]]
Output:
[null,-1,null,null,null,null,null,17]
Explanation:
FirstUnique firstUnique = new FirstUnique([7,7,7,7,7,7]);
firstUnique.showFirstUnique(); // return -1
firstUnique.add(7);            // the queue is now [7,7,7,7,7,7,7]
firstUnique.add(3);            // the queue is now [7,7,7,7,7,7,7,3]
firstUnique.add(3);            // the queue is now [7,7,7,7,7,7,7,3,3]
firstUnique.add(7);            // the queue is now [7,7,7,7,7,7,7,3,3,7]
firstUnique.add(17);           // the queue is now [7,7,7,7,7,7,7,3,3,7,17]
firstUnique.showFirstUnique(); // return 17


Example 3:

Input:
[“FirstUnique”,”showFirstUnique”,”add”,”showFirstUnique”]
[[[809]],[],[809],[]]
Output:
[null,809,null,-1]
Explanation:
FirstUnique firstUnique = new FirstUnique([809]);
firstUnique.showFirstUnique(); // return 809
firstUnique.add(809);          // the queue is now [809,809]
firstUnique.showFirstUnique(); // return -1


Constraints: 1 <= nums.length <= 10^5
1 <= nums[i] <= 10^8 1 <= value <= 10^8
* At most 50000 calls will be made to showFirstUnique and add.

算法思路：

Dict + LL (1次) + Set (2次)。此题非常类似于LRU, 相当于实习LinkedHashMap。

由易到难

题目 LL Map 其他数据结构
LRU 按时间顺序，头删尾入 值->LL节点 N/A
First Unique 按时间顺序，任意删尾入 值->LL节点 Set存两次以上
LFU 多个时间顺序的LL 值->LL节点 第二个Map存freq-> LL的首节点以及min_freq

注意事项：

  1. 注意两种情况，节点不在Map, 在Map中，对应的LL操作同样是add_to_tail和remove_node不过少了move_to_tail。
  2. 头尾dummy node，初始化要相连。
  3. 注意删除顺序，先删map中的entry再删Node。否则会出现NPE。新加入是顺序相反。删除节点要将prev和next赋None
  4. 区别还有ListNode不需要key，因为输入是单值，不是key-value对。数据结构多了set来记录出现两次及以上的元素，直接忽略

Python代码：

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class FirstUnique(TestCases):

    '''
    2, 3, 5, 5
    dict:
    {2:1
     3:1
     5:2 (remove)
     }
    LinkedList: 2, 3, 5(r), 5(r)
    dict:
    {
        2: Node(2)
        3: Node(3)
        5: Node(5)
    }
    
    '''

    def __init__(self, nums: List[int]):
        self.head = ListNode(0)  # only store unique elements
        self.tail = ListNode(0)
        self.key_to_node = {}  # only store unique elements
        self.non_unique_set = set()
        self.head.next, self.tail.prev = self.tail, self.head

        for n in nums:
            self.add(n)

    def showFirstUnique(self) -> int:
        if len(self.key_to_node) == 0:
            return -1
        return self.head.next.val
    # 2, 3, 5, 5
    def add(self, value: int) -> None:
        if value in self.non_unique_set:
            return

        if value not in self.key_to_node:
            new_node = ListNode(value)
            self.add_to_tail(new_node)
            self.key_to_node[value] = new_node
        else:
            to_be_removed_node = self.key_to_node[value]
            self.key_to_node.pop(value)
            self.remove_node(to_be_removed_node)
            self.non_unique_set.add(value)

    def add_to_tail(self, node):
        predecessor = self.tail.prev
        predecessor.next, node.prev = node, predecessor
        node.next, self.tail.prev = self.tail, node

    def remove_node(self, node):
        predecessor, successor = node.prev, node.next
        predecessor.next, successor.prev = successor, predecessor
        node.prev, node.next = None, None


class ListNode:

    def __init__(self, val, next = None, prev = None):
        self.val = val
        self.next = next
        self.prev = prev

算法分析：

每个操作时间复杂度为O(1)，空间复杂度O(n).

Posted on Edited on Disqus:

LeetCode 146 LRU Cache



Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

The cache is initialized with a positive capacity.

Follow up:
Could you do both operations in O(1) time complexity?

Example:

LRUCache cache = new LRUCache( 2 / capacity / );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4


题目大意：

设计LRU。就是最旧的cache会先被删除。

题目 LL Map 其他数据结构
LRU 按时间顺序，头删尾入 值->LL节点 N/A
First Unique 按时间顺序，任意删尾入 值->LL节点 Set存两次以上
LFU 多个时间顺序的LL 值->LL节点 第二个Map存freq-> LL的首节点以及min_freq

解题思路：

因为是Cache，get是O(1)，自然想到用HashMap。如果不限容量，get，put都可以O(1)。限容量的情况下，
就要删除部分数据，这里要求按key的时间排序，所以考虑用一个串将keys串联起来。而key的添加和删除
也要O(1)，所以考虑用LinkedList。HashMap和LinkedList的组合很常见。这里value就指向LL中的Node，
而Node中含key和value，key又可以让Node只向HashMap，做到互相索引。分析get和set，get就只要从Map
中读Node的value即可。set比较复杂，含三种情况：

  1. 已有节点
  2. 不含节点且少于容量
  3. 不含节点且大于等于容量

对应链表操作为：

  1. 删除该节点且插入到末尾（LL顺序为由旧到新）
  2. 插入新节点到末尾
  3. 删除头节点且插入新节点到末尾

总结链表操作为两个：

  1. 删除某节点
  2. 插入新节点到末尾

实现上可以分为单链表和双链表。单链表要让Map指向节点的父节点。实现上很麻烦，因为更新节点都会涉及
两个keys上HashMap更新，即使已有节点换到末尾同样要两次更新Map。但双链表对此情况就避免了Map的更新。

DummyNode的选择：一开始我只选用了DummyHead，但capacity=1的时候要判断末节点是否为空很麻烦，由于
经常性的插入末节点，所以根据若头结点涉及插入删除就应该用dummyNode的原则，末节点也增加dummyNode
程序就简洁很多。

有些解法用单链表，用node映射到对应节点的父节点key_to_prev，这个方法反而不好理解，写的时候也容易错，不推荐

第二遍写

注意事项：

  1. 需求：记得get和set都需要更新LL的顺序
  2. set的时候，如果只是更新值而不产生新的key，不需要查capacity，需要分情况
  3. 此题跟first unique number不同，node有key和val
  4. 注意删除顺序，先删map中的entry再删Node。否则会出现NPE。新加入是顺序相反。删除节点要将prev和next赋None
  5. 函数加入self，内部函数用下划线前缀，跟第一遍不同，只用了两个内部函数，分别是_remove, _append

Python代码：

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
44
45
46
47
48
49
50
51
class LRUCache:

    def __init__(self, capacity: int):
        self.key_to_node = {}
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next, self.tail.prev = self.tail, self.head
        self.capacity = capacity

    def get(self, key: int) -> int:
        if key not in self.key_to_node:
            return -1
        node = self.key_to_node[key]
        #attn update LL
        self._remove(node)
        self._append(node)
        return node.val
        

    def put(self, key: int, value: int) -> None:
        if key not in self.key_to_node and len(self.key_to_node) == self.capacity: #attn key not in self.key_to_node
            old_node = self.head.next
            self.key_to_node.pop(old_node.key)
            self._remove(self.head.next)
        #attn update LL
        if key in self.key_to_node:
            node = self.key_to_node[key]
            node.val = value
            self._remove(node)
        else:
            node = Node(key, value)
        self._append(node)
        self.key_to_node[key] = node

    def _remove(self, node):
        predecessor, successor = node.prev, node.next
        predecessor.next, successor.prev = successor, predecessor
        node.prev, node.next = None, None
    
    def _append(self, node):
        predecessor, successor = self.tail.prev, self.tail
        predecessor.next, node.prev = node, predecessor
        node.next, successor.prev = successor, node
        
class Node:

    def __init__(self, key, val):
        self.val = val
        self.key = key
        self.next = None
        self.prev = None

注意事项：

  1. set中，若节点存在，更新value。更新节点在链表中的顺序。注意三种情况，已有节点以及不含节点的两种。
  2. 头尾dummy node，初始化要相连。
  3. 注意删除顺序，先删map中的entry再删Node。否则会出现NPE。新加入是顺序相反。删除节点要将prev和next赋None
  4. 双向LL加入新节点有两个赋值语句，不要忘记node.prev, node.next = predecessor, successor

Python代码：

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
44
45
46
47
48
49
class LRUCache:

    def __init__(self, capacity: int):
        self.key_to_node = {}
        self.capacity = capacity
        self.head = ListNode(0, 0)
        self.tail = ListNode(0, 0)
        self.head.next, self.tail.prev = self.tail, self.head

    def get(self, key: int) -> int:
        if key not in self.key_to_node:
            return -1
        self.move_to_tail(self.key_to_node[key])
        return self.key_to_node[key].val

    def put(self, key: int, value: int) -> None:
        if key in self.key_to_node:
            self.key_to_node[key].val = value
            self.move_to_tail(self.key_to_node[key])
        else:
            if len(self.key_to_node) == self.capacity:
                self.key_to_node.pop(self.head.next.key)
                self.remove_node(self.head.next)

            node = ListNode(key, value)
            self.add_to_tail(node)  # add_to_tail(node)
            self.key_to_node[key] = node

    def move_to_tail(self, node):
        self.remove_node(node)
        self.add_to_tail(node)

    def add_to_tail(self, node):
        predecessor, successor = self.tail.prev, self.tail
        predecessor.next, node.prev = node, predecessor
        node.next, successor.prev = successor, node

    def remove_node(self, node):
        predecessor, successor = node.prev, node.next
        predecessor.next, successor.prev = successor, predecessor
        node.prev, node.next = None, None


class ListNode:
    def __init__(self, key, val, next = None, prev = None):
        self.val = val
        self.key = key
        self.next = next
        self.prev = prev

Java代码：

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
Map<Integer, ListNode> map;
ListNode head; // from oldest to newest
ListNode tail;
int capacity;
public L146LRUCache(int capacity) {
	this.capacity = capacity;
	head = new ListNode(-1, -1);
	tail = new ListNode(-1, -1);
	head.next = tail;
	tail.prev = head;
	map = new HashMap<>();
}

public int get(int key) {
	if(!map.containsKey(key))
		return -1;
	pushback(key);
	return map.get(key).val;
}

public void put(int key, int value) {
	if(map.containsKey(key)) {
		pushback(key);
		map.get(key).val = value; // remember to update the value
	}
	else {
		if(map.size() == capacity) {
			map.remove(head.next.key);
			deleteNode(head.next);
		}
		// add new key
		ListNode newNode = new ListNode(key, value);
		addNodeToTail(newNode);
		map.put(key, newNode);
	}
}

void pushback(int key) {
	ListNode curNode = map.get(key);
	deleteNode(curNode);
	addNodeToTail(curNode);
}

void addNodeToTail(ListNode curNode) {
	ListNode prevTailNode = tail.prev;
	prevTailNode.next = curNode;
	curNode.prev = prevTailNode;
	curNode.next = tail;
	tail.prev = curNode;
}
// delete head node and updated node
void deleteNode(ListNode curNode) {
	ListNode nextNode = curNode.next;
	ListNode prevNode = curNode.prev;
	prevNode.next = nextNode;
	nextNode.prev = prevNode;
	curNode.next = null;
	curNode.prev = null;
}

public class ListNode {
	public int key;
	public int val;
	public ListNode next;
	public ListNode prev;

	public ListNode(int key, int val) {
		this.key = key;
		this.val = val;
	}
}

算法分析：

时间复杂度为O(1)，空间复杂度为O(n)。

Posted on Edited on Disqus:

LeetCode



You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6


Example 2:

Input: lists = []
Output: []


Example 3:

Input: lists = [[]]
Output: []


Constraints:

k == lists.length 0 <= k <= 10^4
0 <= lists[i].length <= 500 -10^4 <= lists[i][j] <= 10^4
lists[i] is sorted in ascending order. The sum of lists[i].length won’t exceed 10^4.

算法思路：

N/A

注意事项：

  1. heap不能比较ListNode大小，要实现lt函数或者将(node.val, node)对加入到heap中(此法Leetcode有编译错误但PyCharm可过)
  2. 调用heappush时，记得查节点是否None，无论循环里还是初始化
  3. 出堆后node的next赋None不需要，因为每个节点next都会重复赋值，而最后一个节点本来也没有next

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ListNode.__lt__ = lambda x, y: x.val < y.val
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        heap = []
        fake_head = ListNode(0)
        for head in lists:
            if head:
                heappush(heap, head)
        it = fake_head
        while heap:
            node = heappop(heap)
            if node.next:
                heappush(heap, node.next)
            # node.next = None
            it.next = node
            it = it.next
        return fake_head.next

算法分析：

时间复杂度为O(nlogk)，空间复杂度O(k).

算法II解题思路：

Devide and Conquer

注意事项：

  1. k.next = None因为删除节点，所以赋None，这句不加也行，但作为良好习惯建议加，且不能在i = i.next前加，否则i会变空。
  2. 查lists是否为空

Python代码：

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
def mergeKLists2(self, lists: List[List['ListNode']]) -> 'ListNode':
	if not lists:
		return None
	return self.merge_sort(lists, 0, len(lists) - 1)

def merge_sort(self, lists, start, end):
	if start >= end:
		return lists[start]
	mid = start + (end - start) // 2
	li = self.merge_sort(lists, start, mid)
	li2 = self.merge_sort(lists, mid + 1, end)
	return self.merge_two_lists(li, li2)

def merge_two_lists(self, li, li2):
	i, j, res = li, li2, ListNode(0)
	k = res
	while i and j:
		if i.val < j.val:
			k.next = i
			i = i.next
			k = k.next
			k.next = None
		else:
			k.next = j
			j = j.next
			k = k.next
			k.next = None
	if i:
		k.next = i
	if j:
		k.next = j
	return res.next

算法分析：

不管多少次递归，每次递归的一层总的节点数为n，而对k做二分，所以递归数为logk, 时间复杂度为O(nlogk)，空间复杂度O(1).

算法III解题思路：

算法二的迭代法

注意事项：

  1. 输入大小的奇偶处理
  2. 返回值是lists[0]而不是lists

Python代码：

1
2
3
4
5
6
7
8
9
10
11
def mergeKLists3(self, lists: List[List['ListNode']]) -> 'ListNode':
	if not lists:
		return None
	while len(lists) > 1:
		tmp = []
		if len(lists) % 2 == 1:
			lists.append([])
		for i in range(0, len(lists), 2):
			tmp.append(self.merge_two_lists(lists[i], lists[i + 1]))
		lists = tmp
	return lists[0]

算法分析：

同算法二.

Posted on Edited on Disqus:

LeetCode



There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 10<sup>9</sup>.

Example 1:



Input: m = 3, n = 7
Output: 28


Example 2:

Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down


Constraints:

* 1 <= m, n <= 100

题目大意：

求矩阵路径总数

解题思路：

求个数用DP，递归式：

1
dp[i][j] = dp[i-1][j] + dp[i][j-1]

解题步骤：

N/A

注意事项：

  1. 初始值dp[1] = 1而不是dp[0] = 1因为第二行的第一格不能加左边的虚拟格=1
  2. range(m)不是range(len(m))
  3. 优化空间用一维

Python代码：

1
2
3
4
5
6
7
def uniquePaths(self, m: int, n: int) -> int:
	dp = [0] * (n + 1)
	dp[1] = 1 # remember not dp[0] = 1
	for i in range(m): # remember no len(m)
		for j in range(1, len(dp)):
			dp[j] += dp[j - 1]
	return dp[-1]

算法分析：

时间复杂度为O(n2)，空间复杂度O(n2)

Free mock interview