算法笔记

数组和字符串

搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

提示:

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 为无重复元素的升序排列数组
-104 <= target <= 104

思路1：将target与数组中每个元素进行比较，如果相等就返回对应下标。如果不相等则说明target不在数组中此时就要另外考虑，如果target比数组第一个元素小就返回0，比最后一个元素小就返回数组的长度，如果它比数组前一个元素小比后一个元素大就返回i+1。

PLAINTEXT
class Solution {
    public int searchInsert(int[] nums, int target) {
        int flag = 0;
        for (int i=0;i<nums.length;i++) {
            if (nums[i] == target) {
                flag = 1;
                return i;
            } 
        }
        if (flag == 0) {
            for (int i=0;i<nums.length;i++) {
                if (target < nums[0]) {
                    return 0;
                }
                if (target > nums[nums.length - 1]) {
                    return nums.length;
                }
                if (target > nums[i] && target < nums[i+1]) {
                    return i+1;
                }
            }
        }
        return 0;
    }
}

思路2：暴力遍历。如果数组的元素比target大，直接返回下标，遍历结束说明target值最大，直接返回数组长度。

PLAINTEXT
class Solution {
    public int searchInsert(int[] nums, int target) {
        for(int i=0;i<nums.length;i++){
            if(nums[i]>=target) return i;
        }
        return nums.length;
    }
}

合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示：

1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104

旋转矩阵

（https://leetcode-cn.com/problems/rotate-image/）

给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。

不占用额外内存空间能否做到？

示例 1:

给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],

原地旋转输入矩阵，使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
示例 2:

给定 matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
],

原地旋转输入矩阵，使其变为:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]

思路1：画图找规律，发现[j][matrix.length-1-i]=[i][j]，直接秒杀。缺点：费内存，数组元素多了耗时间。

PLAINTEXT
class Solution {
    public void rotate(int[][] matrix) {
        int[][] newMatrix = new int[matrix.length][matrix.length];
        for (int i=0;i<newMatrix.length;i++) {
            for (int j=0;j<newMatrix.length;j++) {
                newMatrix[i][j] = 0;
            }
        }
        for (int i=0;i<matrix.length;i++) {
            for (int j=0;j<matrix.length;j++) {
                newMatrix[j][matrix.length-1-i] = matrix[i][j];
            }
        }
        for (int i=0;i<matrix.length;i++) {
            for (int j=0;j<matrix.length;j++) {
                matrix[i][j]=newMatrix[i][j];
            }
        }
    }
}
PLAINTEXT
class Solution {
    public void rotate(int[][] matrix) {
        int len = matrix.length;
        if(len==1) return;

        int maxIdx = len-1;
        int[][] newMatrix = new int[len][len];
        for(int y=0; y<len; y++){
            for(int x=0; x<len; x++){
                newMatrix[y][maxIdx-x]=matrix[x][y];
            }
        }
        /* 采用逐个赋值的方法，而不是 matrix=newMatrix。
         *
         * 本题中，java的参数是一个指向源数组的指针，
         * 直接使用 matrix=newMatrix 赋值改变的是参数的指向，
         * 不是传输进去的源数组的指向。所以需要为参数逐个赋值。*/
        for(int y=0; y<len; y++){
            for(int x=0; x<len; x++){
                matrix[x][y]=newMatrix[x][y];
            }
        }
    }
}

零矩阵

编写一种算法，若M × N矩阵中某个元素为0，则将其所在的行与列清零。

示例 1：

输入：
[
[1,1,1],
[1,0,1],
[1,1,1]
]
输出：
[
[1,0,1],
[0,0,0],
[1,0,1]
]
示例 2：

输入：
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
输出：
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]

JAVA
class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        boolean[] row = new boolean[m];
        boolean[] col = new boolean[n];

        // 记录每一行和每一列是否存在0
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    row[i] = true;
                    col[j] = true;
                }
            }
        }

        // 根据记录的信息设置行和列
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (row[i] || col[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}

单链表

JAVA
package DataStructure;

import java.util.Stack;

public class SingleLinkedList {
    // 定义节点，其中有数据域和指针域
    class ListNode {
        int val;
        ListNode next;
        public ListNode(int val) {
            this.val = val;
        }
    }
    /**
     * 单链表的初始化
     */
    ListNode head;
    int size;
    public SingleLinkedList() {
        this.size = 0;
        this.head = null;
    }

    /**
     * 头插法插入节点
     * @param data
     */
    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        if (this.head == null) {
            this.head = node;
        } else {
            node.next = this.head;
            this.head = node;
        }
        this.size++;
    }

    /**
     * 尾插法插入节点
     */
    public void addLast(int data) {
        ListNode node = new ListNode(data);
        if (this.head == null) {
            this.head = node;
        } else {
            ListNode cur = this.head;
            while(cur.next != null) {
                cur = cur.next;
            }
            cur.next = node;
        }
        this.size++;
    }

    /**
     * 遍历打印单链表
     */
    public void printSingleLinkedList() {
        ListNode cur = this.head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
    }

    /**
     * 按索引修改链表的值
     * @param pos
     * @param data
     */
    public void modify(int pos, int data) {
        if (pos < 0 || pos >= this.size) {
            throw new RuntimeException("操作位置不合法");
        }
        if (this.head == null) {
            throw new RuntimeException("链表为空，无法修改");
        }
        ListNode cur = this.head;
        int index = 0;
        while (index != pos) {
            cur = cur.next;
            index++;
        }
        cur.val = data;
    }

    /**
     * 根绝索引获取前驱节点
     * @return
     */
    public ListNode getIndex(int pos) {
        if (pos == 0) {
            throw new RuntimeException("头结点无前驱节点");
        }
        int index = 0;
        ListNode cur = this.head;
        while (index != pos - 1) {
            cur = cur.next;
            index++;
        }
        System.out.println("当前节点的职位：" + cur.val);
        return cur;
    }
    /**
     * 按指定值删除链表中的值
     * @param pos
     */
    public void delete(int pos) {
        if (this.head == null) {
            throw new RuntimeException("链表为空，无法删除");
        }
        if (pos < 0 || pos >= this.size) {
            throw new RuntimeException("操作位置不合法");
        }
        if (pos == 0) {
            this.head = this.head.next; // 头结点指向头结点的下一个节点
            this.size--;
            return;
        }
        ListNode prev = getIndex(pos);
        prev.next = prev.next.next;
        this.size--;
    }

    /**
     * 按索引插入值
     * @param pos
     * @param data
     */
    public void insertSingleLinkedList(int pos, int data) {
        if (pos < 0 || pos >= this.size) {
            throw new RuntimeException("操作位置不合法");
        }
        if (pos == 0) {
            addFirst(data);
            return;
        }
        if (pos == this.size) {
            addLast(data);
            return;
        }
        ListNode prev = getIndex(pos);
        ListNode node = new ListNode(data);
        node.next = prev.next;
        prev.next = node;
        this.size++;
    }
    public static void main(String[] args) {
        SingleLinkedList singleLinkedList =  new SingleLinkedList();
        singleLinkedList.addLast(1);
        singleLinkedList.addLast(2);
        singleLinkedList.addLast(3);
        singleLinkedList.insertSingleLinkedList(1, 0);
        Stack stack = new Stack();
        singleLinkedList.printSingleLinkedList();
    }
}

栈和队列

栈：

基于ArrayList实现：

// "static void main" must be defined in a public class.
class MyStack {
    private List<Integer> data;               // store elements
    public MyStack() {
        data = new ArrayList<>();
    }
    /** Insert an element into the stack. */
    public void push(int x) {
        data.add(x);
    }
    /** Checks whether the queue is empty or not. */
    public boolean isEmpty() {
        return data.isEmpty();
    }
    /** Get the top item from the queue. */
    public int top() {
        return data.get(data.size() - 1);
    }
    /** Delete an element from the queue. Return true if the operation is successful. */
    public boolean pop() {
        if (isEmpty()) {
            return false;
        }
        data.remove(data.size() - 1);
        return true;
    }
};

public class Main {
    public static void main(String[] args) {
        MyStack s = new MyStack();
        s.push(1);
        s.push(2);
        s.push(3);
        for (int i = 0; i < 4; ++i) {
            if (!s.isEmpty()) {
                System.out.println(s.top());
            }
            System.out.println(s.pop());
        }
    }
}

Stack（Java自带）√

package DataStructure.JavaStack;

import java.util.ArrayList;
import java.util.List;

class MinStack {
    private List<Integer> stack;
    public MinStack() {
        stack = new ArrayList<>();
    }
    
    public void push(int val) {
        stack.add(val);
    }
    
    public void pop() {
        stack.remove(stack.size() - 1);
    }
    
    public int top() {
        return stack.get(stack.size() - 1);
    }
    
    public int getMin() {
        int min = top();
        for (int i=stack.size()-1;i>=0;i--) {
            if (min > stack.get(i)) {
                min = stack.get(i);
            }
        }
        return min;
    }

    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        minStack.push(2);
        minStack.push(3);
        minStack.push(1);
        minStack.push(4);

        String s = "abc";

        String[] s1 = {"123","345"};
        int length = s1.length;

        System.out.println(minStack.getMin());
    }
}

队列

基于ArrayList实现：

package DataStructure.JavaQueue;// "static void main" must be defined in a public class.

import java.util.ArrayList;
import java.util.List;

class MyQueue {
    // store elements
    private List<Integer> data;         
    // a pointer to indicate the start position
    private int p_start;            
    public MyQueue() {
        data = new ArrayList<Integer>();
        p_start = 0; // 指出起点的索引
    }
    /** Insert an element into the queue. Return true if the operation is successful. */
    public boolean enQueue(int x) {
        data.add(x);
        return true;
    };    
    /** Delete an element from the queue. Return true if the operation is successful. */
    public boolean deQueue() {
        if (isEmpty() == true) {
            return false;
        }
        p_start++;
        return true;
    }
    /** Get the front item from the queue. */
    public int Front() {
        return data.get(p_start);
    }
    /** Checks whether the queue is empty or not. */
    public boolean isEmpty() {
        return p_start >= data.size();
    }
    public static void main(String[] args) {
        MyQueue q = new MyQueue();
        q.enQueue(5);
        q.enQueue(3);
        if (q.isEmpty() == false) {
            System.out.println(q.Front());
        }
        q.deQueue();
        if (q.isEmpty() == false) {
            System.out.println(q.Front());
        }
        q.deQueue();
        if (q.isEmpty() == false) {
            System.out.println(q.Front());
        }
    }
}

基于LinkedList实现 √

PLAINTEXT
import java.util.Queue;
import java.util.LinkedList;
 
public class QueueExample {
    public static void main(String[] args) {
        // 创建一个Queue对象
        Queue<String> queue = new LinkedList<>();
 
        // 添加元素到队列
        queue.add("Apple");
        queue.add("Banana");
        queue.add("Orange");
 
        // 获取队列头部元素
        String head = queue.peek();
        System.out.println("头部元素：" + head);
 
        // 遍历队列并输出元素
        System.out.println("队列元素：");
        for (String element : queue) {
            System.out.println(element);
        }
 
        // 移除队列头部元素
        String removedElement = queue.remove();
        System.out.println("移除的元素：" + removedElement);
 
        // 队列大小
        int size = queue.size();
        System.out.println("队列大小：" + size);
 
        // 判断队列是否为空
        boolean isEmpty = queue.isEmpty();
        System.out.println("队列是否为空：" + isEmpty);
    }
}

peek获取队列的头元素，但是不会移除。

poll获取并移除队列的头元素

循环队列：

size 队列长度

head 头指针

tail 尾指针

head == tail 表示队列只有一个元素

head == (tail + 1) % size 表示队列已满

JAVA
class MyCircularQueue {
    
    private int[] data;
    private int head;
    private int tail;
    private int size;

    // 初始化队列
    public MyCircularQueue(int k) {
        data = new int[k];
        head = -1;
        tail = -1;
        size = k;
    }
    
	/**在循环队列中插入一个元素。如果操作成功，返回true. */
    public boolean enQueue(int value) {
        if (isFull() == true) {
            return false;
        }
        if (isEmpty() == true) {
            head = 0;
        }
        tail = (tail + 1) % size;
        data[tail] = value;
        return true;
    }
    
	/**从循环队列中删除元素。如果操作成功，返回true. */
    public boolean deQueue() {
        if (isEmpty() == true) {
            return false;
        }
        if (head == tail) {
            head = -1;
            tail = -1;
            return true;
        }
        head = (head + 1) % size;
        return true;
    }
    
    /**从队列中获取前面的项目*/
    public int Front() {
        if (isEmpty() == true) {
            return -1;
        }
        return data[head];
    }
    
    /**从队列中获取最后一个元素*/
    public int Rear() {
        if (isEmpty() == true) {
            return -1;
        }
        return data[tail];
    }
    
    
	/**检查循环队列是否为空*/
    public boolean isEmpty() {
        return head == -1;
    }
    
    
	/**检查循环队列是否已满*/
    public boolean isFull() {
        return ((tail + 1) % size) == head;
    }
}

循环队列：http://t.csdnimg.cn/gI6Im

哈希表

http://t.csdnimg.cn/TVdNJ

查找表类算法

两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案

JAVA
class Solution {
    public int[] twoSum(int[] nums, int target) {
        List<Integer> list = new ArrayList<>();
        for(int i=0;i<nums.length;i++) {
            for(int j=i+1;j<nums.length;j++) {
                if (nums[i]+nums[j]==target) {
                    list.add(i);
                    list.add(j);
                }
            }
        }
        int[] a=new int[list.size()];
        for(int i=0;i<list.size();i++) {
            a[i]=list.get(i);
        }
        return a;
    }
}

三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：

3 <= nums.length <= 3000
-105 <= nums[i] <= 105

超时：

JAVA
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Set<List<Integer>> set=new HashSet<>();
            List<Integer> list=new ArrayList<>();
            Arrays.sort(nums);
            for(int i=0;i<nums.length;i++) {
                for(int j=i+1;j<nums.length;j++) {
                    for(int k=j+1;k<nums.length;k++) {
                        if(nums[i]+nums[j]+nums[k]==0) {
                            list.add(nums[i]);
                            list.add(nums[j]);
                            list.add(nums[k]);
                        }
                    }
                }
            }
            int size=list.size();
            for (int i = 0; i < size; i += 3) {
                int endIndex = Math.min(i + 3, size);
                List<Integer> subList = list.subList(i, endIndex);
                set.add(new ArrayList<>(subList));
            }
            return new ArrayList<>(set);
    }
}

二分查找：

