自学内容网 自学内容网

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

原文地址:https://blog.csdn.net/qq_43511039/article/details/140532213

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!