Welcome to Nicholas's Blog!

• 对微XX的一些感悟

  2018-04-02

  张祝浩

  生活杂谈

  感悟

  这是一篇对最近生活中遇到的微××的感想和感悟

  最近在外面工作了一段时间，和同事一块吃饭的时候总是听同事谈论“今日头条”， “抖音”，“微博”之类的一些互联网产品。感觉这类App已经侵入到了各种各样的人的生活的方方面面，按理说作为一个程序员应当乐于接受这类事物，但是最近我确实想要将这些东西给批判一番。
  换句话说，并不是批判这些产品，而是批判一下那些沉溺于其中，没有意识到这类产品仅仅是精神上的Occioccasional Self-indulgence的意志力薄弱的人类。“抖音”，“微博”，这些产品通过算法推荐将大家喜欢看到的内容源源不断地Feed给你，而且推送的信息大多具有短平快这样的特征，这些信息大多都没有任何深度，也不能引导读者思考，绝大多数情况下，看官们都是一笑置之，没有能够加深任何你大脑中的回路。
  现代人类的注意力集中程度在这样不断的训练下恐怕只能集中45秒了，如果人只能集中45秒的注意力，还有可能理解一个稍微的复杂的公式，稍有意思的理论，稍有深度的知识吗？
  事实是这个世界上的知识大多是复杂的，成块的，系统性的。目前来看，文字流畅，简洁明了，编排合理的书籍依旧是传达知识密度最高，最合理也是最传统的载体。那些没有意识到自己陷入到了”微**“这类信息产品陷阱之中的人多是放弃了系统性学习提升自己的机会。

  那有怎样

  那有怎样呢？我就是稀饭刷刷微博，刷刷朋友圈，看看今日头条，抖音小视频咋滴了呢？
  哈哈，诚然，现代社会已经进化到了这样一个地步，大多数人的基本生存需求已经可以轻易满足，机器取代人类的大背景下，许多人其实并不需要工作，换句话说社会不需要这些劳动力。因为他们能够提供的劳动力太简单了，而且能被其他途径有效率地替代。社会通过收入分配制度将财富从创造者手中转移到这类人手中，然后他们有吃喝拉撒打游戏，泡妞，买买买等等的需求，然后这些财富最后又回到社会财富创造者的手中。
  人各有志嘛!
  Which type of person do you want to be?

  Read All

  ---

• Java characters 终结篇

  2017-09-15

  张祝浩

  JVM

  JVM

  Java char unicode 等问题终结篇

  在面试Java的时候，考官总是喜欢问些char能不能存下中文啦之类的无聊的问题。有人说Java内存里是用Unicode存储char的所以可以存储中文。 错！ 我们追根问底一下。 首先Unicode是一个编码字符集(coded character set)，也是ISO国际标准，是为了解决各国人民在美国人第一版计算机只有ascii字符而没有本国文字而自创了各式各样互不兼容的字符集出现的（GB2312 Big-5 日本的 韩国的。。。。），而且目前还一直在发展中，Unicode规定的仅仅是世界上所有的字符和其对应的某个数字——0x????（Unicode code points）存在的映射关系。起初的设计是Unicode只占两个字节16位（Byte），也就是最多只能支持65536种字符。但是咱们博大精深的汉字人家美国佬起初设计的Unicode怎么可能包括我中华民族的所有汉字。JVM平台诞生之初匹配当时的Unicode字符，规定char只能占2个字节，但是随着Unicode的发展，字符编码超出0xFFFF的字符（被称为Supplementary character——补充字符集）就不能存储在一个char变量中了，于是JSR小组决定适配一下新的Unicode字符集。 这里又牵扯到了character encoding scheme的概念。utf-8 utf-16 utf-32是常见的基于Unicode的字符编码方案，我来分别解释下。

  1. utf-32使用4个字节来编码每个Unicode 字符，也就是最多表示42亿的字符，这远大于目前Unicode的所有字符，所以所有Unicode char都统一用4个字节表示，但是对于ascii字符，每个字符我们就用了4倍的存储空间，这在网络传输中明显是不划算的，低效率的。
  2. utf-16使用一个或者两个16位的数（2或4字节）来编码Unicode 字符。用标志位来区分对应的原始Unicode字符应当占4个或者2个字节。但是他做的依旧不彻底，对于Ascii字符来说还是多占用了一个字节。但是这家伙诞生之初可是和第一版Unicode一一对应的啊，因此微软开始将其采用的UTF-16直接称为Unicode。JVM平台最后采用的也是utf-16作为其对0xFFFF以上的平面¹的改造
  3. utf-8使用1到4个单字节数来编码Unicode。也是用每个字节开始的标志位区分原始字符应当占用几个字节。具体转换方式就不详述了。 综上所述，JSR小组最后决定直接采用utf-16作为JVM内部的encoding²，这样最大限度保留了向前兼容性，所有在0x0000-0xFFFF(Basic Multilingual Plane ,BMP， 第一版Unicode 基本平面 包括了常用汉字)而对于超出BMP的字符，JVM会自动将其转为utf-16存储在char[]中。 所以，回到一开始的问题，Java统一使用Unicode字符集 采用utf-16编码。由于汉字博大精深，Unicode里不在BMP里的汉字都不能用一个char变量存储。下面是我随意从Wikipedia上找的一个神奇的汉字，大家可以试一试。

     代码验证

  public class Main {
  	public static void main(String[] args) {
  		//char c = '𠒑'; won't compile!
  		String c = "𠒑";
  		int codePoint = c.codePointAt(0);
  		int lowwer = c.charAt(1);
  		System.out.printf("%x\n",codePoint);
  		System.out.printf("%x\n",lowwer);
  	}
  }
  

  ---

  1. wiki:Unicode Plane ↩

  2. Oracle- supplementary character ↩

  Read All

  ---

