笔试题：

1.判断字符串或者数字是否有相同的部分：

求一个整型数字中有没有相同的部分，例如12386123这个整型数字中相同的部分是123，相同的部分至少应该是2位数，如果有相同部分返回1，如果没有则返回0。

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Test {
    public static void main(String[] args) {
        /**
         * 2.求一个整型数字中有没有相同的部分，例如12386123这个整型数字中相同的部分是123，
         * 相同的部分至少应该是2位数，如果有相同部分返回1，如果没有则返回0。
         * 方法是先将整型数字转换到数组中，再判断。
         * 函数为  int same（int num）其中num是输入的整型数字
         */        
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入一个整数:");
        int num = sc.nextInt();
        int same = same(num);
        System.out.println("是否有相同部分的结果为:"+same);
    }
    public static int same(int num){
        String str = num+"" ;
        List<Character> list = new ArrayList<Character>();
        for (int i = 0; i < str.length(); i++) {
            list.add(str.charAt(i));            
        }
        for (int i = 0; i < list.size()-1; i++) {
            char num1 = list.get(i);
            char num2 = list.get(i+1);        
            String str2 = ""+num1+num2;
            if(str.length()>2){
                str=str.substring(i+1,str.length());
            }
            if(str.contains(str2)){
                return 1;
            }
        }
        return 0;
    }
}

2.二叉树前序遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
 //递归

//class Solution {
  //  List<Integer> list = new ArrayList<>();
    //public List<Integer> preorderTraversal(TreeNode root) {
    //if(root == null) return list;
    //list.add(root.val);
    //preorderTraversal(root.left);
    //preorderTraversal(root.right);
    //return list;
    //}
//}
//递归
class Solution {
   // List<Integer> list = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
     List<Integer> list = new ArrayList<>();
     Stack<TreeNode> stack = new Stack<TreeNode>();
     if(root == null) return list;
     stack.push(root);
     while(!stack.isEmpty()){
         TreeNode node = stack.pop();
         list.add(node.val);
         if(node.right != null){
         stack.push(node.right);
         }
         if(node.left != null){
         stack.push(node.left);
         }
     }
     return list;
    }
}

3.链表反转

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
    //迭代循环
    ListNode pre=null;//前一个节点
    ListNode cur=head;//当前节点
    while(cur!=null){
     ListNode temp = cur.next;//当前节点下一个节点
     cur.next = pre; //当前节点的next换为前一个节点
     pre = cur;//向前移动一个节点
     cur = temp;
    }  
    return pre;
    }
}
//递归
// class Solution{
//     public ListNode reverseList(ListNode head){
//     //递归终止条件:如果head是空直接返回链表为空，如果head.next为空，则返回最后链表到了最后
//     if(head==null||head.next==null){
//         return head;
//     }
//     //下探到下一层
//     ListNode last = reverseList(head.next);
//     head.next.next =head;
//     head.next =null;
//     return last;
//     }
// }

链表反转2：
将给定的单链表\ L L： L0→L_1→…→L{n-1}→L n_L_0→_L_1→…→_L__n−1→L__n
重新排序为：L0→L_n →L_1→L{n-1}→L2→L{n-2}→…L_0→_L__n→L_1→_L__n−1→L_2→_L__n−2→…
要求使用原地算法，不能改变节点内部的值，需要对实际的节点进行交换。
例如：
对于给定的单链表{1,2,3,4}，将其重新排序为{1,4,2,3}.

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public void reorderList(ListNode head) {
      //思路：后半反转然后插入到前半链表
        if(head==null||head.next==null||head.next.next==null) return;
        ListNode fast = head;
        ListNode slow = head;
        while(fast!=null && fast.next!=null){
            slow = slow.next;
            fast =fast.next.next;
        }
        ListNode tailList = slow.next;
        ListNode headList =  head;
        slow.next =null;


        tailList = reverse(tailList);
        insert(headList,tailList);
    }
    private ListNode reverse(ListNode head){
        ListNode pre =null;
        ListNode cur =head;
        while(cur !=null){
            ListNode temp = cur.next;
            cur.next =pre;
            pre =cur;
            cur =temp;
        }
        return pre;
    }
    private void insert(ListNode listA,ListNode listB){
        ListNode nodeA =listA;
        ListNode nodeB =listB;
       while(nodeB!=null){
          ListNode listTempA = nodeA.next;
          ListNode listTempB = nodeB.next;
           nodeA.next =nodeB;
           nodeB.next = listTempA;
           nodeA = listTempA;
           nodeB = listTempB;

       } 
    }
}

