Java

Algorithm 题目 题目描述 设计一个找到数据流中第K大元素的类（class）。注意是排序后的第K大元素，不是第K个不同的元素。703 数据流中的第K大元素 题目解答 public class KthLargest { private PriorityQueue<Integer> queue; private int k; public KthLargest(int k, int[] nums) { this.k = k; queue = new PriorityQueue<>(k); for(int num : nums) { add(num); } } public int add(int val) { if(queue.size() < k) { queue.offer(val); } else if (queue.peek() < val) { queue.poll(); queue.offer(val); } return queue.peek(); } } Review 与程序员相关的CPU缓存知识这是左耳朵耗子的一篇微观技术分享，讲解了程序员要知道的关于CPU缓存的知识，并举例进行了说明。 ...

Algorithm 题目一 题目描述 使用栈实现队列的操作：push(), peek(), pop(), empty()操作，只能使用标准的栈操作 – 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。232 用栈实现队列 题目解答 由于队列是FIFO，而栈是FILO，要想使用栈来实现队列，则可以使用两个栈来达到目的，即负负到正，核心点就是pop()和peek()方法的处理上，在调用pop()与peek()方法时都在要从outStack中来操作，如果outStack不为空，则直接进行操作，否则要把inStack中的元素添加到outStack中。 import java.util.Iterator; import java.util.Stack; class MyQueue { private Stack<Integer> inputStack; private Stack<Integer> outStack; /** Initialize your data structure here. */ public MyQueue() { inputStack = new Stack<>(); outStack = new Stack<>(); } /** Push element x to the back of queue. */ public void push(int x) { inputStack.push(x); } /** Removes the element from in front of queue and returns that element. */ public int pop() { if (empty()) { return -1; } if (outStack.empty()) { while (!inputStack.empty()) { outStack.push(inputStack.pop()); } } return outStack.pop(); } /** Get the front element. */ public int peek() { if (empty()) { return -1; } if (outStack.empty()) { while (!inputStack.empty()) { outStack.push(inputStack.pop()); } } return outStack.peek(); } /** Returns whether the queue is empty. */ public boolean empty() { return inputStack.empty() && outStack.empty(); } } 时间复杂度：push O(1), pop O(n), peek O(n) ...

Algorithm 题目描述 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。 Example 输入: [3,2,1,5,6,4] 和 k = 2 输出: 5 题目解答 public class KthMax { public int findKthLargest(int[] nums, int k) { if (nums.length < k) return -1; int p = 0; int r = nums.length - 1; int q = partition(nums, p, r); while (k != q + 1) { if (k > q + 1) { q = partition(nums, q + 1, r); } else { q = pyrtition(nums, 0, q - 1); } } return nums[q]; } public int partition(int[] nums, int p, int r) { int povit = nums[r]; int i = p; for (int j = p; j < r; j++) { if (nums[j] > povit) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; i++; } } int tmp = nums[i]; nums[i] = nums[r]; nums[r] = tmp; return i; } } 主要是使用快速排序算法来进行查找，先找到一个分区点q，如果k=q+1，则说明找到了，如果k>q+1则从后半区找，否则从前半区找。 ...

Algorithm 题目描述 给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。258.各位相加 Example 输入: 38 输出: 2 解释: 各位相加的过程为：3 + 8 = 11, 1 + 1 = 2。 由于 2 是一位数，所以返回 2。 题目解答 解答一（递归） public class AddDigitsV1 { public int addDigits(int num) { if(num < 10) return num; return addDigits(num % 10 + num / 10); } } 此解法的时间复杂度为O(log(n))，空间复杂度为O(1) 使用递归要满足的条件 一个任务可以拆分成多个子任务 每个任务都有相似的处理步骤（流程） 存在终止条件 解答二（模9法） public class addDigitsV2 { public int addDigits(int num) { return (num - 1) % 9 + 1; } } 查找规律发现可以以%9来得到答案，但是对于整除9的结果就不行了，所以还要采用借1还1的方式来处理。此解的时间复杂度为O(1)，空间复杂度为O(1) ...

Algorithm 题目描述 设计你的循环队列实现，支持入队，出队，获取队首元素，获取队尾元素 题目解答 采用数组可以实现，由于要达到循环效果，主要要考虑队头与队尾的情况 public class MyCircurlarQueue { private int[] queue; private int headIndex; private int count; public MyCircurlarQueue(int capacity) { this.queue = new int[capacity]; } private boolean inQueue(int value) { if (isFull()) { return false; } queue[(headIndex + count) % queue.length] = value; count += 1; return true; } private boolean deQueue() { if (isEmpty()) { return false; } headIndex = (headIndex + 1) % queue.length; count -= 1; return true; } private int First() { if (isEmpty()) { return -1; } return queue[(headIndex + 1) % queue.length]; } private int Rear() { if (isEmpty()) { return -1; } return queue[(headIndex + count - 1) % queue.length]; } private boolean isEmpty() { return count == 0; } private boolean isFull() { return count == queue.length; } } Review code-smells-multi-responsibility-methods本文是Idea作者代码味道系列的第五篇。讲述作者对一个大方法进行重构的过程，主要处理的代码坏味道为多职责方法，在实际开发中随着功能的增加方法会一点点膨胀，这时候就要注意了 ...

