Push the value item onto the heap, maintaining the heap invariant.
heapq.heappop(*heap*)
Pop and return the smallest item from the heap, maintaining the heap invariant. If the heap is empty, IndexError is raised. To access the smallest item without popping it, use heap[0].
heapq.heapify(*x*)
Transform list x into a heap, in-place, in linear time.
0724 - Leetcode797 - All Paths From Source to Target
Given a directed, acyclic graph of N nodes. Find all possible paths from node 0 to node N-1, and return them in any order.
The graph is given as follows: the nodes are 0, 1, …, graph.length - 1. graph[i] is a list of all nodes j for which the edge (i, j) exists.
1 2 3 4 5 6 7 8 9
Example: Input: [[1,2], [3], [3], []] Output: [[0,1,3],[0,2,3]] Explanation: The graph looks like this: 0--->1 | | v v 2--->3 There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.
classSolution(object): defallPathsSourceTarget(self, graph): """ :type graph: List[List[int]] :rtype: List[List[int]] """ edge = defaultdict(list) for i inrange(len(graph)): link = graph[i] for k in link: edge[k] += [i] ans = [] self.dfs(edge, len(graph) - 1, [], ans) return ans defdfs(self, edge, lastnode, path, ans): if lastnode == 0: path = path + [0] ans.append( path[::-1] ) return for node in edge[lastnode]: self.dfs(edge, node, path + [lastnode], ans)
0722 - Leetcode103 - Binary Tree Zigzag Level Order Traversal
Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).
For example: Given binary tree [3,9,20,null,null,15,7],
1 2 3 4 5
3 / \ 9 20 / \ 15 7
return its zigzag level order traversal as:
1 2 3 4 5
[ [3], [20,9], [15,7] ]
解题思路
BFS + 正反向输出 + flag决定
BFS输出，然后设置flag，每次都*-1 可以控制正反向输出。
0720 - Leetcode - Remove Linked List Elements
Remove all elements from a linked list of integers that have value val\.
Example:
1 2
Input: 1->2->6->3->4->5->6, val = 6 Output: 1->2->3->4->5
defsubsets(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ ans = [] sub = [] ans.append(sub) self.newsub(sub, nums, 0, ans) return ans defnewsub(self, sub, nums, i, ans): while i < len(nums): ans.append(sub + [nums[i]]) self.newsub(sub + [nums[i]], nums, i+1, ans) i += 1 return
0708 - 3Sum
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
The solution set must not contain duplicate triplets.
Example:
1 2 3 4 5 6 7
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]
解题思路：
先排序，再固定指针 i ，然后从这个指针向右的序列确定两个指针 left, right, 寻找nums[i] = -(nums[left]+nums[right])。
defthreeSum(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ nums.sort() ans = [] for i inrange(len(nums)): left = i + 1 right = len(nums) - 1 if i > 0and nums[i] == nums[i-1]: continue while left < right: if left - 1 > i and nums[left] == nums[left-1]: left += 1 continue if right+1 < len(nums) and nums[right] == nums[right+1]: right -= 1 continue if nums[left] + nums[right] == -nums[i]: ans.append([nums[i], nums[left], nums[right]]) left += 1 elif nums[left] + nums[right] > -nums[i]: right -= 1 else: left += 1 return ans
0707 - Leetcode463 - Island Perimeter
You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water.
Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).
The island doesn’t have “lakes” (water inside that isn’t connected to the water around the island). One cell is a square with side length 1. The grid is rectangular, width and height don’t exceed 100. Determine the perimeter of the island.
defislandPerimeter(self, grid): """ :type grid: List[List[int]] :rtype: int """ row = len(grid) col = len(grid[0]) count1 = 0 edge = 0 for i inrange(row): for j inrange(col): if grid[i][j] == 1: count1 += 1 edge = edge + (self.countLand(grid, i+1, j) +self.countLand(grid, i-1, j)+self.countLand(grid, i, j+1)+self.countLand(grid, i, j-1)) return4*count1 - edge defcountLand(self, grid, i, j): land = 0 if i >= 0and i < len(grid) and j >= 0and j < len(grid[0]): land += grid[i][j] return land
补充 - Leetcode695 - Max Area of Island
Given a non-empty 2D array grid of 0’s and 1’s, an island is a group of 1‘s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.
Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)
defplusOne(self, digits): """ :type digits: List[int] :rtype: List[int] """ num = 0 i = 0 while i < len(digits): num = 10*num + digits[i] i += 1 num = num+1 plus = [] while num > 0: plus.append(num % 10) num //= 10 return plus[::-1]
defhammingDistance(self, x, y): """ :type x: int :type y: int :rtype: int """ count = 0 whileTrue: if x == 0and y == 0: break count += (x%2) ^ (y%2) x = x // 2 y = y // 2 return count
后面查了一下确实有直接算二进制的：
bin(x) 可以返回x的二进制表示形式，但是返回的值是一个string
int(x, 16) 可以将16进制下的字符串类型x转化为一个十进制的int形式的数字
补充 - Leetcode477 - Total Hamming Distance
The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
Now your job is to find the total Hamming distance between all pairs of the given numbers.
Example:
1 2 3 4 5 6 7
Input: 4, 14, 2
Output: 6
Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just showing the four bits relevant in this case). So the answer will be: HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.
deftotalHammingDistance(self, nums): """ :type nums: List[int] :rtype: int """ count = [0] * 32 for num in nums: i = 0 while num != 0: count[i] += num % 2 num /= 2 i += 1 N = len(nums) total_ham = 0 for i inrange(len(count)): if count[i] > 0: total_ham += N * (N - 1)/2 - count[i]*(count[i]-1)/2 - (N - count[i])*(N - count[i] - 1)/2 return total_ham
0704 - Leetcode264 - Ugly Number II
Write a program to find the n-th ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.
Example:
1 2 3
Input: n = 10 Output: 12 Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.
defisUgly(self, num): """ :type num: int :rtype: bool """
if num == 1: returnTrue if num == 0: returnFalse while num != 1: if num % 2 == 0: num = num //2 elif num%3 == 0: num = num//3 elif num%5 == 0: num = num//5 else: returnFalse returnTrue
0703 - Leetcode957 - Prison Cells After N days
There are 8 prison cells in a row, and each cell is either occupied or vacant.
Each day, whether the cell is occupied or vacant changes according to the following rules:
If a cell has two adjacent neighbors that are both occupied or both vacant, then the cell becomes occupied.
Otherwise, it becomes vacant.
(Note that because the prison is a row, the first and the last cells in the row can’t have two adjacent neighbors.)
We describe the current state of the prison in the following way: cells[i] == 1 if the i-th cell is occupied, else cells[i] == 0.
Given the initial state of the prison, return the state of the prison after N days (and N such changes described above.)
defarrangeCoins(self, n): """ :type n: int :rtype: int """ if n == 0: return0 if n <= 2: return1 count = 0 while n >= 0: count += 1 n -= count return count - 1
defarrangeCoins(self, n): """ :type n: int :rtype: int """ left = 0 right = n while left < right: # print(left, right) mid = (left + right + 1)/2 if mid*(mid+1)/2 < n: left = mid if mid*(mid+1)/2 > n: right = mid - 1 if mid*(mid+1)/2 == n: return mid return left
defextract_sentences(query:str='bill', max_left:int=300, max_right:int=300): """ :param query: 目标搜索词 target word :param max_left: 左侧提取最多字数(以char为单位) maximum str length before target word :param max_right: 右侧提取最多字数(以char为单位)minmum str length after target word :return: None. (Generate the file containing sentences) """
