bytedance

LRU缓存请你设计并实现一个满足LRU (最近最少使用) 缓存约束的数据结构。

class LRUCache {
    class Node{
        int key;
        int value;
        Node pre;
        Node next;
        public Node(){}
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    private int size = 0;
  //key是node的key,value是Node对象。方便get快速获取值。
    private HashMap<Integer,Node> cache = new HashMap<>();
    private int capacity = 0;
    private Node head,tail;//双链表使队尾是可淘汰元素。
    public LRUCache(int capacity) {
        this.capacity = capacity;
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.pre = head;
    }
    
    public int get(int key) {
        Node node = cache.get(key);
        if (node == null) {
            return -1;
        }
        moveToHead(node);
        return node.value;
    }
    private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }
    private void removeNode(Node node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }
    private void addToHead (Node node) {
        node.pre = head;
        node.next = head.next;
        head.next.pre = node;
        head.next = node;
    }
    public void put(int key, int value) {
        Node node = cache.get(key);
        if (node == null) {
            Node newNode = new Node(key,value);
            cache.put(key,newNode);
            addToHead(newNode);
            size++;
            if (size > capacity) {
                Node tail = removeTail();
                cache.remove(tail.key);
            }
        } else {
            node.value = value;
            moveToHead(node);
        }
    }
    private Node removeTail() {
        Node res = tail.pre;
        removeNode(res);
        return res;//返回要在cache中删除掉node
    }
}

• 时间复杂度：对于 put 和 get 都是O(1)。
• 空间复杂度：O(capacity)，因为哈希表和双向链表最多存储capacity+1个元素。

无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character,Integer> record = new HashMap<>();
        int left = 0;
        int right = 0;
        int res = 0;
        for (; right < s.length(); right++) {
            char ch = s.charAt(right);
            if (record.containsKey(ch)) {
                left = Math.max(record.get(ch)+1,left);
            }
            record.put(ch,right);
            res = Math.max(res,right-left+1);
        }
        return res;
    }
}

• 时间复杂度：O(N)，其中N 是字符串的长度。左指针和右指针分别会遍历整个字符串一次。
• 空间复杂度：O(∣Σ∣)，其中Σ 表示字符集（即字符串中可以出现的字符），∣Σ∣ 表示字符集的大小。

K个一组翻转链表反转

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        while (head != null) {
            ListNode tail = pre;
            // 剩余部分长度小于k直接返回
            for (int i = 0; i < k;i++) {
                tail = tail.next;
                if (tail == null) {
                    return dummy.next;
                }
            }
            ListNode next = tail.next;
            ListNode[] reverse = myReverse(head,tail);
            head = reverse[0];// 把子链表重新接回原链表
            tail = reverse[1];
            pre.next = head;//head上一个节点
            tail.next = next;//tail后一个节点
            pre = tail;
            head = tail.next;
        }
        return dummy.next;
    }
    private ListNode[] myReverse (ListNode head, ListNode tail) {
        ListNode pre = tail.next;
        ListNode cur = head;
        while (pre != tail) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return new ListNode[]{tail,head};
    }
}

• 时间复杂度：O(n)，其中 n 为链表的长度。head 指针会在 O(n/k)个节点上停留，每次停留需要进行一次 O(k) 的翻转操作。
• 空间复杂度：O(1)，只需要建立常数个变量。

反转链表

迭代

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

• 时间复杂度: O(n)，其中 n 是链表的长度。需要遍历链表一次。
• 空间复杂度: O(1)。

递归

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
     	  //从最后一个节点一直反转到第一个节点
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

• 时间复杂度：O(n)，其中 n 是链表的长度。需要对链表的每个节点进行反转操作。
• 空间复杂度：O(n)，其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间，最多为 n 层。

二叉树的锯齿形层序遍历

即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) 
            return res;
        Deque<Integer> path;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean flag = true;
        while (!queue.isEmpty()) {
            path = new LinkedList<>();
            int n = queue.size();
            for (int i = 0; i < n; i++) {
                TreeNode node = queue.poll();
            if (flag) {//左到右
                path.offerLast(node.val);
            } else {//右到左
                path.offerFirst(node.val);   
            }
            if (node.left != null)
                queue.offer(node.left);
            if (node.right != null)
                queue.offer(node.right); 
        }
            flag = !flag;
            res.add(new LinkedList(path));
        }
        return res;
    }
}

• 时间复杂度：O(N)，其中 N 为二叉树的节点数。每个节点会且仅会被遍历一次。
• 空间复杂度：O(N)。我们需要维护存储节点的队列和存储节点值的双端队列，空间复杂度为 O(N)。

数组中的第K个最大元素 快排 quicksort kth

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        quickSort(nums,0,nums.length-1);
        return nums[nums.length-k];
    }
    private void quickSort(int[] nums,int left,int right){
        if(left<right){
            swap(nums,(int)(left+Math.random()*(right-left+1)),right);
            int[] res = partition(nums,left,right);
            quickSort(nums,left,res[0]-1);
            quickSort(nums,res[1]+1,right);
        }
    }
    private void swap(int[] nums,int left,int right){
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
    private int[] partition(int[] nums,int left,int right){
        int less = left-1; //小于区域
        int more = right;  //大于区域
        while(left<more){
            if(nums[left]<nums[right]){
                swap(nums,++less,left++);
            }else if(nums[left]>nums[right]){
                swap(nums,--more,left);
            }else{
                left++;
            }
        }
        swap(nums,more,right);
        return new int[]{less+1,more};//返回相等区域
    }
}

• 时间复杂度:O(N)
• 空间复杂度:O(log⁡n)

快排复杂度：

• 时间：O(nlogn),最坏的时间复杂度为 O(n2)
• 空间：O(n), 空间复杂度与递归的层数有关，每层递归会生成一些临时变量，所以空间复杂度为 O(logn) ~ O(n)，平均空间复杂度为 O(logn)

堆排序 Heapsort

class Solution {
    public void heapSort(int[] nums){
        if(nums==null||nums.length<2){
            return;
        }
        for(int i=0;i<nums.length;i++){
            heapInsert(nums,i);
        }
        int heapSize = nums.length;
        swap(nums,0,--heapSize);
        while(heapSize>0){
            heapify(nums,0,heapSize);
            swap(nums,0,--heapSize);
        }
    }
    //某个数处在index，往上继续移动
    private void heapInsert(int[] nums,int index){
        while(nums[(index-1)/2]<nums[index]){
            swap(nums,(index-1)/2,index);
            index = (index-1)/2;
        }
    }
    private void swap(int[] nums,int left,int right){
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
  	//和左、右节点比较，小于则往下换
    private void heapify(int[] nums,int index,int heapSize){
        int left = index*2+1;//从上往下移动,左孩子下标
        while(left<heapSize){
            int largest=left+1<heapSize&&nums[left+1]>nums[left]?left+1:left;
            largest=nums[largest]>nums[index]?largest:index;
            if(largest==index){
                break;
            }
            swap(nums,largest,index);
            index = largest;
            left=index*2+1;
        }
    }
}

• 时间：O(nlogn),初始化建堆为O(n),重建堆为O(nlogn).
• 空间：O(1)，只用了常数级的临时变量.

三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 *a，b，c ，*使得 a + b + c = 0

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; 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) {
                    left++;
                } else if (sum > 0) {
                    right--;
                } else {
                res.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--;
                }
            }
        }
        return res;
    }
}

• 时间复杂度：O(n2)，数组排序 O(NlogN)，遍历数组 O(n)，双指针遍历 O(n)，总体 O(Nlog N)+O(n)∗O(n)，O(n2)
• 空间复杂度：O(1)

搜索旋转排序数组

有一个长度为 n 的按严格升序排列的整数数组 nums ，在实行 search 函数之前，在某个下标 k 上进行旋转，使数组变为[nums[k],nums[k+1],.....,nums[nums.length-1],nums[0],nums[1],.......,nums[k-1]]。

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

