发表于 | 分类于 ，

题目：

　　假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。

思路：

　　设n阶台阶有f(n)种不同的方法爬到楼顶，爬1个台阶后有f(n-1)种不同方法爬到楼顶，爬2个台阶后有f(n-2)种不同的方法爬到楼顶，则f(n)=f(n-1)+f(n-2),
即得出了递推式，同时也是斐波那契数列的递推式，可以使用递归实现，但可能超出限制时间。

代码：

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
// DP
public int climbStairs1(int n) {
	int[] count = new int[n];
	if (n == 1) {
		return 1;
	}
	if (n == 2) {
		return 2;
	}
	count[0] = 1;
	count[1] = 2;
	for(int i = 2;i < n;i++) {
		count[i] = count[i-1]+count[i-2];
	}
	return count[n-1];
}
	// 递归
public int climbStairs2(int n) {
	if (n == 1) {
		return 1;
	}
	if (n == 2) {
		return 2;
	}
	return climbStairs2(n-1) + climbStairs2(n-2);
}

复杂度分析：

动态规划：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(n)。

递归：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(n)。

原题链接：

https://leetcode-cn.com/problems/climbing-stairs/

发表于 | 分类于 ，

题目：

　　一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？

思路：

　　根据题意，设机器人走到m,n处总共有f(m,n)条不同的路径。则f(m,n)=f(m-1,n)+f(m,n-1)。由此递推式即可写出动态规划代码。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// DP
   public int uniquePaths(int m, int n) {
	int[][] count = new int[m][n];
	for(int i = 0;i < m;i++) {
		count[i][0] = 1;
	}
	for(int i = 0;i < n;i++) {
		count[0][i] = 1;
	}
	for(int i = 1;i < m;i++) {
		for(int j = 1;j < n;j++) {
			count[i][j] = count[i-1][j] + count[i][j-1];
		}
	}
	return count[m-1][n-1];
   }

复杂度分析：

动态规划：

　　时间复杂度：
　　　　O(n2)。
　　空间复杂度：
　　　　O(n2)。

原题链接：

https://leetcode-cn.com/problems/unique-paths/

发表于 | 分类于 ，

题目：

　　给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

思路：

　　此题没有明显的递推式，但总体问题的最优解依赖于子问题的最优解。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// DP
   public int maxSubArray(int[] nums) {
	int ans = nums[0];
	int sum = 0;
	for(int num:nums) {
		if (sum > 0) {
			sum += num;
		}else {
			sum = num;
		}
		ans = Math.max(ans, sum);
	}
	return ans;
   }

复杂度分析：

动态规划：

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

发表于 | 分类于 ，

题目：

　　给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

思路：

　　求最值，想到使用动态规划。但此题的递推式比较难想到。我们设P(i,j)=true表示子串si到sj的子串为回文，为false则不为回文，
则p(i,j)=(p(i+1,j-1)and si==sj)，这便是递归式。同时需注意，回文分为奇数回文（aba）和偶数回文(baab)，需要分别求出。

代码：

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
// DP
public static String longestPalindrome1(String s) {
	if (s == null) {
		return null;
	}
	int len = s.length();
	if (len < 2) {
		return s;
	}
	boolean[][] flag = new boolean[len][len];
	String result = s.charAt(0) + "";
	for(int i = 0;i < len;i++) {
		flag[i][i] = true;
	}
	for(int i = 0;i < len - 1;i++) {
		if (s.charAt(i) == s.charAt(i+1)) {
			flag[i][i+1] = true;
		}
		if (flag[i][i+1] == true && result.length() < 2) {
			result = s.substring(i, i+2);
		}
	}
	for(int k = 2;k < len;k++) {
		for(int i = 0;i < len - k;i++) {
			if (s.charAt(i) == s.charAt(i+k) && flag[i+1][i+k-1]) {
				flag[i][i+k] = true;
			}
			if (flag[i][i+k] && result.length() < k+1) {
				result = s.substring(i, i+k+1);
			}
		}
	}
	return result;
}

复杂度分析：

动态规划：