3.对于一个给定的链表，返回环的入口节点，如果没有环，返回null

利用快慢指针方法判断链表是否存在环，并记录两指针相遇位置。

题目描述：对于一个给定的链表，返回环的入口节点，如果没有环，返回null

快慢指针方法:**将两指针分别放在链表头（X）和相遇位置（Z），并改为相同速度推进，则两指针在环开始位置相遇（Y），如图所示。

证明过程：X，Y，Z分别为链表起始位置，环开始位置和两指针相遇位置，由快指针速度的慢指针速度的2倍。

快指针与慢指针均从X出发，在Z相遇。此时，慢指针行使距离为a+b，快指针为a+b+n(b+c）。
所以2(a+b)=a+b+n(b+c),推出
a=(n-1)b+nc=(n-1)(b+c)+c;
得到，将此时两指针分别放在起始位置和相遇位置，并以相同速度前进，当一个指针走完距离a时，另一个指针恰好走出 绕环n-1圈加上c的距离。

public class Solution{
    public ListNode detectCycle(ListNode head){
        if(head==null) return null;
        ListNode slow=head;
        ListNode fast=head;

        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;

            if(slow == fast){                 //利用快慢指针找相遇点
                ListNode slow2=head;    //设置以相同速度的新指针从起始位置出发
                while(slow!=slow2){      //未相遇循环。
                    slow=slow.next;
                    slow2=slow2.next;
                }
                return slow;
            }
        }
        return null;
    }

}

4.判断给定的链表中是否有环
扩展：
你能给出空间复杂度的解法么？

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        boolean flag = false;
        while(fast!=null && fast.next!=null){
            fast = fast.next.next;
            slow =slow.next;
            if(fast==slow){
                flag = true;
                break;
            }
        }
        return flag;
    }
}

5.给定一个仅包含数字\ 0-9 0−9 的二叉树，每一条从根节点到叶子节点的路径都可以用一个数字表示。
例如根节点到叶子节点的一条路径是1\to 2\to 31→2→3,那么这条路径就用\ 123 123 来代替。
找出根节点到叶子节点的所有路径表示的数字之和
例如：

这颗二叉树一共有两条路径，
根节点到叶子节点的路径 1\to 21→2 用数字\ 12 12 代替
根节点到叶子节点的路径 1\to 31→3 用数字\ 13 13 代替
所以答案为\ 12+13=25 12+13=25

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */

     public int sumNumbers(TreeNode root) {
       if (root == null) return 0; 
       return preOrderSum(root,0);
    }

    private int preOrderSum(TreeNode root,int sum) {
        if (root == null) return 0;
        sum = 10*sum +root.val;
        if(root.left==null&&root.right==null)  return sum;
        int left = preOrderSum(root.left,sum);
        int right = preOrderSum(root.right,sum);
        return left + right;
    }


}

6.判断是否是平衡树

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return bool布尔型
     */

    public boolean isBalanced (TreeNode root) {
        // write code here
        return depth(root)!=-1;

    }
    private int depth(TreeNode node){
        if(node==null) return 0;
         int left = depth(node.left);
         if(left==-1) return -1;
         int right = depth(node.right);
         if(right==-1) return -1;
        if(Math.abs(left-right)>=2) return -1;
        else{
            return Math.max(left,right)+1;
        }

    }
}

