leetcode1825,802,583,501

1825

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

        return sel;
    }

802

static Boolean[] flag ;

    public static List<Integer> eventualSafeNodes(int[][] graph) {
        List<Integer> list = new ArrayList<>();
        flag = new Boolean[graph.length];
        LinkedList<Integer> stack = new LinkedList<>();
        for (int i = 0; i < graph.length; i++) {
            if (iter(i,graph,stack)){
                list.add(i);
            }
        }
        return list;
    }

    public static boolean iter(int k,int[][] graph,LinkedList<Integer> stack){
        //已经记录过状态的直接返回
        if (flag[k] != null){
            return flag[k];
        }
        stack.push(k);
        //设置为false
        flag[k] = false;
        for (int i = 0; i < graph[k].length; i++) {
            if (stack.contains(graph[k][i])){
                stack.pop();
                return false;
            }else {
                if (!iter(graph[k][i],graph,stack)){
                    stack.pop();
                    return false;
                }
            }
        }
        stack.pop();
        flag[k] = true;
        return true;
    }

583

public static int minDistance(String word1, String word2) {
        int[][] exist = new int[word1.length()+1][word2.length()+1];
        for (int i = 0; i <= word1.length(); i++) {
            for (int j = 0; j <= word2.length(); j++) {
                if (i == 0 || j == 0){
                    exist[i][j] = 0;
                }else {
                    if ( word1.charAt(i-1) == word2.charAt(j-1)){
                        exist[i][j] = exist[i-1][j-1]+1;
                    }else {
                        exist[i][j] = Math.max(exist[i-1][j],exist[i][j-1]);
                    }
                }
            }
        }
        return word1.length()+word2.length()- 2* exist[word1.length()][word2.length()];
    }

501 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
     Map<Integer,Integer> map = new HashMap<>();
     Set<Integer> result = new HashSet<>();
    Integer maxCount = 1;

    public  int[] findMode(TreeNode root) {
        if (root == null){
            return new int[0];
        }
        search(root);

        int[] arr = new int[result.size()];
        int k = 0;
        for (Integer integer : result) {
            arr[k++] = integer;
        }
        return arr;
    }

    public  void search(TreeNode root){
        Integer count = map.get(root.val);
        count = count == null?1:++count;
        map.put(root.val,count);
        if (count == maxCount ){
            result.add(root.val);
        }
        if (count > maxCount){
            result.clear();
            result.add(root.val);
            maxCount = count;
        }
        if (root.right != null){
            search(root.right);
        }
        if (root.left != null){
            search(root.left);
        }
    }
}