11.17打卡-526互联

1. 分割链表（86）

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。你应当保留两个分区中每个节点的初始相对位置

思想：双链表存储

/**
 * 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 partition(ListNode head, int x) {
ListNode small  = new ListNode(0);
        ListNode large = new ListNode(0);
        ListNode smallhead=small;
        ListNode largehead =large;
       while (head!=null){
           if(head.val<x){
               small.next = head;
               small=small.next;
           }else {
               large.next=head;
               large=large.next;
           }
           head=head.next;
       }
       large.next=null;
       small.next=largehead.next;
       return smallhead.next;
    }
}

2. 扰乱字符串（87）

使用下面描述的算法可以扰乱字符串 s 得到字符串 t ：

如果字符串的长度为 1 ，算法停止
如果字符串的长度 > 1 ，执行下述步骤：
- 在一个随机下标处将字符串分割成两个非空的子字符串。即，如果已知字符串 s ，则可以将其分成两个子字符串 x 和 y ，且满足 s = x + y 。
- 随机决定是要「交换两个子字符串」还是要「保持这两个子字符串的顺序不变」。即，在执行这一步骤之后，s 可能是 s = x + y 或者 s = y + x 。
- 在 x 和 y 这两个子字符串上继续从步骤 1 开始递归执行此算法。

给你两个长度相等的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串。如果是，返回 true ；否则，返回 false 。

思想：递归调用 isScramble检查 s1s1s1 的 [0,i) & [i,n) 部分能否与 s2的 [0,i)& [i,n)[」或者 s2 的 [0,n−i) & [n−i,n) 匹配即可。

class Solution {
    public boolean isScramble(String s1, String s2) {
 if(s1.equals(s2))return true;
        if(s1.length()!=s2.length()) return false;
        int n = s1.length();
        char[] cs1 = s1.toCharArray();
        char[] cs2 = s2.toCharArray();
        boolean[][][] f= new boolean[n][n][n+1];

        //长度为1
        for (int i = 0; i <n ; i++) {
            for (int j = 0; j <n ; j++) {
                f[i][j][1]=cs1[i]==cs2[j];
            }
        }

        for (int len = 2; len <=n ; len++) {
            for (int i = 0; i <= n-len; i++) {
                for (int j = 0; j <=n-len ; j++) {
                    for (int k = 1; k <len ; k++) {
                        boolean a = f[i][j][k]&&f[i+k][j+k][len-k];
                        boolean b = f[i][j+len-k][k]&&f[i+k][j][len-k];
                        if(a||b){
                            f[i][j][len]=true;
                        }
                    }
                }
            }
        }
        return f[0][0][n];
    }
}

3. 合并两个有序数组（88）

给你两个按非递减顺序排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你合并 nums2 到 nums1 中，使合并后的数组同样按非递减顺序排列。

思想：逆向双指针

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) { 
          int p1=m-1,p2=n-1;
        int tail = m+n-1;
        int cur;
        while (p1>=0 ||p2>=0){
            if(p1==-1){
               cur = nums2[p2--]; 
            }else if(p2==-1){
                cur = nums1[p1--];
            }else if(nums2[p2]<nums1[p1]){
                cur=nums1[p1--];
            }else {
                cur = nums2[p2--];
            }
            nums1[tail--]=cur;
        }
    }
}