算法题题型总结

二叉树题型

解法综述：二叉树的解法，基本上都是依赖遍历，再加上递归的思路来做的。那递归又分为深度优先和广度优先。深度优先算法，前序，中序，后序。广度优先，利用先进先出队列，一层一层的遍历完整颗树。

深度优先

1. 求二叉树的最大深度

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

2. 是否是相同的树

class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {return isSame(p, q);}public boolean isSame(TreeNode p, TreeNode q){if (p == null && q == null) {return true;}if ((p == null && q != null) || (p != null && q == null)) {return false;}return p.val == q.val && isSame(p.left, q.left) && isSame(p.right, q.right);}}

3. 求根节点到叶节点数字之和

class Solution {public int sumNumbers(TreeNode root) {return sum(root, 0);}public int sum(TreeNode node, int sum){if (node == null) {return 0;}if (node.left == null && node.right == null) {return 10*sum + node.val;}return sum(node.left,node.val + sum * 10) + sum(node.right, node.val + sum * 10);}
}

广度优先

1. 填充每个节点的下一个右侧节点指针

class Solution {public Node connect(Node root) {if (root == null) {return null;}LinkedList<Node> list = new LinkedList<>();list.add(root);while(list.size()!=0){int size = list.size();Node pre = null;for (int i=0; i<size; i++) {Node cur = list.poll();if (pre != null) {pre.next = cur;}if (cur.left != null) {list.add(cur.left);}if (cur.right != null) {list.add(cur.right);}pre = cur;}}return root;}
}

2. 二叉树的右视图

class Solution {public List<Integer> rightSideView(TreeNode root) {if (root == null) {return new ArrayList<>();}LinkedList<TreeNode> list = new LinkedList<>();list.add(root);List<Integer> resList = new ArrayList<>();while(!list.isEmpty()){int size = list.size();for(int i=0; i<size; i++){TreeNode node = list.poll();if (node.left != null) {list.add(node.left);}if (node.right != null) {list.add(node.right);}if(i==(size-1)){resList.add(node.val);}}}return resList;}
}

3. 二叉树的层平均值

class Solution {public List<Double> averageOfLevels(TreeNode root) {return average(root);}//offer -- add 加在队列的尾部//poll -- 从队列的头部取元素//pop -- 从队列的头部取元素//push -- 放在队列头部public List<Double> average(TreeNode root){List<Double> res = new ArrayList<Double>();LinkedList<TreeNode> list = new LinkedList<TreeNode>();list.add(root);while(list.size() != 0){int size = list.size();double sum = 0.0;for (int i=0; i<size; i++) {TreeNode node = list.poll();sum = sum + node.val;if (node.left != null) {list.add(node.left);}if (node.right != null) {list.add(node.right);}}res.add(sum/size);}return res;}
}

二分查找

解法综述：首先要基于一个有序数组或者是要局部有序的场景，才能比较适合实用二分查找。然后需要通过数组的左边界和右边界确定数组的中间值，再与目标值进行对比。然后不断地调整左右边界，直到左边界大于右边界。

1. 搜索插入位置

class Solution {public int searchInsert(int[] nums, int target) {int left = 0;int right = nums.length -1;int mid = 0;int ans = nums.length;while(left<=right){mid = left + (right - left)/2;if (target <= nums[mid]) {right = mid - 1;ans = mid;} else {left = mid + 1;}}return ans;}
}

2. 寻找峰值（这就是一个局部有序的场景）

class Solution {public int findPeakElement(int[] nums) {int n = nums.length;int left = 0, right = n - 1, ans = -1;while (left <= right) {int mid = (left + right) / 2;if (compare(nums, mid - 1, mid) < 0 && compare(nums, mid, mid + 1) > 0) {ans = mid;break;}if (compare(nums, mid, mid + 1) < 0) {left = mid + 1;} else {right = mid - 1;}}return ans;}int[] get(int[] nums, int a){if (a < 0 || a > nums.length - 1) {return new int[]{0,0};}return new int[]{1, nums[a]};}public int compare(int[] nums, int a, int b){int[] ar = get(nums, a);int[] br = get(nums, b);if (ar[0] > br[0]) {return 1;} else if (ar[0] == br[0] ) {if (ar[1] > br[1]) {return 1;} else if (ar[1] == br[1]) {return 0;} else {return -1;}} else {return -1;}}
}

堆

