用帝国软件做网站的心得/网站如何做推广

题目解析：这是一道面试常考题，借助哈希表赋予了链表快速查找的特性，然后使用链表，可以快速实现LRU(最近最少使用)缓存算法。
代码如下：

/*** 哈希表、双向链表**/
class LRUCache{class Node {int value;Node prev;Node next;public Node() {}public Node(int _value) {value = _value;}}int cap;int size;// 用数组优化HashMap，因为值范围固定，且数组更快// 索引为key，值为value的hashMapNode[] map = new Node[10001];// 双向链表，两个方向Node head;Node tail;public LRUCache(int capacity) {cap = capacity;size = capacity;head = new Node();tail = new Node();head.next = tail;tail.prev = head;size = 0;}public int get(int key) {Node node = map[key];if (node == null || node.value == -1) return -1;// 被查找后，删除，再添加，相当于更新为最新位置remove(node);addHead(node);return node.value;}public void put(int key, int value) {// 为空添加后，如果超长，需要删除旧的if (map[key] == null || map[key].value == -1) {Node node = new Node(value);addHead(node);if (size == cap) removeTail();else ++size;map[key] = node;// 若已存在，更新为最新值，和最新位置} else {map[key].value = value;remove(map[key]);addHead(map[key]);}}public void remove(Node node) {node.prev.next = node.next;node.next.prev = node.prev;}public void addHead(Node node) {node.next = head.next;node.prev = head;head.next.prev = node;head.next = node;}public void removeTail() {Node last = tail.prev.prev;last.next.value = -1;last.next = tail;tail.prev = last;}
}/*** 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);*/

题目解析：用链表，每个节点存储时，把该节点情况下最小值也存进去即可。
代码如下：

/*** 链表*/
class MinStack {private Node head;public void push(int x) {if(head == null) head = new Node(x, x);else head = new Node(x, Math.min(x, head.min), head);}public void pop() {head = head.next;}public int top() {return head.val;}public int getMin() {return head.min;}private class Node {int val;int min;Node next;private Node(int val, int min) {this(val, min, null);}private Node(int val, int min, Node next) {this.val = val;this.min = min;this.next = next;}}
}
/*** Your MinStack object will be instantiated and called as such:* MinStack obj = new MinStack();* obj.push(val);* obj.pop();* int param_3 = obj.top();* int param_4 = obj.getMin();*/

题目解析：用栈做中序迭代。
代码如下：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*//*** 二叉树 */
class BSTIterator {Deque<TreeNode> stack;// 思路:因为要中序遍历,所以把根节点先入栈然后入栈左孩子,每当输出一个节点后把那个节点的右孩子以及右孩子的所有左边的孩子加入进栈（想象递归的思想，空间复杂度O(h):因为最多存入树的高度个节点）public BSTIterator(TreeNode root) {stack = new LinkedList<>();TreeNode t = root;while(t!=null){ // 初始化栈：把根节点和根节点的所有左孩子及左孩子的左孩子加入进栈stack.addLast(t);t = t.left;}}public int next() {TreeNode t = stack.pollLast();int res = t.val;if(t.right!=null){      // 把取出节点的右孩子和右孩子的所有左孩子及左孩子的左孩子加入进栈stack.addLast(t.right);t = t.right.left;while(t!=null){stack.addLast(t);t = t.left;}}    return res;}public boolean hasNext() {return !stack.isEmpty();}
}/*** Your BSTIterator object will be instantiated and called as such:* BSTIterator obj = new BSTIterator(root);* int param_1 = obj.next();* boolean param_2 = obj.hasNext();*/

题目解析：用数组实现字典树。
代码如下：

