//思路一：桶排序
//设置若干个桶，每个桶存储出现频率相同的数，并且桶的下标代表桶中数出现的频率，即第 i 个桶中存储的数出现的频率为 i。
//把数都放到桶之后，从后向前遍历桶，最先得到的 k 个数就是出现频率最多的的 k 个数。
class Solution {
    
    public List<Integer> topKFrequent(int[] nums, int k) {
        //统计数组中元素出现频率
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int num : nums){
            map.put(num, map.getOrDefault(num,0)+1);
        }

        //每个桶存储出现频率相同的数，并且桶的下标代表桶中数出现的频率
        List<Integer>[] buckets = new ArrayList[nums.length+1];
        for(Integer num : map.keySet()){
            Integer freq = map.get(num);
            if(buckets[freq] == null){
                buckets[freq] = new ArrayList<>();
            }
            buckets[freq].add(num);
        }

        List<Integer> res = new ArrayList<>();
        for(int i=buckets.length-1;i>=0 && res.size()<k;i--){
            if(buckets[i]==null){
                continue;
            }
            if(buckets[i].size() <= (k-res.size())){
                res.addAll(buckets[i]);
            }else{
                res.addAll(buckets[i].subList(0,k-res.size()));
            }
        }

        return res;
    }
}

//思路二：堆排序
//利用堆排序
class Solution{
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> res = new ArrayList<>();

        HashMap<Integer,Integer> map = new HashMap<>();
        for(int num : nums){
            int freq = map.getOrDefault(num,0);
            map.put(num,++freq);
        }

        Set<Integer> set = map.keySet();
        Element[] elements = new Element[set.size()];
        int i=0;
        for(Integer key : set){
            elements[i] = new Element(key,map.get(key));
            i++;
        }

        PriorityQueue<Element> pq = new PriorityQueue<>();
        for(Element element : elements){
            pq.add(element);
            if(pq.size() > k){
                pq.poll();
            }
        }

        while(!pq.isEmpty()){
            Element element = pq.poll();
            res.add(element.num);
        }
        return res;
    }
}

class Element implements Comparable<Element>{
    int num;
    int freq;
    Element(int num,int freq){
        this.num = num;
        this.freq = freq;
    }

    @Override
    public int compareTo(Element o) {
        return this.freq - o.freq;
    }
}

//思路如上图：
//i指向值为0的元素，swap(i,zero+1) ,交换后，i位置元素是1(nums[zero+1..i+1]==1)，
//不需要处理，i直接+1
//i指向值为1的元素，不需要处理直接+1
//i指向值为2的元素，swap(i,two-1),交换后，two-1位置元素就是2
public void sortColors(int[] nums) {
	int zero = -1;
	int two = nums.length;
	int i = 0;
	while(i<two){
		if(nums[i] ==0){
			zero++;
			swap(nums,zero,i);
			i++;
		}else if(nums[i] ==2){
			two--;
			swap(nums,two,i);
		}else{
			i++;
		}
	}
}

private void swap(int[] nums,int i,int j){
	int tmp = nums[i];
	nums[i] = nums[j];
	nums[j] = tmp;
}

//思路：
//1、注意：这里求的是求第k个最大元素，就是求(nums.length-k+1)个最小元素
//2、求第m小的元素，是非常典型的快速排序的应用
public int findKthLargest(int[] nums, int k) {
	//1 <= k <= nums.length
	k = nums.length - k + 1; //转化为第k小元素问题

	int lo = 0;
	int hi = nums.length -1;
	while(lo<=hi){
		int p = partition(nums,lo,hi);
		if(p == k-1){
			return nums[p];
		}else if(p<(k-1)){
			lo++;
		}else{ //p> k-1
			assert p > (k-1);
			hi--;
		}
	}
	return nums[0];
}

