【牛客+力扣】高频题随机刷（5.3-5.9）

1、二叉搜索树的第k个结点

输出第k小的结点

分析：
1、中序遍历二叉搜索树是节点值的升序排列
2、利用ArrayList的随机存取

//中序遍历
public class Solution {
    ArrayList<TreeNode> res = new ArrayList<>();
    TreeNode KthNode(TreeNode pRoot, int k) {
        if(pRoot == null || k == 0){return null;}
        inOrder(pRoot);
        if(k > res.size()){return null;}
        return res.get(k-1);
    }
    private void inOrder(TreeNode pRoot){
        if(pRoot == null){return;}       
        inOrder(pRoot.left);
        res.add(pRoot);
        inOrder(pRoot.right);
    }
}

2、最大数

分析：之前做过类似的，其实就是重写比较规则，大的放前边即可。

public class Solution {
    /**
     * 最大数
     * @param nums int整型一维数组 
     * @return string字符串
     */
    //这里的比较是：假如数组元素的第一个数位>另一个元素的第一个数位，那么就判定大
    public String solve (int[] nums) {
        String[] strArr = new String[nums.length];
        for(int i = 0;i < nums.length;i++){
            //整型转字符串
            strArr[i] = String.valueOf(nums[i]);
        }
        //这里重写比较操作
        Arrays.sort(strArr,(o1,o2)->Integer.parseInt(o2+o1)-Integer.parseInt(o1+o2));
        StringBuilder maxString = new StringBuilder();
        //这里判断很重要，不然输出的字符串就是0打头
        if(strArr[0].equals("0")){
            return "0";
        }
        for(int i = 0;i < strArr.length;i++){
            maxString.append(strArr[i]);
        }
        return maxString.toString();
    }
}

3、寻找峰值

public int solve (int[] a) {
        if(a == null || a.length == 0) {
            return -1;
        }
        for(int i = a.length -1;i>=1;i--) {
            if(a[i] >= a[i-1]) {
                return i;
            }
        }
        return 0;
}

4、连续子数组的最大和

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        //只要加起来不是负数，那就往后加
        int max = 0;
        int i = 0;
        //首先找到第一个非负的元素            
        while(i < array.length && array[i] < 0){
            i++;
        }
        if(i >= array.length){return -1;}
        int num = 0;
        for(;i < array.length;i++){
            if(num+array[i] >=0){
                num+=array[i];
                max = Math.max(max,num);
                //System.out.println(max+" "+i);
            }else{
                num = 0;
                //System.out.println(max+" "+i);
            }
        }
        max = Math.max(max,num);
        return max;
    }
}

5、换钱的最小货币数

public int minMoney (int[] arr, int aim) {
        //dp[i] 换得金额i能用的最少硬币数
        int[] dp = new int[aim+1];
        //后面要比较最小值 所以每个dp的初始值都是aim+1
        Arrays.fill(dp,aim+1);
        dp[0] = 0;
        for(int i = 0;i < aim+1;i++){
            for(int j = 0;j < arr.length;j++){
                if(i - arr[j] >=0)
                    dp[i] = Math.min(dp[i],dp[i-arr[j]]+1);
            }
        }
        return dp[aim] == aim+1?-1:dp[aim];
    }

6、矩阵查找

public boolean searchMatrix (int[][] matrix, int target) {
        //从左上角出发就不用判断边界
        int m = matrix.length;
        int n = matrix[0].length;
        int i = 0,j = n-1;
        int num = 0;
        while(i < m && j >=0){
            num = matrix[i][j];
            if(num > target){
                j--;
                //if(j <0){break;}
            }else if(num < target){
                i++;
                //if(i >= m){break;}
            }else{
                return true;
            }
        }
        return false;
    }