• 搬家到github pages

  2017-09-07

  生活  杂谈

  博客

  搬家啦

  这是我发布在github pages 博客上的第一篇测试博客，之前在CSDN写了一点博客。Github pages和jekyll 提供的简洁和美观的博客吸引了我。
  所以今天开始还是主要把自己的知识记录在github博客上吧。

  Read All

  ---

• 经典算法manacher解决最长回文序列问题

  2017-06-02

  经典算法

  算法

  manacher问题概述

  有这么一个经典的问题，就是求一个字符串中的最长回文子序列的长度。有常规的O(n^2)的思想，就是我们每次都尝试以字符串中的某个位置为中心，向两边expand，直到碰到边界或者不匹配，那么就记录这个值。伪代码如下

  int maxOdd;
  int maxEven
  String s;
  for (int i = 0; i < s.length(); i++){
      //assume odd length
      int j = i + 1, k = i -1;
      while (inBounds(j,k, s.length()) && s[j] == s[k])
      j++; k--;
      maxOdd = Math.max(j, k);
      //assume even length
          ...
      
  }
  int ans = max(maxOdd, maxEven);
  

  算法复杂度是O(n^2)，其实manacher就主要是在计算每个位置的最大expand size的地方做了优化我感觉manacher和KMP算法类似，都是利用了子问题的结果，也就是都包含着dp的思想。
  下面简要解释一下manacher算法。
  首先，为了优雅地解决问题，忽略奇偶的影响，我们在每个字符串中插入一个特殊字符。例如’#’吧。 那么就形成了如下的形状
  
  这里下面的P代表每个位置开始最大可以expand的长度数组。
  最关键的就是对称性的使用使得我们可以利用子问题。 现在假定我们有了一个遍历过程中的中心 c(初始值为0)，边界长度p[c]，和目前得到的回文串的右边界r,那么如果i落在r的左边，我们就可以利用对称的特性得知p[i] = min(r-i, p[i’])重点解释一下，如果i + p[i’] < r，那么显然p[i]只能是p[i’]，如果i + p[i’] >= r，由于右边界超出了已知的最大对称边界，我们只能得出p[i]>=r -i, 然后就和i > r的情况相同，我们需要在右边界的基础上继续向两边扩展。如果扩展成功得到新的边界r。那么循环结束后，重新遍历一次p，找到最大的p[i]就是我们要的结果 回顾一下，这里我们通过对称性，保证了r这个右边界每次比较成功就单调向右扩展而不回退，就可以保证O(n)的复杂度。附leetcode链接和Java AC code
  leetcode

  代码

  class Solution {
      public String longestPalindrome(String s) {
          //manacher algo 
          String lr = processString(s);
          int c = 0;
          int r = 0;
          int[] p = new int[lr.length()];
          for (int i = 0; i < lr.length(); i++){
              p[i] = r > i ? Math.min(r - i, p[2 * c -i]) : 0;
              while (inBounds(i+p[i] + 1, i - p[i] -1, lr.length()) && lr.charAt(i + p[i] + 1) == lr.charAt(i - p[i] -1)) 
                  p[i]++;
              //update center to i if (p[i] > r - c)
              if(p[i] + i > r){
                  c = i;
                  r = p[i] + i;
              }
          }
          int max = 0;
          int maxIndex = 0;
          for (int i = 0; i < lr.length();i++){
              if (p[i] > max){
                  max = p[i];
                  maxIndex = i;
              }
          }
          return s.substring((maxIndex - max)/2, (maxIndex + max)/2 );
      }
      private String processString(String s){
          StringBuilder res = new StringBuilder();
          res.append('#');
          for (int i = 0; i < s.length(); i++){
              res.append(s.charAt(i));
              res.append('#');
          }
          return res.toString();
      }
      private boolean inBounds(int right, int left, int length){
          return right < length && left >= 0;
      }
  }
  

  Read All

  ---

• Welcome to Jekyll!

  2017-05-06

  jekyll  update

  You’ll find this post in your _posts directory. Go ahead and edit it and re-build the site to see your changes. You can rebuild the site in many different ways, but the most common way is to run jekyll serve, which launches a web server and auto-regenerates your site when a file is updated.

  To add new posts, simply add a file in the _posts directory that follows the convention YYYY-MM-DD-name-of-post.ext and includes the necessary front matter. Take a look at the source for this post to get an idea about how it works.

  Jekyll also offers powerful support for code snippets:

  def print_hi(name)
    puts "Hi, #{name}"
  end
  print_hi('Tom')
  #=> prints 'Hi, Tom' to STDOUT.

  Check out the Jekyll docs for more info on how to get the most out of Jekyll. File all bugs/feature requests at Jekyll’s GitHub repo. If you have questions, you can ask them on Jekyll Talk.

  Read All

  ---