将数组一分为二，其中一定有一个是有序的，另一个可能是有序，也能是部分有序。
此时有序部分用二分法查找。无序部分再一分为二，其中一个一定有序，另一个可能有序，可能无序。就这样循环.

• 时间复杂度： O(logn)，其中 n 为nums 数组的大小。整个算法时间复杂度即为二分查找的时间复杂度 O(logn)。
• 空间复杂度： O(1) 。我们只需要常数级别的空间存放变量。

买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择某一天买入这只股票,并选择在未来的某一个不同的日子卖出该股票。

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

• 时间复杂度：O(n)，只需要遍历一次。
• 空间复杂度：O(1)，只使用了常数个变量。

合并K个升序链表

给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。

维护当前每个链表没有被合并的元素的最前面一个，k 个链表就最多有 k 个满足这样条件的元素，每次在这些元素里面选取 val 属性最小的元素合并到答案中。

class Solution {
    class Status implements Comparable<Status>{
    int val;
    ListNode node;
    public Status(){}
    public Status(int val, ListNode node) {
        this.val = val;
        this.node = node;
    }
    public int compareTo(Status status) {
        return this.val-status.val;
    }
}
PriorityQueue<Status> queue = new PriorityQueue<>();
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        for (ListNode node:lists) {
            //把每个链表的头节点放入优先队列
            if (node != null)
            queue.offer(new Status(node.val,node));
        }
        while (!queue.isEmpty()) {
            Status status = queue.poll();
            tail.next = status.node;
            tail = tail.next;
            if (status.node.next != null)
            queue.offer(new Status(status.node.next.val,status.node.next));
        }
        return dummy.next;
    }
}

• 时间复杂度：考虑优先队列中的元素不超过 k 个，那么插入和删除的时间代价为 O(logk)，这里最多有 kn 个点，对于每个点都被插入删除各一次，故总的时间代价即渐进时间复杂度为 O(kn×logk)。
• 空间复杂度：这里用了优先队列，优先队列中的元素不超过 k 个，故渐进空间复杂度为 O(k)。

合并两个排序的链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1);
        ListNode prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev.next = l1 == null ? l2 : l1;

        return prehead.next;
    }
}

• 时间复杂度：O(n+m)，其中n和m分别为两个链表的长度。因为每次循环迭代中，l1 和 l2 只有一个元素会被放进合并链表中， 因此 while 循环的次数不会超过两个链表的长度之和。所有其他操作的时间复杂度都是常数级别
• 空间复杂度：O(1)。我们只需要常数的空间存放若干变量。

接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

class Solution {
    public int trap(int[] height) {
        int left = 0;//从左往右处理的当前下标
        int right = height.length - 1;//从右往左处理的当前下标
        int left_max = 0;//左边的最大值，从左往右遍历找到的
        int right_max = 0;//右边的最大值，从右往左遍历找到的
        int res = 0;
        while (left <= right) {
            if (left_max < right_max) {
                res += Math.max(0,left_max-height[left]);
                left_max = Math.max(left_max,height[left]);
                left++;
            } else {
                res += Math.max(0,right_max-height[right]);
                right_max = Math.max(right_max,height[right]);
                right--;
            }
        }
        return res;
    }
}
//在某个位置i处，它能存的水，取决于它左右两边的最大值中较小的一个。
//从左往右处理到left下标时，左边的最大值left_max对它而言是可信的，但right_max对它而言是不可信的。
//从右往左处理到right下标时，右边的最大值right_max对它而言是可信的，但left_max对它而言是不可信的。
//对于位置left而言，它左边最大值一定是left_max，右边最大值“大于等于”right_max，这时候，如果left_max<right_max成立，那么它就知道自己能存多少水了。无论右边将来会不会出现更大的right_max，都不影响这个结果。 所以当left_max<right_max时，我们就希望去处理left下标，反之，我们希望去处理right下标。

时间复杂度：O(n)。单次遍历的时间O(n)。
空间复杂度：O(1) 的额外空间。left,right,leftmax,rightmax 只需要常数的空间。

二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

class Solution {

    private TreeNode ans = null;

    private boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return false;
        boolean lson = dfs(root.left, p, q);
      	//判断该节点左孩子是否包含p或者q
        boolean rson = dfs(root.right, p, q);
        if ((lson && rson) || ((root.val == p.val || root.val == q.val) && (lson || rson))) {
          //root左子树和右子树均包含p节点或q节点
          //root恰好是p节点或q节点且它的左子树或右子树有一个包含了另一个节点
            ans = root;
        } 
        return lson || rson || (root.val == p.val || root.val == q.val);
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root, p, q);
        return this.ans;
    }
}

• 时间复杂度：O(N)，其中N 是二叉树的节点数。二叉树的所有节点有且只会被访问一次，因此时间复杂度为 O(N)。
• 空间复杂度：O(N) ，其中N 是二叉树的节点数。递归调用的栈深度取决于二叉树的高度，二叉树最坏情况下为一条链，此时高度为 NN，因此空间复杂度为 O(N)。

相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;
        int lA = 0;
        int lB = 0;
        while (curA != null) {
            curA = curA.next;
            lA++;
        }
        while (curB != null) {
            curB = curB.next;
            lB++;
        }
        curA = headA;
        curB = headB;
        if (lA > lB) {
            int gap = lA -lB;
            while (gap-- > 0) {
                curA = curA.next;
            }
        } else {
            int gap = lB - lA;
            while (gap-- > 0) {
                curB = curB.next;
            }
        }
        while (curA != null && curB != null) {
            if(curA == curB)
            return curA;
            curA = curA.next;
            curB = curB.next;
        }
        return null;
    }
}

• 时间复杂度：O(m+n)，其中 m 和n是分别是链表 headA 和 headB 的长度。两个指针同时遍历两个链表，每个指针遍历两个链表各一次。
• 空间复杂度：O(1)。

螺旋矩阵

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

class Solution {//转圈遍历。左右下上
    public List<Integer> spiralOrder(int[][] matrix) {
       List<Integer> res = new ArrayList<>();
       int left = 0;
       int right = matrix[0].length-1;
       int top = 0;
       int bottom = matrix.length-1;
       //一共要打印的个数
       int total = matrix.length * matrix[0].length;
       while (total >= 1) {
           for (int i = left;i <= right && total>=1; i++) {
           //从左往右，遍历完一行相当于top少一行，所以top++
               res.add(matrix[top][i]);
               total--;
           }
           top++;
           for (int i = top; i <= bottom && total>=1; i++) {
               res.add(matrix[i][right]);
               total--;
           }
           right--;
           for (int i = right; i >= left && total >=1;i--) {
               res.add(matrix[bottom][i]);
               total--;
           }
           bottom--;
           for (int i = bottom; i >= top && total>=1;i--) {
               res.add(matrix[i][left]);
               total--;
           }
           left++;
       }
       return res;
    }
}

• 时间复杂度：O(mn)，其中m和n分别是输入矩阵的行数和列数。矩阵中的每个元素都要被访问一次。
• 空间复杂度：O(1)。除了输出数组以外，空间复杂度是常数。

重排链表

Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]

