LeetCode 424替换后的最长重复字符、LeetCode 24两两交换链表中的节点、LeetCode 215数组中的第K个最大元素、LeetCode 53最大子数组和、LeetCode46全排列

LeetCode 424替换后的最长重复字符、LeetCode 24两两交换链表中的节点、LeetCode 215数组中的第K个最大元素、LeetCode 53最大子数组和、LeetCode46全排列,第1张

LeetCode 424替换后的最长重复字符

题目描述:给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符,并将其更改为任何其他大写英文字符。该 *** 作最多可执行 k 次。
在执行上述 *** 作后,返回包含相同字母的最长子字符串的长度。

示例 1:
输入:s = “ABAB”, k = 2
输出:4
解释:用两个’A’替换为两个’B’,反之亦然。
示例 2:
输入:s = “AABABBA”, k = 1
输出:4
解释:
将中间的一个’A’替换为’B’,字符串变为 “AABBBBA”。
子串 “BBBB” 有最长重复字母, 答案为 4。

一、我们可以枚举字符串中的每一个位置作为右端点,然后找到其最远的左端点的位置,满足该区间内除了出现次数最多的那一类字符之外,每次从左至右遍历计算其出现次数,到剩余的字符(即非最长重复字符)数量不超过k个。

这样我们可以想到使用双指针维护这些区间,每次右指针右移,如果区间仍然满足条件,那么左指针不移动,否则左指针至多右移一格,保证区间长度不减小。

  • 因为一直都有right++,所以碰到最大的之后长度至少都会是最大,不满足条件的会left++和right++,长度仍不变
  • ABB和ABA中len-maxn都为1满足条件的
  • 维持一个最大值maxn = Math.max(maxn, num[s.charAt(right) - 'A']);
    //求窗口中曾出现某字母的最大次数
    //计算某字母出现在某窗口中的最大次数,窗口长度只能增大或者不变(注意后面left指针只移动了0-1次)
    //这样做的意义:我们求的是最长,如果找不到更长的维持长度不变返回结果不受影响
二、实际代码中,由于字符串中仅包含大写字母,我们可以使用一个长度为 26 的数组维护每一个字符的出现次数。

每次区间右移,我们更新右移位置的字符出现的次数,然后尝试用它更新重复字符出现次数的历史最大值,最后我们使用该最大值计算出区间内非最长重复字符的数量,以此判断左指针是否需要右移即可

可执行完整代码
public class424替换后的最长重复字符 {
    public int characterReplacement(String s, int k) {
        int left = 0, right = 0;   // 左右下标
        int n = s.length();
        int maxn = 0;   // 通过下面的if维持窗口中曾出现某个字母的最大次数,窗口长度只能增大(因为我们要找的是最长,所以不影响)
        int[] nums = new int[26];
        while (right < n) {
            nums[s.charAt(right) - 'A']++;
            maxn = Math.max(maxn, nums[s.charAt(right) - 'A']);
            if (right - left + 1 - maxn > k) {
                nums[s.charAt(left) - 'A']--;
                left++;
            }
            right++;   // 走完这里的时候,其实right会多走一步
        }
        return right - left;   // 因为right已经多走一步了,所以不用再+1,结果为(right-1)-left+1==right-left
    }
}
LeetCode 24两两交换链表中的节点

题目描述:给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。

示例1
输入:head = [1,2,3,4]
输出:[2,1,4,3]
示例 2:

示例2
输入:head = []
输出:[]
示例 3:

示例3
输入:head = [1]
输出:[1]

一、迭代的方法空间复杂度为1,时间复杂度n。创建哑结点 dummyHead,令 dummyHead.next = head。令 temp 表示当前到达的节点,初始时 temp = dummyHead。

每次需要交换 temp 后面的两个节点。如果 temp 的后面没有节点或者只有一个节点,则没有更多的节点需要交换,因此结束交换。否则,获得 temp 后面的两个节点 node1 和 node2,通过更新节点的指针关系实现两两交换节点。

二、while循环中的交换过程,先temp.next = node2,然后才可以切分node1.next = node2.next;然后node2.next = node1。最后将temp引用移动到交换后的节点node1那儿。

