头像

YYC

Coming


访客:2146

离线:2天前



YYC
3天前
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return 1;
        if (root.left != null && root.right != null){
            return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
        } else if (root.left != null){
            return minDepth(root.left) + 1;
        } else {
            return minDepth(root.right) + 1;
        }
    }
}


活动打卡代码 LeetCode 101. 对称二叉树

YYC
3天前
class Solution {

    private boolean isSymmetric(TreeNode left, TreeNode right){
        if (left == null && right == null) return true;
        if (left == null || right == null) return false;
        if (left.val != right.val) return false;
        return isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
    }

    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return isSymmetric(root.left, root.right);
    }
}


活动打卡代码 LeetCode 110. 平衡二叉树

YYC
6天前
class Solution {

    boolean ans = true;

    private int dfs(TreeNode root){
        if (root == null) return 0;
        int l = dfs(root.left);
        int r = dfs(root.right);
        if (Math.abs(l - r) > 1) ans = false;
        return Math.max(l, r) + 1;
    }

    public boolean isBalanced(TreeNode root) {
        dfs(root);
        return ans;
    }
}



YYC
6天前
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}



YYC
6天前

问题描述

Design and implement a data structure for Least Recently Used (LRU) cache.
It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

若执行put()操作时,缓存中元素的数量大于capacity,则删除最近最少使用的元素。

举个例子:

解法1

Thanks [Y总]

先来看下get()put()操作的流程图:

  • get()

  • put()

再来看下remove()insert()操作:

  • remove()

  • insert()

最后来看下完整实现:

class LRUCache {

    class Node{
        private int key, val;
        private Node left, right;
        public Node(int k, int v){
            this.key = k;
            this.val = v;
            this.left  = null;
            this.right = null;
        }
    }

    private Node head, tail;
    private HashMap<Integer, Node> map;
    private int cap;

    public LRUCache(int capacity) {
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        head.right = tail;
        tail.left  = head;
        map  = new HashMap<Integer, Node>();
        this.cap = capacity;
    }

    public void remove(Node p){
        p.right.left = p.left;
        p.left.right = p.right;
    }

    public void insert(Node p){
        p.right = head.right;
        head.right.left = p;
        p.left = head;
        head.right = p;
    }

    public int get(int key) {
        if (!map.containsKey(key)){
            return -1;
        }
        Node p = map.get(key);
        remove(p);
        insert(p);
        return p.val;
    }

    public void put(int key, int value) {
        if (!map.containsKey(key)){
            if (cap == map.size()){
                Node p = tail.left;
                remove(p);
                map.remove(p.key);
            }
            Node p = new Node(key, value);
            insert(p);
            map.put(key, p);
        } else{
            Node p = map.get(key);
            p.val = value;
            remove(p);
            insert(p);
        }
    }
}

Enjoy it !



活动打卡代码 LeetCode 146. LRU缓存机制

YYC
6天前
class LRUCache {

    class Node{
        private int key, val;
        private Node left, right;
        public Node(int k, int v){
            this.key = k;
            this.val = v;
            this.left  = null;
            this.right = null;
        }
    }

    private Node head, tail;
    private HashMap<Integer, Node> map;
    private int cap;

    public LRUCache(int capacity) {
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        head.right = tail;
        tail.left  = head;
        map  = new HashMap<Integer, Node>();
        this.cap = capacity;
    }

    public void remove(Node p){
        p.right.left = p.left;
        p.left.right = p.right;
    }

    public void insert(Node p){
        p.right = head.right;
        head.right.left = p;
        p.left = head;
        head.right = p;
    }

    public int get(int key) {
        if (!map.containsKey(key)){
            return -1;
        }
        Node p = map.get(key);
        remove(p);
        insert(p);
        return p.val;
    }

