[数据结构与算法]每日一练＜2＞

每日一练

大家好呀！我是小笙，接下来分享下10月份每日一题的解题思路~

870. 优势洗牌

给定两个大小相等的数组 nums1 和 nums2，nums1 相对于 nums2 的优势可以用满足 nums1[i] > nums2[i] 的索引 i 的数目来描述 ; 返回 nums1 的任意排列，使其相对于 nums2 的优势最大化

示例 ：

输入：nums1 = [2,7,11,15], nums2 = [1,10,4,11]
输出：[2,11,7,15]

解读：两个长度相同的数组，使相同的索引下数组1的值排序后尽可能大于数组2的值

class Solution {
    public int[] advantageCount(int[] nums1, int[] nums2) {
        int len = nums1.length;
        if(len == 1){
            return nums1;
        }

        int[] res = new int[len];
        Integer[] idx2 = new Integer[len];
        for (int i = 0; i < len; ++i) {
            idx2[i] = i;
            res[i] = -1;
        }
        
        Arrays.sort(idx2, (i, j) -> nums2[i] - nums2[j]);
        Arrays.sort(nums1);
        Arrays.sort(nums2);

        int index = 0;
        for(int i=0;i<len;i++){
            if(nums1[i] > nums2[index]){
                res[idx2[index++]] = nums1[i];
                nums1[i] = -1;
            }
        }
        index = 0;
        for(int i=0;i<len;i++){
            if(res[i] == -1){
                while(nums1[index++] == -1);
                res[i] = nums1[index+-1];
            }
        }
        return res;
    }
}

856. 括号的分数

给定一个平衡括号字符串 S，按下述规则计算该字符串的分数：

• () 1分
• ()() 1+1分
• (()) 1*2分

示例 ：

输入： "()()"
输出： 2
----------------
输入： "(()(()))"
输出： 6

分治思想（递归方式）

class Solution {
    public int scoreOfParentheses(String s) {
        int len = s.length();
        if (len == 2) {
            return 1;
        }
        // 找到第一个累加的分界点
        int sum = 0,split = 0;
        for(int i=0;i<len;i++){
            sum += s.charAt(i) == '('?1:-1;
            if(sum == 0){
                split = i+1;
                break;
            }
        }

        // 不需要累加，类似这种情况((()))
        if(len == split){
            return 2 * scoreOfParentheses(s.substring(1,split-1));
        // 需要累加，类似这种情况()()()
        }else{
            return scoreOfParentheses(s.substring(0,split)) +  scoreOfParentheses(s.substring(split));
        }
    }
}

1790. 仅执行一次字符串交换能否使两个字符串相等

给你长度相等的两个字符串 s1 和 s2 。一次 字符串交换操作的步骤如下：选出某个字符串中的两个下标（不必不同），并交换这两个下标所对应的字符。如果对 其中一个字符串执行最多一次字符串交换就可以使两个字符串相等，返回 true ；否则，返回 false

示例

输入：s1 = "bank", s2 = "kanb"
输出：true
解释：例如，交换 s2 中的第一个和最后一个字符可以得到 "bank"
-----------------------------------------------------
输入：s1 = "attack", s2 = "defend"
输出：false
解释：一次字符串交换无法使两个字符串相等

解题思路：分两种情况：1.字符串相同 2.字符串不相同但是可以通过一次交换使得两个字符串相同

class Solution {
    public boolean areAlmostEqual(String s1, String s2) {
        // 判断字符串是否相同
        if(s1.equals(s2)){
            return true;
        }
        // 通过index1,index2 分别记录不同字符的下标
        int index1 = -1,index2 = -1;
        for(int i=0;i<s1.length();i++){
            if(s1.charAt(i) != s2.charAt(i)){
                if(index1 == -1){
                    index1 = i;
                }else if(index2 == -1){
                    index2 = i;
                }else{
                     // 如果上述情况都没满足，说明出现了第三个字符不相同的情况
                    return false;
                }
            }
        }
        // 排除 1.只有一个字符不同的情况 2.两个字符进行交换但是还是不相同的情况
        if(index1 == -1 || index2 == -1 || s2.charAt(index1) != s1.charAt(index2) || s2.charAt(index2) != s1.charAt(index1)){
            return false;
        }
        return true;
    }
}

817. 链表组件

给定链表头结点 head，该链表上的每个结点都有一个 唯一的整型值 。同时给定列表 nums，该列表是上述链表中整型值的一个子集。返回列表 nums 中组件的个数，这里对组件的定义为：链表中一段最长连续结点的值（该值必须在列表 nums 中）构成的集合

示例

输入: head = [0,1,2,3], nums = [0,1,3]
输出: 2
解释: 链表中,0 和 1 是相连接的，且 nums 中不包含 2，所以 [0, 1] 是 nums 的一个组件，同理 [3] 也是一个组件，故返回 2

解题思路：遍历链表 head ，寻找组件开始点是当前链表值存在于 nums 数组中，如果中断则再次寻找开始点，只要统计开始点则是组件个数

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public int numComponents(ListNode head, int[] nums) {
        List<Integer> list = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        while(head != null){
            list.add(head.val);
            head = head.next;
        }
        for(int i=0;i<nums.length;i++){
            list2.add(nums[i]);
        }
        int res = 0;
        for(int i=0;i<list.size();i++){
            int index = i;
           while(list2.contains(list.get(index++)) && index < list.size());
           if(list2.contains(list.get(i))){
                res++;
                i = index - 1;
           }
        }
        return res;
    }
}

优化代码，既然是存在问题，则使用 HashSet 代替 list 性能会更加好！

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public int numComponents(ListNode head, int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int i=0;i<nums.length;i++){
            set.add(nums[i]);
        }
        int res = 0;
        while(head != null){
            int temp = head.val;
            //寻找开始点
            while(head != null && set.contains(head.val)){
                head = head.next;
            }
            // 判断是否为开始点
            if(head == null || temp != head.val){
                res++;
            }else{
                head = head.next;
            }
        }
        return res;
    }
}

769. 最多能完成排序的块

给定一个长度为 n 的整数数组 arr ，它表示在 [0, n - 1] 范围内的整数的排列。我们将 arr 分割成若干 块 (即分区)，并对每个块单独排序。将它们连接起来后，使得连接的结果和按升序排序后的原数组相同。返回数组能分成的最多块数量

例子

输入: arr = [4,3,2,1,0]
输出: 1
解释:
将数组分成2块或者更多块，都无法得到所需的结果。
例如，分成 [4, 3], [2, 1, 0] 的结果是 [3, 4, 0, 1, 2]，这不是有序的数组
---------------------------------------------------------------------
输入: arr = [1,0,2,3,4]
输出: 4
解释:
我们可以把它分成两块，例如 [1, 0], [2, 3, 4]。
然而，分成 [1, 0], [2], [3], [4] 可以得到最多的块数

解题思路：最早能够分块的就分块，就比如在【1，5】区间肯定需要存在最小的5个数，就可以分块，按照这个思路来记录块数

class Solution {
    public int maxChunksToSorted(int[] arr) {
        int res = 0,index = 0;
        int[] temp = arr.clone();
        Arrays.sort(temp);
        Set<Integer> set = new HashSet<>();
        for(int i=0;i<arr.length;i++){
            set.add(arr[i]);
            while(index <= i && set.contains(temp[index])){
                index++;
            }
            if(index == i+1){
                res++;
            }
        }
        return res;
    }
}