class Solution {
    public void reorderList(ListNode head) {
        if (head == null) {
            return;
        }
        //1.找到中点
        ListNode mid = findMid(head);
        ListNode L1 = head;
        ListNode L2 = mid.next;
        mid.next = null;//断开两个链表
        //2.反转中点后的链表
        L2 = reverse(L2);
        //3.合并反转后的链表和中点前的链表
        merge(L1,L2);
    }
    private ListNode findMid (ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    private ListNode reverse (ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
    private void merge (ListNode L1, ListNode L2) {
        ListNode L1Temp = null;
        ListNode L2Temp = null;
        while (L1 != null && L2 != null) {
            L1Temp = L1.next;
            L2Temp = L2.next;
            L1.next = L2;
            L2.next = L1Temp;
            L1 = L1Temp;
            L2 = L2Temp;
        }
    }
}

• 时间复杂度：O(N)，其中 N 是链表中的节点数。
• 空间复杂度：O(1)。

二叉树的右视图

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null)
            return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int n = queue.size();
            while (n-- > 0) {
                TreeNode node = queue.poll();
              //层次遍历，右试图是每层的最后一位
                if (n == 0) {
                  //为0则是每一层最后一个节点
                    res.add(node.val);
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
        return res;
    }
}

• 时间复杂度 : O(n)。 每个节点最多进队列一次，出队列一次，因此广度优先搜索的复杂度为线性。
• 空间复杂度 : O(n)。每个节点最多进队列一次，所以队列长度最大不不超过 n，所以这里的空间代价为O(n)。

岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

class Solution {
    public int numIslands(char[][] grid) {
        int res = 0;//岛屿沉没
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j <grid[0].length;j++) {
                if (grid[i][j] == '1') {
                    dfs(grid,i,j);
                    res++;
                } 
            }
        }
        return res;
    }
    private void dfs (char[][] grid,int i,int j) {
        if (i >= grid.length ||i < 0||j <0||j >=grid[0].length) {
            return;
        }
        if (grid[i][j] == '0') {
            return;
        }
        grid[i][j] = '0';
        dfs(grid,i+1,j);
        dfs(grid,i-1,j);
        dfs(grid,i,j+1);
        dfs(grid,i,j-1);
    }
}

• 时间复杂度：O(MN)，其中M和N分别为行数和列数。
• 空间复杂度：O(MN)，在最坏情况下，整个网格均为陆地，深度优先搜索的深度达到 MN。

class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                if(grid[i][j] == '1'){
                  //若是则置零（删除岛屿节点），并将此节点上下左右节点加入队列
                    bfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }
    private void bfs(char[][] grid, int i, int j){
        Queue<int[]> list = new LinkedList<>();
        list.add(new int[] { i, j });
        while(!list.isEmpty()){
            int[] cur = list.remove();
            i = cur[0]; j = cur[1];
            if(0 <= i && i < grid.length && 0 <= j && j < grid[0].length && grid[i][j] == '1') {
                grid[i][j] = '0';
                list.add(new int[] { i + 1, j });
                list.add(new int[] { i - 1, j });
                list.add(new int[] { i, j + 1 });
                list.add(new int[] { i, j - 1 });
            }
        }
    }
}

时间复杂度：O(MN)，其中M 和N 分别为行数和列数。

空间复杂度：O(min(M,N))，在最坏情况下，整个网格均为陆地，队列的大小可以达到 min(M,N)。

下一个排列

例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。

class Solution {
    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
      //找到一个不是降序的较小数
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
      //在[i+1,n)中从后往前找到第一个大于较小数的较大数
        if (i >= 0) {
            int j = nums.length - 1;
            while (j >= 0 && nums[i] >= nums[j]) {
                j--;
            }
            swap(nums, i, j);
        }
      //将区间[i+1,n)变为升序，找到一个尽可能小的排列
        reverse(nums, i + 1);
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public void reverse(int[] nums, int start) {
        int left = start, right = nums.length - 1;
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }
}

• 时间复杂度：O(N)，其中N为给定序列的长度。我们至多只需要扫描两次序列，以及进行一次反转操作。
• 空间复杂度：O(1)，只需要常数的空间存放若干变量。

最长递增子序列 最长上升子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
      //dp[i] 为考虑前i个元素，以第i个数字结尾的最长上升子序列的长度
      //dp[i]=max(dp[j])+1,其中0≤j<i且num[j]<num[i]
        dp[0] = 1;
        int res = 1;
        for (int i = 1; i < nums.length;i++) {
            dp[i] = 1;
            for (int j = 0; j < i;j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[j] + 1,dp[i]);
                }
            }
            res = Math.max(res,dp[i]);
        }
        return res;
    }
}

• 时间复杂度：O(n2 )，其中 n 为数组nums 的长度。动态规划的状态数为n，计算状态dp[i] 时，需要 O(n) 的时间遍历 dp[0…i−1] 的所有状态.
• 空间复杂度：O(n)，需要额外使用长度为 n的 dp数组。

贪心+二分查找 返回序列

要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小。

class Solution {
    public int lengthOfLIS(int[] nums) {
      //len 记录目前最长上升子序列的长度
        int len = 1, n = nums.length;
        if (n == 0) {
            return 0;
        }
      //长度为i的最长上升子序列的末尾元素的最小值，d[i]单调递增
        int[] d = new int[n + 1];
      //d[1]=nums[0],长度为1的
        d[len] = nums[0];
        for (int i = 1; i < n; ++i) {
            if (nums[i] > d[len]) {
                d[++len] = nums[i];
            } else {
//在d[1…len]中找满足d[i−1]<nums[j]<d[i]的下标i，并更新d[i]=nums[j]。
                int l = 1, r = len, pos = 0; // 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0
                while (l <= r) {
                    int mid = (l + r) >> 1;
                    if (d[mid] < nums[i]) {
                        pos = mid;
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }
                d[pos + 1] = nums[i];
            }
        }
        return len;
    }
}

//变形，返回序列
class Solution {
    public int[] lengthOfLIS(int[] nums) {
      //len 记录目前最长上升子序列的长度
        int len = 1, n = nums.length;
        if (n == 0) {
            return new int[0];
        }
      //长度为i的最长上升子序列的末尾元素的最小值，d[i]单调递增
        int[] d = new int[n + 1];
        int[] w=new int[n];//辅助数组，存储答案对应的数组索引
      	w[0] = len;
      //d[1]=nums[0],长度为1的
        d[len] = nums[0];
        for (int i = 1; i < n; ++i) {
            if (nums[i] > d[len]) {
                d[++len] = nums[i];
              	w[i]=len;
            } else {
//在d[1…len]中找满足d[i−1]<nums[j]<d[i]的下标i，并更新d[i]=nums[j]。
                int l = 1, r = len, pos = 0; // 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0
                while (l <= r) {
                    int mid = (l + r) >> 1;
                    if (d[mid] < nums[i]) {
                        pos = mid;
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }
                d[pos + 1] = nums[i];
              	w[i]=pos+1;
            }
        }
        int[] res=new int[len];
        for(int i=n-1,j=len;j>0;--i){
            if(w[i]==j){
                res[--j]=nums[i];
            }
        }
      return res;
    }
}

• 时间复杂度：O(nlogn)。数组nums 的长度为n，依次用数组中的元素去更新d 数组，而更新d 数组时需要进行O(logn) 的二分搜索
• 空间复杂度：O(n)，需要额外使用长度为n的d数组。

缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        int res = 0;
        //把所有负数设为n+1，和[1,n]区分开
        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0) {
                nums[i] = n + 1;
            }
        }
      //将存在的整数i用复数打标记
        for (int i = 0; i < n; i++) {
            int cur = Math.abs(nums[i]);
            if (cur <= n) {
                nums[cur-1] = -Math.abs(nums[cur-1]);
            }
        }
      //找到第一个没被负数标记的索引，i+1则是最小正整数
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0)
                return i + 1;
        }
        return n+1;
    }
}

• 时间复杂度：O(N)，其中 N是数组的长度。
• 空间复杂度：O(1)。

懂车帝

三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length-1;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) {
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    res.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--;
                }
            }
        }
        return res;
    }
}

• 时间复杂度：O(N2 )，其中 N是数组 nums 的长度。
• 空间复杂度：O(logN)。我们忽略存储答案的空间，额外的排序的空间复杂度为 O(logN)。然而我们修改了输入的数组 nums，在实际情况下不一定允许，因此也可以看成使用了一个额外的数组存储了 nums 的副本并进行排序，空间复杂度为O(N)。

合并区间

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