完整可执行代码如下
public class24题两两交换链表中的节点 {
    public ListNode swapPairs(ListNode head) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode temp = dummyHead;
        while (temp.next != null && temp.next.next != null) {
            ListNode node1 = temp.next;
            ListNode node2 = temp.next.next;
            temp.next = node2;
            node1.next = node2.next;
            node2.next = node1;
            temp = node1;
        }
        return dummyHead.next;
    }
}
LeetCode 215数组中的第K个最大元素(快排变形,时间复杂度On,空间复杂度logN【递归使用栈空间的空间代价的期望为 O(\log n)O(logn)。】)

题目描述:
给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。
请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

一、因为是random了一个基准元素下标index,从left开始覆盖,所以要nums[index]=nums[left]。【如果是直接使用left作为基准就可以直接tem=nums[l]】 二、外层while和内层while中,nums[r]<=temp的时候r–,将小的元素放再右边;nums[l]>=tem的时候l++,大的元素放在左边,这样外层while找完位置后,就可以直接判断if(l == k-1)直接return nums[l]。else if(l < k - 1) 右侧l+1,right递归,else左侧left,l-1递归。 PS:直接使用left作为基准函数设计为quickSrot(int[] nums, int left, int right);如果自己random基准元素下标的话,也设计为quickSort(int[] nums, int left, int right) ,如果判断k就把k加入进参数中去。 random.nextInt()的用法

带参的nextInt(int x)则会生成一个范围在0~x(不包含X)内的任意正整数
例如:int x=new Random.nextInt(100);
则x为一个0~99的任意整数

可通过完整代码:
public class215题数组中的第K个最大元素 {
    Random rand = new Random();
    public int findKthLargest(int[] nums, int k) {
        return quickSort(nums, k, 0, nums.length - 1);
    }

    private int quickSort(int[] nums, int k, int left, int right) {   // nums[i]修改下标i处的元素值
        int index = rand.nextInt(right - left  +1) + left;   // random取一个基准元素,取个数移动left(+left)
        int temp = nums[index];   // 将基准元素值存起来
        nums[index] = nums[left];   // 随机基准的话,因为首先交换要覆盖nums[l],所以要把left存给nums[index]
        int l = left, r = right;   // 将left和right保存一份用于移动位置,原始的left和right用于最后的quickSort递归
        while (l < r) {
            while (l < r && nums[r] <= temp) r--;   // 小的在右边
            nums[l] = nums[r];
            while (l < r && nums[l] >= temp) l++;   // 大的在左边,方便左边下标第一个是第1大的元素
            nums[r] = nums[l];
        }
        nums[l] = temp;
        if (l == k - 1) return nums[l];
        else if (l < k - 1) return quickSort(nums, k, l + 1, right);
        else return quickSort(nums, k, left, l - 1);
    }
}
LeetCode 53最大子数组和(动态规划)

原题链接:最大子序和

一、我们考虑让nums[i]加入上一段f(n-1)或者自己成一段,作为f(n)的最大值 可通过完整代码如下:
public static int maxSubArray(int[] nums) {
        int pre = 0, ans = nums[0];
        for (int x : nums) {
            pre = Math.max(pre + x, x);
            ans = Math.max(pre, ans);
        }
        return ans;
    }
LeetCode46全排列(因为数组不含重复数字,所以不用考虑去重)

题目描述:给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1:
输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2:
输入:nums = [0,1]
输出:[[0,1],[1,0]]

示例 3:
输入:nums = [1]
输出:[[1]]

一、每次dfs中for循环交换0与[0,1,2…]、1与[1,2,3…]、2与[2,3,4…]【每次后面的内容和本次的first交换】。且因为for循环中是遍历多次,所以dfs后output要有恢复 *** 作

时间复杂度:

java.util.Collections类的swap()方法

可执行完整代码:
public class46题全排列 {
    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> output = new ArrayList<>();
        for (int num : nums) {
            output.add(num);
        }
        int n = nums.length;
        dfs(n, output, res, 0);
        return res;
    }

    private static void dfs(int n, List<Integer> output, List<List<Integer>> res, int first) {
        if (first == n) res.add(new ArrayList<>(output));
        for (int i = first; i < n; i++) {
            Collections.swap(output, first, i);   // 交换 *** 作0-0及0以后、1-1及1以后、2-2及2以后...
            dfs(n, output, res, first + 1);   // 继续递归填下一个数
            Collections.swap(output, first, i);   // 因为for中要遍历多个,所以要有撤销 *** 作方便下一次的for循环正常进行
        }
    }

    public static void main(String[] args) {
        permute(new int[]{1,2,3});
    }
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/801501.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-05-07
下一篇 2022-05-07

发表评论

登录后才能评论

评论列表(0条)

保存