　　时间复杂度：
　　　　O(n2)。
　　空间复杂度：
　　　　O(n2)。

发表于 | 分类于 ，

题目：

　　给你一根长度为n绳子，请把绳子剪成m段（m、n都是整数，n>1并且m≥1）。
每段的绳子的长度记为k[0]、k[1]、……、k[m]。k[0]k[1]…*k[m]可能的最大乘积是多少？
例如当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到最大的乘积18。

思路：

　　动态规划的关键是得出递推式，此题需要求绳子的最大乘积，因此设长度的为n的绳子剪成m段后的最大乘积为f(n)，而绳子上剪一刀有n-1种可能，因此
f(n)=max(f(i)*f(n-i)),得出递归式后，即可从下往上写出代码。写代码过程中需要先求出前几项的值存入数组中。
　　而此题贪心算法需要数学正面每次剪去长度为3的绳子，若剩下长度为4，每次剪长度为2的绳子时，所得乘积最大。

代码：

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
// 动态规划
public static int maxProductAfterCutting2(int len) {
	if (len < 2) {
		return 0;
	}
	if (len == 2) {
		return 2;
	}
	if (len == 3) {
		return 2;
	}
	int[] maxProduct = new int[len+1];
	maxProduct[0] = 0;
	maxProduct[1] = 1;
	maxProduct[2] = 2;
	maxProduct[3] = 3;
	for(int i = 4;i <= len;i++) {
		int max = 0;
		for(int j = 1;j <= i/2;j++) {
			if (maxProduct[j]*maxProduct[i-j] > max) {
				max = maxProduct[j]*maxProduct[i-j];
			}
		}
		maxProduct[i] = max;
	}
	return maxProduct[len];
}
	//贪心算法
public static int maxProductAfterCutting1(int len) {
	if (len < 2) {
		return 0;
	}
	if (len == 2) {
		return 1;
	}
	if(len == 3) {
		return 2;
	}
	int timeof3 = len/3;
	if (len - timeof3*3 == 1) {
		timeof3--;
	}
	int timeof2 = (len-timeof3*3)/2;
	return (int) (Math.pow(3, timeof3)*Math.pow(2, timeof2));
}

复杂度分析：

动态规划：

　　时间复杂度：
　　　　O(n**2)。
　　空间复杂度：
　　　　O(n)。

贪心算法：

　　时间复杂度：
　　　　O(1)。
　　空间复杂度：
　　　　O(1)。

发表于 | 分类于 ，

题目：

　　输入一个链表，反转链表后，输出新链表的表头。

思路：

　　若只定义一个指针进行反转，则会造成链表断开。因此考虑使用多指针暂存后续节点，以防链表断开。同时此题也可以使用递归，利用递归从尾到头反转链表，
代码简洁，但是思路有点绕，需注意。

代码：

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 ListNode ReverseList1(ListNode head) {
   	if (head == null || head.next == null) {
		return head;
	}
   	ListNode node = ReverseList1(head.next);
   	head.next.next = head;
   	head.next = null;
   	return node;
}
   // 双指针
   public ListNode ReverseList2(ListNode head) {
   	if (head == null || head.next == null) {
		return head;
	}
   	ListNode preNode = null;
   	ListNode curNode = head;
   	while(curNode != null) {
   		ListNode temp = curNode.next;
   		curNode.next = preNode;
   		preNode = curNode;
   		curNode = temp;
   	}
   	return preNode;
   }

复杂度分析：

递归

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(n)。

双指针：

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

发表于 | 分类于 ，

题目：

　　给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

思路：