class Solution {
    public int[][] merge(int[][] intervals) {
        if(intervals.length==0) {
            return new int[0][2];
        }
        //将列表中的区间按照左端点升序排序
        Arrays.sort(intervals,new Comparator<int[]>(){
            public int compare(int[] interval1,int[] interval2){
                return interval1[0]-interval2[0];
            }
        });
        List<int[]> record = new ArrayList<>();
        for (int i = 0;i<intervals.length;i++) {
            int L = intervals[i][0];
            int R = intervals[i][1];
            //如果当前区间的左端点在数组 merged 中最后一个区间的右端点之后，那么它们不会重合，我们可以直接将这个区间加入数组 merged 的末尾
            if(record.size()==0||record.get(record.size()-1)[1]<L){
                record.add(new int[]{L,R});
            } else {
                //否则，它们重合，我们需要用当前区间的右端点更新数组 merged 中最后一个区间的右端点，将其置为二者的较大值。
                record.get(record.size()-1)[1] = Math.max(record.get(record.size()-1)[1],R);
            }
        }
        return record.toArray(new int[record.size()][]);
    }
}

• 时间复杂度：O(nlogn)，其中n为区间的数量。除去排序的开销，我们只需要一次线性扫描，所以主要的时间开销是排序的 O(nlogn)。
• 空间复杂度：O(logn)，其中 nn 为区间的数量。这里计算的是存储答案之外，使用的额外空间。O(logn) 即为排序所需要的空间复杂度。

括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。回溯法

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        backTracking(res,sb,n,0,0);
        return res;
    }
    private void backTracking(List<String> res,StringBuilder sb,int n,int open,int close) {
        if(sb.length()==2*n) {
            res.add(sb.toString());
            return;
        }
      //如果左括号数量不大于 nn，我们可以放一个左括号。如果右括号数量小于左括号的数量，我们可以放一个右括号。
        if(open<n){
            sb.append('(');
            backTracking(res,sb,n,open+1,close);
            sb.deleteCharAt(sb.length()-1);
        }
        if(open>close) {
            sb.append(')');
            backTracking(res,sb,n,open,close+1);
            sb.deleteCharAt(sb.length()-1);
        }
    }
}

• 时间复杂度：在回溯过程中，每个答案需要 O(n) 的时间复制到答案数组中。
• 空间复杂度：O(n)，除了答案数组之外，我们所需要的空间取决于递归栈的深度，每一层递归函数需要 O(1)的空间，最多递归 2n 层，因此空间复杂度为 O(n)。

最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

class Solution {
    public int maxSubArray(int[] nums) {
        int pre = 0;
        int max = nums[0];
        for (int n:nums) {
            pre = Math.max(pre+n,n);
            max = Math.max(max,pre);
        }
        return max;
    }
}

• 时间复杂度：O(n)，其中 n为 nums 数组的长度。我们只需要遍历一遍数组即可求得答案。
• 空间复杂度：O(1)。我们只需要常数空间存放若干变量。

按权重随机选择

给你一个 下标从 0 开始 的正整数数组 w ，其中 w[i] 代表第 i 个下标的权重。

请你实现一个函数 pickIndex ，它可以 随机地 从范围 [0, w.length - 1] 内（含 0 和 w.length - 1）选出并返回一个下标。选取下标 i 的 概率 为 w[i] / sum(w) 。

设数组 w的权重之和为total。将 [1,total] 范围内的所有整数分成 n个部分（其中 n 是数组 w的长度），第 i 个部分恰好包含w[i] 个整数，并且这n 个部分两两的交集为空.

class Solution {
    int[] pre;
    int total;
    public Solution(int[] w) {
        pre = new int[w.length];
        pre[0] = w[0];
        for (int i = 1; i < w.length; ++i) {
              //每个区间的左边界是在它之前出现的所有元素的和加上 11，右边界是到它为止的所有元素的和。
            pre[i] = pre[i - 1] + w[i];
        }
        total = Arrays.stream(w).sum();
    }
    
    public int pickIndex() {
        int x = (int) (Math.random() * total) + 1;
        return binarySearch(x);
    }
//由于pre[i] 是单调递增的，使用二分查找在O(logn) 的时间内快速找到i，即找出最小的满足 x≤pre[i]的下标i。
    private int binarySearch(int x) {
        int low = 0, high = pre.length - 1;
        while (low < high) {
            int mid = (high - low) / 2 + low;
            if (pre[mid] < x) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
}

• 时间复杂度：初始化的时间复杂度为 O(n)，每次选择的时间复杂度为 O(logn)，其中 n 是数组 w的长度。
• 空间复杂度:O(n)，即为前缀和数组pre 需要使用的空间。

最小栈 min函数栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

class MinStack {
    Stack<Integer> stack;
    Stack<Integer> minStack;
  //使用一个辅助栈，与元素栈同步插入与删除，用于存储与每个元素对应的最小值。
    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
        minStack.push(Integer.MAX_VALUE);
    }
    public void push(int val) { 
            minStack.push(Math.min(minStack.peek(),val));
      //当一个元素要入栈时，我们取当前辅助栈的栈顶存储的最小值，与当前元素比较得出最小值，将这个最小值插入辅助栈中；
            stack.push(val);   
    }
    public void pop() {
        minStack.pop();
        stack.pop();
    }
    public int top() {
        return stack.peek();
    }
    public int getMin() {
        return minStack.peek();
    }
}

• 时间复杂度：对于题目中的所有操作，时间复杂度均为 O(1)。因为栈的插入、删除与读取操作都是 O(1)，我们定义的每个操作最多调用栈操作两次。
• 空间复杂度：O(n)，其中n为总操作数。最坏情况下，我们会连续插入n 个元素，此时两个栈占用的空间为 O(n)

环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

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

• 时间复杂度：O(N)，其中 N是链表中的节点数。
• 空间复杂度：O(1)。我们只使用了两个指针的额外空间。

随机数索引

给你一个可能含有 重复元素 的整数数组 nums ，请你随机输出给定的目标数字 target 的索引。你可以假设给定的数字一定存在于数组中。

class Solution {
    int[] nums;
    Random random;

    public Solution(int[] nums) {
        this.nums = nums;
        random = new Random();
    }
//遍历nums，第i次遇到值为target的元素时，随机选择区间[0,i)内的一个整数，如果其等于 0，则将返回值置为该元素的下标，否则返回值不变。
    public int pick(int target) {
        int ans = 0;
        for (int i = 0, cnt = 0; i < nums.length; ++i) {
            if (nums[i] == target) {
                ++cnt; // 第 cnt 次遇到 target
                if (random.nextInt(cnt) == 0) {
                    ans = i;
                }
            }
        }
        return ans;
    }
}

• 时间复杂度：初始化为O(1)，pick 为O(n)，其中n是nums 的长度。

• 空间复杂度：O(1)。我们只需要常数的空间保存若干变量。

寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length1 = nums1.length, length2 = nums2.length;
        int totalLength = length1 + length2;
        if (totalLength % 2 == 1) {
            int midIndex = totalLength / 2;
            double median = getKthElement(nums1, nums2, midIndex + 1);
            return median;
        } else {
            int midIndex1 = totalLength / 2 - 1, midIndex2 = totalLength / 2;
            double median = (getKthElement(nums1, nums2, midIndex1 + 1) + getKthElement(nums1, nums2, midIndex2 + 1)) / 2.0;
            return median;
        }
    }

    public int getKthElement(int[] nums1, int[] nums2, int k) {
        /* 主要思路：要找到第 k (k>1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较
         * 这里的 "/" 表示整除
         * nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个
         * nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个
         * 取 pivot = min(pivot1, pivot2)，两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个
         * 这样 pivot 本身最大也只能是第 k-1 小的元素
         * 如果 pivot = pivot1，那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums1 数组
         * 如果 pivot = pivot2，那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums2 数组
         * 由于我们 "删除" 了一些元素（这些元素都比第 k 小的元素要小），因此需要修改 k 的值，减去删除的数的个数
         */

        int length1 = nums1.length, length2 = nums2.length;
        int index1 = 0, index2 = 0;
        int kthElement = 0;

        while (true) {
            // 边界情况
            if (index1 == length1) {
                return nums2[index2 + k - 1];
       //一个数组为空，说明该数组中的所有元素都被排除，返回另一个数组中第 k小的元素。
            }
            if (index2 == length2) {
                return nums1[index1 + k - 1];
            }
            if (k == 1) {
                return Math.min(nums1[index1], nums2[index2]);
            }
            
            // 正常情况
            int half = k / 2;
            int newIndex1 = Math.min(index1 + half, length1) - 1;
            int newIndex2 = Math.min(index2 + half, length2) - 1;
            int pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2];
            if (pivot1 <= pivot2) {
                k -= (newIndex1 - index1 + 1);
                index1 = newIndex1 + 1;
            } else {
                k -= (newIndex2 - index2 + 1);
                index2 = newIndex2 + 1;
            }
        }
    }
}