7、股票的最大收益（无限次交易）

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算最大收益
     * @param prices int整型一维数组 股票每一天的价格
     * @return int整型
     */
    //碰到一个比它大的就抛出
    public int maxProfit (int[] prices) {
        if(prices.length <=1){return 0;}
        int max = 0;
        int cur = prices[0];
        for(int i = 1;i < prices.length;i++){
            if(prices[i] > cur){
                max+=prices[i]-cur;
                cur = prices[i];
            }else{
                //按兵不动这一步不能忘！
                cur = prices[i];
            }
        }
        return max;
    }
}

8、将数字翻译成字符串

import java.util.*;


public class Solution {
    /**
     * 解码
     * @param nums string字符串 数字串
     * @return int整型
     */
    public int solve (String nums) {
		if(nums=="") return 0;
		int n = nums.length();
		int[] dp = new int[n+1];
		dp[0] = 1;
		//dp[1]? 
		dp[1] = dp[0]=='0'?0:1;
		for(int i = 2;i < n;i++){
			int num = Integer.parseToInt(nums.sunstring(i-2,i));
			if(num >= 10 && num <=26){
				dp[i] = dp[i-2];
			}
			//判断该位
			if(nums.charAt(i-1)!='0'){
				dp[i] +=dp[i-1];
			}
		}
		return dp[n];
	}
}

9、完全二叉树结点数

import java.util.*;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }
}*/
//普通人解法
// public class Solution {
//     ArrayList<Integer> list = new ArrayList<>();
//     public int nodeNum(TreeNode head) {
//         if(head == null){return 0;}
//         //遍历一遍二叉树
//         inOrder(head);
//         return list.size();
//     }
//     private void inOrder(TreeNode root){
//         if(root == null){return;}
//         inOrder(root.left);
//         list.add(root.val);
//         inOrder(root.right);
//     }
// }
//大佬解法
public class Solution {
    public int nodeNum(TreeNode head) {
        if(head == null){return 0;}
        int cnt = 1;
        int leftH = getHigh(head.left);
        int rightH = getHigh(head.right);
        //如果左子树高度>右子树，那么右子树一定是满二叉树
        if(leftH > rightH){
            cnt += Math.pow(2,rightH)-1+nodeNum(head.left);
        }else{//左子树高度=右子树，那么左子树一定是满二叉树（不存在<的情况，因为这样就不是完全二叉树）
            cnt+=Math.pow(2,leftH)-1+nodeNum(head.right);
        }
        return cnt;
    }
    private int getHigh(TreeNode root){
        if(root == null){return 0;}
        int left = getHigh(root.left);
        int right = getHigh(root.right);
        return left > right?left+1:right+1;
    }
}

10、合并二叉树

分析：将两棵二叉树对应位置的值加起来。

import java.util.*;

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

public class Solution {
    /**
     * 
     * @param t1 TreeNode类 
     * @param t2 TreeNode类 
     * @return TreeNode类
     */
    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
		if(t1 ==null && t2 == null){return null;}
		if(t1 == null) return t2;
		if(t2 == null) return t1;
		t1.val += t2.val;
		t1.left = mergeTrees(t1.left,t2.left);
		t1.right = mergeTrees(t1.right,t2.right);
		return t1;
	}
}

11、判断两棵树的结构

分析：要么是它的子树，要么和它整棵树相同.

import java.util.*;

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

public class Solution {
    /**
     * 
     * @param root1 TreeNode类 
     * @param root2 TreeNode类 
     * @return bool布尔型
     */
     //判断是否是root1的子树
    public boolean isContains (TreeNode root1, TreeNode root2) {
       if(root1==null&&root2==null) return true;
       if(root1==null) return false;
       return recur(root1,root2)||isContains(root1.left,root2)||isContains(root1.right,root2);   
    }
    
    //判断是否是同一棵树
    public boolean recur(TreeNode A,TreeNode B){
        if(A == null && B == null){return true;}
        if(A == null || B == null){return false;}
        return recur(A.left,B.left) && recur(A.right,B.right) && A.val == B.val;
    }
}

12、判断二叉搜索树中出错的两个结点