7.给定一个二叉树和一个值\ sum sum，请找出所有的根节点到叶子节点的节点值之和等于\ sum sum 的路径，
例如：
给出如下的二叉树，\ sum=22 sum=22，

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> path = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> pathSum (TreeNode root, int sum) {
        // write code here
        ArrayList<Integer> temp = new  ArrayList<Integer>();
        helper(root,sum,temp);
        return path;
    }
   private void helper(TreeNode node,int sum,ArrayList<Integer>temp){
       if(node ==null) return ;
       temp.add(node.val);
       if(node.left==null && node.right==null && sum == node.val){
           path.add(new ArrayList(temp));
       }
       helper(node.left,sum-node.val,temp);
       helper(node.right,sum-node.val,temp);
       temp.remove(temp.size()-1);
   }

}

8.给定一个二叉树和一个值\ sum sum，判断是否有从根节点到叶子节点的节点值之和等于\ sum sum 的路径，
例如：
给出如下的二叉树，\ sum=22 sum=22，

返回true，因为存在一条路径 5\to 4\to 11\to 25→4→11→2的节点值之和为 22.

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return bool布尔型
     */
    public boolean hasPathSum (TreeNode root, int sum) {
        // write code here
        if(root==null) return false;
        if(root.left == null&& root.right ==null ) return  sum == root.val;
        return hasPathSum(root.left,sum-root.val)||hasPathSum(root.right,sum-root.val);
    }
}

9.将一个有序数组转化为平衡二叉树

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param num int整型一维数组 
     * @return TreeNode类
     */
    public TreeNode sortedArrayToBST (int[] num) {
        // write code here
        if(num.length<1) return null;
        return put(num,0,num.length-1);


    }
    private TreeNode put(int []num,int start,int end){
        if(end<start) return null;
        int mid = start +(end-start+1)/2;
        //int mid =start =(end-start)/2;
        TreeNode root = new TreeNode(num[mid]);
        root.left = put(num,start,mid-1);
        root.right =put(num,mid+1,end);
        return root;
    }
}

10.重构二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.*;
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        List<Integer> preList = new ArrayList<>();
        List<Integer> inList = new ArrayList<>();
        for(int i=0;i<in.length;i++){
            preList.add(pre[i]);
            inList.add(in[i]);
        }
        return build(preList,inList);
    }
       private TreeNode build(List<Integer> preList,List<Integer> inList){
           if(inList.isEmpty()) return null;
           int val = preList.remove(0);
           TreeNode root = new TreeNode(val);
           int index = inList.indexOf(val);
           root.left = build(preList,inList.subList(0,index));
           root.right =build(preList,inList.subList(index+1,inList.size()));
           return root;
       } 
    }

11.二叉树的最大高度

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int maxDepth (TreeNode root) {
        // write code here
        if(root ==null) return 0;
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return Math.max(left,right)+1;
    }
}

12.层序遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
      List<List<Integer>> res = new ArrayList<>();
      LinkedList<TreeNode> queue = new LinkedList<>();
      queue.offer(root);
      while(!queue.isEmpty()){
          int size = queue.size();
           List<Integer> level = new ArrayList<>();
           for(int i=0;i<size;i++){
              TreeNode cur = queue.poll();
              if(cur==null) continue;
             level.add(cur.val);
             queue.offer(cur.left);
             queue.offer(cur.right);
           }
           if(!level.isEmpty())res.add(level);
      }
      return res;
    }
}