• 时间复杂度：O(log(m+n))，其中 m和n分别是数组 nums 1 和 nums2的长度。初始时有 k=(m+n)/2 或k=(m+n)/2+1，每一轮循环可以将查找范围减少一半，因此时间复杂度是O(log(m+n))。
• 空间复杂度：O(1)。

和为 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

class Solution {
    public int subarraySum(int[] nums, int k) {
  	    //和为键，出现次数为对应的值
        HashMap<Integer,Integer> record = new HashMap<>();
        int count = 0;
        int pre = 0;
        record.put(0,1);//pre==k时，不会被漏算
        for (int i=0;i<nums.length;i++) {
            pre += nums[i];
            if (record.containsKey(pre-k)) 
            //pre[j−1]==pre[i]−k
                count += record.get(pre-k);
            }
            record.put(pre,record.getOrDefault(pre,0)+1);
        }
        return count;
    }
}

• 时间复杂度：O(n)，其中n为数组的长度。我们遍历数组的时间复杂度为 O(n)，中间利用哈希表查询删除的复杂度均为 O(1)，因此总时间复杂度为 O(n)。
• 空间复杂度：O(n)，其中n 为数组的长度。哈希表在最坏情况下可能有 n个不同的键值，因此需要O(n) 的空间复杂度。

翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

class Solution {//递归
    public TreeNode invertTree(TreeNode root) {
        if(root == null) {
            return root;
        }
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

• 时间复杂度：O(N)，其中N为二叉树节点的数目。我们会遍历二叉树中的每一个节点，对每个节点而言，我们在常数时间内交换其两棵子树。
• 空间复杂度：O(N)。使用的空间由递归栈的深度决定，它等于当前节点在二叉树中的高度。在平均情况下，二叉树的高度与节点个数为对数关系，即 O(logN)。而在最坏情况下，树形成链状，空间复杂度为 O(N)。

class Solution {
    public TreeNode invertTree(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        if(root == null)
            return root;
        queue.offer(root);
        while (!queue.isEmpty()) {
            int n = queue.size();
            while(n-- > 0) {
                TreeNode node = queue.poll();
                TreeNode temp = node.left;
                node.left = node.right;
                node.right = temp;
                if(node.left!=null) 
                    queue.offer(node.left);
                if(node.right!=null)
                    queue.offer(node.right);
            }
        }
        return root;
    }
}

• 时间复杂度：同样每个节点都需要入队列/出队列一次，所以是 O(n)
• 空间复杂度：最坏的情况下会包含所有的叶子节点，完全二叉树叶子节点是 n/2个，所以时间复杂度是 O(n)

四数之和

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足条件且不重复的四元组

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2;i++) {
            if (i > 0 && nums[i] == nums[i-1])
            continue;
            for (int j = i +1; j < nums.length-1; j++) {
                if (j > i + 1 && nums[j] == nums[j-1])
                continue;
                int left = j + 1; 
                int right = nums.length - 1;
                while (left < right) {
                    int sum = nums[i] + nums[j] +nums[left] + nums[right];
                    if (sum > target) {
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        res.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
                        while (left < right && nums[left]==nums[left+1]) {
                            left++;
                        }
                        while (left < right && nums[right] == nums[right-1]) {
                            right--;
                        }
                        left++;
                        right--;
                    }
                }
            }
        }
        return res;
    }
}

• 时间复杂度：O(n3)，其中n是数组的长度。排序的时间复杂度是O(nlogn)，枚举四元组的时间复杂度是 O(n3)，因此总时间复杂度为O(n3+nlogn)=O(n3 )。
• 空间复杂度：O(logn)，其中n是数组的长度。空间复杂度主要取决于排序额外使用的空间。此外排序修改了输入数组nums，实际情况中不一定允许，因此也可以看成使用了一个额外的数组存储了数组nums 的副本并排序，空间复杂度为O(n)。

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

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0,head);
        ListNode slow = dummy;
        ListNode fast = dummy;
        while(n-- > 0) {
            fast = fast.next;
        }
        while(fast.next!=null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}

• 时间复杂度：O(L)，其中 L 是链表的长度。
• 空间复杂度：O(1)。

牛客

两数之和

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

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; ++i) {
            if (hashtable.containsKey(target - nums[i])) {
                return new int[]{hashtable.get(target - nums[i]), i};
            }
            hashtable.put(nums[i], i);
        }
        return new int[0];
    }
}

• 时间复杂度: O(N)，其中N是数组中的元素数量。对于每一个元素 x，我们可以O(1) 地寻找 target - x。
• 空间复杂度:O(N)，其中N是数组中的元素数量。主要为哈希表的开销。

用栈实现队列

存储n个元素的空间复杂度为O(n) ，插入与删除的时间复杂度都是 O(1)

class MyQueue {
    Stack<Integer> s1;
    Stack<Integer> s2;
    public MyQueue() {
        s1 = new Stack<>();
        s2 = new Stack<>();
    }
    
    public void push(int x) {
      //时间O(1),空间O(n)
        s1.push(x);
    }
    
    public int pop() {
      //时间O(1),空间O(n)
        if (!s2.isEmpty()) {
            return s2.pop();
        } else {
            while (!s1.isEmpty()) {
                s2.push(s1.pop());
            }
            return s2.pop();
        }
    }
    
    public int peek() {
        if (!s2.isEmpty()) {
            return s2.peek();
        } else {
            while (!s1.isEmpty()) {
                s2.push(s1.pop());
            }
            return s2.peek();
        }
    }
    
    public boolean empty() {
        return s1.isEmpty() && s2.isEmpty();
    }
}

青蛙跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

class Solution {
    public int numWays(int n) {
        int a = 1, b = 1, sum;
        for(int i = 0; i < n; i++){
          //随着n增大, f(n)会超Int32甚至Int64 的取值范围，导致最终的返回值错误,此操作与最终返回前取余等价。
            sum = (a + b) % 1000000007;
            a = b;
            b = sum;
        }
        return a;
    }
}

• 时间复杂度O(N) ： 计算 f(n)需循环n次，每轮循环内计算操作使用 O(1) 。
• 空间复杂度 O(1)： 几个标志变量使用常数大小的额外空间。

最长无重复子数组

给定一个长度为n的数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。

public class Solution {
    public int maxLength (int[] arr) {
        Set<Integer> record = new HashSet<>();
      // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        int right = -1, res = 0;
        for (int left = 0; left < arr.length;left++) {
            if(left!=0) {
              // 左指针向右移动一格，移除一个字符
                record.remove(arr[left-1]);
            }
            while(right+1<arr.length&& !record.contains(arr[right+1])) {
              // 不断地移动右指针
                record.add(arr[right+1]);
                right++;
            }
            res = Math.max(res,right-left+1);
        }
        return res;
    }
}

• 时间复杂度：O(N)，其中N 是字符串的长度。左指针和右指针分别会遍历整个字符串一次。
• 空间复杂度：O(∣Σ∣)，其中Σ 表示字符集（即字符串中可以出现的字符），∣Σ∣ 表示字符集的大小。

合并两个有序的数组

给出一个有序的整数数组 A 和有序的整数数组 B ，请将数组 B 合并到数组 A 中，变成一个有序的升序数组

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

• 时间复杂度：O(m+n)。指针移动单调递减，最多移动m+n次，因此时间复杂度O(m+n)。
• 空间复杂度：O(1)直接对数组nums 1原地修改，不需要额外空间。

链表中环的入口结点