JAVA
List<List<Integer>> result = new ArrayList<>();
if (nums == null || nums.length <= 2) {
    return result;
}
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
    if (nums[i] > 0) {
        return result;
    }
    // 去掉重复情
    if (i > 0 && nums[i] == nums[i - 1]) {
        continue;
    }

    int left = i + 1;
    int right = nums.length - 1;
    while (left < right) {
        if (nums[i] + nums[left] + nums[right] == 0) {
            result.add(Arrays.asList(nums[i], nums[left], nums[right]));
            left++;
            right--;
            // 去掉重复
            while (left < right && nums[left] == nums[left - 1]) {
                left++;
            }
            while (left < right && nums[right] == nums[right + 1]) {
                right--;
            }
        } else if (nums[i] + nums[left] + nums[right] < 0) {
            left++;
        } else {
            right--;
        }
    }
}
return result;

二分查找

模板1：

用于查找可以通过*访问数组中的单个索引*来确定的元素或条件。

JAVA
int binarySearch(int[] nums, int target){
  if(nums == null || nums.length == 0)
    return -1;

  int left = 0, right = nums.length - 1;
  while(left <= right){
    // Prevent (left + right) overflow
    int mid = left + (right - left) / 2;
    if(nums[mid] == target){ return mid; }
    else if(nums[mid] < target) { left = mid + 1; }
    else { right = mid - 1; }
  }

  // End Condition: left > right
  return -1;
}

模板2：

它用于查找需要*访问数组中当前索引及其直接右邻居索引*的元素或条件。

JAVA
int binarySearch(int[] nums, int target){
  if(nums == null || nums.length == 0)
    return -1;

  int left = 0, right = nums.length;
  while(left < right){
    // Prevent (left + right) overflow
    int mid = left + (right - left) / 2;
    if(nums[mid] == target){ return mid; }
    else if(nums[mid] < target) { left = mid + 1; }
    else { right = mid; }
  }

  // Post-processing:
  // End Condition: left == right
  if(left != nums.length && nums[left] == target) return left;
  return -1;
}

定义mid中间值时，一定要设为mid=left+(right-left)/2，如果设为mid=(left+right)/2会超出空间和时间限制。

模板3：

它用于搜索需要*访问当前索引及其在数组中的直接左右邻居索引*的元素或条件。

JAVA
int binarySearch(int[] nums, int target) {
    if (nums == null || nums.length == 0)
        return -1;

    int left = 0, right = nums.length - 1;
    while (left + 1 < right){
        // Prevent (left + right) overflow
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid;
        } else {
            right = mid;
        }
    }

    // Post-processing:
    // End Condition: left + 1 == right
    if(nums[left] == target) return left;
    if(nums[right] == target) return right;
    return -1;
}

简单的二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：

你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

JAVA
class Solution {
    public int search(int[] nums, int target) {
        int left=0,right=nums.length-1;
        while(left<=right) {
            int mid=(left+right)/2;
            if(nums[mid]<target) {
                left=mid+1;
            } else if(nums[mid]>target) {
                right=mid-1;
            } else{
                return mid;
            }
        }
        return -1;
    }
}

x 的平方根

给你一个非负整数 x ，计算并返回 x 的算术平方根。

由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

输入：x = 4
输出：2
示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。

提示：

0 <= x <= 2^31 - 1

JAVA
class Solution {
    public int mySqrt(int x) {
        if(x==0||x==1) {
            return x;
        }
        int left=1,right=x;
        while(left<=right) {
            int mid=(left+right)/2;
            if(x/mid==mid) {
                return mid;
            } else if(x/mid<mid) {
                right=mid-1;
            } else{
                left=mid+1;
            }
        }
        return right;
    }
}

猜数字大小

猜数字游戏的规则如下：

每轮游戏，我都会从 1 到 n 随机选择一个数字。请你猜选出的是哪个数字。
如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。
你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：

-1：我选出的数字比你猜的数字小 pick < num
1：我选出的数字比你猜的数字大 pick > num
0：我选出的数字和你猜的数字一样。恭喜！你猜对了！pick == num
返回我选出的数字。

示例 1：

输入：n = 10, pick = 6
输出：6
示例 2：

输入：n = 1, pick = 1
输出：1
示例 3：

输入：n = 2, pick = 1
输出：1
示例 4：

输入：n = 2, pick = 2
输出：2

提示：

1 <= n <= 231 - 1
1 <= pick <= n

JAVA
/** 
 * Forward declaration of guess API.
 * @param  num   your guess
 * @return 	     -1 if num is higher than the picked number
 *			      1 if num is lower than the picked number
 *               otherwise return 0
 * int guess(int num);
 */

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        if(guess(n)==0) {
            return n;
        }
        int left=1,right=n;
        while(left<=right) {
            int mid=left+(right-left)/2;
            if(guess(mid)==0) {
                return mid;
            } else if(guess(mid)==-1) {
                right=mid-1;
            } else {
                left=mid+1;
            }
        }
        return right;
    }
}

搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值互不相同。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标从 0 开始计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你旋转后的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
示例 2：

输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
示例 3：

输入：nums = [1], target = 0
输出：-1

提示：

1 <= nums.length <= 5000
-104 <= nums[i] <= 104
nums 中的每个值都独一无二
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-104 <= target <= 104

解法1：

JAVA
class Solution {
    public int search(int[] nums, int target) {
        Map<Integer,Integer> map=new HashMap<>();
        for (int i=0;i<nums.length;i++) {
            map.put(nums[i],i);
        }
        Arrays.sort(nums);
        int left=0,right=nums.length-1;
        while(left<=right) {
            int mid=left+(right-left)/2;
            if(nums[mid]==target) {
                return map.get(nums[mid]);
            } else if(nums[mid]<target) {
                left=mid+1;
            } else {
                right=mid-1;
            }
        }
        return -1;
    }
}

解法2：

思路：

判断mid所在元素是左递增还是右递增。如果nums[mid]>nums[r]，说明是左递增，此时有两种情况，若target在左递增区间，则排除mid右边的所有值，若不在则排除mid左边的所有值；如果nums[mid]<nums[r]，说明是右递增，此时有两种情况，若target在右递增区间，则排除mid左边的所有值，若不在则排除mid右边的所有值。
除了上面这种方法，还可以先找到旋转点，再分情况从[l,旋转点)或[旋转点,r]进行普通二分查找。

JAVA
class Solution {
    public int search(int[] nums, int target) {
        int l=0,r=nums.length-1;
        while(l<=r){
            int mid=l+(r-l)/2;
            if(nums[mid]==target){
                return mid;
            }
            if(nums[mid]>nums[r]){
                if(nums[mid]>target&&target>=nums[l]){
                    r=mid-1;
                }
                else{
                    l=mid+1;
                }
            }
            else{
                if(nums[mid]<target&&target<=nums[r]){
                    l=mid+1;
                }
                else{
                    r=mid-1;
                }
            }
        }
        return -1;
    }
}

第一个错误的版本

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例 1：

输入：n = 5, bad = 4
输出：4
解释：
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。
示例 2：

输入：n = 1, bad = 1
输出：1

提示：

1 <= bad <= n <= 231 - 1

JAVA
/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left=1,right=n;
        while(left<=right) {
            int mid=left+(right-left)/2;
            if(isBadVersion(mid)) {
                right=mid-1;
            } else{
                left=mid+1;
            }
        }
        return left;
    }
}

寻找峰值

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

示例 1：

输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。
示例 2：

输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5
解释：你的函数可以返回索引 1，其峰值元素为 2；
或者返回索引 5，其峰值元素为 6。

提示：

1 <= nums.length <= 1000
-231 <= nums[i] <= 231 - 1
对于所有有效的 i 都有 nums[i] != nums[i + 1]

JAVA
class Solution {
    public int findPeakElement(int[] nums) {
        int l=0;
        int r=nums.length-1;
        while(l<r){
            int mid=(l+r)/2;
            if(nums[mid]>nums[mid+1]){
                r=mid;
            }
            else{
                l=mid+1;
            }
        }
        return l;
    }
}

寻找旋转排序数组中的最小值

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。

给你一个元素值互不相同的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
示例 2：

输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 3 次得到输入数组。
示例 3：

输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。

提示：

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums 中的所有整数互不相同
nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

JAVA
class Solution {
    public int findMin(int[] nums) {
        int n=nums.length;
        int l=0,r=n-1;
        while(l<r){
            int mid=l+(r-l)/2;
            if(nums[mid]<=nums[n-1]){
                r=mid;
            }
            else{
                l=mid+1;
            }
        }
        return nums[l];
    }
}

二叉树

先序遍历

方法1：

JAVA
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        preOrder(root, list);
        return list;
    }
    public void preOrder(TreeNode root, List<Integer> list) {
        if(root==null) {
            return;
        }
        list.add(root.val);
        preOrder(root.left, list);
        preOrder(root.right, list);
    }
}

方法2：

JAVA
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        //加个边界条件判断
        if (root == null)
            return res;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);//压栈
        while (!stack.empty()) {
            TreeNode t1 = stack.pop();//出栈
            res.add(t1.val);
            if (t1.right != null) {
                stack.push(t1.right);
            }
            if (t1.left != null) {
                stack.push(t1.left);
            }
        }
        return res;
    }

中序遍历：

方法1：

JAVA
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        inOrder(root, list);
        return list;
    }
    
    public void inOrder(TreeNode root, List<Integer> list) {
        if(root==null) {
            return;
        }
        inOrder(root.left, list);
        list.add(root.val);
        inOrder(root.right, list);
    }
}

方法2：

JAVA
  /**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
  public List<Integer> inorderTraversal(TreeNode root) {
       List<Integer> res = new ArrayList<>();
       //加个边界条件判断
       if (root == null)
           return res;
       Stack<TreeNode> stack = new Stack<>();
       while (root != null || !stack.isEmpty()) {
           while (root != null) {
               stack.push(root);
               root = root.left;
           }
           if (!stack.isEmpty()) {
               root = stack.pop();
               res.add(root.val);
               root = root.right;
           }
       }
       return res;
   }

后序遍历：

方法1：

JAVA
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        postOrder(root, list);
        return list;
    }

    public void postOrder(TreeNode root, List<Integer> list) {
        if(root==null) {
            return;
        }
        postOrder(root.left, list);
        postOrder(root.right, list);
        list.add(root.val);
    }
}

方法2：

JAVA
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
// 因为后续遍历逆序结果等于前序遍历（先右子树）的结果
    // 所以将前序遍历（先右子树）的结果通过栈逆序输出即可
    public List<Integer> postorderTraversal(TreeNode root) {
        List l1 = new ArrayList();
        if(root==null)
           return l1;
        Stack<TreeNode> s1 = new <TreeNode>Stack();
        Stack<TreeNode> s2 = new <TreeNode>Stack();
        s1.push(root);
        while(!s1.empty()){
            TreeNode temp = s1.pop();
            s2.push(temp);
            if(temp.left!=null)
               s1.push(temp.left);
            if(temp.right!=null)
               s1.push(temp.right);
        }
        while(!s2.empty()){
            l1.add(s2.pop().val);
        }
        return l1;
    }

层序遍历（广度优先搜索法）：

通常，我们使用一个叫做队列的数据结构来帮助我们做广度优先搜索。

二叉树的层序遍历
给你二叉树的根节点 root ，返回其节点值的层序遍历。（即逐层地，从左到右访问所有节点）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
示例 2：

输入：root = [1]
输出：[[1]]
示例 3：

输入：root = []
输出：[]

提示：

树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000

JAVA
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */   
public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        // 先将根节点放入队列
        queue.add(root);
        while (queue.size() > 0) {
            int size = queue.size();
            List<Integer> temp = new ArrayList<>();
            // 遍历队列，把当前层的元素从队列取出来，将下一层放入队列
            for (int i = 0; i < size; i++) {
                // 取出队列元素，放入集合
                TreeNode current = queue.poll();
                temp.add(current.val);
                if (current.left != null) {
                    // 将当前节点的左儿子放入队列
                    queue.add(current.left);
                }
                if (current.right != null) {
                    // 将当前节点的右儿子放入队列
                    queue.add(current.right);
                }
            }
            result.add(temp);
        }
        return result;
    }

二叉搜索树

二叉搜索树是指每个节点的值大于等于其左子树的任何值，小于等于其右子树的任何值。

验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

输入：root = [2,1,3]
输出：true

示例 2：

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：

树中节点数目范围在[1, 104] 内
-2^31 <= Node.val <= 2^31 - 1

方法1（中序递归）：

JAVA
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
//前一个结点，全局的
private TreeNode prev;
public boolean isValidBST(TreeNode root) {
    if (root == null)
        return true;
    //访问左子树
    if (!isValidBST(root.left))
        return false;
    //访问当前节点：如果当前节点小于等于中序遍历的前一个节点直接返回false。
    if (prev != null && prev.val >= root.val)
        return false;
    prev = root;
    //访问右子树
    if (!isValidBST(root.right))
        return false;
    return true;
    }
}

方法2（中序非递归）：

JAVA
public boolean isValidBST(TreeNode root) {
    if (root == null)
        return true;
    Stack<TreeNode> stack = new Stack<>();
    TreeNode pre = null;
    while (root != null || !stack.isEmpty()) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        if (pre != null && root.val <= pre.val)
            return false;
        //保存前一个访问的结点
        pre = root;
        root = root.right;
    }
    return true;
}

方法3（递归）：