private int partition(int[] nums,int l,int r){
	int pivot = nums[l];

	while(l < r){
		//从右向左查找第一个 < pivot 的元素
		while(l < r && nums[r] >= pivot){
			r--;
		}
		nums[l] = nums[r];
		//从左向右查找第一个 > pivot 的元素
		while(l < r && nums[l] <= pivot){
			l++;
		}
		nums[r] = nums[l];
	}
	nums[l] = pivot;
	return l;
}

public List<Integer> diffWaysToCompute(String input) {
	List<Integer> res = new ArrayList<>();

	for(int i=0;i<input.length();i++){
		char c = input.charAt(i);
		if( c =='+' || c=='-' || c=='*'){ //根据运算符进行分治
			List<Integer> left = diffWaysToCompute(input.substring(0,i));
			List<Integer> right = diffWaysToCompute(input.substring(i+1));
			System.out.println(input);
			System.out.println("left:"+left+"，right:"+right);
			System.out.println("==================");
			for(int l : left){
				for(int r : right){
					switch (c){
						case '+' :
							res.add(l+r);
							break;
						case '-' :
							res.add(l-r);
							break;
						case '*' :
							res.add(l*r);
							break;
					}
				}
			}
		}
	}

	if(res.size() ==0){ //说明input 是一个数字
		res.add(Integer.valueOf(input));
	}
	return res;
}

//思路：分治法
//如果把数组分成左右两段，那么加和最大的连续子序列，
//要么出现在数组的左半部分，
//要么出现在数组的右半部分，
//要么出现在中间，即从左半部分和右半部分相邻的地方各取一段。
public int maxSubArray(int[] nums) {
	return maxSubArray(nums,0,nums.length-1);
}

private int maxSubArray(int[] nums,int l,int r){
	if(l==r){
		return nums[l];
	}
	int mid = l + (r-l)/2;
	int leftSubMax = maxSubArray(nums,l,mid);
	int rightSubMax = maxSubArray(nums,mid+1,r);

	int subMax = nums[mid];
	int sum = subMax; //中间元素必然在该最大连续子序列中

	//从中间向左半数组遍历
	for(int i=mid-1;i>=l;i--){
		sum += nums[i];
		subMax = Math.max(subMax,sum);
	}
	sum = subMax;
	//从中间向右半数组遍历
	for(int i=mid+1;i<=r;i++){
		sum += nums[i];
		subMax = Math.max(subMax,sum);
	}
	return max3(leftSubMax,subMax,rightSubMax);
}

private int max3(int a,int b,int c){
	int tmp = (a>b) ? a:b;
	return (tmp>c? tmp : c);
}

public List<TreeNode> generateTrees(int n) {
	if(n==0){
		return new LinkedList<>();
	}
	return generateSubTrees(1,n);
}

public List<TreeNode> generateSubTrees(int s,int e){
	List<TreeNode> res = new LinkedList<>();
	if(s>e){
		res.add(null);
		return res;
	}
	for(int i=s;i<=e;i++){
		List<TreeNode> left = generateSubTrees(s,i-1);
		List<TreeNode> right = generateSubTrees(i+1,e);
		for(TreeNode l : left){
			for(TreeNode r : right){
				TreeNode root = new TreeNode(i);
				root.left = l;
				root.right = r;
				res.add(root);
			}
		}
	}
	return res;
}

//思路：贪心策略
//每次选取最大的饼干给最"贪心"的小朋友。
public int findContentChildren(int[] g, int[] s) {
  Arrays.sort(g);
  Arrays.sort(s);

  int gi = g.length-1;
  int si = s.length-1;
  int res=0;
  while(gi>=0 && si>=0){
    if(s[si]>=g[gi]){
      res++;
      gi--;
      si--;
    }else{ //不能满足这个小朋友,抱歉，饼干就不分给他了。
      gi--;
    }
  }
  return res;
}

