LeetCode刷题第7周小结

文章目录

 1.使序列递增的最小交换次数

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

3.链表组件

4. 最多能完成排序的块

5.不同的子序列

6. 用栈操作构建数组

7.可能的二分法

关键词

动态规划、广度优先搜索、深度优先搜索、染色法、中等困难

---

 1.使序列递增的最小交换次数

难度： ★  ★ ★    链接：力扣

解题思路：动态规划

解题代码：

class Solution {
    public int minSwap(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int a = 0, b = 1;
        for (int i = 1; i < n; i++) {
            int at = a, bt = b;
            a = b = n;
            if (nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1])  {
                a = Math.min(a, at);
                b = Math.min(b, bt + 1);
            }
            if (nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1]) {
                a = Math.min(a, bt);
                b = Math.min(b, at + 1);
            }
        }
        return Math.min(a, b);
    }
}

 

---

 

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

难度： ★  链接：力扣

解题思路：简单模拟进行计数统计

题目要求其中的一个字符串至多进行一次字符串交换操作使得两个字符串相等，那么则表面两个字符串最多出现两个位置i,j上的字符不同，如果大于两处，则肯定无法通过一次字符串交换的操作使其相等。所以，搞明白了这点，本题就迎刃而解了！有以下两种情况：

• 当s1=s2时，则无需交换
• 当s1≠s2时，则必然存在两个位置处的字符不相等，但只需经过其中一个字符串的一次交换字符的操作可以使二者相等，则肯定满足如下关系：s1[i]=s2[j]  s1[j]=s2[i]

解题代码：

class Solution {
    public boolean areAlmostEqual(String s1, String s2) {
        //相等则无需交换直接返回true
        if(s1.equals(s2))return true;
        int n=s1.length();
        Listres=new ArrayList<>();
        for(int i=0;i
            if(s1.charAt(i)!=s2.charAt(i)){
                //如果出现大于两处的不同，则肯定无法通过其中的一个字符串交换一次能使二者相等
                if(res.size()>2)return false;
                res.add(i);//记录字符不相等下的下标
            }
        }
        if(res.size()!=2)return false;
        int i=res.get(0);int j=res.get(1);
        return s1.charAt(i)==s2.charAt(j)&&s1.charAt(j)==s2.charAt(i);
    }
}

 

---

 

3.链表组件

难度： ★ ★  链接：力扣

解题思路：简单模拟，计算组件的起始位置

本题的意思就是统计链表中在数组nums中的最长的连续的结点所组成的子链，这样的子链称为组件，计算它的总个数。所以我们只需要统计一个组件的起始位置即可，一个组件的起始位置一定满足下述的两个条件：

• 第一，它的结点值肯定要在数组nums中且该位置处于子链表的起始位置处
• 第二，它的前一个结点的值不在数组nums中，否则该位置不是起始位置，只是其中的一部分

我们设置一个布尔型变量inSet来依次判断结点处的值是否在数组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) {
        Setset=new HashSet<>();
        boolean inSet=false;
        int res=0;
        for(int num:nums){
            set.add(num);
        }
        while(head!=null){
            if(set.contains(head.val)){
                if(!inSet){
                    inSet=true;
                    res++;
                }
            }else{
                inSet=false;
            }
            head=head.next;
        }
        return res;
    }
}

---

 

4. 最多能完成排序的块

难度： ★ ★  链接：力扣

 解题思路：

因为题目数据限制说每个元素都不重复，且范围是[0,n-1]  所以当对原数组进行排序后会发现元素值与下标值对应相等，那么我们将下标和元素值分别进行累加，如果二者累加和相等则将当前位置切分出一个块，来达到最大划分的目的。

比如：[1,0,2,3,4]，令下标和为indexSum,数值和为valueSum,总划分块数为res初始值为0

• 当第一次累加时，indexSum=0,valueSum=1,二者不相等则不用划分 ，res=0
• 当第二次累加时，indexSum=1,valueSum=1,二者相等，则对其进行划分，即[1,0]成为一个块，res加一后，res=1
• 当第三次累加时，indexSum=3,valueSum=3，二者相等，进行划分，即[2]单独成块
• 以此类推
• 最后划分的块为：[1,0] , [2] , [3] , [4] 分别排序后与原数组排序后顺序相同符合题意，即最大划分块数为4

解题代码：