public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if (pHead == null)
            return null;
        ListNode slow = pHead;
        ListNode fast = pHead;
        while (fast!=null&&fast.next!=null) {
            slow = slow.next;
            fast = fast.next.next;
            if (fast == slow) {
                ListNode temp = pHead;
              //slow 与fast 相遇时，使指针指向链表头部；它和slow 每次向后移动一个位置。最终，它们会在入环点相遇。
                while (temp != fast) {
                    fast = fast.next;
                    temp = temp.next;
                }
                return temp;
            }
        }
        return null;
    }
}

• 时间复杂度：O(N)，其中N为链表中节点的数目。在最初判断快慢指针是否相遇时，slow 指针走过的距离不会超过链表的总长度；随后寻找入环点时，走过的距离也不会超过链表的总长度。
• 空间复杂度：O(1)。只使用了slow,fast,ptr 三个指针。

有效括号序列

public class Solution {
    public boolean isValid (String s) {
        if(s.length()%2==1)
            return false;
        HashMap<Character,Character> record = new HashMap<>();
        record.put(')','(');
        record.put(']','[');
        record.put('}','{');
        Stack<Character> stack = new Stack<>();
        for (int i =0;i<s.length();i++) {
            char ch = s.charAt(i);
            if(record.containsKey(ch)) {
                if(stack.isEmpty()||stack.pop()!=record.get(ch)) {
                    return false;
                }
            } else {
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }
}

• 时间复杂度：O(n)，其中n是字符串s的长度。
• 空间复杂度：O(n+∣Σ∣)，Σ 表示字符集，本题中字符串只包含 6种括号，∣Σ∣=6。栈中的字符数量为O(n)，而哈希表使用的空间为O(∣Σ∣)，相加即可得到总空间复杂度。

大数加法

以字符串的形式读入两个数字，编写一个函数计算它们的和，以字符串形式返回。

public class Solution {
    public String solve (String s, String t) {
        int i = s.length()-1;//i和y指向string末尾
        int j = t.length()-1;
        int add = 0;//维护当前是否有进位
        StringBuilder sb = new StringBuilder();
        while (i >= 0||j>=0||add!=0) {
            int x=i>=0?s.charAt(i)-'0':0;
            int y=j>=0?t.charAt(j)-'0':0;
            int sum = x+y+add;
            add =sum/10;
            sb.append(sum%10);
            i--;
            j--;
        }
        sb.reverse();
        return sb.toString();
    }
}

• 时间复杂度：O(max(len1 ,len2))，其中 len1=num1.length，len2=num2.length。竖式加法的次数取决于较大数的位数。
• 空间复杂度：使用到了 StringBuffer，故 Java 解法的空间复杂度为O(n)。

最长公共子串

给定两个字符串str1和str2,输出两个字符串的最长公共子串，题目保证str1和str2的最长公共子串存在且唯一。

public String LCS(String str1, String str2) {
    int maxLenth = 0;//记录最长公共子串的长度
    //记录最长公共子串最后一个元素在字符串str1中的位置
    int maxLastIndex = 0;
    int[][] dp = new int[str1.length() + 1][str2.length() + 1];
    for (int i = 0; i < str1.length(); i++) {
        for (int j = 0; j < str2.length(); j++) {
            //递推公式，两个字符相等的情况
            if (str1.charAt(i) == str2.charAt(j)) {
                dp[i + 1][j + 1] = dp[i][j] + 1;
                //如果遇到了更长的子串，要更新，记录最长子串的长度，
                //以及最长子串最后一个元素的位置
                if (dp[i + 1][j + 1] > maxLenth) {
                    maxLenth = dp[i + 1][j+1];
                    maxLastIndex = i;
                }
            } else {
                //递推公式，两个字符不相等,不能构成公共子串
                dp[i + 1][j+1] = 0;
            }
        }
    }
    //最字符串进行截取，substring(a,b)中a和b分别表示截取的开始和结束位置
    return str1.substring(maxLastIndex - maxLenth + 1, maxLastIndex + 1);
}

• 时间复杂度：O（mn），m和n分别表示两个字符串的长度
• 空间复杂度：O（mn）

链表相加

假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。给定两个这种链表，请生成代表两个整数相加值的结果链表

public class Solution {
    public ListNode addInList (ListNode head1, ListNode head2) {
      //把所有数字压入栈中，再依次取出相加
        Stack<Integer> s1 = new Stack<>();
        Stack<Integer> s2 = new Stack<>();
        while (head1!=null) {
            s1.push(head1.val);
            head1=head1.next;
        }
        while(head2!=null){
            s2.push(head2.val);
            head2=head2.next;
        }
        int add = 0;
        ListNode res = null;
        while(!s1.isEmpty()||!s2.isEmpty()||add!=0){
            int x=s1.isEmpty()?0:s1.pop();
            int y=s2.isEmpty()?0:s2.pop();
            int sum=x+y+add;
            add = sum/10;
            ListNode node = new ListNode(sum%10);
            node.next=res;
            res = node;
        }
        return res;
    }
}

• 时间复杂度：O(max(m,n))，其中m和n分别为两个链表的长度。我们需要遍历两个链表的全部位置，而处理每个位置只需要O(1) 的时间。
• 空间复杂度：O(m+n)，其中m和n分别为两个链表的长度。空间复杂度主要取决于我们把链表内容放入栈中所用的空间

反转字符串

public class Solution {
    public String solve (String str) {
        char[] s = str.toCharArray();
        int left = 0;
        int right = s.length-1;
        while (left<right) {
            s[left] ^= s[right];
            s[right] ^= s[left];
            s[left] ^= s[right];
            left++;
            right--;
        }
        return new String(s);
    }
}

• 空间复杂度 O(n)
• 时间复杂度 O(n)

斐波那契数列

class Solution {
    public int fib(int n) {
        if (n < 2) {
            return n;
        }
        int p = 0, q = 0, r = 1;
        for (int i = 2; i <= n; ++i) {
          //滚动数组思想
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }
}

• 时间复杂度：O(n)。
• 空间复杂度：O(1)。

最长回文子串

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) {
            return "";
        }
      // 初始化最大回文子串的起点和终点
        int start = 0, end = 0;
       // 遍历每个位置，当做中心位
        for (int i = 0; i < s.length(); i++) {
          //从子串长度为1或2的边界情况向两端扩展
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
           // 计算对应最大回文子串的起点和终点
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    public int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
          //两边字母不同停止，之后的子串都不是回文的
            --left;
            ++right;
        }
        return right - left - 1;
    }
}

• 时间复杂度:O(n2)，其中n是字符串的长度。长度为1和2的回文中心分别有n和n−1个，每个回文中心最多会向外扩展 O(n)次。
• 空间复杂度：O(1)

从前序与中序遍历序列构造二叉树 重建二叉树

给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。

class Solution {
  //键表示一个元素（节点的值），值表示其在中序遍历中的出现位置
    private Map<Integer, Integer> indexMap;
    public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if (preorder_left > preorder_right) {
            return null;
        }
        // 前序遍历中的第一个节点就是根节点
        int preorder_root = preorder_left;
        // 在中序遍历中定位根节点
        int inorder_root = indexMap.get(preorder[preorder_root]);
        // 先把根节点建立出来
        TreeNode root = new TreeNode(preorder[preorder_root]);
        // 得到左子树中的节点数目
        int size_left_subtree = inorder_root - inorder_left;
        // 递归地构造左子树，并连接到根节点
        // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
        root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
        // 递归地构造右子树，并连接到根节点
        // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
        root.right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
        return root;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        // 构造哈希映射，帮助我们快速定位根节点
        indexMap = new HashMap<Integer, Integer>();
        for (int i = 0; i < n; i++) {
            indexMap.put(inorder[i], i);
        }
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }
}

• 时间复杂度：O(n)，其中n是树中的节点个数。
• 空间复杂度:O(n)，除去返回的答案需要的 O(n)空间之外，还需要使用O(n) 的空间存储哈希映射，以及O(h)（其中h是树的高度）的空间表示递归时栈空间。这里h<n，所以总空间复杂度为O(n)。