public int eraseOverlapIntervals(Interval[] intervals) {
    if (intervals.length == 0) {
        return 0;
    }
    Arrays.sort(intervals, Comparator.comparingInt(o -> o.end));
    int cnt = 1;
    int end = intervals[0].end;
    for (int i = 1; i < intervals.length; i++) {
        if (intervals[i].start < end) {
            continue;
        }
        end = intervals[i].end;
        cnt++;
    }
    return intervals.length - cnt;
}

Arrays.sort(intervals, new Comparator<Interval>() {
    @Override
    public int compare(Interval o1, Interval o2) {
        return o1.end - o2.end;
    }
});

public int findMinArrowShots(int[][] points) {
    if (points.length == 0) {
        return 0;
    }
    Arrays.sort(points, Comparator.comparingInt(o -> o[1]));
    int cnt = 1, end = points[0][1];
    for (int i = 1; i < points.length; i++) {
        if (points[i][0] <= end) {
            continue;
        }
        cnt++;
        end = points[i][1];
    }
    return cnt;
}

public int[][] reconstructQueue(int[][] people) {
    if (people == null || people.length == 0 || people[0].length == 0) {
        return new int[0][0];
    }
    Arrays.sort(people, (a, b) -> (a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]));
    List<int[]> queue = new ArrayList<>();
    for (int[] p : people) {
        queue.add(p[1], p);
    }
    return queue.toArray(new int[queue.size()][]);
}

public List<Integer> partitionLabels(String S) {
    int[] lastIndexsOfChar = new int[26];
    for (int i = 0; i < S.length(); i++) {
        lastIndexsOfChar[char2Index(S.charAt(i))] = i;
    }
    List<Integer> partitions = new ArrayList<>();
    int firstIndex = 0;
    while (firstIndex < S.length()) {
        int lastIndex = firstIndex;
        for (int i = firstIndex; i < S.length() && i <= lastIndex; i++) {
            int index = lastIndexsOfChar[char2Index(S.charAt(i))];
            if (index > lastIndex) {
                lastIndex = index;
            }
        }
        partitions.add(lastIndex - firstIndex + 1);
        firstIndex = lastIndex + 1;
    }
    return partitions;
}

private int char2Index(char c) {
    return c - 'a';
}

public boolean canPlaceFlowers(int[] flowerbed, int n) {
    int len = flowerbed.length;
    int cnt = 0;
    for (int i = 0; i < len && cnt < n; i++) {
        if (flowerbed[i] == 1) {
            continue;
        }
        int pre = i == 0 ? 0 : flowerbed[i - 1];
        int next = i == len - 1 ? 0 : flowerbed[i + 1];
        if (pre == 0 && next == 0) {
            cnt++;
            flowerbed[i] = 1;
        }
    }
    return cnt >= n;
}

public boolean isSubsequence(String s, String t) {
    int index = -1;
    for (char c : s.toCharArray()) {
        index = t.indexOf(c, index + 1);
        if (index == -1) {
            return false;
        }
    }
    return true;
}

public boolean checkPossibility(int[] nums) {
    int cnt = 0;
    for (int i = 1; i < nums.length && cnt < 2; i++) {
        if (nums[i] >= nums[i - 1]) {
            continue;
        }
        cnt++;
        if (i - 2 >= 0 && nums[i - 2] > nums[i]) {
            nums[i] = nums[i - 1];
        } else {
            nums[i - 1] = nums[i];
        }
    }
    return cnt <= 1;
}

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

public int maxSubArray(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int preSum = nums[0];
    int maxSum = preSum;
    for (int i = 1; i < nums.length; i++) {
        preSum = preSum > 0 ? preSum + nums[i] : nums[i];
        maxSum = Math.max(maxSum, preSum);
    }
    return maxSum;
}

public int maxProfit(int[] prices) {
    int n = prices.length;
    if (n == 0) return 0;
    int soFarMin = prices[0];
    int max = 0;
    for (int i = 1; i < n; i++) {
        if (soFarMin > prices[i]) soFarMin = prices[i];
        else max = Math.max(max, prices[i] - soFarMin);
    }
    return max;
}

