面试经典150题【81-90】

本文主要是介绍面试经典150题【81-90】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

面试经典150题【81-90】

530.二叉搜索树的最小绝对差值

在中序遍历的过程中 cur.val -pre.val 即可。

230.二叉搜索树中第k小的元素

中序遍历，用两个临时变量记录遍历位置和最终答案即可

98.验证二叉搜索树

中序遍历后检查是否有序。

92.反转链表II

截取出那段要反转的链表，然后用多个节点，遍历即可。

class Solution {public ListNode reverseBetween(ListNode head, int left, int right) {ListNode dummyNode = new ListNode(-1);dummyNode.next=head;ListNode pre =dummyNode;// 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点for(int i=0;i<left-1;i++) pre=pre.next;// 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点ListNode rightNode = pre;for(int i=0;i<right-left+1 ; i++) rightNode=rightNode.next;// 第 3 步：切断出一个子链表（截取链表）ListNode leftNode=pre.next;ListNode curr = rightNode.next;// 切断原来的链表的连接pre.next = null;rightNode.next = null;// 用递归反转链表reverseLinkedList(leftNode);//拼接链表pre.next=rightNode;leftNode.next=curr;return dummyNode.next;}void reverseLinkedList(ListNode head) {ListNode pre = null;ListNode cur = head;while (cur != null) {ListNode nextNode = cur.next;cur.next = pre;pre = cur;cur = nextNode;}}
}

25.K个一组翻转链表

遍历链表，合适的话就切割出来翻转，和上题思路一样。
需要定义多个变量
ListNode pre； //上一段的最后一个
ListNode start; //这一段的开始
ListNode end; //这一段的结束
ListNode nextStart; //下一段的开始
然后将start -> end 送去翻转

146.LRU缓存

• 对于 get 操作，首先判断 key 是否存在：

  如果 key 不存在，则返回 −1；
  如果 key 存在，则 key 对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置，并将其移动到双向链表的头部，最后返回该节点的值。

• 对于 put 操作，首先判断 key 是否存在：

  如果 key 不存在，使用 key 和 value 创建一个新的节点，在双向链表的头部添加该节点，并将 key 和该节点添加进哈希表中。然后判断双向链表的节点数是否超出容量，如果超出容量，则删除双向链表的尾部节点，并删除哈希表中对应的项；

  如果 key 存在，则与 get 操作类似，先通过哈希表定位，再将对应的节点的值更新为 value，并将该节点移到双向链表的头部。

class LRUCache {class DLinkedNode{DLinkedNode prev;DLinkedNode next;int key;int value;public DLinkedNode(){}public DLinkedNode(int key,int val){this.key = key;value = val;}}private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();private int size;private int capacity;private DLinkedNode head, tail;public LRUCache(int capacity) {this.size = 0;this.capacity = capacity;// 使用伪头部和伪尾部节点head = new DLinkedNode();tail = new DLinkedNode();head.next = tail;tail.prev = head;}public int get(int key) {DLinkedNode node = cache.get(key);if(node == null) return -1;//如果存在，就要移动到表头moveToHead(node);return node.value;}public void put(int key, int value) {DLinkedNode node =cache.get(key);if(node == null){//新增DLinkedNode newNode = new DLinkedNode(key,value);cache.put(key,newNode);addToHead(newNode);size++;if(size > capacity){DLinkedNode dLinkedNode = removeTail();//就是因为这里需要用到key才能删除，所以DLinkedNode节点才需要加上Keycache.remove(dLinkedNode.key);size--;}}else{//修改node.value=value;moveToHead(node);}}private void addToHead(DLinkedNode node){node.next = head.next;node.next.prev = node;head.next = node;node.prev = head;}private void removeNode(DLinkedNode node){node.prev.next = node.next;node.next.prev = node.prev;}private void moveToHead(DLinkedNode node) {removeNode(node);addToHead(node);}private DLinkedNode removeTail(){DLinkedNode res=tail.prev;removeNode(res);return res;}}

909. 蛇梯棋（未做）

额这题意还是算了。反正解法和下一个题差不多。BFS

433.最小基因变化

从start变为end, 每一步只能变换一个字母，且变换的必须在bank里。
使用BFS记录路径，且不要重复。最短路径长度。

127.单词接龙（未做）

这个题和上一个题一样的逻辑，只不过数据量很大，可能要用双向的搜索。
从start往中间搜，从end往中间搜。直到重合。

17.电话号码的字母组合

经典回溯

class Solution {public List<String> letterCombinations(String digits) {List<String> combinations = new ArrayList<String>();if (digits.length() == 0) {return combinations;}Map<Character, String> phoneMap = new HashMap<Character, String>() {{put('2', "abc");put('3', "def");put('4', "ghi");put('5', "jkl");put('6', "mno");put('7', "pqrs");put('8', "tuv");put('9', "wxyz");}};backtrack(combinations, phoneMap, digits, 0, new StringBuffer());return combinations;}public void backtrack(List<String> combinations, Map<Character, String> phoneMap, String digits, int index, StringBuffer combination) {if (index == digits.length()) {combinations.add(combination.toString());} else {char digit = digits.charAt(index);String letters = phoneMap.get(digit);int lettersCount = letters.length();for (int i = 0; i < lettersCount; i++) {combination.append(letters.charAt(i));backtrack(combinations, phoneMap, digits, index + 1, combination);combination.deleteCharAt(index);}}}}

这篇关于面试经典150题【81-90】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---