    public void put(int key, int value) {
        if (!map.containsKey(key)){
            if (cap == map.size()){
                Node p = tail.left;
                remove(p);
                map.remove(p.key);
            }
            Node p = new Node(key, value);
            insert(p);
            map.put(key, p);
        } else{
            Node p = map.get(key);
            p.val = value;
            remove(p);
            insert(p);
        }
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */



YYC
8天前
import java.util.*;

public class Main{
    public static void main(String... args){
        Scanner in = new Scanner(System.in);
        double a = in.nextDouble();
        double b = in.nextDouble();
        double c = in.nextDouble();
        double t = b * b - 4 * a * c;
        if (a == 0.d || t < 0){
            System.out.println("Impossivel calcular");
            return;
        }
        double ans1 = (-b + Math.sqrt(t)) / (2 * a);
        double ans2 = (-b - Math.sqrt(t)) / (2 * a);
        System.out.printf("R1 = %.5f\nR2 = %.5f", ans1, ans2);
        return;
    }
}


活动打卡代码 LeetCode 37. 解数独

YYC
10天前
class Solution {

    int N = 9;
    boolean[][] row = new boolean[N][N];
    boolean[][] col = new boolean[N][N];
    boolean[][][] cell = new boolean[N / 3][N / 3][N];

    private boolean dfs(char[][] board, int x, int y){

        // 1. 边缘条件
        if (y == N){
            y = 0;
            x++;
        }

        // 2. 终止条件
        if (x == N) return true;

        // 3. 当前结点已有值
        if (board[x][y] != '.'){
            return dfs(board, x, y + 1);
        }

        // 4. 当前结点无值
        for (int i = 0; i < N; i++){
            if (!row[x][i] && !col[y][i] && !cell[x / 3][y / 3][i]){
                // 当前值可以放在当前单元
                board[x][y] = (char) (i + '1');
                // 标记一下这个单元已经放了值
                row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = true;
                // dfs
                if (dfs(board, x, y + 1)) return true;
                // 恢复现场
                row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = false;
                board[x][y] = '.';
            }
        }
        // 说明该数独无解
        return false;
    }

    public void solveSudoku(char[][] board) {

        // 初始化
        for (int i = 0; i < N; i++){
            for (int j = 0; j < N; j++){
                if (board[i][j] != '.'){
                    int t = board[i][j] - '1';
                    row[i][t] = col[j][t] = cell[i / 3][j / 3][t] = true;
                }
            }
        }

        dfs(board, 0, 0);
    }
}



YYC
12天前
class Solution {
    public int largestRectangleArea(int[] heights) {

        int n = heights.length;
        int[] l = new int[n];
        int[] r = new int[n];
        ArrayDeque<Integer> s = new ArrayDeque<>();

        // left
        for (int i = 0; i < n; i++){
            while (!s.isEmpty() && heights[i] <= heights[s.peek()]){
                s.pop();
            }
            l[i] = s.isEmpty() ? -1 : s.peek();
            s.push(i);
        }

        // right
        s.clear();
        for (int i = n - 1; i >= 0; i--){
            while (!s.isEmpty() && heights[i] <= heights[s.peek()]){
                s.pop();
            }
            r[i] = s.isEmpty() ? n : s.peek();
            s.push(i);
        }

        int ans = 0;
        for (int i = 0; i < n; i++){
            ans = Math.max(ans, (r[i] - l[i] - 1) * heights[i]);
        }
        return ans;
    }
}



YYC
12天前

题目描述

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

给你一个字符串,其中包含圆括号、加减号、非负数和空格,实现简单的运算。

举个例子:

((24 + 8) - (10 - 2)) = 24

Update at 2020_0728

Thanks Y总,重新梳理下思路。

首先,我们需要两个栈,一个用来存放数字,另一个用来存放操作符。

然后,分为四种场景:

第一,如果当前字符为空格,直接跳过。

第二,如果当前字符是(+-,直接加入操作数栈中。

第三,如果当前字符是),此时操作数栈顶必然是(,因此将其弹出。

然后判断操作数栈顶是否为空,且操作数不是(,也就是+-

此时,从数字栈中弹出两个数字,并从操作数中弹出一个操作数,进行计算。

第四,如果当前是数字,注意两点,

第一点,该整数可能是多位的,所以需要借助while循环往后遍历。

第二点,遍历时,我们需要借助一个变量j,防止影响变量i,最后记得调整i的值。

完整实现如下:

class Solution {

    private void calc(ArrayDeque<Character> ops, ArrayDeque<Integer> nums){
        int a = nums.pop();
        int b = nums.pop();
        char c = ops.pop();
        if (c == '+') {
            nums.push(b + a);
        } else {
            nums.push(b - a);
        }
    }

    public int calculate(String s) {

        ArrayDeque<Integer>  nums = new ArrayDeque<>();
        ArrayDeque<Character> ops = new ArrayDeque<>();
        int n = s.length();
        char[] ch = s.toCharArray();

        for (int i = 0; i < n; i++){
            char c = ch[i];
            if (c == ' ') continue;
            else if (c == '(' || c == '+' || c == '-'){
                ops.push(c);
            } else if (c == ')'){
                // 弹出操作数栈顶的(
                ops.pop();
                // 如果操作数非空,且栈顶元素不是(
                // 那么操作数不是+就是-,则进行一次计算操作。
                if (!ops.isEmpty() && ops.peek() != '('){
                    calc(ops, nums);
                }
            } else {
                // 获取完整的整数,需要借助变量j,防止影响变量i
                int j = i;
                int cur = 0;
                while (j < n && ch[j] >= '0' && ch[j] <= '9'){
                    cur = cur * 10 + (ch[j] - '0') % 10;
                    j++;
                }
                // 借助j,调整i
                i = j - 1;
                // 将数字插入数字栈中
                nums.push(cur);
                // 如果操作数非空,且栈顶元素不是(
                // 那么操作数不是+就是-,则进行一次计算操作。
                if (!ops.isEmpty() && ops.peek() != '('){
                    calc(ops, nums);
                }
            }
        }
        return nums.peek();
    }
}