class Solution {
    public int maxChunksToSorted(int[] arr) {
        int valueSum=0,indexSum=0,res=0;
        //依次累加下标和与数值和
        for(int i=0;i
            valueSum+=arr[i];
            indexSum+=i;
            //相等则将当前位置划分为一个块，块数加一
            if(valueSum==indexSum){
                res++;
            }
        }
        return res;
    }
}

---

 

5.不同的子序列

难度： ★ ★ ★  链接：力扣

 解题思路：动态规划

解题代码：

class Solution {
    public int distinctSubseqII(String s) {
        final int MOD = 1000000007;
        int[] last = new int[26];
        Arrays.fill(last, -1);
 
        int n = s.length();
        int[] f = new int[n];
        Arrays.fill(f, 1);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < 26; ++j) {
                if (last[j] != -1) {
                    f[i] = (f[i] + f[last[j]]) % MOD;
                }
            }
            last[s.charAt(i) - 'a'] = i;
        }
 
        int ans = 0;
        for (int i = 0; i < 26; ++i) {
            if (last[i] != -1) {
                ans = (ans + f[last[i]]) % MOD;
            }
        }
        return ans;
    }
}
 

 

---

 

6. 用栈操作构建数组

链接：  ★ ★  链接：力扣

解题思路：简单模拟，遇到和目标数组中值相同则Push，不同则先Push再Pop,是个简单题

解题代码：

class Solution {
    public List buildArray(int[] target, int n) {
        Listres=new ArrayList();
        int count=0;
        for(int i=1,j=0;i<=n;i++){
            if(target[j]==i){
                res.add("Push");
                j++;
                count++;
            }else{
                res.add("Push");
                res.add("Pop");
            }
            if(count==target.length){
                break;
            }
        }
        return res;
    }
}

---

 

7.可能的二分法

难度：★ ★  链接：力扣

 思路一：深度优先搜索+染色法

染色法的思想：假设第一组中的人时红色，第二组中的人为蓝色。我们依次遍历每一个人，如果当前的人没有被分组，就将其分到第一组（即染为红色），那么这个人不喜欢的人必须分到第二组中（染为蓝色）。然后任何新被分到第二组的人，其不喜欢的人必须被分到第一组，依次类推。如果在染色的过程中存在冲突，就表面这个染色任务是不可能完成的，即无法完成题目要求的分成两组且两个互相看不顺眼的人不在同一组的要求。否则说明染色有效，则说明可以将其按照题目要求进行分组。

染色法的思想还是蛮巧妙的，当然还有基于深度优先搜索遍历。

代码：

class Solution {
    public boolean possibleBipartition(int n, int[][] dislikes) {
        int[] color = new int[n + 1];
        List[] g = new List[n + 1];
        for (int i = 0; i <= n; ++i) {
            g[i] = new ArrayList();
        }
        for (int[] p : dislikes) {
            g[p[0]].add(p[1]);
            g[p[1]].add(p[0]);
        }
        for (int i = 1; i <= n; ++i) {
            if (color[i] == 0 && !dfs(i, 1, color, g)) {
                return false;
            }
        }
        return true;
    }
 
    public boolean dfs(int curnode, int nowcolor, int[] color, List[] g) {
        color[curnode] = nowcolor;
        for (int nextnode : g[curnode]) {
            if (color[nextnode] != 0 && color[nextnode] == color[curnode]) {
                return false;
            }
            if (color[nextnode] == 0 && !dfs(nextnode, 3 ^ nowcolor, color, g)) {
                return false;
            }
        }
        return true;
    }
}

 思路二：广度优先搜索+染色法

代码：

class Solution {
    public boolean possibleBipartition(int n, int[][] dislikes) {
        int[] color = new int[n + 1];
        List[] g = new List[n + 1];
        for (int i = 0; i <= n; ++i) {
            g[i] = new ArrayList();
        }
        for (int[] p : dislikes) {
            g[p[0]].add(p[1]);
            g[p[1]].add(p[0]);
        }
        for (int i = 1; i <= n; ++i) {
            if (color[i] == 0) {
                Queue queue = new ArrayDeque();
                queue.offer(i);
                color[i] = 1;
                while (!queue.isEmpty()) {
                    int t = queue.poll();
                    for (int next : g[t]) {
                        if (color[next] > 0 && color[next] == color[t]) {
                            return false;
                        }
                        if (color[next] == 0) {
                            color[next] = 3 ^ color[t];
                            queue.offer(next);
                        }
                    }
                }
            }
        }
        return true;
    }
}