JAVA
public boolean isValidBST(TreeNode root) {
    return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

public boolean isValidBST(TreeNode root, long minVal, long maxVal) {
    if (root == null)
        return true;
    //每个节点如果超过这个范围，直接返回false
    if (root.val >= maxVal || root.val <= minVal)
        return false;
    //这里再分别以左右两个子节点分别判断，
    //左子树范围的最小值是minVal，最大值是当前节点的值，也就是root的值，因为左子树的值要比当前节点小
    //右子数范围的最大值是maxVal，最小值是当前节点的值，也就是root的值，因为右子树的值要比当前节点大
    return isValidBST(root.left, minVal, root.val) && isValidBST(root.right, root.val, maxVal);
}

二叉搜索树迭代器

实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器：
BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。
boolean hasNext() 如果向指针右侧遍历存在数字，则返回 true ；否则返回 false 。
int next()将指针向右移动，然后返回指针处的数字。
注意，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 BST 中的最小元素。

你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 的中序遍历中至少存在一个下一个数字。

示例：

输入
[“BSTIterator”, “next”, “next”, “hasNext”, “next”, “hasNext”, “next”, “hasNext”, “next”, “hasNext”]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
输出
[null, 3, 7, true, 9, true, 15, true, 20, false]

解释
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next(); // 返回 3
bSTIterator.next(); // 返回 7
bSTIterator.hasNext(); // 返回 True
bSTIterator.next(); // 返回 9
bSTIterator.hasNext(); // 返回 True
bSTIterator.next(); // 返回 15
bSTIterator.hasNext(); // 返回 True
bSTIterator.next(); // 返回 20
bSTIterator.hasNext(); // 返回 False

提示：

树中节点的数目在范围 [1, 105] 内
0 <= Node.val <= 106
最多调用 105 次 hasNext 和 next 操作

进阶：

你可以设计一个满足下述条件的解决方案吗？next() 和 hasNext() 操作均摊时间复杂度为 O(1) ，并使用 O(h) 内存。其中 h 是树的高度。

方法1：

JAVA
class BSTIterator {
    Deque<TreeNode> d = new ArrayDeque<>();
    public BSTIterator(TreeNode root) {
        // 步骤 1
        dfsLeft(root);
    }
    
    public int next() {
        // 步骤 2
        TreeNode root = d.pollLast();
        int ans = root.val;
        // 步骤 3
        root = root.right;
        // 步骤 1
        dfsLeft(root);
        return ans;
    }

    void dfsLeft(TreeNode root) {
        while (root != null) {
            d.addLast(root);
            root = root.left;
        }
    }

    public boolean hasNext() {
        return !d.isEmpty();
    }
}

方法2：

JAVA
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class BSTIterator {

    List<Integer> list = new ArrayList<>();
    private int pointer;

    public BSTIterator(TreeNode root) {
        this.pointer = -1;
        inorderBFS(root);
    }

    public int next() {
        return list.get(++pointer);
    }

    public boolean hasNext() {
        return this.pointer+1 < list.size();
    }

    public void inorderBFS(TreeNode node) {
        if (node == null) {
            return;
        }

        inorderBFS(node.left);
        list.add(node.val);
        inorderBFS(node.right);
    }
}

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator obj = new BSTIterator(root);
 * int param_1 = obj.next();
 * boolean param_2 = obj.hasNext();
 */

二叉搜索树中的搜索

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。返回以该节点为根的子树。如果节点不存在，则返回 null 。

示例 1:

输入：root = [4,2,7,1,3], val = 2
输出：[2,1,3]
示例 2:

输入：root = [4,2,7,1,3], val = 5
输出：[]

提示：

树中节点数在 [1, 5000] 范围内
1 <= Node.val <= 107
root 是二叉搜索树
1 <= val <= 107

JAVA
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        while(root!=null) {
            if(root.val>val) {
                root=root.left;
            } else if(root.val<val) {
                root=root.right;
            } else {
                return root;
            }
        }
        return null;
    }
}

二叉搜索树中的插入操作

给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。你可以返回任意有效的结果。

示例 1：

输入：root = [4,2,7,1,3], val = 5
输出：[4,2,7,1,3,5]
解释：另一个满足题目要求可以通过的树是：

示例 2：

输入：root = [40,20,60,10,30,50,70], val = 25
输出：[40,20,60,10,30,50,70,null,null,25]
示例 3：

输入：root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
输出：[4,2,7,1,3,5]

提示：

树中的节点数将在 [0, 104]的范围内。
-108 <= Node.val <= 108
所有值 Node.val 是独一无二的。
-108 <= val <= 108
保证 val 在原始BST中不存在。

JAVA
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        if (root.val > val) {
            root.left = insertIntoBST(root.left, val);
        }
        if (root.val < val) {
            root.right = insertIntoBST(root.right, val);
        }
        return root;
    }
}

删除二叉搜索树中的节点

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

首先找到需要删除的节点；
如果找到了，删除它。

示例 1:

输入：root = [5,3,6,2,4,null,7], key = 3
输出：[5,4,6,2,null,null,7]
解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。

示例 2:

输入: root = [5,3,6,2,4,null,7], key = 0
输出: [5,3,6,2,4,null,7]
解释: 二叉树不包含值为 0 的节点
示例 3:

输入: root = [], key = 0
输出: []

提示:

节点数的范围 [0, 104].
-105 <= Node.val <= 105
节点值唯一
root 是合法的二叉搜索树
-105 <= key <= 105

方法1：

JAVA
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null)return null;
        if(key<root.val){
            root.left = deleteNode(root.left,key);
        }else if(key>root.val){
            root.right = deleteNode(root.right,key);
        }else{//key==root.val
            if(root.left == null && root.right == null){
                root = null;
            }else if(root.right == null){
                root = root.left;
            }else{
                TreeNode curr = root.right;
                while(curr.left != null){
                    curr = curr.left;
                }
                root.val = curr.val;
                root.right = deleteNode(root.right, root.val);
            }
        }
        return root;
    }
}

方法2（递归实现）：

JAVA
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
/**
 * 删除，三种情况
 * 1. 目标节点没有左右子树，直接删除
 * 2. 目标节点只有左子树或只有右子树，原来指向目标节点的指针指向其左子树或右子树
 * 3. 目标节点有左右子树:
 * 方案一：找到左子树的最右节点，让原来指向这个左子树最右节点的指针指向其左子树，然后用这个左子树最右节点替换掉目标节点
 * 方案二：找到右子树的最左节点，让原来指向这个右子树最左节点的指向指向其右子树，然后用这个右子树最左节点替换掉目标节点
 *
 * @param root 根节点
 * @param key  待删除节点值
 * @return 新的根节点
 */
public TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) {
        return root;
    }
    if (root.val == key) {
        return newTree(root);
    }
    if (root.val > key) {
        TreeNode newTree = deleteNode(root.left, key);
        root.left = newTree;
    }
    if (root.val < key) {
        TreeNode newTree = deleteNode(root.right, key);
        root.right = newTree;
    }
    return root;
}

private TreeNode newTree(TreeNode root) {
    if (root.left == null && root.right == null) {
        return null;
    }
    if (root.left == null) {
        return root.right;
    }
    if (root.right == null) {
        return root.left;
    }
    TreeNode pre = root, cur = root.right;
    while (cur.left != null) {
        pre = cur;
        cur = cur.left;
    }
    if (cur != root.right) {
        pre.left = cur.right;
        cur.left = root.left;
        cur.right = root.right;
    } else {
        cur.left = root.left;
    }
    return cur;
}

数组类算法

移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:

输入: nums = [0]
输出: [0]

提示:

1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1

进阶：你能尽量减少完成的操作次数吗？

方法1（将非0的元素往前移）：

JAVA
class Solution {
    public void moveZeroes(int[] nums) {
        if(nums.length==0) {
            return;
        }
        int index=0;
        for(int i=0;i<nums.length;i++) {
            if(nums[i]!=0) {
                nums[index++]=nums[i];
            }
        }
        while(index<nums.length) {
            nums[index++]=0;
        }
    }
}

方法2（双指针）：

删除排序数组中的重复项

给你一个非严格递增排列的数组 nums ，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。元素的相对顺序应该保持一致。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
返回 k 。
判题标准:

系统会用下面的代码来测试你的题解:

int[] nums = […]; // 输入数组
int[] expectedNums = […]; // 长度正确的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}
如果所有断言都通过，那么您的题解将被通过。

示例 1：

输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
示例 2：

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ，并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示：

1 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按非严格递增排列

class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums.length==0) {
            return 0;
        }
        int slow=0;
        for(int fast=0;fast<nums.length-1;fast++) {
            if(nums[fast]!=nums[fast+1]) {
                slow++;
                nums[slow]=nums[fast+1];
            }
        }
        return slow+1;
    }
}

删除排序数组中的重复项 II

给你一个有序数组 nums ，请你原地删除重复出现的元素，使得出现次数超过两次的元素只出现两次，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

说明：

为什么返回数值是整数，但输出的答案是数组呢？

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}

示例 1：

输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]
解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3。不需要考虑数组中超出新长度后面的元素。
示例 2：

输入：nums = [0,0,1,1,1,1,2,3,3]
输出：7, nums = [0,0,1,1,2,3,3]
解释：函数应返回新长度 length = 7, 并且原数组的前七个元素被修改为 0, 0, 1, 1, 2, 3, 3。不需要考虑数组中超出新长度后面的元素。

提示：

1 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按升序排列

JAVA
class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums.length==0) {
            return 0;
        }
        int len=0;
        for(int i=0;i<nums.length;i++) {
            if(len < 2 || nums[len-2]!=nums[i]) {
                nums[len++]=nums[i];
            }
        }
        return len;
    }
}

合并两个有序数组

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

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

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。
示例 3：

输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

提示：

nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-109 <= nums1[i], nums2[j] <= 109

进阶：你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗？

方法1：

JAVA
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        for(int i=0;i<n;i++) {
            nums1[m++]=nums2[i];
        }
        Arrays.sort(nums1);
    }
}

方法2：

JAVA
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;

        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }

        while (j >= 0) {
            nums1[k--] = nums2[j--];
        }
    }
}

验证回文串

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个回文串。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是回文串，返回 true ；否则，返回 false 。

示例 1：

输入: s = “A man, a plan, a canal: Panama”
输出：true
解释：”amanaplanacanalpanama” 是回文串。
示例 2：

输入：s = “race a car”
输出：false
解释：”raceacar” 不是回文串。
示例 3：

输入：s = “ “
输出：true
解释：在移除非字母数字字符之后，s 是一个空字符串 “” 。
由于空字符串正着反着读都一样，所以是回文串

JAVA
class Solution {
    public boolean isPalindrome(String s) {
        s = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
        char[] chars = s.toCharArray();
        int left = 0;
        int right = chars.length - 1;
        while (left < right) {
            if (chars[left] == chars[right]) {
                left++;
                right--;
            } else {
                return false;
            }
        }
        return true;
    }
}

反转字符串中的元音字母

给你一个字符串 s ，仅反转字符串中的所有元音字母，并返回结果字符串。

元音字母包括 ‘a’、’e’、’i’、’o’、’u’，且可能以大小写两种形式出现不止一次。

示例 1：

输入：s = “hello”
输出：”holle”
示例 2：

输入：s = “leetcode”
输出：”leotcede”

提示：

1 <= s.length <= 3 * 105
s 由可打印的 ASCII 字符组成

JAVA
class Solution {
    public String reverseVowels(String s) {
        char[] chars = s.toCharArray();
        int l = 0;
        int r = chars.length - 1;
        while(l < r) {
            if (isYuanyin(chars[r]) && isYuanyin(chars[l])) {
                char temp = chars[l];
                chars[l] = chars[r];
                chars[r] = temp;
                l++;
                r--;
            } else if(isYuanyin(chars[l])){
                r--;
            } else if(isYuanyin(chars[r])) {
                l++;
            } else {
                l++;
                r--;
            }
        }
        return new String(chars);
    }

    public boolean isYuanyin(char c) {
        c = Character.toLowerCase(c);
        List<Character> list =  Arrays.asList('a', 'e', 'i', 'o', 'u');
        return list.contains(c);
    }
}

编程基础从0到1

1768. 交替合并字符串

给你两个字符串 word1 和 word2 。请你从 word1 开始，通过交替添加字母来合并字符串。如果一个字符串比另一个字符串长，就将多出来的字母追加到合并后字符串的末尾。

返回 合并后的字符串 。

示例 1：

PLAINTEXT
输入：word1 = "abc", word2 = "pqr"
输出："apbqcr"
解释：字符串合并情况如下所示：
word1：  a   b   c
word2：    p   q   r
合并后：  a p b q c r

示例 2：

PLAINTEXT
输入：word1 = "ab", word2 = "pqrs"
输出："apbqrs"
解释：注意，word2 比 word1 长，"rs" 需要追加到合并后字符串的末尾。
word1：  a   b 
word2：    p   q   r   s
合并后：  a p b q   r   s

示例 3：

PLAINTEXT
输入：word1 = "abcd", word2 = "pq"
输出："apbqcd"
解释：注意，word1 比 word2 长，"cd" 需要追加到合并后字符串的末尾。
word1：  a   b   c   d
word2：    p   q 
合并后：  a p b q c   d

提示：

1 <= word1.length, word2.length <= 100
word1 和 word2 由小写英文字母组成

方法1：

JAVA
class Solution {
    public String mergeAlternately(String word1, String word2) {
        char[] chars1 = word1.toCharArray();
        char[] chars2 = word2.toCharArray();
        int length = Math.max(word1.length(), word2.length());
        char[] chars = new char[word1.length() + word2.length()];
        int index = 0;
        for (int i=0;i<length;i++) {
             if (i < word1.length()) {
                 chars[index++] = chars1[i];
             }
             if (i < word2.length()) {
                 chars[index++] = chars2[i];
             }
        }
        return new String(chars);
    }
}

方法2：

JAVA

389. 找不同

给定两个字符串 s 和 t ，它们只包含小写字母。

字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。

请找出在 t 中被添加的字母。

示例 1：

PLAINTEXT
输入：s = "abcd", t = "abcde"
输出："e"
解释：'e' 是那个被添加的字母。

示例 2：

1
2
3

PLAINTEXT
输入：s = "", t = "y"
输出："y"

提示：

0 <= s.length <= 1000
t.length == s.length + 1
s 和 t 只包含小写字母

思路：先排序找第一个不同的字符，找到了就返回，没找到就返回字符串t的最后一个字符

JAVA
class Solution {
    public char findTheDifference(String s, String t) {
        char[] chars1 = s.toCharArray();
        char[] chars2 = t.toCharArray();
        Arrays.sort(chars1);
        Arrays.sort(chars2);
        int length = Math.min(s.length(), t.length());
        for (int i=0;i<length;i++) {
            if (chars1[i] != chars2[i]) {
                return chars2[i];
            }
        }
        return chars2[t.length()-1];
    }
}

28. 找出字符串中第一个匹配项的下标

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

示例 1：

PLAINTEXT
输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：

输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。
JAVA
class Solution {
    public int strStr(String haystack, String needle) {
        String replaced = haystack.replace(needle, "1");
        if (haystack.equals(replaced)) {
            return -1;
        }
        char[] h = replaced.toCharArray();
        for (int i=0;i<h.length;i++) {
            if (h[i] == '1') {
                return i;
            }
        }
        return -1;
    }
}

class Solution {
    public int strStr(String haystack, String needle) {
        int n = haystack.length();
        int m = needle.length();

        for (int i = 0; i <= n - m; i++) {
            int j;
            for (j = 0; j < m; j++) {
                if (haystack.charAt(i + j) != needle.charAt(j)) {
                    break;
                }
            }
            if (j == m) {
                return i;
            }
        }
        return -1;
    }
}

242. 有效的字母异位词

给定两个字符串 *s* 和 *t* ，编写一个函数来判断 *t* 是否是 *s* 的字母异位词。

注意：若 *s* 和 *t* 中每个字符出现的次数都相同，则称 *s* 和 *t* 互为字母异位词。

示例 1:

1
2
3

PLAINTEXT
输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

1
2
3

PLAINTEXT
输入: s = "rat", t = "car"
输出: false

提示:

1 <= s.length, t.length <= 5 * 104
s 和 t 仅包含小写字母

class Solution {
    public boolean isAnagram(String s, String t) {
        HashMap<Character, Integer> hashMap = new HashMap<>();
        char[] chars1 = s.toCharArray();
        char[] chars2 = t.toCharArray();
        if (s.length() != t.length()) {
            return false;
        }
        for (int i=0;i<chars1.length;i++) {
            hashMap.put(chars1[i], hashMap.getOrDefault(chars1[i], 0)+1);
        }
        for (int i=0;i<chars2.length;i++) {
            if (!hashMap.containsKey(chars2[i])) {
                return false;
            }
            if (hashMap.get(chars2[i]) <= 0) {
                return false;
            }
            hashMap.put(chars2[i], hashMap.get(chars2[i]) - 1);
        }
        return true;
    }
}

