LeetCode 86分割链表&87扰乱字符串

快来打我* 2022-12-29 00:13 170阅读 0赞

> **微信搜一搜**：`bigsai` 专注于Java、数据结构与算法，**一起进大厂不迷路！**  
> **算法文章题解全部收录在github仓库[bigsai-algorithm][],求star！**  
> 关注回复**进群**即可加入力扣打卡群，欢迎划水。近期打卡：  
> [LeetCode 73矩阵置零&74搜素二维矩阵&75颜色分类][LeetCode 73_74_75]  
> [Leetcode 76最小覆盖子串&77组合&78子集][Leetcode 76_77_78]  
> [LeetCode 79单词搜索&80删除排序数组中的重复项Ⅱ&81.搜索旋转排序数组Ⅱ][LeetCode 79_80_81.]  
> 如有帮助，记得**一键三连**！

## 分割链表 ##

题目描述：

> 给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

> 你应当保留两个分区中每个节点的初始相对位置。

示例:

> 输入: head = 1->4->3->2->5->2, x = 3  
> 输出: 1->2->2->4->3->5

分析：  
这题的话也很简单，它要求将小于x的节点放到前面，且相对位置不变。我们可以采用两个链表将其分割开来然后再合并，在具体的处理上，可以创建**两个带头节点**的链表，遍历这个链表，其中一个收集比x小的节点，另一个收集比x大的节点，最后组合一下即可。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70]

实现代码为：

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public ListNode partition(ListNode head, int x) {
        
            ListNode smallhead=new ListNode(0);//头节点 0不使用
        	ListNode smallteam=smallhead;//进行遍历
        	ListNode bighead=new ListNode(0);//头
        	ListNode bigteam=bighead;//遍历使用
        	while (head!=null) {
        
    			if(head.val<x)
    			{
        
    				smallteam.next=head;
    				smallteam=smallteam.next;
    			}
    			else {
        
    				bigteam.next=head;
    				bigteam=bigteam.next;
    			}
    			head=head.next;
    		}
        	smallteam.next=bighead.next;//拼接
            bigteam.next=null;//置空
        	return smallhead.next;
        }
    }

时间的话都是0ms。

## 扰乱字符串 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70 1]

**分析：**  
题意很清晰，就问你s1能不能转换成s2。本题可以采用递归和动态规划的方式，两者一个是从前往后，一个是从后往前进行递推。

判断是否能够经过递归交换转换而来，首先两个字符串s1和s2需要等长，然后其中的元素种类和个数也需要完全相同才行。(具体实现上可以借助hashmap或者数组进行计数统计)。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70 2]

相同之后可能有很多种划分需要一一的进行比较，可以递归向下进行(要有递归信任)，分的两个组合情况有一个可以交换即可认为是true的。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70 3]  
具体实现代码上，我使用递归的方式，通过字符串转成字符数组优化一点速度。

class Solution {
        
        public boolean isScramble(String s1, String s2) {
        
            if(s1.equals(s2))return true;
    		 if(s1.length()!=s2.length())return false;
    		 char ch1[]=s1.toCharArray();
    		 char ch2[]=s2.toCharArray();
    		 int count[]=new int[26];
    		
    		 for(int i=0;i<ch2.length;i++)
    		 {
        
    			 count[ch1[i]-'a']++;
    			 count[ch2[i]-'a']--;
    		 }
    		 for(int  i=0;i<26;i++)
    		 {
        
    			 if(count[i]!=0)//计数看看单词是否等
    			 {
        
    				 return false;
    			 }
    		 }
    		 for(int i=1;i<ch1.length;i++)//进行划分，递归的匹配
    		 {
        
    		      if(isScramble(s1.substring(0,i), s2.substring(0, i))&&isScramble(s1.substring(i), s2.substring(i)))
    		      {
        
    		    	  return true;
    		      }
    		      if(isScramble(s1.substring(0,i), s2.substring(s2.length()-i))&&isScramble(s1.substring(i), s2.substring(0,s2.length()-i)))
    		      {
        
    		    	  return true;
    		      }
    		 }
    		 return false;		 
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70 4]

至于动态规划的解题方法，是一个从下往上的递推过程，实现上需要考虑下边界初始化和递推式，这里就不实现啦，有兴趣的可以参考官网。

## 结语 ##

原创不易，bigsai请你帮两件事帮忙一下:

1.  star支持一下， 您的肯定是我在平台创作的源源动力。
2.  微信搜索「**bigsai**」，关注我的公众号，不仅免费送你电子书，我还会第一时间在公众号分享知识技术。加我还可拉你进力扣打卡群一起打卡LeetCode。

记得关注、咱们下次再见！

![image-20201114211553660][]

[bigsai-algorithm]: https://github.com/javasmall/bigsai-algorithm
[LeetCode 73_74_75]: https://bigsai.blog.csdn.net/article/details/110312873
[Leetcode 76_77_78]: https://bigsai.blog.csdn.net/article/details/110682620
[LeetCode 79_80_81.]: https://bigsai.blog.csdn.net/article/details/110734770
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70]: /images/20221120/5655285424d44fe58a0b1b8b0a326ceb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70 1]: /images/20221120/b3f1c3137d8e4f7881a5774f62e89129.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70 2]: /images/20221120/3a01302b6a53494e9f22173781a94dc6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70 3]: /images/20221120/3f8766ce7b41433c9bfa80c244f00c91.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70 4]: /images/20221120/be7d2e9e23d0487d855719c8446e2ce2.png
[image-20201114211553660]: /images/20221120/e4ec0815ff524a2a81ea84b3f7832041.png