class Solution {public int findKthLargest(int[] nums, int k) {//第一次大顶堆要完整构建//第k-1次大顶堆，使用局部构造大顶堆的方式进行//构建好了大顶堆要，交换，并且长度要减1//剔除到第k次时，就是第k个最大值int length = nums.length;buildMaxHeap(nums, length);swap( 0, length - 1, nums);length = length - 1;for(int i =0 ; i<k-1;i++){buildSubMaxHeap(nums, 0,length);swap( 0, length - 1, nums);length = length - 1;}return nums[nums.length-k];}void buildMaxHeap(int[] nums, int length){int start = length/2 - 1;for (int i = start ; i >=0; i--) {buildSubMaxHeap(nums, i, length);}}void buildSubMaxHeap(int[] nums, int pos,int length){int left = 2 * pos + 1;int right = 2 * pos + 2;int large = pos;if (left<length && nums[left] > nums[large]) {large = left;}if (right<length && nums[right] > nums[large]) {large = right;}if (large != pos) {swap(large, pos, nums);buildSubMaxHeap(nums, large, length);}}void swap(int a, int b , int[] nums){int temp = nums[a];nums[a] = nums[b];nums[b] = temp;}
}

链表

解法综述：

        1. 单链表，有两个指针，一个快，一个慢。或者一个pre，一个cur

        2. 双链表，有两个指针，一个快，一个慢

        3. 使用递归 + map的方式来解

        4. 需要使用3个指针，pre，cur，next

        5. LRU缓存-涉及到的数据结构很多，最好还是使用LinkedHashMap实现

单链表，有两个指针，一个快，一个慢

1. 环形链表

public class Solution {public boolean hasCycle(ListNode head) {if (head == null || head.next == null) {return false;}ListNode first = head;ListNode second = head.next;while (second != null) {if (first == second) {return true;}first = first.next;if (second.next != null) {second = second.next.next;} else {second = second.next;}}return false;}
}

2. 删除链表的倒数第n个节点

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode newHead = new ListNode();newHead.next = head;ListNode fast = head;ListNode slow = head;for (int i=1; i<n; i++) {if (fast != null) {fast = fast.next;} else {return newHead.next;} }ListNode pre = newHead;while(fast.next!=null){fast=fast.next;slow = slow.next;pre = pre.next;}pre.next = slow==null?null:slow.next;return newHead.next;}
}

3. 旋转链表

class Solution {public ListNode rotateRight(ListNode head, int k) {ListNode f = head;ListNode s = head;int l = 0;ListNode cur = head;while(cur!=null){l++;cur = cur.next;}if (l==0) {return head;}int nk = k%l;if (l==0 || l==1 || nk==0) {return head;}for (int i=1; i<nk; i++) {f = f.next;}ListNode newHead = new ListNode();newHead.next = head;ListNode pre = newHead;while(f.next != null){f = f.next;s = s.next;pre = pre.next;}pre.next = null;f.next = head;return s;}
}

一个pre，一个cur

class Solution {public ListNode deleteDuplicates(ListNode head) {ListNode newHead = new ListNode();newHead.next = head;ListNode cur = newHead;while(cur.next != null && cur.next.next != null){if (cur.next.val == cur.next.next.val) {int val = cur.next.val;cur.next = cur.next.next.next;while (cur.next != null && cur.next.val == val){cur.next = cur.next.next;}} else{cur = cur.next;}}return newHead.next;}
}

双链表，有两个指针，一个快，一个慢

1. 合并两个有序链表

class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode head = new ListNode();ListNode tail = head; while(list1 != null && list2 != null){if (list1.val >= list2.val) {tail.next = list2;tail = tail.next;list2 = list2.next;} else{tail.next = list1;tail = tail.next;list1 = list1.next;}}ListNode sub = list1 != null?list1 : list2;tail.next = sub;return head.next;}
}

2. 两数相加

class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode p1 = l1;ListNode p2 = l2;int yushu = 0;int zhengshu = 0;ListNode tail = p1;while (p1 != null || p2 != null) {int v1 = p1 != null? p1.val:0;int v2 = p2 != null? p2.val:0;yushu = (v1 + v2 + zhengshu)%10;tail.val = yushu;zhengshu = (v1 + v2 + zhengshu)/10;   if(p1 != null){p1 = p1.next;}if (p2 != null) {p2 = p2.next; }ListNode notNull = (p1 !=null)? p1 : p2;if (notNull != null) {tail.next = notNull;tail = tail.next;}}if (zhengshu != 0) {ListNode last = new ListNode();last.val = zhengshu;tail.next = last;}return l1;}
}

使用递归 + map的方式来解

1. 随机链表的复制

class Solution {Map<Node, Node> cachedNode = new HashMap<Node, Node>();public Node copyRandomList(Node head) {if (head == null) {return null;}if (!cachedNode.containsKey(head)) {Node headNew = new Node(head.val);cachedNode.put(head, headNew);headNew.next = copyRandomList(head.next);headNew.random = copyRandomList(head.random);}return cachedNode.get(head);}
}

需要使用3个指针，pre，cur，next

1. 翻转链表

class Solution {public ListNode reverseBetween(ListNode head, int left, int right) {ListNode cur = head;ListNode pre = new ListNode();pre.next = cur;for (int i = 0; i<left-1;i++) {cur = cur.next;pre = pre.next;}for (int i=0; i<right - left; i++) {ListNode next = cur.next;cur.next = next.next;next.next = pre.next;pre.next = next;}return head;}
}

