1. Algorithm: 每周至少做一个 LeetCode 的算法题

题目

31. Next Permutation



Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.



If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).



The replacement must be in-place and use only constant extra memory.



Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.



1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

解答

分析这道题：求刚好大于当前排列的数组，并且只能通过交换位置的方式实现。实际上是大整数用数组来实现，比如123，刚好比它大的是132. 这里要分3个步骤解决：

1. 从右到左，找出第一个当前数小于其右侧的数字，位置为i；

2. 再次从右到左，找出第一个数字比位置i的数大的数，位置为j；交换位置i和j；

3. 把i+1 到最后的数组逆序。



具体如下图所示。



package array;
public class NextPermutation {
  public void nextPermutation(int[] nums) {
    int i = nums.length - 2;
    // find the first small number
    while (i >= 0 && nums[i] >= nums[i + 1]) {
      i--;
    }
    // switch with the just last then the nums[i] number
    if (i >= 0) { // validate whether is -1
      int j = nums.length - 1;
      while (j >= 0 && nums[j] <= nums[i]) {
        j--;
      }
      swap(nums, i, j);
    }
    // swap the array from i + 1 to the end
    reverse(nums, i+1, nums.length - 1);
  }
  private void swap(int[] nums, int from, int to) {
    int temp = nums[from];
    nums[from] = nums[to];
    nums[to] = temp;
  }
  private void reverse(int[] nums, int from, int to) {
    while (from < to) {
      swap(nums, from, to);
      from++;
      to--;
    }
  }
}



2. Review: 阅读并点评至少一篇英文技术文章



How one code review rule turned my team into a dream team

https://medium.com/inside-league/how-one-code-review-rule-turned-my-team-into-a-dream-team-fdb172799d11



这篇文章分享code review的经验：

1. 必须有两个人review pull request 才能merge code；

2. 必须清楚描述pull request信息；

3. 必须要有Unit Test；

4. 如果是Bug fixed，必须要能测试已经修复问题。



3. Tips: 学习至少一个技术技巧

笔者写的博客：



iOS swift当app从后台切换到前台，或者锁屏后开启唤醒，app收到通知,didBecomeActiveNotification



说明

iOS swift当app从后台切换到前台，或者锁屏后开启，app收到通知。根据单一职责原则，所以在需要该方法的ViewController中加入监听就好。



代码实现 for swift 5