459. 重复的子字符串

已解答

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

示例 1:

PLAINTEXT
输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。

示例 2:

1
2
3

PLAINTEXT
输入: s = "aba"
输出: false

示例 3:

PLAINTEXT
输入: s = "abcabcabcabc"
输出: true
解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)

提示：

1 <= s.length <= 104
s 由小写英文字母组成

JAVA

66. 加一

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位，数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1：

PLAINTEXT
输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。

示例 2：

PLAINTEXT
输入：digits = [4,3,2,1]
输出：[4,3,2,2]
解释：输入数组表示数字 4321。

示例 3：

1
2
3

PLAINTEXT
输入：digits = [0]
输出：[1]

提示：

1 <= digits.length <= 100
0 <= digits[i] <= 9

JAVA
class Solution {
    public int[] plusOne(int[] digits) {
        for(int i = digits.length-1; i >=0; i--) {
            if(digits[i] == 9) {
                digits[i] = 0;
            } else {
                digits[i] +=1;
                return digits;
            }
        }
        digits = new int[digits.length + 1];
        digits[0] = 1;
        return digits;
    }
}

1822. 数组元素积的符号

已知函数 signFunc(x) 将会根据 x 的正负返回特定值：

如果 x 是正数，返回 1 。
如果 x 是负数，返回 -1 。
如果 x 是等于 0 ，返回 0 。

给你一个整数数组 nums 。令 product 为数组 nums 中所有元素值的乘积。

返回 signFunc(product) 。

示例 1：

PLAINTEXT
输入：nums = [-1,-2,-3,-4,3,2,1]
输出：1
解释：数组中所有值的乘积是 144 ，且 signFunc(144) = 1

示例 2：

PLAINTEXT
输入：nums = [1,5,0,2,-3]
输出：0
解释：数组中所有值的乘积是 0 ，且 signFunc(0) = 0

示例 3：

PLAINTEXT
输入：nums = [-1,1,-1,1,-1]
输出：-1
解释：数组中所有值的乘积是 -1 ，且 signFunc(-1) = -1

1822. 数组元素积的符号

已知函数 signFunc(x) 将会根据 x 的正负返回特定值：

如果 x 是正数，返回 1 。
如果 x 是负数，返回 -1 。
如果 x 是等于 0 ，返回 0 。

给你一个整数数组 nums 。令 product 为数组 nums 中所有元素值的乘积。

返回 signFunc(product) 。

示例 1：

PLAINTEXT
输入：nums = [-1,-2,-3,-4,3,2,1]
输出：1
解释：数组中所有值的乘积是 144 ，且 signFunc(144) = 1

示例 2：

PLAINTEXT
输入：nums = [1,5,0,2,-3]
输出：0
解释：数组中所有值的乘积是 0 ，且 signFunc(0) = 0

示例 3：

PLAINTEXT
输入：nums = [-1,1,-1,1,-1]
输出：-1
解释：数组中所有值的乘积是 -1 ，且 signFunc(-1) = -1

思路：寻找数组中元素是否有等于0的，有就直接返回，同时记录负数的个数，负数个数是偶数的话直接返回1，否则返回-1。

JAVA
class Solution {
    public static int arraySign(int[] nums) {
        int count=0;
        for (int num : nums) {
            if (num < 0) {
                count++;
            } else if (num==0) {
                return 0;
            }
        }
        if (count%2==0) {
            return 1;
        } else {
            return -1;
        }
    }
}

1502. 判断能否形成等差数列

给你一个数字数组 arr 。

如果一个数列中，任意相邻两项的差总等于同一个常数，那么这个数列就称为 等差数列 。

如果可以重新排列数组形成等差数列，请返回 true ；否则，返回 false 。

示例 1：

PLAINTEXT
输入：arr = [3,5,1]
输出：true
解释：对数组重新排序得到 [1,3,5] 或者 [5,3,1] ，任意相邻两项的差分别为 2 或 -2 ，可以形成等差数列。

示例 2：

PLAINTEXT
输入：arr = [1,2,4]
输出：false
解释：无法通过重新排序得到等差数列。

提示：

2 <= arr.length <= 1000
-10^6 <= arr[i] <= 10^6

思路：比较间隔的数是否相等注意不要超出数组的长度，另外数组长度为2的数组就是等差数列。

JAVA
class Solution {
    public boolean canMakeArithmeticProgression(int[] arr) {
        if (arr.length<=2) {
            return true;
        }
        Arrays.sort(arr);
        for (int i=0;i<arr.length-2;i++) {
            if (arr[i+1]-arr[i]!=arr[i+1+1]-arr[i+1]) {
                return false;
            }
        }
        return true;
    }
}

896. 单调数列

如果数组是单调递增或单调递减的，那么它是单调的。

如果对于所有 i <= j，nums[i] <= nums[j]，那么数组 nums 是单调递增的。如果对于所有 i <= j，nums[i]> = nums[j]，那么数组 nums 是单调递减的。

当给定的数组 nums 是单调数组时返回 true，否则返回 false。

示例 1：

1
2
3

PLAINTEXT
输入：nums = [1,2,2,3]
输出：true

示例 2：

1
2
3

PLAINTEXT
输入：nums = [6,5,4,4]
输出：true

示例 3：

1
2
3

PLAINTEXT
输入：nums = [1,3,2]
输出：false

提示：

1 <= nums.length <= 105
-105 <= nums[i] <= 105

class Solution {
    public boolean isMonotonic(int[] nums) {
        if (nums.length<=2) {
            return true;
        }
        boolean increasing = true;
        boolean descreasing = true;
        for (int i=0;i<nums.length-1;i++) {
            if (nums[i+1]>nums[i]) {
                descreasing = false;
            }
            if (nums[i+1]<nums[i]) {
                increasing = false;
            }
        }
        return increasing || descreasing;
    }
}

13. 罗马数字转整数

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

PLAINTEXT
字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如，罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个罗马数字，将其转换成整数。

示例 1:

1
2
3

PLAINTEXT
输入: s = "III"
输出: 3

示例 2:

1
2
3

PLAINTEXT
输入: s = "IV"
输出: 4

示例 3:

1
2
3

PLAINTEXT
输入: s = "IX"
输出: 9

示例 4:

PLAINTEXT
输入: s = "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.

示例 5:

PLAINTEXT
输入: s = "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

提示：

1 <= s.length <= 15
s 仅含字符 ('I', 'V', 'X', 'L', 'C', 'D', 'M')
题目数据保证 s 是一个有效的罗马数字，且表示整数在范围 [1, 3999] 内
题目所给测试用例皆符合罗马数字书写规则，不会出现跨位等情况。
IL 和 IM 这样的例子并不符合题目要求，49 应该写作 XLIX，999 应该写作 CMXCIX 。
关于罗马数字的详尽书写规则，可以参考罗马数字 - Mathematics 。

class Solution {
    public int romanToInt(String s) {
        char[] chars = s.toCharArray();
        int preNum = getValue(chars[0]);
        int sum = 0;
        for (int i=1;i<s.length();i++) {
            int num = getValue(chars[i]);
            if (preNum < num) {
                sum -= preNum;
            } else {
                sum += preNum;
            }
            preNum = num;
        }
        sum += preNum;
        return sum;
    }

    private int getValue(char ch) {
        switch(ch) {
            case 'I' : return 1;
            case 'V' : return 5;
            case 'X' : return 10;
            case 'L' : return 50;
            case 'C' : return 100;
            case 'D' : return 500;
            case 'M' : return 1000;
            default: return 0;
        }
    }
}

58. 最后一个单词的长度

给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。

单词是指仅由字母组成、不包含任何空格字符的最大子字符串。

示例 1：

PLAINTEXT
输入：s = "Hello World"
输出：5
解释：最后一个单词是“World”，长度为5。

示例 2：

PLAINTEXT
输入：s = "   fly me   to   the moon  "
输出：4
解释：最后一个单词是“moon”，长度为4。

示例 3：

方法1：

PLAINTEXT
输入：s = "luffy is still joyboy"
输出：6
解释：最后一个单词是长度为6的“joyboy”。

方法2：

JAVA
class Solution {
    public int lengthOfLastWord(String s) {
        int n = s.length();
        int j = n - 1;
        while (j >= 0 && s.charAt(j) == ' ') j--;
        int i = j;
        while (i >= 0 && s.charAt(i) != ' ') i--;
        return j - i;
    }
}

方法3：

JAVA
class Solution {
    public int lengthOfLastWord(String s) {
        String[] array = s.split(" ");
        return array[array.length-1].length();
    }
}
JAVA
class Solution {
    public int lengthOfLastWord(String s) {
        s = s.trim();
        int  count = 0;
        for (int i=s.length()-1;i>=0;i--){
            if (s.charAt(i) == ' ') {
                return count;
            }
            count++;
        }
        return count;
    }
}

709. 转换成小写字母

给你一个字符串 s ，将该字符串中的大写字母转换成相同的小写字母，返回新的字符串。

示例 1：

1
2
3

PLAINTEXT
输入：s = "Hello"
输出："hello"

示例 2：

1
2
3

PLAINTEXT
输入：s = "here"
输出："here"

示例 3：

1
2
3

PLAINTEXT
输入：s = "LOVELY"
输出："lovely"

提示：

1 <= s.length <= 100
s 由 ASCII 字符集中的可打印字符组成

JAVA
class Solution {
    public String toLowerCase(String s) {
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] >= 'A' && chars[i] <= 'Z') {
                chars[i] = (char) (chars[i] + 'a' - 'A');
            }
        }
        return new String(chars);
    }
}

682. 棒球比赛

你现在是一场采用特殊赛制棒球比赛的记录员。这场比赛由若干回合组成，过去几回合的得分可能会影响以后几回合的得分。

比赛开始时，记录是空白的。你会得到一个记录操作的字符串列表 ops，其中 ops[i] 是你需要记录的第 i 项操作，ops 遵循下述规则：

整数 x - 表示本回合新获得分数 x
"+" - 表示本回合新获得的得分是前两次得分的总和。题目数据保证记录此操作时前面总是存在两个有效的分数。
"D" - 表示本回合新获得的得分是前一次得分的两倍。题目数据保证记录此操作时前面总是存在一个有效的分数。
"C" - 表示前一次得分无效，将其从记录中移除。题目数据保证记录此操作时前面总是存在一个有效的分数。

请你返回记录中所有得分的总和。

示例 1：

PLAINTEXT
输入：ops = ["5","2","C","D","+"]
输出：30
解释：
"5" - 记录加 5 ，记录现在是 [5]
"2" - 记录加 2 ，记录现在是 [5, 2]
"C" - 使前一次得分的记录无效并将其移除，记录现在是 [5].
"D" - 记录加 2 * 5 = 10 ，记录现在是 [5, 10].
"+" - 记录加 5 + 10 = 15 ，记录现在是 [5, 10, 15].
所有得分的总和 5 + 10 + 15 = 30

示例 2：

PLAINTEXT
输入：ops = ["5","-2","4","C","D","9","+","+"]
输出：27
解释：
"5" - 记录加 5 ，记录现在是 [5]
"-2" - 记录加 -2 ，记录现在是 [5, -2]
"4" - 记录加 4 ，记录现在是 [5, -2, 4]
"C" - 使前一次得分的记录无效并将其移除，记录现在是 [5, -2]
"D" - 记录加 2 * -2 = -4 ，记录现在是 [5, -2, -4]
"9" - 记录加 9 ，记录现在是 [5, -2, -4, 9]
"+" - 记录加 -4 + 9 = 5 ，记录现在是 [5, -2, -4, 9, 5]
"+" - 记录加 9 + 5 = 14 ，记录现在是 [5, -2, -4, 9, 5, 14]
所有得分的总和 5 + -2 + -4 + 9 + 5 + 14 = 27

示例 3：

PLAINTEXT
输入：ops = ["1"]
输出：1
JAVA
class Solution {
    public int calPoints(String[] operations) {
        int sum = 0;
        List<Integer> list = new ArrayList<>();
        for (int i=0;i<operations.length;i++) {
            if (operations[i].equals("+")) {
                list.add(list.get(list.size()-1) + list.get(list.size()-2));
            } else if (operations[i].equals("D")) {
                list.add(list.get(list.size()-1)*2);
            } else if (operations[i].equals("C")) {
                list.remove(list.size()-1);
            } else {
                list.add(Integer.parseInt(operations[i]));
            }
        }
        for (int value : list) {
            sum += value;
        }
        return sum;
    }
}
JAVA
class Solution {
    static int[] nums = new int[1010];
    public int calPoints(String[] ops) {
        int n = ops.length, idx = 0;
        for (int i = 0; i < n; i++, idx++) {
            if (ops[i].equals("+")) nums[idx] = nums[idx - 1] + nums[idx - 2];    
            else if (ops[i].equals("D")) nums[idx] = nums[idx - 1] * 2;
            else if (ops[i].equals("C")) idx -= 2;
            else nums[idx] = Integer.parseInt(ops[i]);
        }
        int ans = 0;
        for (int i = 0; i < idx; i++) ans += nums[i];
        return ans;
    }
}

657. 机器人能否返回原点

在二维平面上，有一个机器人从原点 (0, 0) 开始。给出它的移动顺序，判断这个机器人在完成移动后是否在 (0, 0) 处结束。

移动顺序由字符串 moves 表示。字符 move[i] 表示其第 i 次移动。机器人的有效动作有 R（右），L（左），U（上）和 D（下）。

如果机器人在完成所有动作后返回原点，则返回 true。否则，返回 false。

注意：机器人“面朝”的方向无关紧要。 “R” 将始终使机器人向右移动一次，“L” 将始终向左移动等。此外，假设每次移动机器人的移动幅度相同。

示例 1:

PLAINTEXT
输入: moves = "UD"
输出: true
解释：机器人向上移动一次，然后向下移动一次。所有动作都具有相同的幅度，因此它最终回到它开始的原点。因此，我们返回 true。

示例 2:

PLAINTEXT
输入: moves = "LL"
输出: false
解释：机器人向左移动两次。它最终位于原点的左侧，距原点有两次 “移动” 的距离。我们返回 false，因为它在移动结束时没有返回原点。

提示:

1 <= moves.length <= 2 * 104
moves 只包含字符 'U', 'D', 'L' 和 'R'

方法1：

JAVA
class Solution {
    public boolean judgeCircle(String moves) {
        int countU = 0;
        int countD = 0;
        int countL = 0;
        int countR = 0;
        for (int i=0;i<moves.length();i++) {
            if (moves.charAt(i) == 'U') {
                countU++;
            }
            if (moves.charAt(i) == 'D') {
                countD++;
            }
            if (moves.charAt(i) == 'L') {
                countL++;
            }
            if (moves.charAt(i) == 'R') {
                countR++;
            }
        }
        return countU == countD && countL == countR;
    }
}