LRU缓存-涉及到的数据结构很多，最好还是使用LinkedHashMap实现

public class Test {static class LRU extends LinkedHashMap<String, Object>{private int capability;public LRU(int capability){super(capability);this.capability = capability;}@Overrideprotected boolean removeEldestEntry(HashMap.Entry eldest) {return this.size() > capability;}}public static void main(String[] args) {Test t = new Test();LRU lru = new LRU(3);lru.put("2","2");lru.put("1","1");lru.put("3","3");for (Map.Entry<String, Object> entry : lru.entrySet()) {System.out.println(entry.getKey() + ":" + entry.getValue());}System.out.println("=====1=====");lru.put("4","4");for (Map.Entry<String,Object> entry : lru.entrySet()) {System.out.println(entry.getKey() + ":" + entry.getValue());}System.out.println("====2======");lru.remove("1");lru.put("1","1");for (Map.Entry<String,Object> entry : lru.entrySet()) {System.out.println(entry.getKey() + ":" + entry.getValue());}System.out.println("=====3=====");lru.put("5","5");for (Map.Entry<String,Object> entry : lru.entrySet()) {System.out.println(entry.getKey() + ":" + entry.getValue());}int[] ints = {1, 2};int[] arr = {1,2,3};int[] arr2 = new int[3];int[] arr3 = new int[]{1,2,3,4,5};}
}

数组

解法综述：

        1. 使用双指针的方式来解：

                a. 尾指针 + check指针

                b. 快慢指针，用在股票中，如果是上升趋势就累加

        2. 数组如何轮转

        3. 利用数组做跳跃玩法

        4. 整数转罗马数字

        5. 翻转字符串中的单词

尾指针 + check指针

删除排序数组中的重复项 II

class Solution {public int removeDuplicates(int[] nums) {if (nums.length <= 2){return nums.length;}boolean flag = false;int tail = 0;int pos = 1;while (pos < nums.length) {if (nums[tail] == nums[pos] && !flag) {nums[tail + 1] = nums[pos];tail++ ;pos++;flag = true;}else if (nums[tail] == nums[pos] && flag) {pos++;}else {nums[tail + 1] = nums[pos];tail++ ;pos++;flag = false;}}return tail + 1;}
}

快慢指针，用在股票中，如果是上升趋势就累加

股票买卖的最佳时机

class Solution {//思路：马后炮，知道第二天会涨， 所以前一天会买public int maxProfit(int[] prices) {if (prices.length == 1) {return 0;}int slow = 0;int fast = 1;int total_profit = 0;while(fast < prices.length){if (prices[fast] > prices[slow]) {total_profit = total_profit + prices[fast] - prices[slow];}fast++;slow++;}return total_profit;}
}

数组如何轮转

轮转数组

class Solution {//思路很巧妙：将翻转问题转为，全局倒序，再局部正序。 public void rotate(int[] nums, int k) {int real_k = k % nums.length ;reverse(nums, 0, nums.length - 1);reverse(nums, 0, real_k - 1);reverse(nums, real_k, nums.length - 1);}public void reverse(int[] nums, int left, int right){while (left < right) {int temp = nums[left];nums[left] = nums[right];nums[right] = temp;left++;right--;}}
}

利用数组做跳跃玩法

只能跳到指定位置

class Solution {//思路：//1. 确定可以跳到的最大位置，如果没有变大就是false。//2. 如果可以变大就继续跳，直到最尾部，那就是truepublic boolean canJump(int[] nums) {if (nums.length == 1) {return true;}int cur = 0;int tail = cur + nums[cur];// if (nums[cur] == 0) {//     return false;// }while (cur<=tail) {int pos = nums[cur] + cur;if (pos > tail) {tail = pos;}if (tail >= nums.length - 1) {return true;}cur++;}return false;}
}

可以在一定范围内随意跳

class Solution {//思路：//1. 确定可以跳到的最大位置，如果没有变大就是false。//2. 如果可以变大就继续跳，直到最尾部，那就是truepublic boolean canJump(int[] nums) {if (nums.length == 1) {return true;}int cur = 0;int tail = cur + nums[cur];// if (nums[cur] == 0) {//     return false;// }while (cur<=tail) {int pos = nums[cur] + cur;if (pos > tail) {tail = pos;}if (tail >= nums.length - 1) {return true;}cur++;}return false;}
}

整数转罗马数字

class Solution {int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};public String intToRoman(int num) {StringBuffer roman = new StringBuffer();for (int i = 0; i < values.length; ++i) {int value = values[i];String symbol = symbols[i];while (num >= value) {num -= value;roman.append(symbol);}if (num == 0) {break;}}return roman.toString();}
}

反正字符串中的单词

class Solution {public String reverseWords(String s) {s = s.trim();String[] words = s.split("\\s+");StringBuilder res = new StringBuilder();for (int i= words.length - 1; i>=0; i--) {res.append(words[i]);res.append(" ");}return res.toString().trim();}
}