class LRUCache {
  private List<Integer> list; //使用 LinkedList 来代替双向链表，维护数据顺序
  private Map<Integer,Integer> map; //使用 map 保存数据，实现 O(1) 的访问
  private int size;//链表长度
  private int capacity;//缓存总量，方便后面判断是否链表长度是否超过缓存容量

  public LRUCache(int capacity) {
    list = new LinkedList<>();
    map = new HashMap<>();
    size=0;
    this.capacity = capacity;
  }

  //判断 key 在 HashMap 中是否存在，
  //如果存在，则把对应的节点移动到链表头部，并返回对应的 value 值;
  //如果不存在，则返回-1。
  public int get(int key) {
    if(!map.containsKey(key)){
      return -1;
    }
    //将对应节点移动到链表头部
    list.remove((Integer)key);
    list.add(0,key);
    return map.get(key);
  }

  //如果 key 在 HashMap 中存在，则先重置对应的 value 值，将节点移动到链表的头部；
  //如果 key 在 HashMap 中不存在，则新建一个节点，并将节点放到链表的头部。
  //注意：当 Cache 存满的时候，将链表最后一个节点删除。
  public void put(int key, int value) {
    if(map.containsKey(key)){
      map.put(key,value);
      //将节点移到链表的头部
      list.remove((Integer)key);
      list.add(0,key);
    }else{
      list.add(0,key);
      map.put(key,value);
      size++;
      if(size>capacity){ //每次插入新元素，都会检查是否超过 capacity,只会多出一个元素
        //如果超过容量，则删除链表最后一个元素，同时要去相应的 map 中删除元素
        int lastElement = list.remove(list.size()-1);
        map.remove(lastElement);
      }
    }
  }
}

@Test
public void test(){
  LRUCache cache = new LRUCache( 2);

  cache.put(1, 1);
  cache.put(2, 2);
  System.out.println(cache.get(1));       // 返回  1
  cache.put(3, 3);    // 该操作会使得密钥 2 作废
  System.out.println(cache.get(2));       // 返回 -1 (未找到)
  cache.put(4, 4);    // 该操作会使得密钥 1 作废
  System.out.println(cache.get(1));       // 返回 -1 (未找到)
  System.out.println(cache.get(3));       // 返回  3
  System.out.println(cache.get(4));       // 返回  4
}

//思路：线段切割法
//在一条线段上找 N-1 个随机点，就可以将该线段随机且公平地切割成 N 段。
public class RedPocket {
    public List<Integer> generatePacketsByLineCutting(int people, int money) {
        List<Integer> res = new ArrayList<>();

        //在[0,money] 这条线段上找 （people-1） 个随机点
        Set<Integer> points = new TreeSet<>(); //存储（people-1）个随机点
        //使用 treeset 存储，保证这些点是有序的，方便后面的切分

        Random random = new Random();

        while(points.size() < people-1){
            points.add(random.nextInt(money));
        }
        //此时 points.size() == people-1
        points.add(money);

        int pre=0;
        for(int point:points){
            res.add(point-pre);
            pre = point;
        }
        return res;
    }

    @Test
    public void test(){
        int people =10;
        int money = 100;
        List<Integer> res= generatePacketsByLineCutting(people,money);
        System.out.println(res);
        int result =0;
        for(Integer d:res){
            result += d;
        }
        System.out.println("reslut:"+result);
    }
}

// 算法的基本思想：每次从一组数中随机选出一个数，
// 然后与最后一个数交换位置，并且不再考虑最后一个数。
// 时间复杂度：O(N)
public static void shuffle(int[] nums){
  Random random = new Random();
  for(int i=nums.length-1;i>=0;i--){
    int j = random.nextInt(i+1); //在[0,i]范围内
    if(i==j){ //一个小优化
      continue;
    }
    swap(nums,i,j); // i 指向数组最后一个元素
  }
}

private static void swap(int[] nums,int i,int j){
  int tmp = nums[i];
  nums[i] = nums[j];
  nums[j] = tmp;
}