分析：
朴素的做法是，先中序遍历，然后扫描list找出大小不符合升序的元素；
优雅的做法是，边中序遍历边纠错（需要维护一个preNode）。

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */
public class Solution {
    /**
     * 
     * @param root TreeNode类 the root
     * @return int整型一维数组
     */
    ArrayList<Integer> list = new ArrayList<>();
    public int[] findError (TreeNode root) {
		if(root == null){return new int[0];}
		//返回数组
		int[] res = new int[2];
		inOrder(root);
		//往后遍历，找到错序的大数
		for(int i = 0;i < list.size()-1;i++){
			//大于它后边的数
			if(list.get(i) > list.get(i+1)){
				res[1] = list.get(i);
				break;
			}
		}
		//从后向前遍历，找到错序的小数
		for(int j = list.size()-1;j >0;j--){
			//小于它前边的数
			if(list.get(i) < list.get(i-1)){
				res[0] = list.get(i);
				break;
			}
		}
		return res;
	}
	private void inOrder(TreeNode root){
		if(root == null){return;}
		inOrder(root.left);
		list.add(root.val);
		inOrder(root.right);
	}
}

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */
public class Solution {
    /**
     * 
     * @param root TreeNode类 the root
     * @return int整型一维数组
     */
    int[] res = new int[2];
    //维护一个指向前边数据的结点（方便比较）
    TreeNode preNode = null;
    //由于返回的值需要按照升序，因此需要先填充res[1]
    int index = 1;
    public int[] findError (TreeNode root) {
		//二话不说先判一个空，然后定义返回数组(因为要递归，所以把返回数组啥的定义在函数外边)
		if(root== null){return new int[0];}
		int[] res = new int[2];
		//中序遍历 左根右 的“左”
		findError(root.left);
		//需要将preNode赋值，因为null没有val
		if(preNode == null){
			preNode = root;
		}
		//此时，说明大数保存在了preNode
		if(index == 1 && root.val < preNode.val){
			res[index] = preNode.val;
			index = 0;
		}
		if(index == 0 && root.val < preNode.val){
			res[index] = root.val;
		}
		preNode = root;
		//中序遍历 左根右 的“右”
		findError(root.right);
		return res;
	}
}

13、最长无重复子串

分析：
每次加入元素都要判断是否在列表中已经存在，假如不存在，那么加入列表；假如存在，先将当前的长度与之前存放的最大长度比较（维护一个最大长度），然后记录下当前重复元素出现的索引，进行删除操作，删除的对象是重复元素以及其之前的所有元素。
最后在for循环结束时，需要再次更新maxLen，因为可能之后没有出现重复元素，而maxLen还没有更新。

import java.util.*;