思路2：

维护x和y记录机器人X轴和Y轴的移动距离，机器人向上移x++，反之x–

；机器人向左移y–，反之y++。

1041. 困于环中的机器人

在无限的平面上，机器人最初位于 (0, 0) 处，面朝北方。注意:

北方向 是y轴的正方向。
南方向 是y轴的负方向。
东方向 是x轴的正方向。
西方向 是x轴的负方向。

机器人可以接受下列三条指令之一：

"G"：直走 1 个单位
"L"：左转 90 度
"R"：右转 90 度

机器人按顺序执行指令 instructions，并一直重复它们。

只有在平面中存在环使得机器人永远无法离开时，返回 true。否则，返回 false。

JAVA
class Solution {
    public boolean isRobotBounded(String instructions) {
        // 定义初始位置和方向
        int x = 0;
        int y = 0;
        int direction = 0; // 0: 北, 1: 东, 2: 南, 3: 西
        
        // 定义移动方向数组：北，东，南，西
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        
        // 模拟机器人移动
        for (char instruction : instructions.toCharArray()) {
            if (instruction == 'G') {
                x += directions[direction][0];
                y += directions[direction][1];
            } else if (instruction == 'L') {
                direction = (direction + 3) % 4; // 左转90度，相当于方向-1
            } else if (instruction == 'R') {
                direction = (direction + 1) % 4; // 右转90度，相当于方向+1
            }
        }
        
        // 判断机器人是否回到原点或者方向不为北（因为北方是y轴的正方向）
        return (x == 0 && y == 0) || direction != 0;
    }
}

1672. 最富有客户的资产总量

给你一个 m x n 的整数网格 accounts ，其中 accounts[i][j] 是第 i 位客户在第 j 家银行托管的资产数量。返回最富有客户所拥有的 资产总量 。

客户的 资产总量 就是他们在各家银行托管的资产数量之和。最富有客户就是 资产总量 最大的客户。

示例 1：

PLAINTEXT
输入：accounts = [[1,2,3],[3,2,1]]
输出：6
解释：
第 1 位客户的资产总量 = 1 + 2 + 3 = 6
第 2 位客户的资产总量 = 3 + 2 + 1 = 6
两位客户都是最富有的，资产总量都是 6 ，所以返回 6 。

示例 2：

PLAINTEXT
输入：accounts = [[1,5],[7,3],[3,5]]
输出：10
解释：
第 1 位客户的资产总量 = 6
第 2 位客户的资产总量 = 10 
第 3 位客户的资产总量 = 8
第 2 位客户是最富有的，资产总量是 10

示例 3：

PLAINTEXT
输入：accounts = [[2,8,7],[7,1,3],[1,9,5]]
输出：17
JAVA
class Solution {
    public int maximumWealth(int[][] accounts) {
        int maxNum = 0;
        for (int i=0;i<accounts.length;i++) {
            int sum = 0;
            for (int j=0;j<accounts[0].length;j++) {
                sum += accounts[i][j];
                maxNum = Math.max(maxNum, sum);
            }
        }
        return maxNum;
    }
}

1572. 矩阵对角线元素的和

给你一个正方形矩阵 mat，请你返回矩阵对角线元素的和。

请你返回在矩阵主对角线上的元素和副对角线上且不在主对角线上元素的和。

示例 1：

PLAINTEXT
输入：mat = [[1,2,3],
            [4,5,6],
            [7,8,9]]
输出：25
解释：对角线的和为：1 + 5 + 9 + 3 + 7 = 25
请注意，元素 mat[1][1] = 5 只会被计算一次。

示例 2：

PLAINTEXT
输入：mat = [[1,1,1,1],
            [1,1,1,1],
            [1,1,1,1],
            [1,1,1,1]]
输出：8

示例 3：

PLAINTEXT
输入：mat = [[5]]
输出：5
JAVA
class Solution {
    public int diagonalSum(int[][] mat) {
        int sum = 0;
        for (int i=0;i<mat.length;i++) {
            sum += mat[i][i];
            sum += mat[i][mat.length-i-1];
        }
        if (mat.length%2 != 0) {
                    return sum - mat[mat.length/2][mat.length/2];
        }
        return sum;
    }
}

54. 螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

示例 1：

1
2
3

PLAINTEXT
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

示例 2：

1
2
3

PLAINTEXT
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 100

思路：用四个变量跟踪未遍历矩阵的四个边界。初始时，top 初始化为0（矩阵的顶部），bottom 初始化为矩阵的行数减一（矩阵的底部），left 初始化为0（矩阵的左侧），right 初始化为矩阵的列数减一（矩阵的右侧）。

在循环内部：

第一个循环遍历矩阵的上边界，从左到右。
第二个循环遍历矩阵的右边界，从上到下。
第三个循环遍历矩阵的下边界，从右到左。
第四个循环遍历矩阵的左边界，从下到上。

在每次遍历完一个边界后，我们相应地更新边界的位置，并确保仍有剩余的元素需要遍历。这通过检查 top <= bottom 和 left <= right 来实现。如果上边界 top 小于等于下边界 bottom，则仍有行未被遍历，如果左边界 left 小于等于右边界 right，则仍有列未被遍历。

JAVA
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> result = new ArrayList<>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return result;
        int top = 0, bottom = matrix.length - 1;
        int left = 0, right = matrix[0].length - 1;
        while (top <= bottom && left <= right) {
            // 从左到右遍历上边界
            for (int i = left; i <= right; i++)
                result.add(matrix[top][i]);
            top++;
            // 从上到下遍历右边界
            for (int i = top; i <= bottom; i++)
                result.add(matrix[i][right]);
            right--;
            // 从右到左遍历下边界
            if (top <= bottom) {
                for (int i = right; i >= left; i--)
                    result.add(matrix[bottom][i]);
                bottom--;
            }
            // 从下到上遍历左边界
            if (left <= right) {
                for (int i = bottom; i >= top; i--)
                    result.add(matrix[i][left]);
                left++;
            }
        }
        return result;
    }
}

73. 矩阵置零

给定一个 *m* x *n* 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用原地算法。

示例 1：

1
2
3

PLAINTEXT
输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

示例 2：

1
2
3

PLAINTEXT
输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

提示：

m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
-231 <= matrix[i][j] <= 231 - 1

方法1：

JAVA
class Solution {
    public void setZeroes(int[][] matrix) {
        List<Integer> list1= new ArrayList<>();
        List<Integer> list2= new ArrayList<>();
        for (int i=0;i<matrix.length;i++) {
            for (int j=0;j<matrix[0].length;j++) {
                if (matrix[i][j] == 0) {
                    list1.add(i);
                    list2.add(j);
                }
            }
        }
        for (int x : list1) {
            for (int k=0;k<matrix[0].length;k++) {
                matrix[x][k]=0;
             }
        }
        for (int y : list2) {
             for (int k=0;k<matrix.length;k++) {
                matrix[k][y]=0;
            }
        }
    }
}

方法2：

JAVA

1523. 在区间范围内统计奇数数目

给你两个非负整数 low 和 high 。请你返回 low 和 high 之间（包括二者）奇数的数目。

示例 1：

PLAINTEXT
输入：low = 3, high = 7
输出：3
解释：3 到 7 之间奇数数字为 [3,5,7] 。

示例 2：

PLAINTEXT
输入：low = 8, high = 10
输出：1
解释：8 到 10 之间奇数数字为 [9] 。

提示：

0 <= low <= high <= 10^9

方法1:

JAVA
class Solution {
    public int countOdds(int low, int high) {
        int sum = 0;
        if (low%2!=0) {
            for (int i=low;i<=high;i+=2) {
                sum++;
            }
            return sum;
        } else {
            for (int i=low;i<=high;i+=2) {
                sum++;
            }
            return sum - ( high%2==0 ? 1 : 0);
        }
    }
}

方法2：（超时）

JAVA
class Solution {
    public int countOdds(int low, int high) {
        int sum = 0;
        for (int i=low;i<=high;i++) {
            if (i%2!=0) {
                sum++;
            }
        }
        return sum;
    }
}

1491. 去掉最低工资和最高工资后的工资平均值

给你一个整数数组 salary ，数组里每个数都是唯一的，其中 salary[i] 是第 i 个员工的工资。

请你返回去掉最低工资和最高工资以后，剩下员工工资的平均值。

示例 1：

PLAINTEXT
输入：salary = [4000,3000,1000,2000]
输出：2500.00000
解释：最低工资和最高工资分别是 1000 和 4000 。
去掉最低工资和最高工资以后的平均工资是 (2000+3000)/2= 2500

示例 2：

PLAINTEXT
输入：salary = [1000,2000,3000]
输出：2000.00000
解释：最低工资和最高工资分别是 1000 和 3000 。
去掉最低工资和最高工资以后的平均工资是 (2000)/1= 2000

示例 3：

1
2
3

PLAINTEXT
输入：salary = [6000,5000,4000,3000,2000,1000]
输出：3500.00000

示例 4：

1
2
3

PLAINTEXT
输入：salary = [8000,9000,2000,3000,6000,1000]
输出：4750.00000

提示：

3 <= salary.length <= 100
10^3 <= salary[i] <= 10^6
salary[i] 是唯一的。
与真实值误差在 10^-5 以内的结果都将视为正确答案。

注意：平均值是小数，要用double或者float类型。

JAVA
class Solution {
    public double average(int[] salary) {
        double sum=0;
        int maxNum=0;
        int minNum=salary[0];
        int count = salary.length-2;
        for (int x : salary) {
            sum+=x;
            maxNum=Math.max(maxNum,x);
            minNum=Math.min(minNum,x);
        }
        return (sum-maxNum-minNum) / count;
    }
}

860. 柠檬水找零

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

注意，一开始你手头没有任何零钱。

给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

示例 1：

PLAINTEXT
输入：bills = [5,5,5,10,20]
输出：true
解释：
前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零，所以我们输出 true。

示例 2：

PLAINTEXT
输入：bills = [5,5,10,10,20]
输出：false
解释：
前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。
对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。
对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。
由于不是每位顾客都得到了正确的找零，所以答案是 false。

提示：

1 <= bills.length <= 105
bills[i] 不是 5 就是 10 或是 20

JAVA
class Solution {
    public boolean lemonadeChange(int[] bills) {
        int five = 0;
        int ten = 0;
        List<Integer> list = new ArrayList<>();
        for (int x : bills) {
            if (x==5) {
                five++;
            } else if (x==10) {
                if (five > 0) {
                    five--;
                    ten++;
                } else {
                    return false;
                }
            } else if (x==20) {
                if (five > 0 && ten > 0) {
                    five--;
                    ten--;
                }
                else if (five >= 3) {
                    five -= 3;
                } else {
                    return false;
                }
            }
        }
        return true;
    }
}

976. 三角形的最大周长

给定由一些正数（代表长度）组成的数组 nums ，返回 由其中三个长度组成的、面积不为零的三角形的最大周长 。如果不能形成任何面积不为零的三角形，返回 0。

示例 1：

PLAINTEXT
输入：nums = [2,1,2]
输出：5
解释：你可以用三个边长组成一个三角形:1 2 2。

示例 2：

PLAINTEXT
输入：nums = [1,2,1,10]
输出：0
解释：
你不能用边长 1,1,2 来组成三角形。
不能用边长 1,1,10 来构成三角形。
不能用边长 1、2 和 10 来构成三角形。
因为我们不能用任何三条边长来构成一个非零面积的三角形，所以我们返回 0。

提示：

3 <= nums.length <= 104
1 <= nums[i] <= 106

重点：

判断三个边是否能构成三角形
如果能构成三角形则判断其周长是不是最长的
遍历数组的 3 个边验证是否有三角形，有就返回最当周长，反之返回 0
因为数组是有序的，所以 x < y < z，只需验证 x + y ?> z，如果成立则一定是三角形，否则则不是

JAVA
class Solution {
    public int largestPerimeter(int[] nums) {
        int maxNum = 0;
        boolean hasTriangle = false;
        Arrays.sort(nums);
        for (int i=0;i<nums.length-2;i++) {
            if (isTriangle(nums[i], nums[i+1], nums[i+1+1])) {
                maxNum = Math.max(maxNum, nums[i] + nums[i+1] + nums[i+2]);
                hasTriangle = true;
            }
        }
        if (hasTriangle) {
            return maxNum;
        }
        return 0;
    }

    public boolean isTriangle(int side1, int side2, int side3) {
        return side1 + side2 > side3;
    }
}

1232. 缀点成线

给定一个数组 coordinates ，其中 coordinates[i] = [x, y] ， [x, y] 表示横坐标为 x、纵坐标为 y 的点。请你来判断，这些点是否在该坐标系中属于同一条直线上。

示例 1：

1
2
3

PLAINTEXT
输入：coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]]
输出：true

示例 2：

1
2
3

PLAINTEXT
输入：coordinates = [[1,1],[2,2],[3,4],[4,5],[5,6],[7,7]]
输出：false

提示：

2 <= coordinates.length <= 1000
coordinates[i].length == 2
-10^4 <= coordinates[i][0], coordinates[i][1] <= 10^4
coordinates 中不含重复的点

思路：

验证所有点在不在一个直线上，其实就是验证任意三个点的斜率是否相同（高中知识）。以前两个点连成的直线为标准直线，验证第三个点是否在直线上，如果全部都在说明都在直线上，有一个不在说明所有点构成不了一条直线。解法如下：

JAVA
class Solution {
    public boolean checkStraightLine(int[][] coordinates) {
        int len = coordinates.length;

        for (int i = 1; i < len - 1; ++i) {
            int y1 = coordinates[i][1] -coordinates[i-1][1];
            int x1 = coordinates[i][0] -coordinates[i-1][0];
            int y2 = coordinates[i+1][1] -coordinates[i][1];         
            int x2 = coordinates[i+1][0] -coordinates[i][0];
            if (y1*x2 != y2*x1) {
                return false;
            }
            
        }
        return true;

    }
}

21. 合并两个有序链表

示例 1：

1
2
3

PLAINTEXT
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

1
2
3

PLAINTEXT
输入：l1 = [], l2 = []
输出：[]

示例 3：

1
2
3

PLAINTEXT
输入：l1 = [], l2 = [0]
输出：[0]

提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