　　此题包含两个问题：1.判断链表中是否有环；2.若有环，找出环的入口节点。对于此问题，无论是判断是否有环还是找入口节点，都可以使用哈希表（Set）
解出，但需要O(n)的空间复杂度。现在来优化空间复杂度。判断是否有环可以使用快慢双指针（慢指针一次走一步，快指针一次走两步），若有环则两指针必定
会相遇。对于寻找入口节点，需要进行推导。假设环外节点数为F，环内节点数为C，当慢指针走到入口节点处时，慢指针走了F步，同样快指针在环内一定走了F
步，若慢指针继续走C-F步，则两指针必定相遇（快指针走2（C-F）步），即两指针必定相遇在C-F处，此时再定义一个指针指向头节点，当头节点指针与相遇节点
指针相遇时，相遇的节点即为入口节点。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 public ListNode EntryNodeOfLoop(ListNode pHead)
 {
     ListNode fastNode = pHead;
     ListNode slowNode = pHead;
     while(fastNode != null && fastNode.next != null) {
     	fastNode = fastNode.next.next;
     	slowNode = slowNode.next;
     	if (fastNode == slowNode) {
	while(pHead != fastNode) {
		pHead = pHead.next;
		fastNode = fastNode.next;
	}
	return fastNode;
}
     }
     return null;
 }

复杂度分析：

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

发表于 | 分类于 ，

题目：

　　输入一个链表，输出该链表中倒数第k个结点

思路：

　　此题很明显可以想到倒数第k个节点即是正数第len-k+1个节点，但为了求链表的长度，我们解此题需要遍历链表两次。为了只遍历一次，我们可以使用双指针。
让前面的指针先走k-1步，这样当前面的指针到达尾节点时，后面的节点即为倒数第k个节点。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
  public ListNode FindKthToTail(ListNode head,int k) {
  	if (head == null || k <= 0) {
	return null;
}
  	ListNode preHead = head;
  	ListNode curHead = head;
  	for(int i = 0;i < k - 1;i++) {
  		curHead = curHead.next;
  	}
  	if (curHead == null) {
	return null;
}
  	while(curHead.next != null) {
  		preHead = preHead.next;
  		curHead = curHead.next;
  	}
  	return preHead;
  }

复杂度分析：

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

相关题目：

　　求链表的中间节点。

总结：

　　当想优化链表遍历次数时，可以考虑使用双指针。

发表于 | 分类于 ，

题目：

　　在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。
例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

思路：

　　使用双指针，注意考虑删除头节点的特殊情况。

代码：

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
public ListNode deleteDuplication1(ListNode pHead) {
	if (pHead == null || pHead.next == null) {
		return pHead;
	}
	ListNode preHead = null;
	ListNode curHead = pHead;
	while(curHead != null) {
		if (curHead.next != null && curHead.val == curHead.next.val) {
			int value = curHead.val;
			ListNode tempNode = curHead;
			while(tempNode != null && tempNode.val == value) {
				tempNode = tempNode.next;
			}
			if (curHead == pHead) {
				pHead = tempNode;
			}else {
				preHead.next = tempNode;
			}
			curHead = tempNode;
		}else {
			preHead = curHead;
			curHead = curHead.next;
		}
	}
	return pHead;
}

复杂度分析：

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

发表于 | 分类于 ，

题目：

　　给定单向链表的头指针和一个结点指针，定义一个函数在O(1)时间删除该结点。

思路：

　　正常删除链表节点的思路为找到待删除节点的前一个节点，使该节点的next指针指向待删除节点的下一个节点即可，但这种思路的时间复杂度为O(n)。与题目要求不符。根据
《剑指offer》的思路，可以将待删除节点的值修改为其下一个节点的值，然后将待删除节点的next指针指向下下个节点。但需要特别注意的是特殊情况：待删除的节点是尾节点；原链表只有一个节点。

代码：

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 ListNode deleteNode(ListNode head,ListNode pToBeDeleted) {
	if (head == null || pToBeDeleted == null) {
		return head;
	}
	// 删除的不是尾节点
	if (pToBeDeleted.next != null) {
		ListNode pNext = pToBeDeleted.next;
		pToBeDeleted.val = pNext.val;
		pToBeDeleted.next = pNext.next;
		pNext = null;
	// 删除的是尾节点并且原链表只有一个节点
	}else if (head == pToBeDeleted) {
		pToBeDeleted = null;
		head = null;
	// 删除的是尾节点并且原链表有多个节点
	}else {
		ListNode node = head;
		while(node.next != pToBeDeleted) {
			node = node.next;
		}
		node.next = null;
		pToBeDeleted = null;
	}
	return head;
}

复杂度分析：

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