public static void main(String[] args) {
  int[] nums = {1,2,3,4,5,6,7,8};
  shuffle(nums);
  for(int num:nums){
    System.out.println(num);
  }
}

private int m;
private int n;

//用来标记是否是同一个岛屿
private boolean[][] visited;

//TODO:二维数组四个方向查找的小技巧
private int[][] d={{-1,0},{0,1},{1,0},{0,-1}};

private boolean isArea(int x,int y){
    return (x>=0 && x<m) && (y>=0 && y<n);
}

//找到一个岛，就将这个岛标记
private void dfs(char[][] grid, int x, int y) {
    //[x,y]是陆地，并且标记为已经访问的了
    visited[x][y]=true;
    //向四个方向去扩散
    for(int i=0;i<4;i++){
        int newx=x+d[i][0];
        int newy=y+d[i][1];
        if(isArea(newx,newy)){
            //[newx,newy]合法
            if(grid[newx][newy]=='1' && visited[newx][newy]==false){
                //[newx,newy]位置陆地，并且未被标记，进行深度优先遍历
                //如果已经被标记了，则直接忽略
                ////找到一个岛，就将整个岛进行标记
                dfs(grid,newx,newy);
            }
        }
    }
}

public int numIslands(char[][] grid) {
    m=grid.length;
    if(m==0){
        return 0;
    }
    n=grid[0].length;
    visited=new boolean[m][n];
    int res=0;
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            //有陆地，并且这块陆地未被标记，则就是一个新的岛屿
            if(grid[i][j]=='1' && visited[i][j]==false){
                res++;
                //使用floodfill算法来标记这个新岛屿岛屿
                dfs(grid,i,j);
            }
        }
    }
    return res;
}

private int m;
private int n;

//用来标记是否是同一个岛屿
private boolean[][] visited;

//TODO:二维数组四个方向查找的小技巧
private int[][] d={{-1,0},{0,1},{1,0},{0,-1}};

private boolean isArea(int x,int y){
    return (x>=0 && x<m) && (y>=0 && y<n);
}

//找到一个岛，就将这个岛标记
//返回的值就是[x,y]所在岛屿的面积
private int dfs(int[][] grid, int x, int y) {
    if(grid[x][y] == 0){
        return 0;
    }

    //[x,y]是陆地，并且标记为已经访问的了
    visited[x][y]=true;

    int area=1;

    //向四个方向去扩散
    for(int i=0;i<4;i++){
        int newx=x+d[i][0];
        int newy=y+d[i][1];
        if(isArea(newx,newy)){
            //[newx,newy]合法
            if(grid[newx][newy]==1 && visited[newx][newy]==false){
                //[newx,newy]位置陆地，并且未被标记，进行深度优先遍历
                //如果已经被标记了，则直接忽略
                //找到一个岛，就将整个岛进行标记
                area+=dfs(grid,newx,newy);
            }
        }
    }
    return area;
}

public int maxAreaOfIsland(int[][] grid) {
    m=grid.length;
    if(m==0){
        return 0;
    }
    n=grid[0].length;
    visited=new boolean[m][n];
    int res=0;
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            //有陆地，并且这块陆地未被标记，则就是一个新的岛屿
            if(grid[i][j]==1 && visited[i][j]==false){
                //使用floodfill算法来标记这个新岛屿岛屿
                res=Math.max(res,dfs(grid,i,j));
            }
        }
    }
    return res;
}

//思路：深度优先遍历
//1、假设M是(n*n) 矩阵，说明有 n 个人。
//2、遍历编号为 i 的朋友，进行朋友圈标记，是同一个朋友圈的必然会被标记。
//3、是同一个朋友圈，只统计一次。
private int n;
private boolean[] friend;

public int findCircleNum(int[][] M) {
    n = M.length;
    if( n == 0){
        return 0;
    }
    friend = new boolean[n];

    int res = 0;
    for(int i=0;i<n;i++){
        if(!friend[i]){
            res++;
            dfs(M,i);
        }
    }
    return res;
}