1. 返回链表第k节点后的链表 Leetcode 855 双指针

   /**
   * Definition for singly-linked list.
   * public class ListNode {
   *     int val;
   *     ListNode next;
   *     ListNode(int x) { val = x; }
   * }
   */
   // class Solution {
   //     public ListNode getKthFromEnd(ListNode head, int k) {
   //      ListNode node1 = head;
   //      ListNode node2 = head;
   //      int count =1;
   //      while(node1.next!=null){
   //          node1 = node1.next;
   //          count++; 
   //      }
   //      if(k<=0||k>count) return null;
   //      int index =1;
   //      while(index<count-k+1){
   //          node2 = node2.next;
   //          index++;
   //      }
   //      return node2;
   //     }
   // }
   class Solution{
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode node1 = head;
        ListNode node2 = head;
        //让第一个指针先向前走k步
        while(k>0){
            node1 = node1.next;
            k--;
        }
        //然后两个指针同时走
        while(node1 !=null){
            node1 =node1.next;
            node2 = node2.next;
        }
        return node2;
    }
   }
   

2. 删除表的节点：

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

注意：此题对比原题有改动
示例 1:
输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
示例 2:
输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
说明：

题目保证链表中节点的值互不相同

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteNode(ListNode head, int val) {
    ListNode node =  head;
    ListNode pre  =null;
    if(head.val == val){
        return head.next;
    }
    while(node.val!= val && node !=null){
        pre =node;
        node = node.next;
    }
    if(node!=null){
        pre.next = node.next;
    }
    return head;
    }
}

//递归
public ListNode deleteNode(ListNode head, int val) {
    if (head == null)
        return head;
    if (head.val == val)
        return head.next;
    head.next = deleteNode(head.next, val);
    return head;
}

15 .删除链表倒数第k个点 ：先计算链表长，然后删除：双指针

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
         ListNode node1 = head;
        ListNode node2 = head;
        int count =1;
        while(node1.next!=null){
            node1 = node1.next;
            count++;
        }
       if(count-n+1==1){
            return head.next;
          }else{
           int index =1;
           ListNode pre = null;
           while(index<count-n+1){
               pre = node2;
               node2 =node2.next;
               index++;
           }
           pre.next = node2.next;
           return head;
       }
    }
}

16.链表求和：给定两个用链表表示的整数，每个节点包含一个数位。这些数位是反向存放的，也就是个位排在链表首部。编写函数对这两个整数求和，并用链表形式返回结果。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
       ListNode node1 = l1;
       ListNode node2 = l2;
       ListNode pre =null;
       int upFlag = 0;
       while(node1!=null || node2!=null){
           if(node1!=null && node2 !=null){
          int val = node1.val + node2.val+upFlag;
          upFlag =0;
           if(val>=10) {
               node1.val = val -10;
               upFlag = 1;
               }else{
                   node1.val = val;
               }
                pre = node1;
                node1 = node1.next;
                node2 = node2.next;
               }else if(node1==null && node2!=null){
                   int val = node2.val+upFlag;
                   upFlag = 0;
                   if(val>=10){
                       ListNode temp = new ListNode(val-10);
                       upFlag = 1;
                       pre.next = temp;
                       pre =temp;
                   }else{
                   ListNode temp = new ListNode(val);
                   pre.next = temp;
                   pre =temp;
                   }
                   node2 = node2.next;
               }else if(node1 !=null && node2 ==null){
                   int val = node1.val+upFlag;
                   upFlag =0;
                   if(val>=10){
                       node1.val = val-10;
                       upFlag =1;
                   }else{
                       node1.val =val;
                   }
                   pre =node1;
                   node1 =node1.next;
                    }


       }
       if(upFlag==1) {
           ListNode upNode = new ListNode(1);
           pre.next = upNode;
       }

     return l1;
    }
}

