KK's blog

LeetCode 019 Remove Nth Node From End of List

Given a linked list, remove the n^th node from the end of list and return its head.

For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.
Try to do this in one pass.

题目大意：

删除一个单链表末尾开始算起的第n个结点，然后返回该单链表。 例如：
输入: 1->2->3->4->5 其中n=2；
输出： 1->2->3->5;
n一定合法，只能遍历一次链表。

解题思路：

这是经典题。两指针法。距离为N的两指针，当前指针到末尾，后指针即是要删除的节点。头部插入fake节点，类似于mergeIntervals L56末尾插入一个空节点避免特别化处理。

1. 快指针从fake节点开始先走n步
2. 慢指针开始一起和快指针同步走，直到快指针到最后一个（next为空）
3. 此时慢指针是要删除指针的上一个，删除操作是可以的。

注意事项：

因为头指针也可能被删除，如只有一个节点的链表，n=1。删除操作在待删除节点的上一个节点上操作，所以引入假头节点prehead。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

public ListNode removeNthFromEnd(ListNode head, int n) {
	ListNode prehead = new ListNode(-1);
	prehead.next = head;
	
	ListNode slow = prehead, fast = prehead;
	for(int i=0;i<n;i++)
		fast = fast.next;
	
	while(fast.next != null){
		fast = fast.next;
		slow = slow.next;
	}
	deleteNode(slow);
	return prehead.next;
}

public void deleteNode(ListNode p){
	p.next = p.next.next;
}

算法分析：

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

LeetCode 001 Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

题目大意：

给定一个整数数组，从中找出两个数的下标，使得它们的和等于一个特定的数字。可以假设题目有唯一解。

解题思路：

1. 最简单的思路是暴力法，两重循环试遍所有组合。
2. 先排序，再用两指针法，若指针指向的数和小于target则左指针右移，反之亦然。注意，为了保持原数组的下标，要预先保留下标及值对到Node中。
3. 遍历数组，同时查看target-该数是否在HashMap中，否则加入到HashMap中。

Python代码：

1
2
3
4
5

def twoSum(self, nums: List[int], target: int) -> List[int]:
	for i in range(len(nums)):
		for j in range(i + 1, len(nums)):
			if nums[i] + nums[j] == target:
				return [i, j]

1
2
3
4
5
6
7
8
9
10
11

def twoSum(self, nums: List[int], target: int) -> List[int]:
	temp = [(n, i) for i, n in enumerate(nums)]
	temp.sort()
	i, j = 0, len(temp) - 1
	while i < j:
		if temp[i][0] + temp[j][0] < target:
			i += 1
		elif temp[i][0] + temp[j][0] > target:
			j -= 1
		else:
			return [temp[i][1], temp[j][1]]

1
2
3
4
5
6

def twoSum(self, nums: List[int], target: int) -> List[int]:
	nums_dict = {}
	for i, n in enumerate(nums):
		if target - n in nums_dict:
             return [nums_dict[target - n], i]
		nums_dict[n] = i

第二种方法，Python的tuple相当于Java的自定义Node，但节省了很多代码。每种方法都大概节省了2/3的代码。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13

public int[] twoSum0(int[] nums, int target) {
	int[] re = new int[2];
	for(int i=0;i<nums.length;i++)
		for(int j=i+1;j<nums.length;j++){
			if(nums[i]+nums[j]==target){
				re[0] = i;
				re[1] = j;
				return re;
			}
				
		}
	return re;
}

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

public int[] twoSum2(int[] nums, int target) {
	Node[] ary = new Node[nums.length];
	for(int i=0;i<nums.length;i++){
		ary[i] = new Node(i, nums[i]);
	}
	
	Arrays.sort(ary, new Comparator<Node>() {
		@Override
		public int compare(Node o1, Node o2) {
			return o1.value - o2.value;
		}
	});
	int[] re = new int[2];
	int start=0, end=nums.length-1;
	while(start<end){
		if(ary[start].value+ary[end].value==target){
			re[0] = ary[start].index;
			re[1] = ary[end].index;
			return re;
		}
		else if(ary[start].value+ary[end].value<target)
			start++;
		else
			end--;
	}
	return re;
}

