深圳幻海软件技术有限公司 欢迎您!

【Day28】力扣算法(超详细思路+注释) [1790. 仅执行一次字符串交换能否使两个字符串相等 ] [328. 奇偶链表 ][148. 排序链表]

2023-04-05

刷题打卡,第二十八天题目一、1790.仅执行一次字符串交换能否使两个字符串相等题目二、328.奇偶链表题目三、148.排序链表题目一、1790.仅执行一次字符串交换能否使两个字符串相等原题链接:1790.仅执行一次字符串交换能否使两个字符串相等题目描述:给你长度相等的两个字符串s1和s2。一次字符串

刷题打卡,第 二十八 天

  • 题目一、1790. 仅执行一次字符串交换能否使两个字符串相等
  • 题目二、328. 奇偶链表
  • 题目三、148. 排序链表


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

原题链接:1790. 仅执行一次字符串交换能否使两个字符串相等

题目描述

给你长度相等的两个字符串 s1 和 s2 。一次 字符串交换操作的步骤如下:选出某个字符串中的两个下标(不必不同),并交换这两个下标所对应的字符。
如果对 其中一个字符串 执行 最多一次字符串交换 就可以使两个字符串相等,返回 true ;否则,返回 false 。
/
示例 1:
输入:s1 = “bank”, s2 = “kanb”
输出:true
解释:例如,交换 s2 中的第一个和最后一个字符可以得到 “bank”
/
示例 2:
输入:s1 = “attack”, s2 = “defend”
输出:false
解释:一次字符串交换无法使两个字符串相等
/
示例 3:
输入:s1 = “kelb”, s2 = “kelb”
输出:true
解释:两个字符串已经相等,所以不需要进行字符串交换
/
示例 4:
输入:s1 = “abcd”, s2 = “dcba”
输出:false
/
提示:

  • 1 <= s1.length, s2.length <= 100
  • s1.length == s2.length
  • s1 和 s2 仅由小写英文字母组成

解题思路
题目已经给定我们两个长度相同字符串s1s2,要求我们判断字符串s2可否仅通过一次交换得到s1

在最开始,我们应该先判断两个字符串s1s2是否相等,相等就直接返回true即可。

通过思考,我们可以知道,交换一次,就会变动两个位置的字符,同时代表着字符串s2有两个位置的字符是与字符串s1不相同的,这么一来我们就找到了突破点。

我们同时遍历两个字符串,比较两字符串在相同位置的字符是否相等,如果不相等就将下标记录下来。

当我们记录下来的下标数量大于2时,就知道无法 仅执行一次字符串交换使两个字符串相等,直接返回false。

当遍历完成了,我们会得到两种情况:

①被记录下的下标只有一个,这也是无法通过最多一次交换相等的,false;

②被记录的下标有两个,这时候,我们需要判断字符串s2中,交换这两个位置的字符可以使得s2s1相等。相等则返回true,否则返回false;

提交代码

