看到Leetcode 编程训练这篇文章,于是也开始尝试扫题。上面的题目基本是毫无实际用处的,但是训练下编程还是可以的。做题过程中感受到了一些平常没有的感觉(不要问我是不是查克拉流动的感觉,我还没具体的感受到),反正感觉应该对自己挺有用的。不过,也出现了很多让人想吐槽的bug(或者是我太弱了,还无法理解原因)。
Min Stack
题目
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
- push(x) -- Push element x onto stack.
- pop() -- Removes the element on top of the stack.
- top() -- Get the top element.
- getMin() -- Retrieve the minimum element in the stack.
答案V1
采用一个
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
class MinStack { java.util.Stack<Integer> data = new java.util.Stack<>(); java.util.SortedMap<Integer, Integer> map = new java.util.TreeMap<>(); public void push(int x) { data.push(x); if(map.containsKey(x)) { map.put(x, map.get(x) + 1); } else { map.put(x, 1); } } public void pop() { int x = data.pop(); if(map.get(x) > 1) { map.put(x, map.get(x) - 1); } else { map.remove(x); } } public int top() { return data.peek(); } public int getMin() { return map.firstKey(); } } |
好吧,这版答案确实比较弱,因为才发现要求富的一次吧,因为当时Works给的薪水好像是年薪40W。
答案V2
这次达到
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
public class MinStack { class Pair { int val; int min; Pair(int val, int min) { this.val = val; this.min = min; } } Stack<Pair> data = new Stack<>(); public void push(int x) { if(data.isEmpty() || x < data.peek().min) { data.push(new Pair(x, x)); } else { data.push(new Pair(x, data.peek().min)); } } public void pop() { data.pop(); } public int top() { return data.peek().val; } public int getMin() { return data.peek().min; } } |
内存占用太多,内存占用明显已经是不太可能再变得更小了,怎么还会占用内存过多。检查了好多遍后,突然想到难道会是内部类的问题?内部类若不是静态,则需要初始化外部类才能进行初始化。但我这是在外部类中进行操作的啊,难道也会有影响?结果尝试将
Palindrome Number
题目
Determine whether an integer is a palindrome. Do this without extra space.
答案
本来对x的处理是
此外,还发现
这种Java的小细节不会有变态公司当成宝典来考吧?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
public static boolean isPalindrome(int x) { if(x < 0) return false; int length = (int)Math.log10(x); int mid = (length + 1) / 2; for(int i = 0; i < mid; i++) { int mod = x % 10; int hight = x / ((int)Math.pow(10.0, (double)length)); System.out.println(mod); System.out.println(hight); if(mod != hight) return false; x %= ((int)Math.pow(10.0, (double)length)); x /= 10; length -= 2; } return true; } |
Symmetric Tree
题目
题目太长:https://oj.leetcode.com/problems/symmetric-tree/
答案
递归类的题目,答案比较短。
1 2 3 4 5 6 7 8 9 10 11 |
public boolean isSymmetric(TreeNode root) { return root == null || isMirror(root.left, root.right); } public boolean isMirror(TreeNode p, TreeNode q) { return p == null && q == null || p != null && q != null && p.val == q.val && isMirror(p.left, q.right) && isMirror(p.right, q.left); } |
Same Tree
题目
Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.
答案
1 2 3 |
public boolean isSameTree(TreeNode p, TreeNode q) { return p == null && q == null || p != null && q != null && p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right); } |
Gabriela disse:Eu QUEROOOO experimentar. O ansolar eu comprei pela sua dica e tb adorei…Esse é muito melhor? Outro vicio: protetor solar! rsBem chr.qe.ursisrsBeijos