求平方跟 sqrt

public class Solution {
    public int sqrt (int x) {
        int left = 0;
        int right = x;
        int res = -1;
        while (left <= right) {
            int mid = left+(right-left)/2;
            if ((long)mid*mid <= x) {
                res = mid;
                left = mid +1;
            } else {
                right = mid -1;
            }
        }
        return res;
    }
}

• 时间复杂度：O(logx)，即为二分查找需要的次数。
• 空间复杂度：O(1)。

字符串的排序

输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。

public class Solution {
    ArrayList<String> res;
    boolean[] used;
    public ArrayList<String> Permutation(String str) {
       int n = str.length();
        res = new ArrayList<>();
        used = new boolean[n];
        char[] arr = str.toCharArray();
        Arrays.sort(arr);
        StringBuilder sb = new StringBuilder();
        backTrack(arr,sb);
        return res;
    }
    private void backTrack(char[] arr,StringBuilder sb){
        if (sb.length()==arr.length){
            res.add(sb.toString());
            return;
        }
        for(int i=0;i<arr.length;i++) {
          // used[i - 1] == true，说明同⼀树⽀arr[i - 1]使⽤过
          // used[i - 1] == false，说明同⼀树层arr[i - 1]使⽤过
          // 如果同⼀树层arr[i - 1]使⽤过则直接跳过
            if(i>0&&arr[i-1]==arr[i]&&used[i-1]==false) {
                continue;
            }
            if(used[i]==false){//如果同⼀树⽀arr[i]没使⽤过开始处理
                used[i]=true;//标记同⼀树⽀arr[i]使⽤过，防止同一树支重复使用
                sb.append(arr[i]);
                backTrack(arr,sb);
                sb.deleteCharAt(sb.length()-1);
                used[i] = false;
            }
        }
    }
}

• 时间复杂度：O(n×n!)，其中n为给定字符串的长度。这些字符的全部排列有O(n!) 个，每个排列平均需要O(n)的时间来生成。
• 空间复杂度:O(n)。需要O(n)的栈空间进行回溯，注意返回值不计入空间复杂度。

二叉树的最大深度

求给定二叉树的最大深度，深度是指树的根节点到任一叶子节点路径上节点的数量。

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            int leftHeight = maxDepth(root.left);
            int rightHeight = maxDepth(root.right);
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }
}

• 时间复杂度：O(n)，其中n为树节点的个数。每个节点在递归中只被遍历一次。
• 空间复杂度：O(height)，其中height 表示树的高度。递归函数需要栈空间，而栈空间取决于递归的深度，因此空间复杂度等价于树的高度。

单链表的排序

给定一个节点数为n的无序单链表，对其按升序排序。 归并

public class Solution {
    public ListNode sortInList (ListNode head) {
        if(head == null) {
            return head;
        }
        int len = 0;//链表长度
        ListNode node = head;
        while (node != null) {
            len++;
            node = node.next;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
      //subLength 表示每次需要排序的子链表的长度
        for(int subLength=1;subLength<len;subLength<<=1) {
            ListNode pre = dummy, cur = dummy.next;
            while (cur != null) {
   //每次将链表拆分成若干个长度为subLength 的子链表，按照每两个子链表一组进行合并
                ListNode head1 = cur;
                for(int i=1;i<subLength&&cur.next!=null;i++) {
                    cur = cur.next;
                }
                ListNode head2 = cur.next;
                cur.next = null;
                cur = head2;
                for(int i=1;i<subLength&&cur!=null&&cur.next!=null;i++){
                    cur = cur.next;
                }
                ListNode next = null;
                if (cur!=null){
                    next = cur.next;
                    cur.next = null;
                }
                ListNode merged = merge(head1,head2);
                pre.next = merged;
                while(pre.next != null) {
                    pre = pre.next;
                }
                cur = next;
            }
        }
        return dummy.next;
    }
    private ListNode merge(ListNode head1,ListNode head2){
        ListNode dummy = new ListNode(0);
        ListNode temp = dummy,temp1 = head1, temp2 = head2;
        while(temp1 != null && temp2 != null){
            if (temp1.val <= temp2.val){
                temp.next = temp1;
                temp1 = temp1.next;
            } else {
                temp.next = temp2;
                temp2 = temp2.next;
            }
            temp = temp.next;
        }
        if(temp1 !=null){
            temp.next = temp1;
        } else if(temp2 != null) {
            temp.next = temp2;
        }
        return dummy.next;
    }
}

• 时间复杂度：O(nlogn)，其中 n 是链表的长度。
• 空间复杂度：O(1)。

最小路径和

给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。

public class Solution {
    public int minPathSum (int[][] matrix) {
        // write code here
        int[][] dp = new int[matrix.length][matrix[0].length];
        dp[0][0] = matrix[0][0];
        for (int i = 1;i<matrix.length;i++) {
            dp[i][0] = dp[i-1][0]+matrix[i][0];
        }
        for(int i=1;i<matrix[0].length;i++) {
            dp[0][i] = dp[0][i-1]+matrix[0][i];
        }
        for(int i = 1;i<matrix.length;i++) {
            for (int j= 1;j< matrix[0].length;j++) {
                dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1])+matrix[i][j];
            }
        }
        return dp[matrix.length-1][matrix[0].length-1];
    }
}

• 时间复杂度：O(mn)，其中m和n分别是网格的行数和列数。需要对整个网格遍历一次，计算 dp 的每个元素的值。
• 空间复杂度：O(mn)，其中m和n分别是网格的行数和列数。创建一个二维数组dp，和网格大小相同。空间复杂度可以优化，例如每次只存储上一行的dp 值，则可以将空间复杂度优化到 O(n)。

表达式求值 基本计算器

public class Solution {
    // 使用 map 维护一个运算符优先级（其中加减法优先级相同，乘法有着更高的优先级）
    Map<Character, Integer> map = new HashMap<Character, Integer>(){{
        put('-', 1);
        put('+', 1);
        put('*', 2);
    }};

    public int solve(String s) {
        // 将所有的空格去掉
        s = s.replaceAll(" ", "");

        char[] cs = s.toCharArray();
        int n = s.length();

        // 存放所有的数字
        Deque<Integer> nums = new ArrayDeque<>();
        // 为了防止第一个数为负数，先往 nums 加个 0
        nums.addLast(0);
        // 存放所有「非数字以外」的操作
        Deque<Character> ops = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            char c = cs[i];
            if (c == '(') {
                ops.addLast(c);
            } else if (c == ')') {
                // 计算到最近一个左括号为止
                while (!ops.isEmpty()) {
                    if (ops.peekLast() != '(') {
                        calc(nums, ops);
                    } else {
                        ops.pollLast();
                        break;
                    }
                }
            } else {
                if (isNumber(c)) {
                    int u = 0;
                    int j = i;
                    // 将从 i 位置开始后面的连续数字整体取出，加入 nums
                    while (j < n && isNumber(cs[j])) u = u * 10 + (cs[j++] - '0');
                    nums.addLast(u);
                    i = j - 1;
                } else {
                    if (i > 0 && (cs[i - 1] == '(' || cs[i - 1] == '+' || cs[i - 1] == '-')) {
                        nums.addLast(0);
                    }
                    // 有一个新操作要入栈时，先把栈内可以算的都算了 
                    // 只有满足「栈内运算符」比「当前运算符」优先级高/同等，才进行运算
                    while (!ops.isEmpty() && ops.peekLast() != '(') {
                        char prev = ops.peekLast();
                        if (map.get(prev) >= map.get(c)) {
                            calc(nums, ops);
                        } else {
                            break;
                        }
                    }
                    ops.addLast(c);
                }
            }
        }
        // 将剩余的计算完
        while (!ops.isEmpty() && ops.peekLast() != '(') calc(nums, ops);
        return nums.peekLast();
    }
    // 计算逻辑：从 nums 中取出两个操作数，从 ops 中取出运算符，然后根据运算符进行计算即可
    void calc(Deque<Integer> nums, Deque<Character> ops) {
        if (nums.isEmpty() || nums.size() < 2) return;
        if (ops.isEmpty()) return;
        int b = nums.pollLast(), a = nums.pollLast();
        char op = ops.pollLast();
        int ans = 0;
        if (op == '+') ans = a + b;
        else if (op == '-') ans = a - b;
        else if (op == '*') ans = a * b;    
        nums.addLast(ans);
    }
    boolean isNumber(char c) {
        return Character.isDigit(c);
    }
}