class Solution {
    public boolean areAlmostEqual(String s1, String s2) {
        if(s1.equals(s2)) return true;          //两个字符串相等,true

        List<Integer> diff = new ArrayList<>(); //使用集合记录不相等字符的位置(下标)
        
        for(int i = 0;i < s1.length();++i){     //遍历两个字符串
            if(s1.charAt(i) != s2.charAt(i))    //相同位置下字符不相等
            diff.add(i);                        //记录下来

            if(diff.size() > 2) return false;   //记录下的下标数大于2,false
        }
        
        if(diff.size() == 1) return false;      //只有一个位置不等,也不符合,false

        int a = diff.get(0),b = diff.get(1);    //取出记录的下标
        //判断交换位置后是否与s1相等
        return s1.charAt(a) == s2.charAt(b) && s2.charAt(a) == s1.charAt(b);
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

提交结果


题目二、328. 奇偶链表

原题链接:328. 奇偶链表

题目描述

给定单链表的头节点 head ,将所有索引为奇数的节点和索引为偶数的节点分别组合在一起,然后返回重新排序的列表。
第一个节点的索引被认为是 奇数 , 第二个节点的索引为 偶数 ,以此类推。
请注意,偶数组和奇数组内部的相对顺序应该与输入时保持一致。
你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。
/
示例 1:

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

输入: head = [2,1,3,5,6,4,7]
输出: [2,3,6,7,1,5,4]
/
提示:

  • n == 链表中的节点数
  • 0 <= n <= 104
  • -106 <= Node.val <= 106

解题思路
第一个节点是奇数,第二个节点是偶数,往后的节点也是 奇数-偶数-奇数--的位置顺序。

题目要求我们将所有奇数节点连在一块,所有偶数节点连在一块,且奇数连链表于偶数链表拼接。

必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。

我们可以创建两个新的链表,分别代表奇数链表 与 偶数链表,第一个节点是奇数,作为奇数链表的头节点;第二个节点为偶数,作为偶数链表的头节点。

因为奇数偶数是交替的,也就是奇数下一个节点为偶数,偶数下一个节点为奇数。我们就可以将所有奇数节点指向其后偶数节点的下一节点,偶数节点也指向其后奇数节点的下一个节点。

当我们遍历完原始链表,也就完成了奇数链表与偶数链表的节点连接,这时候将奇数链表末尾节点指向偶数链表头节点即可。

提交代码

/**
 * 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 ListNode oddEvenList(ListNode head) {
        if(head == null) return null;             //链表为空,直接返回空值
        ListNode odd = head;                      //创建奇数链表,头节点为原始链表的第一个节点
        ListNode even = head.next;                //创建偶数链表,头节点为原始链表的第二个节点
        ListNode temp = even;                     //额外创建链表指向偶数链表头节点,方便后续拼接

        while(temp != null && temp.next != null){ 
            odd.next = temp.next;   //奇数链表节点指向其后偶数节点的下一位置
            odd = odd.next;         //后移一位
            temp.next = odd.next;   //偶数数链表节点指向其后奇数节点的下一位置
            temp = temp.next;       //后移一位
        }
        odd.next = even;            //技术链表尾巴节点指向偶数链表头节点
        return head;                //返回头节点,也是奇数链表的头节点
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27

提交结果


题目三、148. 排序链表

原题链接:148. 排序链表

题目描述

给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。
/
示例 1:

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

输入:head = [-1,5,3,4,0]
输出:[-1,0,3,4,5]
/
示例 3:
输入:head = []
输出:[]
/
提示:

  • 链表中节点的数目在范围 [0, 5 * 104] 内
  • -105 <= Node.val <= 105

解题思路
我们需要给链表节点值进行排序。

我是用的排序方法是归并排序,我们知道,归并排序首先需要获得排序元素的中间元素位置。

但是链表又没有办法向数组那样通过下标获取,所以我们需要使用到快慢指针,快指针一次走两个节点,慢指针一次走一个节点,那么快指针遍历到链表结尾时,我们的慢指针所在位置就是中间节点的位置。

这时候我们借助递归,用同样的方式将每一个子链表通过中间节点平分,最后得到单个的节点,然后相邻的两个节点按照升序合并,这就是归并操作。

我们不断对相邻的两个节点进行归并操作,将归并好的节点按照顺序放入准备好的新链表中,最后返回新链表的头节点即可!

最主要还是理解归并排序的步骤、模板。

提交代码

/**
 * 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 ListNode sortList(ListNode head) {
       return sort(head,null);               //调用递归方法
    }
    //递归方法
    public ListNode sort(ListNode head,ListNode tail){
        if(head == null){      //头节点为空,返回空值
            return head;
        }
        if(head.next == tail){ //节点最终平分至单节点
            head.next = null;  //结点指向空值
            return head;       //返回节点
        }
        ListNode fast = head,slow = head;  //设置快慢指针
        while(fast != tail){               //快指针遍历到结尾前
            slow = slow.next;              //满指针后移
            fast = fast.next;              //快指针后移
            if(fast != tail){              //依旧未到尾部
            fast = fast.next;              //快指针第二次后移
            }
        }
        ListNode mid = slow;               //中间节点就是满指针当前节点
        ListNode list1 = sort(head,mid);   //同样方式平分左子链表
        ListNode list2 = sort(mid,tail);   //同样方式平分右子链表
        ListNode sorted = merge(list1,list2);  //调用归并操作方法
        return sorted;                         //返回升序链表头节点
    }
    public static ListNode merge(ListNode list1,ListNode list2){
        //创建新的链表,存放升序节点
        ListNode list = new ListNode();
        ListNode temp1 = list1;    //两个相邻的链表
        ListNode temp2 = list2;
    ListNode temp = list;
    while(temp1 != null && temp2 != null){ //对相邻链表进行归并操作
        if(temp1.val <= temp2.val){        //较小的节点放入链表
            temp.next = temp1;
            temp1 = temp1.next; 
        }else{
            temp.next = temp2;             //较小的节点放入链表
            temp2 = temp2.next;            
        }
        temp = temp.next;
    }
    if(temp1 != null){          //一个链表遍历完,相邻链表剩下的一个节点存入新链表
        temp.next = temp1;
    }
    if(temp2 != null){
        temp.next = temp2;
    }
    return list.next;           //返回升序链表
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62

提交结果



求关注⚽ 作者🥇 .29. 🥇 的✔博客主页✔
来刷题⚽ 记录每日LeetCode✔刷题专栏✔
您的点赞收藏以及关注是对作者最大的鼓励喔 ~~

文章知识点与官方知识档案匹配,可进一步学习相关知识
算法技能树首页概览43103 人正在系统学习中