class ViewController: UIViewController {
    override func viewDidLoad() {
        super.viewDidLoad()
        // Do any additional setup after loading the view.
        NotificationCenter.default.addObserver(self, selector: #selector(applicationDidBecomeActive), name: UIApplication.didBecomeActiveNotification, object: nil)
    }
    @objc func applicationDidBecomeActive(notification: NSNotification) {
        // Application is back in the foreground
        print("applicationDidBecomeActive")
    }
}



参考

https://stackoverflow.com/questions/11928126/how-can-i-use-applicationdidbecomeactive-in-uiviewcontroller/63275933#63275933



4. Share: 分享一篇有观点和思考的技术文章

笔者写的博客链接



极客大学架构师训练营 JVM虚拟机原理 JVM垃圾回收原理 Java编程优化 第17课 听课总结

说明

讲师：李智慧



JVM虚拟机原理

JVM 组成架构

Java 是一种跨平台的语言，JVM 屏蔽了底层系统的不同，为Java 字节码文件构造了一个统一的运行环境。



Windows, Mac OS, Android OS每个不同的环境下，执行引擎会不一样, 实现跨平台。



Tomcat 启动命令

java org.apache.catalina.startup.Bootstrap "@" start

当启动Tomcat之前，先会初始化JVM 虚拟机，Java虚拟机会启动一个主线程，Bootstrap会执行main方法，在方法区。 new 出来的对象A，是放在堆中的，创建对象是由执行引擎处理的。



Java字节码文件

Java 如何实现在不同操作系统、不同硬件平台上，都可以不用修改代码就能顺畅地执行？



计算机领域的任何问题都可以通过增加个中间层(虚拟层)来解决。



Java 所有的指令有 200 个左右，一个字节(8位)可以存储256种不同的指令信息，一个这样的字节称为字节码(Bytecode). 在代码的执行过程中，JVM将字节码解释执行，屏蔽对底层操作系统的依赖，JVM也可以将字节码编译执行，如果是热点代码，会通过JIT（just-in-time compilation即时编译）动态地编译为机器码，提高执行效率。

cafe babe 表示Java的字节码。



字节码执行流程

热点代码就提交编译，达到复用的效果。



Java 字节码文件编译过程

类加载器的双亲委托模型

低层次的当前类加载器，不能覆盖更高层次类加载器已经加载的类。如果低层次的类加载器想加载一个未知类，需要上级类加载器确认。只有当上级类加载器没有加载过这个类，也允许加载的时候，才让当前类加载器加载这个未知类。





自定义类加载器

1. 隔离加载类：同一个JVM中不同组件加载同一个类的不同版本。

2. 扩展加载源：从网络、数据库等处加载字节码。

3. 字节码加密：加载自定义的加密字节码，在ClassLoader中解密。

堆 & 栈

堆：每个JVM实例唯一对应一个堆。应用程序在运行中所创建的所有类实例或数组都放在这个堆中，并由应用所有的线程共享。



堆栈：JVM为每个新创建的线程都分配一个堆栈。也就是说，对于一个 Java 程序来说，它的运行就是通过对堆栈的操作来完成的。



Java 中所有对象的存储空间都是在堆中分配的，但是这个对象的引用却是在堆栈中分配，也就是说在创建一个对象时从两个地方都分配内存。在堆中分配的内存实际建立这个对象，而在堆栈中分配的内存只是一个指向这个堆对象的引用而已。

方法区 & 程序计数器

方法区主要存放从磁盘加载进来的字节码，而在程序运行过程中创建的类实例则存放在堆里。程序运行的时候，实际上是以线程为单位运行的，当JVM进入启动类的 main 方法的时候，就会为应用程序创建一个主线程。 main 方法里的代码就会被这个主线程执行，每个线程有自己的 Java 栈，栈里存放着方法运行期的局部变量。而当前线程执行到哪一行字节码指令，这个信息则被存放在程序计数寄存器。



静态变量、静态方法放在方法区，只会有一个。



Java (线程)栈

所有在方法内定义的基本数据类型变量，都会被每个运行这个方法的线程放入自己的栈中，线程的栈彼此隔离，所以这些变量一定是线程安全的。

线程工作内存 & volatile

Java 内存模型规定在多线程情况下，线程操作主内存变量，需要通过线程独有的工作内存拷贝主内存变量副本来进行。



一个共享变量（类的成员变量、类的静态成员变量）被volatile 修饰之后，那么就具备了两层语义：

1. 保证了不同线程对这个变量进行操作时的可见性，即一个线程修改了某个变量的值，这新值对其它线程来说是可见的。

2. 禁止进行指令重排序。

工作内存：CPU的cache，寄存器。

用volatile修饰的变量，当该变量被修改时，确保数据刷到主内存中。保证数据的可见性，并不能保证数据的安全性，还是得需要锁。



Java 运行环境



JVM 的垃圾回收



JVM 垃圾回收即使将 JVM 堆中的已经不再被使用的对象清理掉，释放宝贵的内存资源。



JVM 通过一种可达性分析算法进行垃圾对象的标识。具体过程是：

1. 从线程栈帧中的局部变量，或者方法区的静态变量出发，将这个变量引用的对象进行标记；

2. 然后看这些被标记的对象是否引用了其它对象，继续进行标记；

3. 所有被标记过的对象都是被使用的对象，而那些没有被标记的对象就是可回收的垃圾对象了。



进行完标记以后，JVM 就会对垃圾对象占用的内存进行回收，回收主要有三种方法：

1. 清理：将垃圾对象占据的内存清理掉，其实 JVM 并不会真的将这些垃圾内存进行清理，而是将这些垃圾对象占用的内存空间标记为空闲，记录在一个空闲的列表里，当应用程序需要创建新的对象的时候，就从空闲列表中找一段空闲内存分配给这个对象。

2. 压缩：从堆空间的头部开始，将存活的对象拷贝到一段连续的内存空间中，那么其余的空间就是连续的空闲空间。

3. 复制：将堆空间分成两部分，只在其中一部分创建对象，当这个部分空间用完的时候，将标记过的可用对象复制到另一个空间中。

清理：把已经没用的空间标记为可用空间。

压缩：清理有个短板，空间不是连续的，压缩就是把还在用的copy放在前面。

复制：压缩还是需要成本的，速度较慢；分两块区域会更好一点。



JVM 分代垃圾回收

1. 创建新对象在Eden区，当Eden区满了以后，就会进行Young GC，把在用的对象copy到From区；

2. 当Eden区再次满了以后，再次进行YoungGC，把Eden区和From区的在用对象，copy到To区；

3. 当多次Eden发送YoungGC，把一些还用的对象放到老年代；

4. 当老年代满了以后，就会进行Full GC。这是要应用线程都要暂停，进行Full GC。



JVM垃圾回收器算法

1. 串行回收器：当JVM空间满了以后，stop-the-world 停止所有应用程序的线程，进行垃圾回收。（以前的都是单CPU）

2. 并行回收器：多CPU时代，当JVM空间满了以后，stop-the-world 多线程进行垃圾回收。（大数据用这种方式，效率比较高）

3. 并发回收器CMS：初始化标记静态变量等以及引用的对象 > 并发标记 > 重标记(永远表不完对象，因为对象一直在创建。所以这个阶段也会stop-the-world) > 并发清理。（早期Web应用都是用这种方式，但是浪费计算资源比较多。）

4. G1回收器(主流)：效率更高，下面详细介绍。每次stop-the-world的时候，只会清理一部分区域，控制范围更小一些。



G1垃圾回收内存管理机制

把大的内存分为2000个小块。

配置参数： -XX:MaxGCPauseMillis



Java 启动参数

标准参数，所有的JVM 实现都必须实现这些参数的功能，而且向后兼容：

• 运行模式： -server, -client

• 类加载路径: -cp, -classpath

• 运行调试: -verbose

• 系统遍历: -D



非标准参数，默认 JVM 实现这些参数，但不保证所有 JVM 实现都实现，且不保证向后兼容：

• -Xms 初始堆大小

• -Xmx 最大堆大小

• -Xmn 新生代大小

• -Xss 线程堆栈大小



一般 -Xms 和 -XMx 都是配置一样的。

非 Stable 参数，此类参数各个 JVM 实现会有所不同，将来可能会随时取消

• -XX:-UseConcMarkSweepGC 启用 CMS 垃圾回收