public class Solution {
    /**
     * 
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxLength (int[] arr) {
		if(arr.length == 0){return 0;}
		int maxLen = Integer.MIN_VALUE;
		ArrayList<Integer> list = new ArrayList();
		for(int i = 0;i < arr.length;i++){
			if(list.contains(arr[i])){
				maxlen = Math.max(maxLen,list.size());
				//记录列表中重复元素出现的索引：{2,3,4,3}遇到重复元素3，记下索引1，remove之后是{4,3} 
				int j = list.indexOf(arr[i]);
				//把重复元素及之前的元素全部删除
                while(j>=0){
					list.removeFirst();
					j--;
				}
			}
			list.add(arr[i]);//加入新的3，牺牲之前的3及其前边元素
		}
		maxlen = Math.max(maxLen,list.size());
		return maxLen;
	}
}

14、首个公共祖先

分析：
1、假如两者在不同的子树，那么公共祖先就是根节点；
2、假如两者都在左子树，先找到谁谁就是
3、假如两者都在右子树，先找到谁谁就是

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
		if(root == null){return null;}
		//先找到谁谁就是
		if(root == p || root == q){return root;}
		//在左子树找
		TreeNode left = lowestCommonAncestor(root.left,p,q);
		//在右子树找
		TreeNode right = lowestCommonAncestor(root.right,p,q);
		//两者都不为空,说明两者在不同子树，直接返回根节点
		if(left != null && right !=null){
			return root;
		}
		//都在左子树
		else if(right ==null) return left;
		//都在右子树
		else return right;
	}
}

15、字符串出现次数的Top-k问题

假如两个字符串出现的次数一样，那么取字典序大的那个；否则取出现次数大的那个。
返回top-k字符串数组：[string,出现次数]

分析：
要是没有规定复杂度，那么可以用列表排序啥的；
要是规定了复杂度，那么用堆或者快排——>哈希表存放字符串和频率的映射，

import java.util.*;


public class Solution {
    /**
     * return topK string
     * @param strings string字符串一维数组 strings
     * @param k int整型 the k
     * @return string字符串二维数组
     */
    //统计出现次数用map，堆用来维护top-k
    public String[][] topKstrings (String[] strings, int k) {
		Map<String,Integer> map = new HashMap<>();
		//统计每个字符串出现的次数
		for(String s:strings){
			map.merge(s,1,Integer::sum);
		}
		//存放key
		Set<String> set = map.keyset();
		ArrayList<String> str= new ArrayList<>(set);
		//排序
		str.sort((s1,s2)->map.get(s1).equals(map.get(s2))?s1.compareTo(s2):map.get(s2)-map.get(s1));
		String[][] result = new String[k][2];
		for(int i = 0;i < k;i++){
			result[i] = new String[]{str.get(i),String.ValueOf(map.get(str.get(i)))};
		}
		return result;
	}
}

public String[][] topKstrings (String[] strings, int k) {
        //统计字符串频率
        HashMap<String,Integer> map= new HashMap<>();
        for(String s:strings){
            map.merge(s,1,Integer::sum);
        }
        //建立大小为k的小顶堆
        PriorityQueue<String> heap = new PriorityQueue<String>(
            //这里两个返回函数注意：w2和w1比字典序，w1和w2比大小
            (w1,w2)->map.get(w1).equals(map.get(w2))?w2.compareTo(w1):map.get(w1)-map.get(w2)
            //(w1, w2) -> map.get(w1).equals(map.get(w2))?w2.compareTo(w1) : map.get(w1) - map.get(w2)
        );
        
        //维护一个k个元素的heap
        for(String word:map.keySet()){
            heap.offer(word);
            if(heap.size()>k)
                heap.poll();
            //每次吐出最小的一个
        }
        String[][] res = new String[k][2];
        int j = k-1;
        while(!heap.isEmpty()){
            String tmp = heap.poll();
            //从后边开始存，因为吐出的是最小的
            res[j][0] = tmp;
            res[j][1] = String.valueOf(map.get(tmp));
            //res[j][1] = map.get(tmp)+"";
            j--;
        }
        return res;
    }

16、链表反转

public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head == null){return null;}
        ListNode pre = null;
        ListNode next = null;
        while(head!=null){
            next = head.next;
            head.next = pre;
            pre = head;
            head=next;
        }
        //此时head已经为空了，所以要返回head的前边一个结点pre
        return pre;
    }
}

17、链表内指定区间反转

反转：
1、头插法
2、分成三份，原地反转之后重新连接
3、用栈

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    //头插法
    public ListNode reverseBetween (ListNode head, int m, int n) {
        if(head == null){return null;}
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode preStart = dummy;
        ListNode start = head;
        //走到反转的第一个结点
        for(int i = 1;i < m;i++){
            preStart = start;
            start = start.next;
        }
        //反转
        for(int i = 1;i <= n-m;i++){
            ListNode tmp = start.next;
            start.next = tmp.next;
            tmp.next = preStart.next;
            preStart.next = tmp;
        }
        return dummy.next;
    }
}