17.链表正向放

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
       //将两个链表进行翻转
       // ListNode node1 = head1;
      //  ListNode pre1 = null;
        //while(node1!=null){
          //  ListNode temp = node1.next;
            //node1.next = pre1;
            //pre1 = node1;
            //node1 = temp;
        //}
       ListNode node1 = reverse(head1);
       ListNode node2 = reverse(head2);

       ListNode res = addTwoNumbers(node1,node2);
       return reverse(res);
       // return res;


}
    public ListNode reverse(ListNode head){
         //迭代循环
    ListNode pre=null;//前一个节点
    ListNode cur=head;//当前节点
    while(cur!=null){
     ListNode temp = cur.next;//当前节点下一个节点
     cur.next = pre; //当前节点的next换为前一个节点
     pre = cur;//向前移动一个节点
     cur = temp;
    }  
    return pre;
    }
     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
       ListNode node1 = l1;
       ListNode node2 = l2;
       ListNode pre =null;
       int upFlag = 0;
       while(node1!=null || node2!=null){
           if(node1!=null && node2 !=null){
          int val = node1.val + node2.val+upFlag;
          upFlag =0;
           if(val>=10) {
               node1.val = val -10;
               upFlag = 1;
               }else{
                   node1.val = val;
               }
                pre = node1;
                node1 = node1.next;
                node2 = node2.next;
               }else if(node1==null && node2!=null){
                   int val = node2.val+upFlag;
                   upFlag = 0;
                   if(val>=10){
                       ListNode temp = new ListNode(val-10);
                       upFlag = 1;
                       pre.next = temp;
                       pre =temp;
                   }else{
                   ListNode temp = new ListNode(val);
                   pre.next = temp;
                   pre =temp;
                   }
                   node2 = node2.next;
               }else if(node1 !=null && node2 ==null){
                   int val = node1.val+upFlag;
                   upFlag =0;
                   if(val>=10){
                       node1.val = val-10;
                       upFlag =1;
                   }else{
                       node1.val =val;
                   }
                   pre =node1;
                   node1 =node1.next;
                    }


       }
       if(upFlag==1) {
           ListNode upNode = new ListNode(1);
           pre.next = upNode;
       }

     return l1;
    }
}

18.二叉树中序遍历

class Solution {
    public List<Integer> list = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
     dfs(root);
     return list;

    }
    public void dfs(TreeNode root){
        if(root==null) return ;
        if(root.left!=null) dfs(root.left);
        list.add(root.val);
        if(root.right!=null) dfs(root.right);

    }
}

19.对称二叉树

//递归
public boolean isSymmetric(TreeNode root) {
    if (root == null)
        return true;
    //从两个子节点开始判断
    return isSymmetricHelper(root.left, root.right);
}

public boolean isSymmetricHelper(TreeNode left, TreeNode right) {
    //如果左右子节点都为空，说明当前节点是叶子节点，返回true
    if (left == null && right == null)
        return true;
    //如果当前节点只有一个子节点或者有两个子节点，但两个子节点的值不相同，直接返回false
    if (left == null || right == null || left.val != right.val)
        return false;
    //然后左子节点的左子节点和右子节点的右子节点比较，左子节点的右子节点和右子节点的左子节点比较
    return isSymmetricHelper(left.left, right.right) && isSymmetricHelper(left.right, right.left);
}

//迭代
public boolean isSymmetric(TreeNode root) {
    //队列
    Queue<TreeNode> queue = new LinkedList<>();
    if (root == null)
        return true;
    //左子节点和右子节点同时入队
    queue.add(root.left);
    queue.add(root.right);
    //如果队列不为空就继续循环
    while (!queue.isEmpty()) {
        //每两个出队
        TreeNode left = queue.poll(), right = queue.poll();
        //如果都为空继续循环
        if (left == null && right == null)
            continue;
        //如果一个为空一个不为空，说明不是对称的，直接返回false
        if (left == null ^ right == null)
            return false;
        //如果这两个值不相同，也不是对称的，直接返回false
        if (left.val != right.val)
            return false;
        //这里要记住入队的顺序，他会每两个两个的出队。
        //左子节点的左子节点和右子节点的右子节点同时
        //入队，因为他俩会同时比较。
        //左子节点的右子节点和右子节点的左子节点同时入队，
        //因为他俩会同时比较
        queue.add(left.left);
        queue.add(right.right);
        queue.add(left.right);
        queue.add(right.left);
    }
    return true;
}

