力扣爆刷第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];
}
}