public ListNode reverseBetweenOld (ListNode head, int m, int n) {
        // write code here
        if(head==null||head.next==null){
            return head;
        }
        if((n-m)<1){
            return head;
        }
        int i=1;
        ListNode tmpHead=new ListNode(0);
        tmpHead.next=head;
        head=tmpHead;
        tmpHead=head.next;
        ListNode tmpHeadPre=head;
        //初始化待翻转子列表头及头前驱节点
        while(i<m&&tmpHead!=null){
            tmpHeadPre=tmpHeadPre.next;
            tmpHead=tmpHead.next;
            i++;
        }
        //开始翻转 记录当前翻转前一个节点以便翻转后拼接
        ListNode fHeadPre=tmpHeadPre;
        //翻转链表尾节点
        ListNode fTail=tmpHead;
        //前驱节点
        ListNode pre=null;
 
        while(i<n&&tmpHead!=null){
            ListNode next=tmpHead.next;
            tmpHead.next=pre;
            pre=tmpHead;
            tmpHead=next;
            i++;
        }
        //循环后还差一次翻转
        ListNode next=null;
        if(tmpHead!=null){
             next=tmpHead.next;
             tmpHead.next=pre;
             pre=tmpHead;
             tmpHead=next;
        }
 
        //链接无需翻转后续的链表
        fTail.next=next;
        //拼接翻转链表
        fHeadPre.next=pre;
        return head.next;
    }

18、寻找第K大的数

分析：
1、小顶堆；
2、快排的partition

import java.util.*;

public class Solution {
    public int findKth(int[] a, int n, int K) {
        PriorityQueue<Integer> heap = new PriorityQueue<>(
            (n1,n2)->(n1-n2)
        );
        
        for(int i = 0;i < n;i++){
            heap.offer(a[i]);
            if(heap.size()>K){
                heap.poll();
            }
        }       
        return heap.poll();
    }
}

//将第一个元素设置为pivot好慢（在有序的情况下会退化到O(n^2)）！应该随机选择pivot
import java.util.*;

//只要左边有K-1个比它大的数，那么该数就是第K大的数
public class Solution {
    public int findKth(int[] a, int n, int K) {
        return partition(a,K,0,n-1);
        
    }
    private int partition(int[] a,int K,int left,int right){
        int pivot = left;
        int end = right;
        while(left < right){
            //淦，在同一个地方跌倒两次！！！一定要先判断右边啊！！！
            while(left < right && a[right] <= a[pivot]){
                right--;
            }
            while(left < right && a[left] >= a[pivot]){
                left++;
            }          
            swap(a,left,right);
        }
        swap(a,pivot,left);
        if(left == K-1){return a[left];}
        else if(left < K-1){
            return partition(a,K,left+1,end);
        }else{
            return partition(a,K,pivot,left-1);
        }
    }
    private void swap(int[] arr,int right,int left){
        if(left == right){return;}
        int tmp = arr[right];
        arr[right] = arr[left];
        arr[left] = tmp;
    }  
}

//随机产生pivot，应对有序导致快排时间复杂度降为n^2的情况
import java.util.Random;

public class Solution {

    private static Random random = new Random(System.currentTimeMillis());

    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        int target = len - k;
        int left = 0;
        int right = len - 1;
        while (true) {
            int index = partition(nums, left, right);
            if (index < target) {
                left = index + 1;
            } else if (index > target) {
                right = index - 1;
            } else {
                return nums[index];
            }
        }
    }

    // 在区间 [left, right] 这个区间执行 partition 操作

    private int partition(int[] nums, int left, int right) {
        // 在区间随机选择一个元素作为标定点
        if (right > left) {
            int randomIndex = left + 1 + random.nextInt(right - left);
            swap(nums, left, randomIndex);
        }

        int pivot = nums[left];
        int j = left;
        for (int i = left + 1; i <= right; i++) {
            if (nums[i] < pivot) {
                j++;
                swap(nums, j, i);
            }
        }
        swap(nums, left, j);
        return j;
    }

    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
} 


