分割链表
题目描述：
给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
示例:
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5
分析：
这题的话也很简单，它要求将小于x的节点放到前面，且相对位置不变。我们可以采用两个链表将其分割开来然后再合并，在具体的处理上，可以创建两个带头节点的链表，遍历这个链表，其中一个收集比x小的节点，另一个收集比x大的节点，最后组合一下即可。
实现代码为：
/** * 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。
扰乱字符串
分析：
题意很清晰，就问你s1能不能转换成s2。本题可以采用递归和动态规划的方式，两者一个是从前往后，一个是从后往前进行递推。
判断是否能够经过递归交换转换而来，首先两个字符串s1和s2需要等长，然后其中的元素种类和个数也需要完全相同才行。(具体实现上可以借助hashmap或者数组进行计数统计)。
相同之后可能有很多种划分需要一一的进行比较，可以递归向下进行(要有递归信任)，分的两个组合情况有一个可以交换即可认为是true的。
具体实现代码上，我使用递归的方式，通过字符串转成字符数组优化一点速度。
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; } }
至于动态规划的解题方法，是一个从下往上的递推过程，实现上需要考虑下边界初始化和递推式，这里就不实现啦，有兴趣的可以参考官网。
结语
原创不易，bigsai请你帮两件事帮忙一下:
- star支持一下， 您的肯定是我在平台创作的源源动力。
- 微信搜索「bigsai」，关注我的公众号，不仅免费送你电子书，我还会第一时间在公众号分享知识技术。加我还可拉你进力扣打卡群一起打卡LeetCode。
记得关注、咱们下次再见！