JAVA
/**
 * 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 mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        if (list1.val < list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}

206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

1
2
3

PLAINTEXT
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

1
2
3

PLAINTEXT
输入：head = [1,2]
输出：[2,1]

示例 3：

1
2
3

PLAINTEXT
输入：head = []
输出：[]

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

方法1：迭代（双指针）

JAVA
/**
 * 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 reverseList(ListNode head) {
        ListNode cur=head, pre=null;
        while (cur!=null) {
            ListNode tmp = cur.next;
            cur.next=pre;
            pre=cur;
            cur=tmp;
        }
        return pre;
    }
}

方法2：递归

JAVA
class Solution {
    public ListNode reverseList(ListNode head) {
        return recur(head, null);    // 调用递归并返回
    }
    private ListNode recur(ListNode cur, ListNode pre) {
        if (cur == null) return pre; // 终止条件
        ListNode res = recur(cur.next, cur);  // 递归后继节点
        cur.next = pre;              // 修改节点引用指向
        return res;                  // 返回反转链表的头节点
    }
}

67. 二进制求和

给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。

示例 1：

1
2
3

PLAINTEXT
输入:a = "11", b = "1"
输出："100"

示例 2：

1
2
3

PLAINTEXT
输入：a = "1010", b = "1011"
输出："10101"

提示：

1 <= a.length, b.length <= 104
a 和 b 仅由字符 '0' 或 '1' 组成
字符串如果不是 "0" ，就不含前导零

JAVA
class Solution {
    public String addBinary(String a, String b) {
        StringBuilder ans = new StringBuilder();
        int ca = 0;
        for(int i = a.length() - 1, j = b.length() - 1;i >= 0 || j >= 0; i--, j--) {
            int sum = ca;
            sum += i >= 0 ? a.charAt(i) - '0' : 0;
            sum += j >= 0 ? b.charAt(j) - '0' : 0;
            ans.append(sum % 2);
            ca = sum / 2;
        }
        ans.append(ca == 1 ? ca : "");
        return ans.reverse().toString();
    }
}

27. 移除元素

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

示例 1：

1
2
3

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

示例 2：

1
2
3

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,3,0,4]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

提示：

0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100

方法一（双指针）：

class Solution {
    public int removeElement(int[] nums, int val) {
        int left = 0;
        int right = nums.length;
        while (left < right) {
            if (nums[left] == val) {
                nums[left] = nums[right - 1];
                right--;
            } else {
                left++;
            }
        }
        return left;
    }
}

方法二（覆盖移除）：

class Solution {
    public int removeElement(int[] nums, int val) {
        int ans = 0;
        for(int num: nums) {
            if(num != val) {
                nums[ans] = num;
                ans++;
            }
        }
        return ans;
    }
}

面试经典 150 题

169. 多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

1 2	输入：nums = [3,2,3] 输出：3

示例 2：

1 2	输入：nums = [2,2,1,1,1,2,2] 输出：2

提示：

n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109

进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

方法一（暴力统计哈希）：

class Solution {
    public int majorityElement(int[] nums) {
                int len = nums.length;
        Map<Integer, Integer> map = new HashMap<>();
        for (int x : nums) {
            map.put(x, map.getOrDefault(x, 0) + 1);
        }
        int max = Integer.MIN_VALUE;
        for (Map.Entry entry : map.entrySet()) {
            int value = (int) entry.getValue();
            max = Math.max(max, value);
        }
        for (Map.Entry entry : map.entrySet()) {
            if (((int) entry.getValue()) == max) {
                return (int) entry.getKey();
            }
        }
        return nums[0];
    }
}

方法二（简易版哈希）：

public int majorityElement(int[] nums) {
    Map<Integer,Integer> counts = new HashMap<>();
    int maxNum = 0;
    int maxCount = 0;
    for (int i:nums){
        int count = counts.getOrDefault(i,0) + 1;
        counts.put(i,count);

        if (count>maxCount){
            maxNum = i;
            maxCount = count;
        }
    }
    return maxNum;
}

方法三（摩尔投票）：

public int majorityElement(int[] nums) {
    int candidate = nums[0];
    int count = 1;
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] == candidate) {
            count++;
        } else {
            count--;
            if (count == 0) {
                candidate = nums[i];
                count = 1;
            }
        }
    }
    return candidate;
}

189. 轮转数组

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

提示：

1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105

方法一：

class Solution {
    public void rotate(int[] nums, int k) {
        if (nums.length == 1 || k == 0) {
            return;
        }
        int len = nums.length;
        List<Integer> list = new ArrayList<>();
        for (int i=nums.length-k%len;i<len;i++) {
            list.add(nums[i]);
        }
        for (int i=0;i<len-k%len;i++) {
            list.add(nums[i]);
        }
        for (int i=0;i<list.size();i++) {
            nums[i] = list.get(i);
        }
    }
}

方法二（）：

思路：

首先对整个数组实行翻转，这样子原数组中需要翻转的子数组，就会跑到数组最前面。
这时候，从 k 处分隔数组，左右两数组，各自进行翻转即可。

class Solution {
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }
    public void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start += 1;
            end -= 1;
        }
    }
}

方法三（使用额外的数组）：

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        int[] newArr = new int[n];
        for (int i = 0; i < n; ++i) {
            newArr[(i + k) % n] = nums[i];
        }
        System.arraycopy(newArr, 0, nums, 0, n);
    }
}

121. 买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：

1
2
3

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

1 <= prices.length <= 105
0 <= prices[i] <= 104

class Solution {
    public int maxProfit(int[] prices) {
        int min = Integer.MAX_VALUE;
        int profit = 0;
        for(int i = 0;i<prices.length;i++){
            min = Math.min(min,prices[i]);
            profit = Math.max(profit,prices[i] - min);
        }
        return profit;
    }
}

122. 买卖股票的最佳时机 II

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的最大利润 。

示例 1：

输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
     总利润为 4 + 3 = 7 。

示例 2：

输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
     总利润为 4 。

示例 3：

1
2
3

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。

提示：

1 <= prices.length <= 3 * 104
0 <= prices[i] <= 104

思路：

遍历整个股票交易日价格列表 price，并执行贪心策略：所有上涨交易日都买卖（赚到所有利润），所有下降交易日都不买卖（永不亏钱）。

设 tmp 为第 i-1 日买入与第 i 日卖出赚取的利润，即 tmp = prices[i] - prices[i - 1] ；
当该天利润为正 tmp > 0，则将利润加入总利润 profit；当利润为 000 或为负，则直接跳过；
遍历完成后，返回总利润 profit。

class Solution {
    public int maxProfit(int[] prices) {
        int count = 0;
        int len = prices.length;
        for (int i=0;i<len-1;i++) {
            if (prices[i+1] - prices[i] > 0) {
                count += prices[i+1] - prices[i];
            }
        }
        return count;
    }
}

55. 跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false

示例 1：

1
2
3

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

1
2
3

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

提示：

1 <= nums.length <= 104
0 <= nums[i] <= 105

思路：

方法一：

class Solution {
    public boolean canJump(int[] nums) {
        int len = nums.length;
        if (len == 1) {
            return true;
        }
        
        int maxReach = 0; // 当前能够到达的最远位置
        
        for (int i = 0; i < len; i++) {
            // 如果当前位置超过了能够到达的最远位置，则无法继续跳跃到达终点
            if (i > maxReach) {
                return false;
            }
            // 更新当前能够到达的最远位置
            maxReach = Math.max(maxReach, i + nums[i]);
            
            // 如果最远位置已经能够到达终点，则可以提前返回true
            if (maxReach >= len - 1) {
                return true;
            }
        }
        
        return false;
    }
}

方法二：

class Solution {
    public boolean canJump(int[] nums) {
        int len = nums.length;
        if (len == 1) {
            return true;
        }
        if (nums[0] >= len) {
            return true;
        }
        int cover = 0;
        for (int i=0;i<=cover;i++) {
            cover = Math.max(cover, i + nums[i]);
            if (cover >= nums.length - 1) {
                return true;
            }
        }
        return false;
    }
}

45. 跳跃游戏 II

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

0 <= j <= nums[i]
i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例 2:

1 2	输入: nums = [2,3,0,1,4] 输出: 2

提示:

1 <= nums.length <= 104
0 <= nums[i] <= 1000
题目保证可以到达 nums[n-1]

class Solution {
    public int jump(int[] nums) {
        int end = 0;
        int maxPosition = 0; 
        int steps = 0;
        for(int i = 0; i < nums.length - 1; i++){
            //找能跳的最远的
            maxPosition = Math.max(maxPosition, nums[i] + i); 
            if( i == end){ //遇到边界，就更新边界，并且步数加一
                end = maxPosition;
                steps++;
            }
        }
        return steps;
    }
}

380. O(1) 时间插入、删除和获取随机元素

实现RandomizedSet 类：

RandomizedSet() 初始化 RandomizedSet 对象
bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。

你必须实现类的所有函数，并满足每个函数的平均时间复杂度为 O(1) 。

示例：

输入
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
输出
[null, true, false, true, 2, true, false, 2]

解释
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomizedSet.remove(2); // 返回 false ，表示集合中不存在 2 。
randomizedSet.insert(2); // 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomizedSet.getRandom(); // getRandom 应随机返回 1 或 2 。
randomizedSet.remove(1); // 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
randomizedSet.insert(2); // 2 已在集合中，所以返回 false 。
randomizedSet.getRandom(); // 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。

提示：

-231 <= val <= 231 - 1
最多调用 insert、remove 和 getRandom 函数 2 * ``105 次
在调用 getRandom 方法时，数据结构中 至少存在一个 元素。

class RandomizedSet {

    private List<Integer> list;

    private Random random;

    public RandomizedSet() {
        this.list = new ArrayList<>();
        this.random = new Random();
    }
    
    public boolean insert(int val) {
        if (list.contains(val)) {
            return false;
        }
        list.add(val);
        return true;
    }
    
    public boolean remove(int val) {
        boolean b = false;
        for (int i=0;i<list.size();i++) {
            if (val == list.get(i)) {
                list.remove(i);
                b = true;
            }
        }
        return b;
    }
    
    public int getRandom() {
        if (list.size() < 1) {
            return -1;
        }
        int idx = random.nextInt(list.size());
        return list.get(idx);
    }
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */

238. 除自身以外数组的乘积

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 不要使用除法，且在 O(*n*) 时间复杂度内完成此题。

示例 1:

1 2	输入: nums = [1,2,3,4] 输出: [24,12,8,6]

示例 2:

1 2	输入: nums = [-1,1,0,-3,3] 输出: [0,0,9,0,0]

提示：

2 <= nums.length <= 105
-30 <= nums[i] <= 30
保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内

进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。

方法一（前缀积、后缀积）：

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int numsLen = nums.length;
        int[] prefix = new int[numsLen];
        int[] postfix = new int[numsLen];
        int[] res = new int[numsLen];

        // 预生成前缀积数组
        prefix[0] = 1;
        for (int i = 1; i < numsLen; ++i) {
            prefix[i] = prefix[i-1] * nums[i-1];
        }

        // 预生成后缀积数组
        postfix[numsLen - 1] = 1;
        for (int j = numsLen - 2; j >= 0; --j) {
            postfix[j] = postfix[j+1] * nums[j+1];
        }

        // 生成结果
        for (int k = 0; k < numsLen; ++k) {
            res[k] = prefix[k] * postfix[k];
        }

        return res;
    }
}

方法二（除法）：

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int len = nums.length;
        int[] array = new int[len];
        int ans = 1;
        for (int i=0;i<len;i++) {
            ans = nums[i] * ans;
        }
        for (int i=0;i<len;i++) {
            if (nums[i] == 0) {
                int sum = 1;
                for (int j=0;j<len;j++) {
                    if (j != i) {
                        sum *= nums[j];
                    }
                }
                array[i] = sum;
            } else {
                array[i] = ans / nums[i];
            }
        }
        return array;
    }
}

2244. 完成所有任务需要的最少轮数

给你一个下标从 0 开始的整数数组 tasks ，其中 tasks[i] 表示任务的难度级别。在每一轮中，你可以完成 2 个或者 3 个 相同难度级别 的任务。

返回完成所有任务需要的最少轮数，如果无法完成所有任务，返回 -1 。

示例 1：

输入：tasks = [2,2,3,3,2,4,4,4,4,4]
输出：4
解释：要想完成所有任务，一个可能的计划是：
- 第一轮，完成难度级别为 2 的 3 个任务。 
- 第二轮，完成难度级别为 3 的 2 个任务。 
- 第三轮，完成难度级别为 4 的 3 个任务。 
- 第四轮，完成难度级别为 4 的 2 个任务。 
可以证明，无法在少于 4 轮的情况下完成所有任务，所以答案为 4 。

示例 2：

1
2
3

输入：tasks = [2,3,3]
输出：-1
解释：难度级别为 2 的任务只有 1 个，但每一轮执行中，只能选择完成 2 个或者 3 个相同难度级别的任务。因此，无法完成所有任务，答案为 -1 。

提示：

1 <= tasks.length <= 105
1 <= tasks[i] <= 109

方法一：

https://leetcode.cn/problems/minimum-rounds-to-complete-all-tasks/solutions/1427626/ha-xi-biao-tan-xin-by-endlesscheng-tgtf/

public class Solution {
    public int minimumRounds(int[] tasks) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int t : tasks) {
            cnt.merge(t, 1, Integer::sum);
        }
        int ans = 0;
        for (int c : cnt.values()) {
            if (c == 1) {
                return -1;
            }	
            ans += (c + 2) / 3;
        }
        return ans;
    }

方法二：

class Solution {
    public int minimumRounds(int[] tasks) {
        int len = tasks.length;
        if (len == 1) {
            return -1;
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int i=0;i<len;i++) {
            map.put(tasks[i], map.getOrDefault(tasks[i], 0) + 1);
        }
        int ans = 0;
        for (Map.Entry entry : map.entrySet()) {
            int value = (int) entry.getValue();
            if (value < 2) {
                return -1;
            }
            else {
                if (value % 3 ==0) {
                    ans += value / 3;
                    continue;
                }
                if ((value - 2) % 3 == 0) {
                    ans += 1;
                    ans += (value - 2) / 3;
                    continue;
                } 
                if ((value - 4) % 3 == 0) {
                    ans += 2;
                    ans += (value -4 ) /3;
                }
            }
        }
        return ans;
    }
}

134. 加油站

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则保证它是唯一的

示例 1:

输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。

示例 2:

输入: gas = [2,3,4], cost = [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。

提示:

gas.length == n
cost.length == n
1 <= n <= 105
0 <= gas[i], cost[i] <= 104

思路：先判断当前油量是否能够跑到下一个加油站，如果不能就换个起点，统计每次到达加油站的油量，大于 0 就返回，否则就返回 -1

方法一：

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int totalNum = 0;
        int curNum = 0;
        int idx = 0;

        for (int i = 0; i < gas.length; i++) {
            curNum += gas[i] - cost[i];
            totalNum += gas[i] - cost[i];
            if (curNum < 0) {
                idx = (i+1) % gas.length;
                curNum = 0;
            }

        }

        if(totalNum < 0) return -1;
        return idx;
    }
}

135. 分发糖果

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

示例 1：

1
2
3

输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

示例 2：

输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
     第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。

提示：

n == ratings.length
1 <= n <= 2 * 104
0 <= ratings[i] <= 2 * 104