作者：liweiwei1419
链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/solution/partitionfen-er-zhi-zhi-you-xian-dui-lie-java-dai-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

19、祖父节点值为偶数的节点和

分析：
1、直接判断；
2、深度优先

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int sumEvenGrandparent(TreeNode root) {
        //祖父节点，那么至少是第三层呀
        if(root == null){return 0;}
        int res = 0;
        if(root.val % 2 == 0){
            if(root.left !=null){
                if(root.left.left!=null) res+=root.left.left.val;
                if(root.left.right!=null) res+=root.left.right.val;
            }
            if(root.right !=null){
                if(root.right.left!=null) res+=root.right.left.val;
                if(root.right.right!=null) res+=root.right.right.val;
            }
        }
        return res+sumEvenGrandparent(root.left)+sumEvenGrandparent(root.right);
    }
}

class Solution {
    //祖父节点值为偶数的节点和，深度优先搜索
    private int ans;
    public int sumEvenGrandparent(TreeNode root) {
        ans = 0;
        dfs(null, null, root);
        return ans;
    }

    //深度优先遍历树节点
    private void dfs(TreeNode grandParent, TreeNode parent, TreeNode root){
        if (root == null) return;
        dfs(parent, root, root.left);
        dfs(parent, root, root.right);
        if (grandParent != null && (grandParent.val & 1) == 0){
            ans += root.val;
        }
    }
}

20、链表两数相加

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode cur= dummy;
        int c = 0;
        while(l1 != null || l2 != null || c!=0){
            int val1 = l1 == null?0:l1.val;
            int val2 = l2 == null?0:l2.val;
            ListNode node = new ListNode((val1+val2+c)%10);
            c = (val1+val2+c)/10;
            node.next = null;
            cur.next = node;
            cur = node;
            //这个往后走的操作咋搞啊
            if(l1!=null) l1 = l1.next;
            if(l2!=null) l2 = l2.next;
        }       
        return dummy.next;
    }
}

21、无重复字符的最长子串

分析：和13题一样
用数组模拟列表

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length() <= 1){return s.length();}
        LinkedList<Character> list = new LinkedList<>();
        int max = 0;
        for(int i = 0;i < s.length();i++){
            if(!list.contains(s.charAt(i))){
                list.add(s.charAt(i));
            }else{
                max = Math.max(max,list.size());
                int index = list.indexOf(s.charAt(i));
                while(index>=0){
                    list.removeFirst();
                    index--;
                }
                list.add(s.charAt(i));
            }
        }
        return Math.max(max,list.size());
    }
}

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 记录字符上一次出现的位置
        int[] last = new int[128];
        for(int i = 0; i < 128; i++) {
            last[i] = -1;
        }
        int n = s.length();

        int res = 0;
        int start = 0; // 窗口开始位置
        for(int i = 0; i < n; i++) {
            int index = s.charAt(i);
            start = Math.max(start, last[index] + 1);
            res   = Math.max(res, i - start + 1);
            last[index] = i;
        }

        return res;
    }
}

22、删除链表的倒数第 N 个结点

