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

简介: 了解(超详细思路+注释) [1790. 仅执行一次字符串交换能否使两个字符串相等 ] [328. 奇偶链表 ][148. 排序链表]。

刷题打卡,第 二十八 天


题目一、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 仅由小写英文字母组成

解题思路:

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


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


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


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


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


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


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


②被记录的下标有两个,这时候,我们需要判断字符串s2中,交换这两个位置的字符可以使得s2与s1相等。相等则返回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);
    }
}

提交结果:

微信图片_20221031111325.png


题目二、328. 奇偶链表


原题链接:328. 奇偶链表


题目描述:


给定单链表的头节点 head ,将所有索引为奇数的节点和索引为偶数的节点分别组合在一起,然后返回重新排序的列表。

第一个节点的索引被认为是 奇数 , 第二个节点的索引为 偶数 ,以此类推。

请注意,偶数组和奇数组内部的相对顺序应该与输入时保持一致。

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

/

示例 1:

微信图片_20221031111337.png

输入: head = [1,2,3,4,5]

输出: [1,3,5,2,4]

/

示例 2:

微信图片_20221031111343.png

输入: 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;                //返回头节点,也是奇数链表的头节点
    }
}

提交结果:

微信图片_20221031111349.png


题目三、148. 排序链表


原题链接:148. 排序链表


题目描述:


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

/

示例 1:

微信图片_20221031111355.png

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

输出:[1,2,3,4]

/

示例 2:

微信图片_20221031111400.png

输入: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;           //返回升序链表
    }
}

提交结果:

微信图片_20221031111406.png

⚽求关注⚽ 作者🥇 .29. 🥇 的✔博客主页✔

⚽来刷题⚽ 记录每日LeetCode✔刷题专栏✔

您的点赞,收藏以及关注是对作者最大的鼓励喔 ~~

目录
相关文章
|
27天前
|
算法 C++
【洛谷 P1223】排队接水(贪心算法+结构体排序)
该问题要求安排$n$个人的排队顺序以最小化平均等待时间。每个人接水需时$T_i$,解决方案是让接水时间短的人优先。给定$n\leq1000$和$t_i\leq10^6$,代码示例使用C++实现,通过排序使时间从小到大排列,然后计算平均等待时间。样例输入为10个人的时间数组,输出为优化后的排队顺序及平均等待时间(291.90)。
18 0
|
5天前
|
存储 算法 搜索推荐
算法进阶之路:Python 归并排序深度剖析,让数据排序变得艺术起来!
【7月更文挑战第12天】归并排序是高效稳定的排序算法,采用分治策略。Python 实现包括递归地分割数组及合并已排序部分。示例代码展示了如何将 `[12, 11, 13, 5, 6]` 分割并归并成有序数组 `[5, 6, 11, 12, 13]`。虽然 $O(n log n)$ 时间复杂度优秀,但需额外空间,适合大规模数据排序。对于小规模数据,可考虑其他算法。**
25 4
|
19天前
力扣随机一题 哈希表 排序 数组
力扣随机一题 哈希表 排序 数组
10 1
|
19天前
|
存储 算法 搜索推荐
力扣每日一题 6/13 反悔贪心算法
力扣每日一题 6/13 反悔贪心算法
12 1
|
1月前
|
搜索推荐 算法
【排序】数据结构——排序算法概念及代码详解(插入、冒泡、快速、希尔)
【排序】数据结构——排序算法概念及代码详解(插入、冒泡、快速、希尔)
|
1月前
|
存储 算法 调度
力扣中级算法(Python)
力扣中级算法(Python)
|
1月前
|
算法 Python
力扣初级算法(Python)(二)
力扣初级算法(Python)(二)
|
1月前
|
算法 Python
力扣初级算法(Python)(一)
力扣初级算法(Python)(一)
|
1月前
|
算法
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
|
19天前
|
存储
力扣每日一题 6/19 排序+动态规划
力扣每日一题 6/19 排序+动态规划
9 0

热门文章

最新文章