20.最长回文子串 返回子串

class Solution {
    //动态规划
    public String longestPalindrome(String s) {
     // [i,j] 判断 dp[i][j] = dp[i+1][j-1] && s[i]==s[j];
     int maxLen =1;
     int len = s.length();
     int begin =0;
     if(len<2) return s;
     boolean dp[][] =  new boolean[len][len];
     for(int i=0;i<len;i++){
         dp[i][i] = true;
     }
     for(int j =1;j<len;j++){
         for(int i=0;i<j;i++){
             if(s.charAt(i)!=s.charAt(j)) dp[i][j] = false;
             else{
                 if(j-i<3) dp[i][j] = true;
                 else dp[i][j] = dp[i+1][j-1];
             }
          if(dp[i][j] && j-i+1>maxLen){
              maxLen = j-i+1;
              begin =i;
          }
         }

     }
     return s.substring(begin,begin+maxLen);
    }

}

21.最长回文子串 ，返回长度

import java.util.*;

public class Palindrome {
    public int getLongestPalindrome(String A, int n) {
        // write code here
        if(n<2) return n;
        boolean dp[][] = new boolean[n][n];
        int maxLen =1;
        for(int i =0;i<n;i++){
            dp[i][i] = true;
        }
        for(int j=1;j<n;j++){
            for(int i=0;i<j;i++){
                if(A.charAt(i)== A.charAt(j)){
                    if(j-i<3) dp[i][j] = true;
                    else{
                        dp[i][j] = dp[i+1][j-1];

                    }
                    if(dp[i][j] && j-i+1>maxLen){
                        maxLen = j-i+1;
                    }
                }
            }
        }
        return maxLen;

    }
}

1. 最大子数组和 ```java import java.util.*;

public class Solution { /**

 * max sum of the subarray
 * @param arr int整型一维数组 the array
 * @return int整型
 */
public int maxsumofSubarray (int[] arr) {

    // write code here
    int len =  arr.length;
    if(len==0) return 0;
    if(len==1) return arr[0];
    int dp1 =arr[0];
    int dp2 =0;
    int max = arr[0];
    for(int i=1;i<len;i++){
         if(dp1>0) {
             dp2 = dp1+arr[i];    
         }else{
             dp2= arr[i];
         }
        dp1 =dp2;
        if(dp1>max)
            max =dp1;

    }
    return max;
}

}

23.矩阵旋转90度<br />24.合并有序数组：从数组后面向前插
```java
public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        //从数组后面往前插
        int l = m+n-1;
        int i =m-1;
        int j = n-1;
        while(j>=0){
            if(i<0)A[l--] = B[j--];
            else{
                A[l--] = (A[i]<B[j]) ? B[j--] :A[i--];  
            }
        }

    }
}

25.分隔链表

/**
 * 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 before_head = new ListNode(0);
     ListNode after_head = new ListNode(0);
     ListNode before  =before_head;
     ListNode after =  after_head;
     while(head!=null){
         if(head.val<x) {
             before.next = head;
             before = before.next;

         }else{
             after.next = head;
             after =after.next;

         }
         head =head.next;
     }
     //不加这条内部会出现环
     after.next =null;
     before.next = after_head.next;
     return before_head.next;
    }
}

26. 删除排序链表中的重复元素 II

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
示例 1:
输入: 1->2->3->3->4->4->5
输出: 1->2->5

示例 2:
输入: 1->1->1->2->3
输出: 2->3

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
      if(head ==null||head.next==null) return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode a =  dummy;
        ListNode b = head;
     while(b!=null && b.next !=null){
            if(a.next.val!=b.next.val){
                a= a.next;
                b= b.next;
            }else{
                while(b!=null && b.next !=null && b.val ==b.next.val){
                    b = b.next;
                }
                a.next = b.next;
                b = b.next;
                 }
        }
        return dummy.next;
    }
}