//遍历编号为 x 的人员的朋友圈，并进行标记
//标记后，只统计一次
private void dfs(int[][] M,int x){
    friend[x] = true;
    for(int i=0;i<n;i++){
        if(i != x){ //看看其他人员是否是朋友
            if(M[x][i] == 1 && !friend[i]){ //是朋友，但是还未被标记
                dfs(M,i);
            }
        }
    }
}

class Solution {
    private int m;
    private int n;

    //标记边界上的元素是否是'O'
    private boolean[][] isO;

    private int[][] d={{-1,0},{0,1},{1,0},{0,-1}};

    private boolean isArea(int x,int y){
        return (x>=0 && x<m) && (y>=0 && y<n);
    }

    //深度优先遍历，来标记边界 'O'
    private void dfs(char[][] board, int x, int y) {
        isO[x][y]=true;
        for(int i=0;i<4;i++){
            int newx=x+d[i][0];
            int newy=y+d[i][1];
            if(isArea(newx,newy)){
                if(board[newx][newy]=='O' && isO[newx][newy]==false){
                        dfs(board,newx,newy);
                }
            }
        }
    }

    /**
     * 思路：
     * 除了和边界有接触的’O'的区域，其他的‘O'的区域都会变成'X'。
     * 所以扫描一遍边界，对于在边界上的’O', 通过BFS标记与它相邻的'O'。
     */
    public void solve(char[][] board) {
        m=board.length;
        if(m==0){
            return;
        }
        n=board[0].length;
        isO= new boolean[m][n];
        //对边界进行深度优先遍历，标记‘O’
        for(int j=0;j<n;j++){
            if(board[0][j]=='O' && isO[0][j]==false){
                dfs(board,0,j);
            }
            if(board[m-1][j]=='O' && isO[m-1][j]==false){
                dfs(board,m-1,j);
            }
        }
        for(int i=0;i<m;i++){
            if(board[i][0]=='O' && isO[i][0]==false){
                dfs(board,i,0);
            }
            if(board[i][n-1]=='O' && isO[i][n-1]==false){
                dfs(board,i,n-1);
            }
        }

        //对整个数组进行遍历，覆盖非边界的 'O'
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(isO[i][j]==false && board[i][j]=='O'){
                    board[i][j]='X';
                }
            }
        }
    }
}

private int m;
private int n;

private boolean[][] pacific;
private boolean[][] atlantic;


//TODO:二维数组四个方向查找的小技巧
private int[][] d={{-1,0},{0,1},{1,0},{0,-1}};

private boolean isArea(int x,int y){
    return (x>=0 && x<m) && (y>=0 && y<n);
}

private void dfs(int[][] matrix,boolean[][] visited,int x,int y){
    visited[x][y]=true;
    for(int i=0;i<4;i++){
        int newx=x+d[i][0];
        int newy=y+d[i][1];
        if(isArea(newx,newy)){
            //[newx,newy]地势高，并且未被标记
            if(visited[newx][newy]==false && (matrix[newx][newy]>=matrix[x][y])){
                dfs(matrix,visited,newx,newy);
            }
        }
    }
}

public List<int[]> pacificAtlantic(int[][] matrix) {
    List<int[]> res=new ArrayList<>();
    m=matrix.length;
    if(m==0){
        return res;
    }
    n=matrix[0].length;
    pacific=new boolean[m][n];
    atlantic=new boolean[m][n];

    for(int i=0;i<m;i++){
        dfs(matrix,pacific,i,0);
        dfs(matrix,atlantic,i,n-1);
    }
    for(int j=0;j<n;j++){
        dfs(matrix,pacific,0,j);
        dfs(matrix,atlantic,m-1,j);
    }
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(pacific[i][j] && atlantic[i][j]){
                res.add(new int[]{i,j});
            }
        }
    }
    return res;
}