力扣爆刷第166天之TOP100五连刷96-100（单词拆分、回溯、旋转数组）

力扣爆刷第166天之TOP100五连刷96-100（单词拆分、回溯、旋转数组）

一、24. 两两交换链表中的节点

题目链接：https://leetcode.cn/problems/swap-nodes-in-pairs/description/
思路：要求把相邻的节点两两交换，不能只交换值，其实对于这种交换类型的题目很简单，只需要维护3个或者4个指针，指针①维护要交换的两个节点的前一个节点，这个属于前驱节点，避免断线了，指针②指向第一个要交换的节点，指针③指向第二个要交换的节点，指针②和指针③负责交换节点，指针④用来记录后继节点，所以思路就清晰了，只需要②③节点进行交换，①④维护两个端点，每交换完一组后，指针向后移动就行。

class Solution {public ListNode swapPairs(ListNode head) {if(head == null || head.next == null) return head;ListNode root = new ListNode(-1, head);ListNode pro = root, cur = head, pre = null;while(cur != null && cur.next != null) {pre = cur.next.next;pro.next = cur.next;cur.next.next = cur;cur.next = pre;pro = cur;cur = pre;}return root.next;}
}

二、139. 单词拆分

题目链接：https://leetcode.cn/problems/word-break/description/
思路：单词拆分，问一个单词字典能否拼成一个字符串，要求单词可以不全使用，单个单词可以重复使用，从这几点可以看出，本题是一个完全背包问题，问的就是能不能把背包装满，对于完全背包，在不求排列数和组合数的情况下，物品和背包不讲究向后遍历顺序，而且都是正序，那么定义dp[i]表示以s[0, i]区间的字符串可以被拼接成功，那么就可以找到递推规律，只要在前一个位置可以拼成，然后比较后面的区间，如果相同即可拼成。

class Solution {public boolean wordBreak(String s, List<String> wordDict) {boolean[] dp = new boolean[s.length()+1];dp[0] = true;for(int i = 0; i < s.length(); i++) {for(String t : wordDict) {int k = t.length();if(k > i+1 || dp[i+1] || !dp[i+1-k]) continue;if(isEquals(s, t, i+1-k, i)) {dp[i+1] = true;}}}return dp[s.length()];}boolean isEquals(String s, String t, int left, int right) {int i = 0;while(left <= right && i < t.length()) {if(s.charAt(left) != t.charAt(i)) return false;left++;i++;}return true;}}

三、560. 和为 K 的子数组

题目链接：https://leetcode.cn/problems/subarray-sum-equals-k/
思路：本题要求求和为K的子数组，要求子数组连续，其实如果子数组不连续让求子序列，直接回溯就可以做。但是现在子数组连续，这种情况下可以考虑前缀和，遍历数组的过程中用map记录前缀和出现的次数，然后对于每一个前缀和都尝试去减k，看看对应的前缀和是否存在，如果存在，则说明一定有和为k的子数组，与上一个前缀和相加，得到当前的前缀和。此时计数即可。

class Solution {public int subarraySum(int[] nums, int k) {Map<Integer, Integer> map = new HashMap<>();map.put(0, 1);int count = 0, preSum = 0;for(int i = 0; i < nums.length; i++) {preSum += nums[i];if(map.containsKey(preSum-k)) {count += map.get(preSum-k);}map.put(preSum, map.getOrDefault(preSum, 0)+1);}return count;}
}

四、209. 长度最小的子数组

题目链接：https://leetcode.cn/problems/minimum-size-subarray-sum/description/
思路：求和为k的长度最小的子数组，这种类型一看就是滑动窗口，不停的扩大右边界，直到出发条件，然后记录长度，然后缩小左边界，直到不再满足条件，然后再重新扩大右边界。

class Solution {public int minSubArrayLen(int target, int[] nums) {int left = 0, right = 0, sum = 0, min = Integer.MAX_VALUE;while(right < nums.length) {sum += nums[right++];while(sum >= target) {min = Math.min(min, right - left);sum -= nums[left++];}}return min == Integer.MAX_VALUE ? 0 : min;}
}

五、153. 寻找旋转排序数组中的最小值

题目链接：https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/description/
思路：本题说的是数组旋转若干次之后求数组中的最小值，因为原数组是升序的且无重，无论旋转多少次，最后数组只能是两种形态，要么单调递增，要么分段递增，那么就很简单，先排除第一种，如果右边界的值大于左边界就可以说明是单调递增的，那么剩下的就都是分段递增了，对于分段递增，采用二分法，如果二分之后的中值大于nums[0]说明中值位于左分段，最小值在右区间，如果二分之后的中值小于nums[0]则说明最小值位于左区间。然后以此往复一直寻找就可以。

class Solution {public int findMin(int[] nums) {int len = nums.length;if(nums[len-1] >= nums[0]) return nums[0];int left = 0, right = len - 1;while(left <= right) {int mid = left + (right - left) / 2;if(nums[mid] < nums[0]) {right = mid-1;}else{left = mid+1;}}return nums[left];}
}