Arts

Algorithm 题目 题目描述 98.验证二叉搜索树，给定一个二叉树，判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征： 节点的左子树只包含小于当前节点的树 节点的右子树只包含大于当前节点的树 所有左子树及右子树自身也必须是二叉搜索树 题目解答 import java.util.Stack; public class ValidBST { public boolean isValidBST (TreeNode root) { Stack<TreeNode> stack = new Stack<>(); double inorder = -Double.MAX_VALUE; while (!stack.isEmpty() || root != null) { while (root != null) { stack.push(root); root = root.left; } root = stack.pop(); if (inorder >= root.val) { return false; } inorder = root.val; root = root.right; } return true; } } 使用中序遍历(即左->根->右)来实现，从左至右进行比对，每次与上次保存的值进行对比，如果当前节点值比上次保存的值小，则可以判定此树不是二叉搜索树。时间复杂度为O(n)，空间复杂度为O(n) ...

Algorithm 题目 题目描述 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。答案中不可以包含重复的三元组。 题目解答 import java.util.ArrayList; import java.util.Arrays; import java.util.List; class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> result = new ArrayList<>(); if(null == nums || nums.length < 3) { return result; } Arrays.sort(nums); for (int i = 0; i < nums.length; i ++) { if(nums[i] > 0) { break; } if(i > 0 && nums[i] == nums[i - 1]) { continue; } int L = i + 1; int R = nums.length - 1; while (L < R) { int target = nums[i] + nums[L] + nums[R]; if (target == 0) { result.add(Arrays.asList(nums[i], nums[L], nums[R])); while (L < R && nums[L] == nums[L + 1]) L++; while (L < R && nums[R] == nums[R - 1]) R--; L++; R--; } else if (target < 0) { L++; } else { R--; } } } return result; } 一共有三种解法，一是三层for循环，时间复杂度为O(n3)；二是二层for循环外加Hash表，时间复杂度为O(n2)，增加了空间复杂度O(n);第三种就是上面的解法，排序后从两侧开始匹配，时间复杂度为O(n2)，空间复杂度为O(1) ...

Algorithm 题目 题目描述 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。242 valid anagram 题目解答 可以使用先排序后判断的方法来实现，这样的时间复杂度为O(nlog(n))。更好的方法是借助Hash表来实现，可以达到O(n)的时间复杂度。 public class ValidAnagram { public boolean isAnagram(String s, String t) { if (null == s || null == t || s.length() != t.length()) { return false; } Map<Character, Integer> map = new HashMap<>(); final char[] chars = s.toCharArray(); for (int i = 0; i < chars.length; i++) { final char key = s.charAt(i); map.put(key, map.getOrDefault(key, 0) + 1); final char key1 = t.charAt(i); map.put(key1, map.getOrDefault(key1, 0) - 1); } for (Map.Entry<Character, Integer> entry : map.entrySet()) { if (0 != entry.getValue()) { return false; } } return true; } } Review 你可能不知道的SHELLCoolShell左耳朵耗子2012年的关于强大Shell的文章，里面列出了很多有用的命令，看完后收获颇丰。针对实际使用场景，列出我认为暂时可以直接使用的一些操作命令。 ...

Algorithm 题目 题目描述 给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。 239 sliding-window-maximum 题目解答 一般与滑动窗口有关的问题都可以使用双端队列来处理。 import java.util.ArrayDeque; import java.util.List; import java.util.ArrayList; public class MaxSlidingWindow { private ArrayDeque<Integer> window = new ArrayDeque<>(); public int[] slidingWindowMax(int[] nums, int k) { if(nums.length == 0) { return new int[0]; } List<Integer> res = new ArrayList<>(); for(int i = 0; i < nums.length; i++) { if(i >= k && window.getFirst() <= i - k) { window.pollFirst(); } while(!window.isEmpty() && nums[window.getLast()] < nums[i]) { window.pollLast(); } window.add(i); if(i >= k - 1) { res.add(nums[window.getFirst()]); } } return res.stream().mapToInt(i->i).toArray(); } } Review Consistent_hashing一致性Hash算法。 ...

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作者代码味道系列的第四篇。讲述了作者对一个近百行的方法进行重构的过程，主要是因为可变变量的坏味道。 ...