Posts

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作者代码味道系列的第五篇。讲述作者对一个大方法进行重构的过程，主要处理的代码坏味道为多职责方法，在实际开发中随着功能的增加方法会一点点膨胀，这时候就要注意了 ...

前言 为了给mac找一款合适的android模拟器，先前使用的Nox player，但是老哥这Mac版本好几年都不更新了，使用的VirtualBox也不兼容。 替代者 网易MuMu模拟器 号称非常快，主要是Mac版本有更新。其它的都不行。 配置Charles抓包 以为找到了一个非常好的模拟器，没想到配置Charles抓包时遇到很多问题（我这使用的是Mumu版本是1.9.1） SSL代理配置问题 正常情况下的代码只需要配置ip和端口就可以，但是发现配置保存后，不能进行输入，修改成无代理就又可以了，后来各种找发现还得在配置中不使用代理中要配置10.0.2.2这个ip，好像是模拟器内部要用这个地址。 SSL证书安装问题 配置好代码ip后，要下载Charles的证书并安装，这时要配置模拟器的解锁密码，如果遇到输入正确密码后不能安装的问题，则可以考虑重新配置一下密码，大于6位的吧 多开问题 对于Nox player可以进行真正意义的完全多开（模拟器环境隔离），Mumu只是实现了简单的多开，不能使用不同版本的app，目测只是一个镜像。但是好在能使用了，希望后续开发团队可以支持。 软件窗口问题 如果在Mac使用窗口操作工具对Mumu进行操作，则可能一下子就找不到应用了，只能重启，正确的使用方式是使用Mumu菜单中的窗口下的拼贴功能，使用起来还不错。

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两个节点的反转。这个递归看着还是有点懵，多看看就好了。 ...