今日鸡汤
对外界的焦虑，来自自己对自己的看法，对自己的看法会篡改你在外界收到的真实信息。
https://github.com/gaoshengnan/LeetCode
数组PART
双指针
26. 删除排序数组中的重复项
一般数组问题，都用双指针或多指针做，尤其是要移动的或者替换的情况，通过维护两个指针来确定一个窗口进行操作。
public int removeDuplicates(int[] nums) {
int start = 0;
int end = 0;
int current = 0;
while(end <= nums.length -1){
while(end < nums.length && nums[end] == nums[start]){
end++;
}
if(end >= nums.length) break;
nums[++current] = nums[end];
start = end;
end++;
}
return current + 1;
}
88. 合并两个有序数组
双指针，由于num1已经预留了位置，因此从后往前选数插入。
public void merge(int[] nums1, int m, int[] nums2, int n) {
int last = m + n - 1;
int n1Index = m - 1;
int n2Index = n - 1;
while(n1Index >= 0 && n2Index >= 0){
if(nums1[n1Index] > nums2[n2Index]){
nums1[last--] = nums1[n1Index--];
} else{
nums1[last--] = nums2[n2Index--];
}
}
while(n2Index >= 0){
nums1[last--] = nums2[n2Index--];
}
}
283. 移动零
数组移动，且在原数组上操作，记得数组值可以覆盖，只需要用指针把当前操作的下标值记录好即可。
第一种方法，不断把所有非零的数往左边堆，每次移动一个就将非零指针往后移。之后再从非零指针的位置开始把右边的脏数据清零。
public void moveZeroes(int[] nums) {
int nonZeroIndex = 0;
for(int i = 0;i < nums.length;i++){
if(nums[i] != 0){
nums[nonZeroIndex] = nums[i];
nonZeroIndex++;
}
}
for(int j = nonZeroIndex; j < nums.length;j++){
nums[j] = 0;
}
}
第二种方法，利用快排哨兵的思想，用0作为哨兵，把不等于0的数放在左边，把等于零的数放在右边。遍历一次，如果当前数非零，就交换，否则直接后移。
public void swap(int[] nums, int i, int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
public void moveZeroes(int[] nums) {
int low = 0;
for(int i = 0;i < nums.length;i++){
if(nums[i] != 0){
swap(nums, i, low);
low++;
}
}
}
15. 三数之和
之前做 Two Sum，用了神奇的MAP方法，3sum用到的是三指针。
首先先给数组从小到大排序，从头用i遍历一遍数组，每轮遍历里：
1、用两个指针left和right分别从i+1和end开始记录位置。
2、判断 nums[i] + nums[left] + nums[right]的值：
1）刚好等于0，发现一组解，加入list中，left右移，right左移；
2）<0，说明left太小了，left右移；
3）>0，说明right太大了，right左移；
去重的点：
1）在i遍历的时候，如果nums[i]和nums[i-1]相同，则略过
2）在每轮遍历和等于零时，left和right需要一直移动，直到不重复。
奇怪的解法
66. 加一
普通的数组移位，当有进位或最后一位的时候需要加一。
public int[] plusOne(int[] digits) {
int len = digits.length;
boolean over = false;
for(int i = len - 1;i >= 0;i--){
int num = digits[i];
if(over || i == len - 1){
num += 1;
}
if(num < 10){
digits[i] = num;
over = false;
break;
} else{
digits[i] = 0;
over = true;
}
}
if(over){
int[] newdigits = new int[len + 1];
newdigits[0] = 1;
return newdigits;
}
return digits;
}
189. 旋转数组
这个方法基于这个事实：当我们旋转数组 k 次， k%n 个尾部元素会被移动到头部，剩下的元素会被向后移动。
所以分三步：
- 数组所有数反转
- 反转前k个
- 反转后n-k个
public void swap(int[] nums, int start, int end){
int temp = nums[end];
nums[end] = nums[start];
nums[start] = temp;
}
public void rotatePart(int[] nums, int start, int end){
while(start < end){
swap(nums, start, end);
start++; end--;
}
}
public void rotate(int[] nums, int k) {
int len = nums.length;
if(len == 0 || len == 1 || k == 0) return;
if(k >= len){
k = k % len;
}
rotatePart(nums, 0, len - 1);
rotatePart(nums, 0, k - 1) ;
rotatePart(nums, k, len - 1);
}
动态规划PART
70. 爬楼梯
类似斐波那契数列，尝试几个：
f(0) = 1
f(1) = 1
f(2) = f(1) + f(0)
f(3) = f(2) + f(1)
f(4) = f(3) + f(2)
可以发现规律，f(n)只与f(n-1)和f(n-2)有关，因此不需要开辟数组存表，只需要弄两个变量存上次和上上次的值就行了。
public int climbStairs(int n) {
int ll = 1;
int l = 1;
int result = 0;
if(n <= 1) return 1;
for(int i = 2;i <= n;i++){
result = ll + l;
l = ll;
ll = result;
}
return result;
}
链表PART
21. 合并两个有序链表
链表题，主要是指针的移动，以及非空的判断，记得在挂节点的时候要用一个指针指向下一个节点保留它的位置，头结点也需要一个指针记录位置。
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode psmall;
ListNode plarge;
ListNode start;
if(l1 == null) return l2;
if(l2 == null) return l1;
if(l1.val < l2.val){
psmall = l1;
plarge = l2;
start = l1;
} else{
psmall = l2;
plarge = l1;
start = l2;
}
while(psmall != null && plarge != null){
if(psmall.val <= plarge.val){
if(psmall.next != null){
if(psmall.next.val > plarge.val){
// Append plarge
ListNode plargeNext = plarge.next;
plarge.next = psmall.next;
psmall.next = plarge;
plarge = plargeNext;
psmall = psmall.next;
}else{
psmall = psmall.next;
}
} else{
psmall.next = plarge;
break;
}
}
}
return start;
}
142. 环形链表 II
之前用双指针法判断链表是否有环，两个指针一块一慢，一个走两格，一个走一格，快追慢，如果有环，是一定追的上的。
这道题增加了需要返回环入口的节点位置要求。需要走两轮，第一轮用快慢两个指针检查是否有环，第二轮用走一步的指针找到入口位置。
设置 a 为链表头到环入口的节点数，b为环的节点数。
慢指针走过的路程为s=a + b
快指针走过的路程为f = a + nb
同时由于快指针每次走两步，慢指针每次走一步，当他们相遇时一定满足：f = 2s
结合上面三个式子，可以得出：s = nb 和 f=2nb
接下来考虑怎样走才能找到入口，如果从头一直走的话，走到入口的步数为a + nb（只要走过a之后一直绕圈就行了），而现在s已经走过nb，因此只要再走过a就可以了。
于是在第二轮，让fast从head开始，跟slow一起走，当他们相遇时，fast一定走过了a步，他们俩也就同时停在了入口，返回即可。
public ListNode detectCycle(ListNode head) {
// Round1: Check if there is a loop.
ListNode slow = head;
ListNode fast = head;
while(fast != null){
if(slow.next != null){
slow = slow.next;
} else{
return null;
}
if(fast.next != null){
if(fast.next.next != null){
fast = fast.next.next;
} else{
return null;
}
} else{
return null;
}
if(slow == fast) break;
}
// fast move to the end, no loop
if(fast == null) return null;
else{
// Round2: Find start index.
fast = head;
while(fast != null){
if(fast == slow) return fast;
fast = fast.next;
slow = slow.next;
}
}
return null;
}