class Node {
	Node(int i, int v){
		this.index = i;
		this.value = v;
	}
	int index;
	int value;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public int[] twoSum(int[] nums, int target) {
	HashMap<Integer,Integer> h  = new HashMap<Integer,Integer>();
	
	int[] re = new int[2];
	for(int i=0;i<nums.length;i++){
		Integer index = h.get(target-nums[i]);
		if(index!=null){
			re[0]=index;
			re[1]=i;
			return re;
		}
		h.put(nums[i],i);
	}
	return re;
}

算法分析：

1. 时间复杂度为O(n2)，空间复杂度O(1)。
2. 时间复杂度为O(nlogn)，空间复杂度O(n)。
3. 时间复杂度为O(n)，空间复杂度O(n)。

LeetCode 054 Spiral Matrix

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,
Given the following matrix:

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

You should return [1,2,3,6,9,8,7,4,5].

题目大意：

给定一个mxn的矩阵（m行 n列），以螺旋状返回矩阵中的所有元素。

解题思路：

打印方法主要是以下两种：第一种四边对称打印，实现起来边际情况很多，不推荐。因为要不断向内遍历，所以对称打印不合适。第二种方法是每条边比上一条少一个，
用四个指针，top, bottom, left, right来记录四个边界，每打印完一条边该边界向内扩展。注意有些回路不是完整比如[1,2]或上面例子中5就不是完整回路，此情况，
注意判断top和bottom以及left和right关系即可。四指针法可以进一步升级到两指针法甚至一个指针法，其实都是大同小异。

注意事项：

1. 注意不是所有矩阵都有完整回路。所以后两个for循环要加if语句
2. 右边和左边，遍历矩阵用matrix[i][right]，而不是matrix[right][i]
3. Python中从后往前遍历要注意始点-1，range(right, left - 1, -1):

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
	if not matrix or not matrix[0]:
		return []
	res = []
	top, bottom, left, right = 0, len(matrix) - 1, 0, len(matrix[0]) - 1
	while top <= bottom and left <= right:
		for i in range(left, right + 1):
			res.append(matrix[top][i])
		top += 1
		for i in range(top, bottom + 1):
			res.append(matrix[i][right])  # remember [i[[right] not [right][i]
		right -= 1
		if top <= bottom:
			for i in range(right, left - 1, -1):
				res.append(matrix[bottom][i])
			bottom -= 1
		if left <= right:
			for i in range(bottom, top - 1, -1):
				res.append(matrix[i][left])
			left += 1
	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

public void spiral2(int[][] a){
	int rowTop = 0, rowBottom = a.length-1, colLeft = 0, colRight = a[0].length-1;
	
	while(rowTop<=rowBottom && colLeft<=colRight){
		//topRow
		for(int i=colLeft;i<=colRight;i++)
			System.out.print(a[rowTop][i]+" ");
		rowTop++;
		//rightCol
		for(int i=rowTop;i<=rowBottom;i++)
			System.out.print(a[i][colRight]+" ");
		colRight--;
		if(rowTop<=rowBottom){
			for(int i=colRight;i>=colLeft;i--)
				System.out.print(a[rowBottom][i]+" ");
			rowBottom--;
		}
		if(colLeft<=colRight){
			for(int i=rowBottom;i>=rowTop;i--)
				System.out.print(a[i][colLeft]+" ");
			colLeft++;
		}
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public void spiral3(int[][] a){
	int rowTop = 0, colLeft = 0;
	
	while(rowTop<=a.length-rowTop-1 && colLeft<=a[0].length-colLeft-1){
		//topRow
		for(int i=colLeft;i<=a[0].length-colLeft-1;i++)
			System.out.print(a[rowTop][i]+" ");
		rowTop++;
		//rightCol
		for(int i=rowTop;i<=a.length-rowTop;i++)
			System.out.print(a[i][a[0].length-colLeft-1]+" ");
		//colRight--;
		if(rowTop<=a.length-rowTop){
			for(int i=a[0].length-colLeft-2;i>=colLeft;i--)
				System.out.print(a[a.length-rowTop][i]+" ");
		}
		if(colLeft<=a[0].length-colLeft-2){
			for(int i=a.length-rowTop-1;i>=rowTop;i--)
				System.out.print(a[i][colLeft]+" ");
			colLeft++;
		}
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public void spiral4(int[][] a){
	int num = Math.min(a.length, a[0].length);
	for(int st=0;st<(num+1)/2;st++){
		//complete edge(top)
		for(int i=st;i<a[0].length-st;i++)
			System.out.print(a[st][i]+" ");
		//complete edge-top (right)
		for(int i=st+1;i<a.length-st;i++)
			System.out.print(a[i][a[0].length-1-st]+" ");
		if(a[0].length-2-st>st)
			for(int i=a[0].length-2-st;i>=st;i--)
				System.out.print(a[a.length-st-1][i]+" ");
		if(a.length-2-st>st+1)
			for(int i=a.length-2-st;i>=st+1;i--)
				System.out.print(a[i][st]+" ");
	}
}

算法分析：

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

LeetCode 004 Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

题目大意：

求两个有序数组中的中位数。

数值二分法解题思路(推荐)：

由于是求中位数或第k小的数，根据题型分类用Heap或binary select。Heap的话，由于是有序，所以优势不大，复杂度为O[(m+n)log2].
考虑用binary select，思路比较直接，就是将两个数组看成一个，统计个数的时候由于有序，分别在两数组用二分法统计。

注意事项：

1. 中位数有1-2两个。用单一元素数组的例子来确定+1还是-1，Line 6
2. 统计最大最小值，注意空数组
3. 统计count用bisect不需要+1

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

def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
	m, n = len(nums1), len(nums2)
	if (m + n) % 2 == 1:
		return self.find_kth_smallest(nums1, nums2, (m + n) // 2)
	else:
		return (self.find_kth_smallest(nums1, nums2, (m + n) // 2) + self.find_kth_smallest(nums1, nums2, (m + n) // 2 - 1)) / 2

def find_kth_smallest(self, nums1, nums2, k):
	min_val, min_val2 = nums1[0] if nums1 else float('inf'), nums2[0] if nums2 else float('inf')
	max_val, max_val2 = nums1[-1] if nums1 else float('-inf'), nums2[-1] if nums2 else float('-inf')
	start, end, epsilon = min(min_val, min_val2), max(max_val, max_val2), 0.5
	while end - start > epsilon:
		mid = start + (end - start) / 2
		count = self.count(nums1, nums2, mid)
		if k < count:
			end = mid
		elif k > count:
			start = mid
		else:
			start = mid
	return math.floor(end)

def count(self, nums1, nums2, mid):
	return bisect.bisect(nums1, mid) + bisect.bisect(nums2, mid)  # remember

算法分析：

时间复杂度为O(nlog(|hi-lo|/delta))，由于数据大小范围是10^6, 而前面的n是基于全数组扫描，这里用二分法，n变成log(m)+log(n)
时间复杂度为O(logm + logn)，空间复杂度O(1)

Merge sort算法II解题思路：

既然是有序，考虑用merge sort中的merge步骤
merge sort里面的数组是无序，但这里是有序，所以merge这个步骤可以改进，不是一个个数比较，可以分别取第k/2进行比较，原理是一样的，但效率更高。
若num1[k/2] < num2[k/2]相当于nums1[i] <= nums2[j]，此时表示num1[0..k/2]都满足小于等于第k个数的结果数组中。i移位，不是移一位，而是移k/4.
这样得到方法三。方法三解释比较难懂，用mergesort模拟较易懂。
一般是对数组二分，此法采用对k二分

注意事项：

1. 若i或j用完，返回另一个数组的元素，下标是j+k或i+k，k此时是剩余的k

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

def findMedianSortedArrays2(self, nums1: List[int], nums2: List[int]) -> float:
	m, n = len(nums1), len(nums2)
	if (m + n) % 2 == 1:
		return self.find_kth_smallest2(nums1, nums2, (m + n) // 2)
	else:
		return (self.find_kth_smallest2(nums1, nums2, (m + n) // 2) + self.find_kth_smallest2(nums1, nums2, (m + n) // 2 - 1)) / 2

def find_kth_smallest2(self, nums1, nums2, k):
	i, j = 0, 0
	while i < len(nums1) and j < len(nums2) and k > 0:
		if nums1[i] <= nums2[j]:
			i += 1
		else:
			j += 1
		k -= 1
	if i == len(nums1):  # remember dont use (not nums1)
		return nums2[j + k]  # remember use j+k rather than k
	if j == len(nums2):
		return nums1[i + k]
	return min(nums1[i], nums2[j])

算法分析：

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

二分法算法III解题思路：

将上面的方法换成递归，if判断语句换成递归终止条件，+1变成+k/2，注意判断越界
说起来轻松，但非常容易错，不推荐

注意事项：

1. 中位数有1-2两个。
2. off by 1的问题。递归子函数要用(k+1)//2而不是k//2因为若k=1时候，k//2就不能移动一位。
3. 若nums中i + k // 2越界，不碰nums，右移j，因为nums不能右移那么多, 所以num1赋最大值不是最小值
4. 终止条件i >= len(nums1)取大于号，跟上面不同，因为可能越界

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

def findMedianSortedArrays3(self, nums1: List[int], nums2: List[int]) -> float:
	m, n = len(nums1), len(nums2)
	if (m + n) % 2 == 1:
		return self.find_kth_smallest3(nums1, nums2, 0, 0, (m + n) // 2)
	else:
		aa = self.find_kth_smallest3(nums1, nums2, 0, 0, (m + n) // 2)
		bb = self.find_kth_smallest3(nums1, nums2, 0, 0, (m + n) // 2 - 1)
		return (self.find_kth_smallest3(nums1, nums2, 0, 0, (m + n) // 2)
				+ self.find_kth_smallest3(nums1, nums2, 0, 0, (m + n) // 2 - 1)) / 2

    def find_kth_smallest3(self, nums1, nums2, i, j, k):
        if i >= len(nums1):  # remember to use >= rather than ==
            return nums2[j + k]
        if j == len(nums2):
            return nums1[i + k]
        if k == 0:
            return min(nums1[i], nums2[j])
        num1 = nums1[i + k // 2] if i + k // 2 < len(nums1) else float('inf')  # remember sys.maxsize not minus
        num2 = nums2[j + k // 2] if j + k // 2 < len(nums2) else float('inf')
        if num1 <= num2:  # remember the steps are same by moving i and k, k + 1
            return self.find_kth_smallest3(nums1, nums2, i + (k + 1) // 2, j, k - (k + 1) // 2)
        else:
            return self.find_kth_smallest3(nums1, nums2, i, j + (k + 1) // 2, k - (k + 1) // 2)

Java实现

题目要求log(m+n)复杂度，也就提示要对数组总长做二分法。因为要同时处理两个数组所以考虑用递归版二分法。因奇偶中位数有1-2个，
所以加强命题为求两有序数组的第k个数(k>=1)。
对k的值进行二分k/2，先尝试num1数组的第k/2个数和num2数组的第k/2个数。若它们相等，表示它们即为第k个数。也就是比如求第4个数，
分别在两数组中取前两个，平均分配名额。此题类似于求前k大的数(算法文档4.1.13)用统计个数的方法来判断走左还是右。若它们不等，不妨假设
aKey<bKey，这样表示第k个数一定不会是aKey，因为即使比bKey小的数均小于aKey的话（有k/2-1个），总共有k/2-1+k/2-1=k-2个数小于
aKey，也就是aKey为第k-1个数，不可能为第k个数，它只可能出现是bKey或者在num1中比aKey大的数。既然aKey不是解，比aKey小的数
更不可能是解。所以，可以抛掉num1[0, k/2]这部分，转而求num1[k/2+1,nums.length-1]以及nums2的第k-k/2个数，抛掉部分会影响结果
吗？答案是否定的。比如
1 2 3 4
0 6 7 8
k=4，比较2和6,2<6抛掉1 2，转求[3,4],[0,6,7,8]的第2个数，答案仍为3，不影响结果，因为前k/2个数即使有些在nums2也不会影响
最后结果，求的是第k个。
1 2 3 4
0 6 7 8
第k=4数可能出现在num1[k/2+1,nums.length-1]=3或num2=6（下面例子），所以保留部分是正确的。
主要思路是每次递归抛掉k/2个数，数组规模减少k/2，k变成k-k/2, API为left, left2表示新数组的左边界(因为永远抛左边部分)以及k。
递归终止条件为

1. left越界，这时此数组的数刚好用完或此数组为空(不会越界太多，否则aKey无穷大会递归到num2)。归结为求另一数组[left..]的第k个数.
2. k为1时候，是基本情况，表示求两数组的第1个数，只要返回左端的最小值即可。

注意事项：

1. 中位数有1-2两个。
2. off by 1的问题。若API中的k定义为第k个数k>=1，若总长len=5，中位数为第len/2+1=3个数。所以在递归函数中，数组下标用到k时
   都要-1。抛掉[left, left+k/2-1],递归[left+k/2..]。
3. 若nums中left+k/2-1越界，不碰nums，右移left2，因为nums不能右移那么多。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

public double findMedianSortedArrays(int[] num1, int[] num2){
	int len = num1.length+num2.length;
	if(len%2==1)
		return findKth(num1,num2,0,0,len/2+1);
	else return (findKth(num1,num2,0,0,len/2)+findKth(num1,num2,0,0,len/2+1))/2.0;
}

public int findKth(int[] num1, int[] num2, int left, int left2, int k){
	if(left>=num1.length)
		return num2[left2+k-1];
	if(left2>=num2.length)
		return num1[left+k-1];
	if(k==1)
		return Math.min(num1[left], num2[left2]);;
	
	int aKey = left+k/2-1<num1.length?num1[left+k/2-1]:Integer.MAX_VALUE;
	int bKey = left2+k/2-1<num2.length?num2[left2+k/2-1]:Integer.MAX_VALUE;
	if(aKey<bKey)
		return findKth(num1,num2,left+k/2,left2,k-k/2);
	else
		return findKth(num1,num2,left,left2+k/2, k-k/2);
}

算法分析：

假设两数组总长度为N，k为中位数即N/2，每次抛掉k/2也就是子问题规模为N-k/2=N-N/4=3N/4. f(N)=f(3N/4)+1.
利用master理论b=4/3, a=1, f(n)=1代入时间复杂度为O(log(m+n))，空间复杂度O(1)。

LeetCode 006 ZigZag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

题目大意：

给定字符串按如上的“Z”字锯齿形进行按行重排。

解题思路：

这是一个周期性的字符串。周期是竖+折（不含首节点）。

首节点和竖的最后一点在每周期只会出现一次，其他点会出现两次。
T=2×numRows-2(因为不含竖节点最后一点+折线上的最后一点属于另一个周期)。nT是有几个周期，即使不完成的周期也算一个。
按行遍历（实质是周期上的每个点），再按周期遍历，非顶点有两个需加入到结果中：j×T+i,(j+1)×T-i。由于周期可能不完成，只要写一个API检查边界且加入字符即可。

注意事项：

一个字符的字符串。此时T=0.直接返回原字符串。

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

public String convert2(String s, int numRows) {
	StringBuffer sb = new StringBuffer();
	int T = numRows*2-2;
	if(T==0)
		return s;
	int nT = (int)Math.ceil((s.length()+0.0)/T);
	for(int i=0;i<numRows;i++){
		for(int j=0;j<nT;j++){
			if(i==0 || i==numRows-1)
				sb.append(addChar(s, j*T+i));
			else{
				sb.append(addChar(s, j*T+i));
				sb.append(addChar(s, (j+1)*T-i));
			}
		}
	}
	return sb.toString();
}

public String addChar(String s, int index){
	String a = "";
	if(index<s.length())
		return s.substring(index, index+1);
	return a;
}

算法分析：

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