分割链表
题目描述：
示例:
分析：
这题的话也很简单，它要求将小于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。
记得关注、咱们下次再见！
本文同步分享在 博客“Big sai”（CSDN）。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。