class Solution {
    public int candy(int[] ratings) {
        if (ratings.length == 1) {
            return 1;
        }
        if (ratings.length == 2) {
            if (ratings[0] != ratings[1]) {
                return 3;
            } else {
                return 2;
            }
        }
        int len = ratings.length;
        int[] count = new int[len];
        Arrays.fill(count, 1);
        for (int i=1;i<len;i++) {
            if (ratings[i] > ratings[i-1]) {
                count[i] = count[i-1] + 1;
            }
        }
        for (int i=len-2;i>=0;i--) {
            if (ratings[i] > ratings[i+1]) {
                count[i] = Math.max(count[i], count[i+1] + 1);
            }
        }
        int ans = 0;
        for (int x : count) {
            ans += x;
        }
        return ans;
    }
}

13. 罗马数字转整数

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如，罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个罗马数字，将其转换成整数。

示例 1:

1 2	输入: s = "III" 输出: 3

示例 2:

1 2	输入: s = "IV" 输出: 4

示例 3:

1 2	输入: s = "IX" 输出: 9

示例 4:

1
2
3

输入: s = "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.

示例 5:

1
2
3

输入: s = "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

提示：

1 <= s.length <= 15
s 仅含字符 ('I', 'V', 'X', 'L', 'C', 'D', 'M')
题目数据保证 s 是一个有效的罗马数字，且表示整数在范围 [1, 3999] 内
题目所给测试用例皆符合罗马数字书写规则，不会出现跨位等情况。
IL 和 IM 这样的例子并不符合题目要求，49 应该写作 XLIX，999 应该写作 CMXCIX 。
关于罗马数字的详尽书写规则，可以参考罗马数字 - Mathematics 。

class Solution {
    public int romanToInt(String s) {
        // 哈希表
        HashMap<Character, Integer> map = new HashMap<>();
        char[] chars = {'I', 'V', 'X', 'L', 'C', 'D', 'M'};
        int[] vals = {1, 5, 10, 50, 100, 500, 1000};
        for (int i = 0; i < 7; i++)
            map.put(chars[i], vals[i]);
        int n = s.length();
        int ans = 0;
        int max = Integer.MIN_VALUE;
        for (int i = n - 1; i > -1; i--) {
            int val = map.get(s.charAt(i));
            if (val >= max) {
                ans += val;
                // 更新最大值
                max = val;
            } else {
                ans -= val;
            }
        }
        return ans;
    }
}

12. 整数转罗马数字

七个不同的符号代表罗马数字，其值如下：

符号	值
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

罗马数字是通过添加从最高到最低的小数位值的转换而形成的。将小数位值转换为罗马数字有以下规则：

如果该值不是以 4 或 9 开头，请选择可以从输入中减去的最大值的符号，将该符号附加到结果，减去其值，然后将其余部分转换为罗马数字。
如果该值以 4 或 9 开头，使用 减法形式，表示从以下符号中减去一个符号，例如 4 是 5 (V) 减 1 (I): IV ，9 是 10 (X) 减 1 (I)：IX。仅使用以下减法形式：4 (IV)，9 (IX)，40 (XL)，90 (XC)，400 (CD) 和 900 (CM)。
只有 10 的次方（I, X, C, M）最多可以连续附加 3 次以代表 10 的倍数。你不能多次附加 5 (V)，50 (L) 或 500 (D)。如果需要将符号附加4次，请使用 减法形式。

给定一个整数，将其转换为罗马数字。

示例 1：

输入：num = 3749

输出： “MMMDCCXLIX”

解释：

3000 = MMM 由于 1000 (M) + 1000 (M) + 1000 (M)
 700 = DCC 由于 500 (D) + 100 (C) + 100 (C)
  40 = XL 由于 50 (L) 减 10 (X)
   9 = IX 由于 10 (X) 减 1 (I)
注意：49 不是 50 (L) 减 1 (I) 因为转换是基于小数位

示例 2：

输入：num = 58

输出：“LVIII”

解释：

1 2	50 = L 8 = VIII

示例 3：

输入：num = 1994

输出：“MCMXCIV”

解释：

1000 = M
 900 = CM
  90 = XC
   4 = IV

提示：

1 <= num <= 3999

public class Solution {

    public String intToRoman(int num) {
        // 把阿拉伯数字与罗马数字可能出现的所有情况和对应关系，放在两个数组中，并且按照阿拉伯数字的大小降序排列
        int[] nums = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] romans = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

        StringBuilder stringBuilder = new StringBuilder();
        int index = 0;
        while (index < 13) {
            // 特别注意：这里是等号
            while (num >= nums[index]) {
                stringBuilder.append(romans[index]);
                num -= nums[index];
            }
            index++;
        }
        return stringBuilder.toString();
    }
}

58. 最后一个单词的长度

给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。

单词是指仅由字母组成、不包含任何空格字符的最大子字符串。

示例 1：

1
2
3

输入：s = "Hello World"
输出：5
解释：最后一个单词是“World”，长度为 5。

示例 2：

1
2
3

输入：s = "   fly me   to   the moon  "
输出：4
解释：最后一个单词是“moon”，长度为 4。

示例 3：

1
2
3

输入：s = "luffy is still joyboy"
输出：6
解释：最后一个单词是长度为 6 的“joyboy”。

提示：

1 <= s.length <= 104
s 仅有英文字母和空格 ' ' 组成
s 中至少存在一个单词

class Solution {
    public int lengthOfLastWord(String s) {
        if(s == null || s.length() == 0) return 0;
        int count = 0;
        for(int i = s.length()-1; i >= 0; i--){
            if(s.charAt(i) == ' '){
                if(count == 0) continue;
                break;
            }
            count++;
        }
        return count;
    }
}

14. 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例 1：

1 2	输入：strs = ["flower","flow","flight"] 输出："fl"

示例 2：

1
2
3

输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。

提示：

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs.length==0)return "";
        //公共前缀比所有字符串都短，随便选一个先
        String s=strs[0];
        for (String string : strs) {
            while(!string.startsWith(s)){
                if(s.length()==0)return "";
                //公共前缀不匹配就让它变短！
                s=s.substring(0,s.length()-1);
            }
        }
        return s;
    }
}

151. 反转字符串中的单词

给你一个字符串 s ，请你反转字符串中单词的顺序。

单词是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。

返回单词顺序颠倒且单词之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：

1 2	输入：s = "the sky is blue" 输出："blue is sky the"

示例 2：

1
2
3

输入：s = "  hello world  "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。

示例 3：

1
2
3

输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

提示：

1 <= s.length <= 104
s 包含英文大小写字母、数字和空格 ' '
s 中 至少存在一个 单词

class Solution {
    public String reverseWords(String s) {
        s = s.trim();
        String[] strings = s.split(" ");
        int len = strings.length;
        StringBuilder sb = new StringBuilder();
        for (int i=len-1;i>-1;i--) {
            if (strings[i].length() > 0) {
                sb.append(strings[i]);
                if (i > 0) {
                    sb.append(" ");
                }
            }
        }
        return sb.toString();
    }
}

6. Z 字形变换

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

1
2
3

P   A   H   N
A P L S I I G
Y   I   R

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

请你实现这个将字符串进行指定行数变换的函数：

1	string convert(string s, int numRows);

示例 1：

1 2	输入：s = "PAYPALISHIRING", numRows = 3 输出："PAHNAPLSIIGYIR"

示例 2：

输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P     I    N
A   L S  I G
Y A   H R
P     I

示例 3：

1 2	输入：s = "A", numRows = 1 输出："A"

提示：

1 <= s.length <= 1000
s 由英文字母（小写和大写）、',' 和 '.' 组成
1 <= numRows <= 1000

class Solution {
    public String convert(String s, int numRows) {
        if(numRows < 2) return s;
        List<StringBuilder> rows = new ArrayList<StringBuilder>();
        for(int i = 0; i < numRows; i++) rows.add(new StringBuilder());
        int i = 0, flag = -1;
        for(char c : s.toCharArray()) {
            rows.get(i).append(c);
            if(i == 0 || i == numRows -1) flag = - flag;
            i += flag;
        }
        StringBuilder res = new StringBuilder();
        for(StringBuilder row : rows) res.append(row);
        return res.toString();
    }
}

28. 找出字符串中第一个匹配项的下标

示例 1：

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：

1
2
3

输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1

提示：

1 <= haystack.length, needle.length <= 104
haystack 和 needle 仅由小写英文字符组成

class Solution {
    public int strStr(String haystack, String needle) {
        String replaced = haystack.replace(needle, "1");
        if (haystack.equals(replaced)) {
            return -1;
        }
        char[] h = replaced.toCharArray();
        for (int i=0;i<h.length;i++) {
            if (h[i] == '1') {
                return i;
            }
        }
        return -1;
    }
}

125. 验证回文串

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

示例 1：

1
2
3

输入: s = "A man, a plan, a canal: Panama"
输出：true
解释："amanaplanacanalpanama" 是回文串。

示例 2：

1
2
3

输入：s = "race a car"
输出：false
解释："raceacar" 不是回文串。

示例 3：

输入：s = " "
输出：true
解释：在移除非字母数字字符之后，s 是一个空字符串 "" 。
由于空字符串正着反着读都一样，所以是回文串。

提示：

1 <= s.length <= 2 * 105
s 仅由可打印的 ASCII 字符组成

class Solution {
    public boolean isPalindrome(String s) {
        s = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
        char[] chars = s.toCharArray();
        int left = 0;
        int right = chars.length - 1;
        while (left < right) {
            if (chars[left] == chars[right]) {
                left++;
                right--;
            } else {
                return false;
            }
        }
        return true;
    }
}

392. 判断子序列

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

进阶：

如果有大量输入的 S，称作 S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

示例 1：

1 2	输入：s = "abc", t = "ahbgdc" 输出：true

示例 2：

1 2	输入：s = "axc", t = "ahbgdc" 输出：false

提示：

0 <= s.length <= 100
0 <= t.length <= 10^4
两个字符串都只由小写字符组成。

class Solution {
    public boolean isSubsequence(String s, String t) {
        int sLen = s.length();
        int tLen = t.length();
        
        int sIdx = 0, tIdx = 0;
        
        while (sIdx < sLen && tIdx < tLen) {
            if (s.charAt(sIdx) == t.charAt(tIdx)) {
                sIdx++;
            }
            tIdx++;
        }
        
        return sIdx == sLen;
    }
}

167. 两数之和 II - 输入有序数组

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

示例 1：

1
2
3

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

示例 2：

1
2
3

输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。

示例 3：

1
2
3

输入：numbers = [-1,0], target = -1
输出：[1,2]
解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

提示：

2 <= numbers.length <= 3 * 104
-1000 <= numbers[i] <= 1000
numbers 按 非递减顺序 排列
-1000 <= target <= 1000
仅存在一个有效答案

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int len = numbers.length;
        int left = 0;
        int right = len - 1;
        while (left < len && right > 0) {
            if (numbers[left] + numbers[right] > target) {
                right--;
            } else if (numbers[left] + numbers[right] < target) {
                left++;
            } else {
                return new int[] {left + 1, right + 1};
            }
        }
        return new int[] {-1};
    }
}

11. 盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例 1：

1
2
3

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

1 2	输入：height = [1,1] 输出：1

提示：

n == height.length
2 <= n <= 105
0 <= height[i] <= 104

class Solution {
    public int maxArea(int[] height) {
        int i=0;int j=height.length-1;
        int tall,len;
        int area=0;
        while(i<j){
            len= j-i;
            tall=height[i]<height[j]?height[i++]:height[j--];//固定一端，高度更小的那条边，向中间尝试
            if(len*tall>area){
                area=len*tall;
            }
        }
        return area;
    }
}

15. 三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

1
2
3

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

1
2
3

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：

3 <= nums.length <= 3000
-105 <= nums[i] <= 105

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();  
        Arrays.sort(nums); // 先对数组进行排序  
  
        for (int i = 0; i < nums.length - 2; i++) {  
            // 跳过重复的数字，避免产生重复的三元组  
            if (i > 0 && nums[i] == nums[i - 1]) {  
                continue;  
            }  
  
            int left = i + 1;  
            int right = nums.length - 1;  
  
            while (left < right) {  
                int sum = nums[i] + nums[left] + nums[right];  
  
                if (sum == 0) {  
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));  
  
                    // 跳过重复的数字，避免产生重复的三元组  
                    while (left < right && nums[left] == nums[left + 1]) {  
                        left++;  
                    }  
                    while (left < right && nums[right] == nums[right - 1]) {  
                        right--;  
                    }  
  
                    left++;  
                    right--;  
                } else if (sum < 0) {  
                    left++;  
                } else {  
                    right--;  
                }  
            }  
        }  
  
        return result;  
    }
}

209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的连续

子数组

[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

1
2
3

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

1 2	输入：target = 4, nums = [1,4,4] 输出：1

示例 3：

1 2	输入：target = 11, nums = [1,1,1,1,1,1,1,1] 输出：0

提示：

1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int lo = 0, hi = 0, sum = 0, min = Integer.MAX_VALUE;
        while (hi < nums.length) {
            sum += nums[hi++];
            while (sum >= target) {
                min = Math.min(min, hi - lo);
                sum -= nums[lo++];
            }
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }
}

383. 赎金信

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

示例 1：

1 2	输入：ransomNote = "a", magazine = "b" 输出：false

示例 2：

1 2	输入：ransomNote = "aa", magazine = "ab" 输出：false

示例 3：

1 2	输入：ransomNote = "aa", magazine = "aab" 输出：true

提示：

1 <= ransomNote.length, magazine.length <= 105
ransomNote 和 magazine 由小写英文字母组成

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        Map<Character, Integer> map1 = new HashMap<>();
        Map<Character, Integer> map2 = new HashMap<>();
        for (char c : ransomNote.toCharArray()) {
            map1.put(c, map1.getOrDefault(c, 0) + 1);
        }
        for (char c : magazine.toCharArray()) {
            map2.put(c, map2.getOrDefault(c, 0) + 1);
        }
        for (char c : ransomNote.toCharArray()) {
            if (!map2.containsKey(c)) {
                return false;
            }
            int left = (int) map1.get(c);
            int right = (int) map2.get(c);
            if (left > right) {
                return false;
            }
        }
        return true;
    }
}

205. 同构字符串

给定两个字符串 s 和 t ，判断它们是否是同构的。

如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。

每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

示例 1:

1 2	输入：s = "egg", t = "add" 输出：true

示例 2：

1 2	输入：s = "foo", t = "bar" 输出：false

示例 3：

1 2	输入：s = "paper", t = "title" 输出：true

*提示：

1 <= s.length <= 5 * 104
t.length == s.length
s 和 t 由任意有效的 ASCII 字符组成

class Solution {
    public boolean isIsomorphic(String s, String t) {
        Map<Character,Character> map1 = new HashMap<>();
        Map<Character,Character> map2 = new HashMap<>();
        for (int i=0;i<s.length();i++) {
            char c1 = s.charAt(i);
            char c2 = t.charAt(i);
            if (map1.containsKey(c1) && map1.get(c1) != c2) {
                return false;
            }
            if (map2.containsKey(c2) && map2.get(c2) != c1) {
                return false;
            }
            map1.put(c1,c2);
            map2.put(c2,c1);
        }
        return true;
    }
}