/**
 * 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 removeNthFromEnd(ListNode head, int n) {
        if(head == null || head.next == null){return null;}
        if(n == 0){return head;}
        ListNode fast = head;
        ListNode slow = head;
        while(n > 0){
            fast = fast.next;
            n--;
        }
        if(fast == null){
            return slow.next;
        }
        //将条件设置为这个，可以让slow停在被删节点的前驱
        while(fast.next!=null){
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return head;
    }
}

23、最长回文子串

24、在排序数组中查找元素的第一个和最后一个位置

分析：
普通人：顺序查找
非普通人：二分查找

class Solution {
    public int[] searchRange(int[] nums, int target) {
        if(nums.length == 0){return new int[]{-1,-1};}
        int firstIndex = 0;
        int lastIndex = 0;
        int i = 0;
        for(i = 0;i < nums.length;i++){
            if(target == nums[i]){
                firstIndex = i;
                break;
            }
        }
        if(i >= nums.length){return new int[]{-1,-1};}
        for(int j = nums.length-1;j >=firstIndex;j--){
            if(target == nums[j]){
                lastIndex = j;
                break;
            }
        }
        return new int[]{firstIndex,lastIndex};
    }
}

class Solution {
    public int[] searchRange(int[] nums, int target) {
    	int res[] = new int[]{-1,-1};
		if(nums.length == 0){return res;}
		res[0] = binarySearch(nums,target,0,nums.length-1,true);
		res[1] = binarySearch(nums,target,0,nums.length-1,false);
		return res;	
	}
	private int binarySearch(int[] nums,int target,int left,int right,boolean leftOrRight){
		int res = -1;
		while(left <= right){
			mid = (left+right) >>> 1;
			if(nums[mid] < target){
				left = mid+1;
			}else if(nums[mid] > target){
				right = mid-1;
			}else{
				res = mid;
				if(leftOrRight)
					right = mid-1;
				else
					left = mid+1;
			}
		}
		return res;
	}
}

25、三数之和

分析：
首先确定一个数，另外两个就根据两数之和来找
答案不能包含重复的三元组——>先排序去重

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {// 总时间复杂度：O(n^2)
        List<List<Integer>> ans = new ArrayList<>();
        if (nums == null || nums.length <= 2) return ans;

        Arrays.sort(nums); // O(nlogn)

        for (int i = 0; i < nums.length - 2; i++) { // O(n^2)
            if (nums[i] > 0) break; // 第一个数大于 0，后面的数都比它大，肯定不成立了
            if (i > 0 && nums[i] == nums[i - 1]) continue; // 去掉重复情况
            int target = -nums[i];
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                if (nums[left] + nums[right] == target) {
                    ans.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right])));
                    
                    // 现在要增加 left，减小 right，但是不能重复，比如: [-2, -1, -1, -1, 3, 3, 3], i = 0, left = 1, right = 6, [-2, -1, 3] 的答案加入后，需要排除重复的 -1 和 3
                    left++; right--; // 首先无论如何先要进行加减操作
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (left < right && nums[right] == nums[right + 1]) right--;
                } else if (nums[left] + nums[right] < target) {
                    left++;
                } else {  // nums[left] + nums[right] > target
                    right--;
                }
            }
        }
        return ans;
    }
}

26、两数之和

有人相爱，有人夜里开车看海，有人leetcode第一题都做不出来。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        //将各个数组元素需要的数作为key，然后边遍历边寻找该数（map.containsKey(nums[i])）。
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0;i < nums.length;i++){
            if(map.containsKey(nums[i])){
                res[0] = i;
                res[1] = map.get(nums[i]);
                return res;
            }
            map.put(target-nums[i],i);
        }
        return res;
    }
}

27、两两交换链表的节点

分析：

28、旋转数组

分析：不使用额外数组，完成循环

import java.util.*;


public class Solution {
    /**
     * 旋转数组
     * @param n int整型 数组长度
     * @param m int整型 右移距离
     * @param a int整型一维数组 给定数组
     * @return int整型一维数组
     */
    //不允许使用额外数组
    public int[] solve (int n, int m, int[] a) {
        int k = m%n;
        //第一步：翻转整个数组
        reverse(a,0,n-1);
        //第二步:翻转前k个数字
        reverse(a,0,k-1);
        //第三步：翻转后面的数字
        reverse(a,k,n-1);
        return a;
    }
    private void reverse(int[] a,int left,int right){
        while(left < right){
            int tmp = a[left];
            a[left] = a[right];
            a[right] = tmp;
            left++;
            right--;
        }
    }
}

30、数组中只出现一次的数字

分析：
假设这两个不同的数为m，n
1、先得到m^n；
2、将数组元素分成两组，一组包含m，一组包含n

在这里插入代码片