/*** 设计*/
class Trie {private class TrieNode { // 每个节点最多有26个不同的小写字母private boolean isEnd;private TrieNode[] next;public TrieNode() {isEnd = false;next = new TrieNode[26];}}private TrieNode root;/** Initialize your data structure here. */public Trie() {root = new TrieNode();}/** Inserts a word into the trie. */public void insert(String word) {TrieNode cur = root;for (int i = 0, len = word.length(), ch; i < len; i++) {ch = word.charAt(i) - 'a';if (cur.next[ch] == null)cur.next[ch] = new TrieNode();cur = cur.next[ch];}cur.isEnd = true; // 加上一个标记，表示为一个单词}/** Returns if the word is in the trie. */public boolean search(String word) {TrieNode cur = root;for (int i = 0, len = word.length(), ch; i < len; i++) {ch = word.charAt(i) - 'a';if (cur.next[ch] == null)return false;cur = cur.next[ch];}return cur.isEnd;}/*** Returns if there is any word in the trie that starts with the given prefix.*/public boolean startsWith(String prefix) {TrieNode cur = root;for (int i = 0, len = prefix.length(), ch; i < len; i++) {ch = prefix.charAt(i) - 'a';if (cur.next[ch] == null)return false; // 若还没遍历完给定的前缀子串，则直接返回falsecur = cur.next[ch];}return true; // 直接返回true}
}/*** Your Trie object will be instantiated and called as such:* Trie obj = new Trie();* obj.insert(word);* boolean param_2 = obj.search(word);* boolean param_3 = obj.startsWith(prefix);*/

题目解析：字典树与208.实现 Trie (前缀树)大同小异，只需要对.单独处理就可以了。
代码如下：

/*** 设计 */
class WordDictionary {private WordDictionary[] items;boolean isEnd;public WordDictionary() {items = new WordDictionary[26];}public void addWord(String word) {WordDictionary curr = this;int n = word.length();for(int i = 0; i < n; i++){int index = word.charAt(i) - 'a';if(curr.items[index] == null)curr.items[index] = new WordDictionary();curr = curr.items[index];}curr.isEnd = true;}public boolean search(String word) {return search(this, word, 0);}private boolean search(WordDictionary curr, String word, int start){int n = word.length();if(start == n)return curr.isEnd;char c = word.charAt(start);if(c != '.'){WordDictionary item = curr.items[c - 'a'];return item != null && search(item, word, start + 1);}for(int j = 0; j < 26; j++){if(curr.items[j] != null && search(curr.items[j], word, start + 1))return true;}return false;}
}/*** Your WordDictionary object will be instantiated and called as such:* WordDictionary obj = new WordDictionary();* obj.addWord(word);* boolean param_2 = obj.search(word);*/

题目解析：用一个队列或两个队列都可以实现，一个队列的情况：每次删除栈顶，把除出栈值外，全部再次添加到队尾，再删除出栈值。两个队列情况：一个队列做备份用，每次添加新元素，都把除新元素外其它元素重添加入队尾。
代码如下：

/*** 队列*/
class MyStack {private Queue<Integer> inQ;  // 输入队列private Queue<Integer> outQ;  // 输出队列public MyStack() {inQ = new LinkedList<>();outQ = new LinkedList<>();}public void push(int x) {inQ.offer(x);// 把outQ中元素全部转到inQ队列while (!outQ.isEmpty()) {inQ.offer(outQ.poll());}// 交换两队列Queue temp = inQ;inQ = outQ;outQ = temp;}public int pop() {return outQ.poll();}public int top() {return outQ.peek();}public boolean empty() {return outQ.isEmpty();}
}/*** Your MyStack object will be instantiated and called as such:* MyStack obj = new MyStack();* obj.push(x);* int param_2 = obj.pop();* int param_3 = obj.top();* boolean param_4 = obj.empty();*/

题目解析：用两个栈，相互导，可以实现队列。
代码如下：

/*** 栈*/
class MyQueue {private Stack<Integer> inStack; // 输入栈private Stack<Integer> outStack; // 输出栈public MyQueue() {inStack = new Stack<>();outStack = new Stack<>();}public void push(int x) {inStack.push(x);}public int pop(){// 如果outStack栈为空，则将inStack栈全部弹出并压入b栈中，然后outStack.pop()if (outStack.isEmpty()) {while (!inStack.isEmpty()) {outStack.push(inStack.pop());}}return outStack.pop();}public int peek() {if (outStack.isEmpty()) {while (!inStack.isEmpty()) {outStack.push(inStack.pop());}}return outStack.peek();}public boolean empty() {return inStack.isEmpty() && outStack.isEmpty();}
}/*** Your MyQueue object will be instantiated and called as such:* MyQueue obj = new MyQueue();* obj.push(x);* int param_2 = obj.pop();* int param_3 = obj.peek();* boolean param_4 = obj.empty();*/

题目解析：最直观的做法是使用一个列表存储迭代器中的每个元素，然后按顺序遍历列表中的元素模拟迭代器。
代码如下：

/*** 迭代器*/class PeekingIterator implements Iterator<Integer> {private Iterator<Integer> iterator;private Integer nextElement;public PeekingIterator(Iterator<Integer> iterator) {this.iterator = iterator;nextElement = iterator.next();}public Integer peek() {return nextElement;}@Overridepublic Integer next() {Integer ret = nextElement;nextElement = iterator.hasNext() ? iterator.next() : null;return ret;}@Overridepublic boolean hasNext() {return nextElement != null;}
}

题目解析：我们用两个优先队列 queMax 和 queMin 分别记录大于中位数的数和小于等于中位数的数。当累计添加的数的数量为奇数时，queMin 中的数的数量比 queMax 多一个，此时中位数为 queMin 的队头。当累计添加的数的数量为偶数时，两个优先队列中的数的数量相同，此时中位数为它们的队头的平均值。
代码如下：

/*** 优先队列*/
class MedianFinder {PriorityQueue<Integer> queMin;PriorityQueue<Integer> queMax;public MedianFinder() {queMin = new PriorityQueue<Integer>((a, b) -> (b - a));queMax = new PriorityQueue<Integer>((a, b) -> (a - b));}public void addNum(int num) {if (queMin.isEmpty() || num <= queMin.peek()) {queMin.offer(num);if (queMax.size() + 1 < queMin.size()) {queMax.offer(queMin.poll());}} else {queMax.offer(num);if (queMax.size() > queMin.size()) {queMin.offer(queMax.poll());}}}public double findMedian() {if (queMin.size() > queMax.size()) {return queMin.peek();}return (queMin.peek() + queMax.peek()) / 2.0;}
}

题目解析：二叉树的序列化本质上是对其值进行编码，更重要的是对其结构进行编码。可以遍历树来完成上述任务。
代码如下：

/*** 深度优先搜索*/
public class Codec {public String serialize(TreeNode root) {return rserialize(root, "");}public TreeNode deserialize(String data) {String[] dataArray = data.split(",");List<String> dataList = new LinkedList<String>(Arrays.asList(dataArray));return rdeserialize(dataList);}public String rserialize(TreeNode root, String str) {if (root == null) {str += "None,";} else {str += str.valueOf(root.val) + ",";str = rserialize(root.left, str);str = rserialize(root.right, str);}return str;}public TreeNode rdeserialize(List<String> dataList) {if (dataList.get(0).equals("None")) {dataList.remove(0);return null;}TreeNode root = new TreeNode(Integer.valueOf(dataList.get(0)));dataList.remove(0);root.left = rdeserialize(dataList);root.right = rdeserialize(dataList);return root;}
}