290. 单词规律

给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。

这里的遵循指完全匹配，例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。

示例1:

1 2	输入: pattern = "abba", s = "dog cat cat dog" 输出: true

示例 2:

1 2	输入:pattern = "abba", s = "dog cat cat fish" 输出: false

示例 3:

1 2	输入: pattern = "aaaa", s = "dog cat cat dog" 输出: false

提示:

1 <= pattern.length <= 300
pattern 只包含小写英文字母
1 <= s.length <= 3000
s 只包含小写英文字母和 ' '
s 不包含 任何前导或尾随对空格
s 中每个单词都被 单个空格 分隔

class Solution {
    public boolean wordPattern(String pattern, String s) {
        String[] strings = s.split(" ");
        if (pattern.length() != strings.length) {
            return false;
        }
        Map<Character, String> map1 = new HashMap<>();
        Map<String, Character> map2 = new HashMap<>();
        for (int i=0;i<pattern.length();i++) {
            if (map1.containsKey(pattern.charAt(i)) && !strings[i].equals(map1.get(pattern.charAt(i)))) {
                return false;
            }
            if (map2.containsKey(strings[i]) && map2.get(strings[i]) != pattern.charAt(i)) {
                return false;
            }
            map1.put(pattern.charAt(i), strings[i]);
            map2.put(strings[i], pattern.charAt(i));
        }
        return true;
    }
}

242. 有效的字母异位词

给定两个字符串 *s* 和 *t* ，编写一个函数来判断 *t* 是否是 *s* 的字母异位词。

注意：若 *s* 和 *t* 中每个字符出现的次数都相同，则称 *s* 和 *t* 互为字母异位词。

示例 1:

1 2	输入: s = "anagram", t = "nagaram" 输出: true

示例 2:

1 2	输入: s = "rat", t = "car" 输出: false

提示:

1 <= s.length, t.length <= 5 * 104
s 和 t 仅包含小写字母

class Solution {
    public boolean isAnagram(String s, String t) {
        HashMap<Character, Integer> hashMap = new HashMap<>();
        char[] chars1 = s.toCharArray();
        char[] chars2 = t.toCharArray();
        if (s.length() != t.length()) {
            return false;
        }
        for (int i=0;i<chars1.length;i++) {
            hashMap.put(chars1[i], hashMap.getOrDefault(chars1[i], 0)+1);
        }
        for (int i=0;i<chars2.length;i++) {
            if (!hashMap.containsKey(chars2[i])) {
                return false;
            }
            if (hashMap.get(chars2[i]) <= 0) {
                return false;
            }
            hashMap.put(chars2[i], hashMap.get(chars2[i]) - 1);
        }
        return true;
    }
}

49. 字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

1 2	输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"] 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:

1 2	输入: strs = [""] 输出: [[""]]

示例 3:

1 2	输入: strs = ["a"] 输出: [["a"]]

提示：

1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        
        for (String str : strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String sortedStr = new String(chars);
            
            if (!map.containsKey(sortedStr)) {
                map.put(sortedStr, new ArrayList<>());
            }
            map.get(sortedStr).add(str);
        }
        
        return new ArrayList<>(map.values());
    }
}

1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

1
2
3

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

1 2	输入：nums = [3,2,4], target = 6 输出：[1,2]

示例 3：

1 2	输入：nums = [3,3], target = 6 输出：[0,1]

提示：

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i< nums.length; i++) {
            if(map.containsKey(target - nums[i])) {
                return new int[] {map.get(target-nums[i]),i};
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

202. 快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：

输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

示例 2：

1 2	输入：n = 2 输出：false

提示：

1 <= n <= 231 - 1

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> visitedSet = new HashSet<>();
        while(visitedSet.add(n) && n!= 1) {
            int newValue = 0;
            while(n != 0) {
                int n1 = n % 10;
                newValue += (n1 * n1);
                n /= 10; 
            }
            n = newValue;
        }
        return n == 1;
    }
}

219. 存在重复元素 II

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

示例 1：

1 2	输入：nums = [1,2,3,1], k = 3 输出：true

示例 2：

1 2	输入：nums = [1,0,1,1], k = 1 输出：true

示例 3：

1 2	输入：nums = [1,2,3,1,2,3], k = 2 输出：false

提示：

1 <= nums.length <= 105
-109 <= nums[i] <= 109
0 <= k <= 105

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        if (nums.length == 1) {
            return false;
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int i=0;i<nums.length;i++) {
            if (map.containsKey(nums[i]) && Math.abs(i - map.get(nums[i])) <= k) {
                return true;
            }
            map.put(nums[i], i);
        }
        return false;
    }
}

128. 最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：

1
2
3

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：

1 2	输入：nums = [0,3,7,2,5,8,4,6,0,1] 输出：9

提示：

0 <= nums.length <= 105
-109 <= nums[i] <= 109

思路：

class Solution {
    public int longestConsecutive(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int num : nums) {
        set.add(num);
    }
    
    int max = 0;
    for (int num : nums) {
        if (!set.contains(num - 1)) { // 如果当前数字是连续序列的起始数字
            int currLength = 1;
            while (set.contains(++num)) { // 继续向后查找连续的数字
                currLength++;
            }
            max = Math.max(max, currLength);
        }
    }
    
    return max;
    }
}

228. 汇总区间

给定一个 无重复元素 的有序整数数组 nums 。

返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。

列表中的每个区间范围 [a,b] 应该按如下格式输出：

"a->b" ，如果 a != b
"a" ，如果 a == b

示例 1：

输入：nums = [0,1,2,4,5,7]
输出：["0->2","4->5","7"]
解释：区间范围是：
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"

示例 2：

输入：nums = [0,2,3,4,6,8,9]
输出：["0","2->4","6","8->9"]
解释：区间范围是：
[0,0] --> "0"
[2,4] --> "2->4"
[6,6] --> "6"
[8,9] --> "8->9"

提示：

0 <= nums.length <= 20
-231 <= nums[i] <= 231 - 1
nums 中的所有值都 互不相同
nums 按升序排列

class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> list = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int start = nums[i];

            // 寻找连续范围的终点
            while (i < nums.length - 1 && nums[i + 1] == nums[i] + 1) {
                i++;
            }
            
            // 如果范围只有一个数，则直接添加该数
            if (start == nums[i]) {
                list.add(Integer.toString(start));
            } else {
                // 否则添加范围的起始和终止点
                list.add(start + "->" + nums[i]);
            }
        }
        return list;
    }
}

1738. 找出第 K 大的异或坐标值

给你一个二维矩阵 matrix 和一个整数 k ，矩阵大小为 m x n 由非负整数组成。

矩阵中坐标 (a, b) 的值可由对所有满足 0 <= i <= a < m 且 0 <= j <= b < n 的元素 matrix[i][j]（下标从 0 开始计数）执行异或运算得到。

请你找出 matrix 的所有坐标中第 k 大的值（**k 的值从 1 开始计数**）。

示例 1：

1
2
3

输入：matrix = [[5,2],[1,6]], k = 1
输出：7
解释：坐标 (0,1) 的值是 5 XOR 2 = 7 ，为最大的值。

示例 2：

1
2
3

输入：matrix = [[5,2],[1,6]], k = 2
输出：5
解释：坐标 (0,0) 的值是 5 = 5 ，为第 2 大的值。

示例 3：

1
2
3

输入：matrix = [[5,2],[1,6]], k = 3
输出：4
解释：坐标 (1,0) 的值是 5 XOR 1 = 4 ，为第 3 大的值。

示例 4：

1
2
3

输入：matrix = [[5,2],[1,6]], k = 4
输出：0
解释：坐标 (1,1) 的值是 5 XOR 2 XOR 1 XOR 6 = 0 ，为第 4 大的值。

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 1000
0 <= matrix[i][j] <= 106
1 <= k <= m * n

思路：我们定义一个二维前缀异或数组 sss，其中 s[i][j]s[i][j]s[i][j] 表示矩阵前 iii 行和前 jjj 列的元素异或运算的结果，即：

s[i][j]=⨁0≤x≤i,0≤y≤jmatrix[x][y]s[i][j] = \bigoplus_{0 \leq x \leq i, 0 \leq y \leq j} matrix[x][y]
s[i][j]=
0≤x≤i,0≤y≤j
⨁

matrix[x][y]
而 s[i][j]s[i][j]s[i][j] 可以由 s[i−1][j]s[i - 1][j]s[i−1][j], s[i][j−1]s[i][j - 1]s[i][j−1] 和 s[i−1][j−1]s[i - 1][j - 1]s[i−1][j−1] 三个元素计算得到，即：

s[i][j]=s[i−1][j]⊕s[i][j−1]⊕s[i−1][j−1]⊕matrix[i−1][j−1]s[i][j] = s[i - 1][j] \oplus s[i][j - 1] \oplus s[i - 1][j - 1] \oplus matrix[i - 1][j - 1]
s[i][j]=s[i−1][j]⊕s[i][j−1]⊕s[i−1][j−1]⊕matrix[i−1][j−1]
我们遍历矩阵，计算出所有的 s[i][j]s[i][j]s[i][j]，然后将其排序，最后返回第 kkk 大的元素即可。如果不想使用排序，也可以使用快速选择算法，这样可以优化时间复杂度。

方法一：

class Solution {
    public int kthLargestValue(int[][] matrix, int k) {
        int m = matrix.length, n = matrix[0].length;
        int[][] s = new int[m + 1][n + 1];
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                s[i + 1][j + 1] = s[i + 1][j] ^ s[i][j + 1] ^ s[i][j] ^ matrix[i][j];
                ans.add(s[i + 1][j + 1]);
            }
        }
        Collections.sort(ans);
        return ans.get(ans.size() - k);
    }
}

方法二：

public class Solution {
    public int kthLargestValue(int[][] matrix, int k) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[] a = new int[m * n];
        int[] colSum = new int[n];
        int i = 0;
        for (int[] row : matrix) {
            int s = 0;
            for (int j = 0; j < row.length; j++) {
                colSum[j] ^= row[j];
                s ^= colSum[j];
                a[i++] = s;
            }
        }
        Arrays.sort(a);
        return a[i - k];
    }
}

2981. 找出出现至少三次的最长特殊子字符串 I

给你一个仅由小写英文字母组成的字符串 s 。

如果一个字符串仅由单一字符组成，那么它被称为特殊字符串。例如，字符串 "abc" 不是特殊字符串，而字符串 "ddd"、"zz" 和 "f" 是特殊字符串。

返回在 s 中出现 至少三次 的 最长特殊子字符串 的长度，如果不存在出现至少三次的特殊子字符串，则返回 -1 。

子字符串 是字符串中的一个连续非空字符序列。

示例 1：

输入：s = "aaaa"
输出：2
解释：出现三次的最长特殊子字符串是 "aa" ：子字符串 "aaaa"、"aaaa" 和 "aaaa"。
可以证明最大长度是 2 。

示例 2：

1
2
3

输入：s = "abcdef"
输出：-1
解释：不存在出现至少三次的特殊子字符串。因此返回 -1 。

示例 3：

输入：s = "abcaba"
输出：1
解释：出现三次的最长特殊子字符串是 "a" ：子字符串 "abcaba"、"abcaba" 和 "abcaba"。
可以证明最大长度是 1 。

提示：

3 <= s.length <= 50
s 仅由小写英文字母组成。

方法一：

 public class Solution {
    public int maximumLength(String S) {
        char[] s = S.toCharArray();
        List<Integer>[] groups = new ArrayList[26];
        Arrays.setAll(groups, i -> new ArrayList<>());
        int cnt = 0;
        for (int i = 0; i < s.length; i++) {
            cnt++;
            if (i + 1 == s.length || s[i] != s[i + 1]) {
                groups[s[i] - 'a'].add(cnt); // 统计连续字符长度
                cnt = 0;
            }
        }

        int ans = 0;
        for (List<Integer> a : groups) {
            if (a.isEmpty()) continue;
            a.sort(Collections.reverseOrder());
            a.add(0);
            a.add(0); // 假设还有两个空串
            ans = Math.max(ans, Math.max(a.get(0) - 2, Math.max(Math.min(a.get(0) - 1, a.get(1)), a.get(2))));
        }

        return ans > 0 ? ans : -1;
    }
}

方法二：

class Solution {
    private String s;
    private int n;

    public int maximumLength(String s) {
        this.s = s;
        n = s.length();
        int l = 0, r = n;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (check(mid)) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return l == 0 ? -1 : l;
    }

    private boolean check(int x) {
        int[] cnt = new int[26];
        for (int i = 0; i < n;) {
            int j = i + 1;
            while (j < n && s.charAt(j) == s.charAt(i)) {
                j++;
            }
            int k = s.charAt(i) - 'a';
            cnt[k] += Math.max(0, j - i - x + 1);
            if (cnt[k] >= 3) {
                return true;
            }
            i = j;
        }
        return false;
    }
}

2965. 找出缺失和重复的数字

给你一个下标从 0 开始的二维整数矩阵 grid，大小为 n * n ，其中的值在 [1, n2] 范围内。除了 a 出现两次，b 缺失之外，每个整数都 恰好出现一次 。

任务是找出重复的数字a 和缺失的数字 b 。

返回一个下标从 0 开始、长度为 2 的整数数组 ans ，其中 ans[0] 等于 a ，ans[1] 等于 b 。

示例 1：

1
2
3

输入：grid = [[1,3],[2,2]]
输出：[2,4]
解释：数字 2 重复，数字 4 缺失，所以答案是 [2,4] 。

示例 2：

1
2
3

输入：grid = [[9,1,7],[8,9,2],[3,4,6]]
输出：[9,5]
解释：数字 9 重复，数字 5 缺失，所以答案是 [9,5] 。

提示：

2 <= n == grid.length == grid[i].length <= 50
1 <= grid[i][j] <= n * n
对于所有满足1 <= x <= n * n 的 x ，恰好存在一个 x 与矩阵中的任何成员都不相等。
对于所有满足1 <= x <= n * n 的 x ，恰好存在一个 x 与矩阵中的两个成员相等。
除上述的两个之外，对于所有满足1 <= x <= n * n 的 x ，都恰好存在一对 i, j 满足 0 <= i, j <= n - 1 且 grid[i][j] == x 。

public class Solution {
    public int[] findMissingAndRepeatedValues(int[][] grid) {
        int n = grid.length;
        int[] cnt = new int[n * n + 1];
        for (int[] row : grid) {
            for (int x : row) {
                cnt[x]++;
            }
        }

        int[] ans = new int[2];
        for (int i = 1; i <= n * n; i++) {
            if (cnt[i] == 2) {
                ans[0] = i; // 出现两次的数
            } else if (cnt[i] == 0) {
                ans[1] = i; // 出现零次的数
            }
        }
        return ans;
    }
}