代码随想录第五天复习

Posted on In

数组

704 二分查找 左闭右闭，左闭右开 两种方法 checked!
27 移除元素 暴力解法 快慢指针 左右指针（while查找右边第一个不是val的值， 无需考虑right是什么值） checked!
977 有序数组的平方 左右指针法（右指针– ！） checked!
209 长度最小的子数组 滑动窗口解决（左右指针，比较方法） checked!
59 螺旋数组II 模拟四次左闭右开（循环不变量原则） checked!

链表

203 移除链表元素 有dummy node 有 pre, 无dummy node 有 pre checked!
无dummy node 无 pre （while只判断cur，while之中的while判断cur.next） double checked!
707 设计链表 单链表 双链表 （此题切记，在插入方法，和删除方法中对size的运算） checked!
206 反转链表 无递归，正向递归，反向递归(像背下来的) checked!
反向同函数递归 double checked!
24 两两交换链表中的节点 无递归 checked!
有递归（需要着重复习） unchecked!!!!!!
19 删除链表倒数第N个节点 两次遍历，一次遍历（快慢指针） checked!
160 链表相交 两个for loop， 交换A 和 B checked!
142 环形链表II 快慢指针，注意while loop的条件，如何查找环入口 checked!

拓展

704 二分查找 拓展
35 搜索插入位置 简单的二分法之后，return left checked!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution{
	public int searchInsert(int[] nums, int target){
		int left = 0, right = nums.length - 1;
		
		while (left <= right){
			int mid = left + ((right - left) >> 1);
			
			if (nums[mid] == target){
				return mid;
			} else if (nums[mid] < target){
				left = mid + 1;
			} else {
				right = mid - 1;
			}
			
		}
		
		return left;
	
	}
}

34 在排序数组中查找元素的第一个和最后一个位置
二分法先查找出一个target的位置，后两个指针向两侧滑动到不是target值的位置 checked!
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
class Solution{
	public int[] searchRange(int[] nums, int target){
		int index = binarySearch(nums, target);
		
		if (index == -1) return new int[] {-1,-1};
		
		int left = index;
		int right = index;
		
		while (left >= 0&& nums[left] == target ) left--;
		
		while (right <= nums.length - 1 && nums[right] == target) right++;
		
		return new int[] {left+1,right-1};
	
	}
	
	public int binarySearch(int[] nums, int target){
		int left = 0, right = nums.length - 1;

		while (left<= right){
			int mid = left + ((right - left) >> 1);
			
			if (nums[mid] == target){
				return mid;
			} else if (nums[mid] < target){
				left = mid + 1;
			} else {
				right = mid - 1;
			}
		
		}
		return -1;
	}
}

27 移除元素 拓展
26 删除排序数组中的重复项 checked!
快慢指针检测，注意条件的使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution{
	public int removeDuplicates(int[] nums){
		if (nums.length < 2) return nums.length;
		
		int slowIndex = 0, fastIndex = 0;
		
		while (fastIndex < nums.length){
			if (nums[slowIndex] == nums[fastIndex]){
				fastIndex++;
			
			} else{
				slowIndex++;
				nums[slowIndex] = nums[fastIndex];
				fastIndex++;
			}
		}
		
		return slowIndex+1;
	}
}

链表拓展
234 回文链表

  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
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    class Solution{
    	public boolean isPalindrome(ListNode head){
    		int length = 0;
    		ListNode cur = head;
    		
    		while (cur != null){
    			cur= cur.next;
    			length++;
    		}
    		
    		int[] headList = new int[length];
    		cur = head;
    		for(int i = 0; i < length; i++){
    			headList[i] = cur.val;
    			cur = cur.next;
    		}
    		
    		int left = 0, right = length - 1;
    		
    		while (left <= right){
    			if (headList[left]==headList[right]){
    				left++;
    				right--;
    			} else {
    				return false;
    			}
    		
    		}
    		
    		return true;
    	
    	}

    }

  2. 利用快慢指针

    1. 快慢指针， 快指针进2步，慢指针进1步，找到中点
    2. 在中点前断成两个LinkedList
    3. 反转后面的链表
    4. 对比短链表数量的值看是否相等
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
class Solution{
	public boolean isPalindrome(ListNode head){
		if (head == null || head.next == null) return true;
		
		ListNode slowIndex = head;
		ListNode fastIndex = head;
		
		while (fastIndex != null && fastIndex.next != null){
			fastIndex = fastIndex.next.next;
			slowIndex = slowIndex.next;
		}
		
		ListNode curA = reverseList(slowIndex);
		slowIndex = null;
		ListNode curB = head;
			
		while (curA != null){
			if (curA.val == curB.val){
				curA = curA.next;
				curB = curB.next;
			} else {
				return false;
			}
		}
		
		return true;
	}
	
	public ListNode reverseList(ListNode head){
		if (head == null) return null;
		if (head != null && head.next == null) return head;
		
		ListNode last = reverseList(head.next);
		head.next.next = head;
		head.next = null;
		
		return last;
	}
}