• 时间复杂度：O(n)
• 空间复杂度：O(n)

判断平衡二叉树

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        int height = judge(root);
        return height >= 0;
    }
    private int judge (TreeNode root) {
        if (root == null)
            return 0;
        int left = judge(root.left);
        int right = judge(root.right);
        if(left==-1||right==-1||Math.abs(left-right)>1) {
            return -1;
        } else {
            return Math.max(left,right)+1;
        }
    }
}

• 时间复杂度：O(n)，其中n是二叉树中的节点个数。使用自底向上的递归，每个节点的计算高度和判断是否平衡都只需要处理一次，最坏情况下需要遍历二叉树中的所有节点，因此时间复杂度是O(n)。
• 空间复杂度：O(n)，其中n 是二叉树中的节点个数。空间复杂度主要取决于递归调用的层数，递归调用的层数不会超过n。

数组中超过一半的数字

class Solution {
    public int majorityElement(int[] nums) {
        int candidate = 0;
        int count = 0;
        for (int n : nums) {
            if (count == 0)
                candidate = n;
            if (candidate == n) {
                count++;
            } else {
                count--;
            }
        }
        return candidate;
    }
}

• 时间复杂度：O(n)。Boyer-Moore 算法只对数组进行了一次遍历。
• 空间复杂度：O(1)。Boyer-Moore 算法只需要常数级别的额外空间。

字符串出现次数topk

import java.util.*;
public class Solution {
public String[][] topKstrings (String[] strings, int k) {
   // write code here
   if (k == 0){
       return new String[][]{};
   }
   String[][] res = new String[k][2];
   TreeMap<String,Integer> map = new TreeMap<>();
   // 统计各个字符串出现的次数
   for (int i=0;i<strings.length;++i){
       String s = strings[i];
       if (!map.containsKey(s)) {
           map.put(s, 1);
       } else {
           map.put(s, map.get(s) + 1);
       }
   }

   ArrayList<Map.Entry<String, Integer>> list = 
       new ArrayList<>(map.entrySet());
   // 先是按出现次数降序比较，相同则再按照字符ASCII码降序比较
   Collections.sort(list,
                    (o1, o2) -> 
                    (o1.getValue().compareTo(o2.getValue()) ==
                     0 ? o1.getKey().compareTo(o2.getKey()) : 
                     o2.getValue().compareTo(o1.getValue()))
                   );
   // 返回topK
   for (int i = 0; i < k; i++) {
       res[i][0] = list.get(i).getKey();
       res[i][1] = String.valueOf(list.get(i).getValue());
   }
   return res;
}
}

• 时间复杂度：O(nlogn)，遍历统计为O(N)，但是降序排序需要O(nlogn)
• 空间复杂度：O(n)，使用hashmap辅助结构。

进制转换

给定一个十进制数 M ，以及需要转换的进制数 N 。将十进制数 M 转化为 N 进制数。

public String solve (int M, int N) {
        // write code here
        if(M == 0)  return "0";
        String s = "0123456789ABCDEF";
        StringBuffer sb = new StringBuffer();
        boolean f = false;
        if(M < 0){
            f = true;
            M = -M;
        }
        while(M != 0){
            sb.append(s.charAt(M%N));
            M /= N;
        }
        if(f) sb.append("-");
        return sb.reverse().toString();
    }
}

• 时间 O(M)
• 空间 O((N))

leetcode

整数反转

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。

class Solution {
    public int reverse(int x) {
        int res = 0;
        while (x != 0) {
            if (res < Integer.MIN_VALUE/10||res>Integer.MAX_VALUE/10) {
                return 0;
            }
            int digit = x % 10;
            x /= 10;
            res = res*10 + digit;
        }
        return res;
    }
}

• 时间复杂度：O(log∣x∣)。翻转的次数即 x十进制的位数。
• 空间复杂度：O(1)。

字典序的第K小数字

给定整数 n 和 k，返回 [1, n] 中字典序第 k 小的数字。

1.初始化前缀为1，计算以1开头的节点树的所有子树结点个数，如果小于k，那么根节点往右走（说明当前子 树的结点树不够）；如果大于k，那么根节点往下走（说明答案就在当前根节点的子 树结点）

2.减去已遍历过的结点数之后，可以直接将当前结点看成新的根节点，一直重复这两步的操作，直到k = 0，找到答案。

public int findKthNumber(int n, int k) {
        //从根节点下面的第一个结点1开始遍历，由于数据范围很大，所以用long
        long cur = 1;
        //从1出发开始往后按字典序从小到大的顺序走k-1步到达的就是 字典序的第K小数字
        k -= 1;
        while (k > 0) {
            //得到以当前结点为根的所有子树节点数目
            int nodes = getNodes(n, cur);
            //如果k要大于当前根节点下所有子树结点的数目，就向右侧节点走(->2->3->4->5->6->7->8->9)：字典序上升nodes位
            if (k >= nodes) {
                //减去已经遍历的个数
                k -= nodes;
                //根节点右移
                cur ++;
            } 
            //如果k小于当前根节点下所有子树结点的数目，说明答案就在当前根节点的子树结点中
            else {
                //减去根节点的数量1
                k -= 1;
                //将根结点移动到下一层（每一层右10个结点）
                cur *= 10;
            }
        }
        //最终k = 0时，就找到了答案
        return (int)cur;
    }

    // 计算以cur为根的子树节点数目，所有节点的值必须 <= n
    private int getNodes(int n, long cur){
        // 记录子树中的全部节点数目
        long totalNodes = 0; 
        // 当前节点右侧右边节点的值
        long next = cur + 1; 
        while(cur <= n){
            //取整行结点的个数，可能全部都满了，也可能是叶子结点，没有充满
            totalNodes += Math.min(n - cur + 1, next - cur);
            //cur - cur在当前层的第一个结点， next - cur右侧根结点的第一个结点
            next *= 10;
            cur *= 10;
        }
        return (int)totalNodes;
    }

• 时间复杂度：O(log2n)，其中 n为 给定的 数值的大小。每次计算子树下的节点数目的搜索深度最大为log10n，最多需要搜索log10n 层，每一层最多需要计算10 次，最多需要计算 (log 10n) 2 次，因此时间复杂度为 O(log 2n)。
• 空间复杂度：O(1)不需要开辟额外的空间，只需常数空间记录常量即可。

分发糖果

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。你需要按照以下要求，给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int ret = 1;
        int inc = 1, dec = 0, pre = 1;
        for (int i = 1; i < n; i++) {
            if (ratings[i] >= ratings[i - 1]) {
                dec = 0;
        //如果当前同学比上一个同学评分高，说明我们就在最近的递增序列中，直接分配给该同学pre+1个糖果即可。
                pre = ratings[i] == ratings[i - 1] ? 1 : pre + 1;
                ret += pre;
                inc = pre;
            } else {
       //否则我们就在一个递减序列中，我们直接分配给当前同学一个糖果，并把该同学所在的递减序列中所有的同学都再多分配一个糖果，以保证糖果数量还是满足条件。
                dec++;
                if (dec == inc) {
  //当当前的递减序列长度和上一个递增序列等长时，需要把最近的递增序列的最后一个同学也并进递减序列中
                    dec++;
                }
                ret += dec;
                pre = 1;
            }
        }
        return ret;
    }
}

• 时间复杂度：O(n)，其中 n是孩子的数量。我们需要遍历两次数组以分别计算满足左规则或右规则的最少糖果数量。

• 空间复杂度：O(1)。我们只需要常数的空间保存若干变量。