Algorithm 题目描述 给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串，判断字符串是否有效。leetcode-20 Example 输入: “()” -> 输出: true 输入: “()[]{}” -> 输出：true 题目解答 此种题目可以使用栈来进行处理，主要有几个核心点 入参数为奇数则一定不匹配 对于左括号，直接进行push操作 对于右括号，对栈进行pop操作与右括号进行匹配 最后栈为空则说明所有都匹配成功 public class BracketMatching { public boolean isValid (String s) { if (null == s || s.length() % 2 != 0) return false; Stack<Character> stack = new Stack<>(); Map<Character, Character> map = new HashMap<>(); map.put(')', '('); map.put('}', '{'); map.put(']', '['); for (char c : s.toCharArray()) { if (!map.containsKey(c)) { stack.push(c); } else if (stack.empty() || map.get(c) != stack.pop()) { return false; } } return stack.empty(); } Review code-smells-mutation本文是Idea作者代码味道系列的第四篇。讲述了作者对一个近百行的方法进行重构的过程，主要是因为可变变量的坏味道。 ...

Algorithm 题目描述 给定一个链表，判断链表中是否有环。 Example 输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。 题目解答 首先能想到的解法是使用一个Set存储已经遍历过的节点，如果在遍历中节点已经存在于Set中，则说明链表是有环的，这种解法额外使用了其它的数据结构。另一种更好的方法就是使用快慢指针的方式，类似于跑道上的套圈，如果快的人追上了慢的人则说明是有环的，否则就是快的人先到达终点（即访问到最后的Null） public class CycleSolution { public static boolean hasCycle(ListNode node) { ListNode slow = node; ListNode fast = node; while (slow != null && fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { return true; } } return false; } } 快慢指针的解法的时间复杂度为O(n)，空间复杂度为O(1)，因为只使用了两个指针。 ...

Algorithm 题目描述 反转一个单链表。 Example 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 题目解答 迭代解法 class Solution3 { public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode current = head; while (current != null) { ListNode tempNode = current.next; current.next = prev; prev = current; current = tempNode; } return prev; } } 第一次搞链表的题，还真是给难住了。此题的核心就是当前节点的指针要指向前一个节点，处理过程中还要考虑节点的丢失问题，所以要有一个变量保存当前节点的前一个节点，还要有一个变量来保存当前节点的下一个节点，方便后续的指针前移。此解法的时间复杂度为O(n)，因其不需要额外的空间，所以空间复杂度为O(1)。 递归解法 class Solution3 { public ListNode reverseList2(ListNode node) { if (node == null || node.next == null) { return node; } ListNode current = reverseList2(node.next); node.next.next = node; node.next = null; return current; } } 此解的核心在于当有一部分是反转时，后续的反转问题，对于node.next.next = node这句，使用A->B两个节点进行示例，A.next为B，A.next.next为B.next，A.next.next = A为B.next = A，这样就实现了A与B两个节点的反转。这个递归看着还是有点懵，多看看就好了。 ...

Algorithm 题目描述 判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。 Example 输入123->true 输入-123->false 输入12->true 题目解答 class Solution2 { public boolean isPalindrome(int x) { if(x < 0) { return false; } if(x % 10 == 0 && x != 0) { return false; } int reverseNumber = 0; while (x > reverseNumber) { reverseNumber = reverseNumber * 10 + x % 10; x /= 10; } return reverseNumber == x || x == reverseNumber / 10; } } 最简单暴力的方法是把int转换成String进行处理，String反转一半再与后续的进行比较，对于溢出的数字一定不是回文字。此方法则可以更快速的解决问题，关键是怎么找到当前数字的一半位置，可以使用当前数字pop与反转数字的push相比较，当push后的值大于pop后的值则说明到达了数字长度的一半了，对于奇数位的数字则可以使用reverseNumber/10来判断，因为中间的单个字默认就是回文字。此算法的时间复杂度为O(log(n))，空间复杂度为O(1)。 ...

Algorithm 题目描述 给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。 Example 输入123->321 输入-123->-321 输入120->21 题目解答 import java.util.*; public class Solution1 { public int[] reverseNumber(int num) { int res = 0; while(num != 0) { int pod = num % 10; if(res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && pod > 7)) { return 0; } if(res < Integer.MIN_VALUE / 10 || (res == Integer.MIN_VALUE / 10 && pod < -8)) { return 0; } res = res * 10 + pod; num = num / 10; } return res; } } 此题主要考察对栈的使用，如果不使用其它辅助类，则要考虑Int的整数溢出问题。时间复杂度O(log(n))，空间复杂度为O(1) ...