android 中的 Unsafe

发表于 2020-07-12 更新于 2020-07-18 分类于 android

unSafe 类之初见

假设有如下的代码：

data class Person(var name: String, var age: Int)

private fun test() {
 val person = Gson().fromJson("{  \"age\":1 }", Person::class.java)
        Log.d(TAG, "persion :${person.age} & ${person.name} ")
}

上述代码，执行 test 函数之后会怎么样？

在执行 fromJson 时就抛出空指针异常？因为 name为null ?
返回的 person 为 null, 导致后续执行抛出空指针?
test() 正常执行，输出 persion: 1 null
test() 正常执行，输出 persion: 1

答案应该是 3

通过源码的角度来快速了解一下 gson 转换成对应对象的过程
Gson类中的 fromJson相关实现：

public <T> T fromJson(String json, Class<T> classOfT) throws JsonSyntaxException {
   //转化成功都在 fromJson 方法中, 重点
  Object object = fromJson(json, (Type) classOfT);
  return Primitives.wrap(classOfT).cast(object);
}

  @SuppressWarnings("unchecked")
public <T> T fromJson(String json, Type typeOfT) throws JsonSyntaxException {
  if (json == null) {
    return null;
  }
  StringReader reader = new StringReader(json);
  // 从 StringReader 转化成对应的对象, 重点
  T target = (T) fromJson(reader, typeOfT);
  return target;
}

public <T> T fromJson(Reader json, Type typeOfT) throws JsonIOException, JsonSyntaxException {
  JsonReader jsonReader = newJsonReader(json);
  T object = (T) fromJson(jsonReader, typeOfT);
  assertFullConsumption(object, jsonReader);
  return object;
}

 public <T> T fromJson(JsonReader reader, Type typeOfT) throws JsonIOException, JsonSyntaxException {
  boolean isEmpty = true;
  boolean oldLenient = reader.isLenient();
  reader.setLenient(true);
  try {
    reader.peek();
    isEmpty = false;
    TypeToken<T> typeToken = (TypeToken<T>) TypeToken.get(typeOfT);
    // 通过 typeToken 获得 TypeAdapter<T>,TypeAdapter 就是抓换成目标对象的关键
    TypeAdapter<T> typeAdapter = getAdapter(typeToken);
    T object = typeAdapter.read(reader);
    return object;
  } catch (EOFException e) {
      ...
      //省略了异常处理相关代码
  }
 }

从上述源码来看，fromJson 通过将传入的数据转化成 StringReader ，通过 getAdapter方法就传入的 class示例话成对象，然后数据read 到示例化出来的对象之后，返回，就达到了将 json 数据转换成 bean 对象的目的。了解了大致流程之后，我们主要关注 getAdapter(typeToken) 是如何获取到合适的对象，并最终实例化出来的。
下面是 getAdapter(typeToken) 部分代码：

@SuppressWarnings("unchecked")
 public <T> TypeAdapter<T> getAdapter(TypeToken<T> type) {
  ...
     for (TypeAdapterFactory factory : factories) {
       TypeAdapter<T> candidate = factory.create(this, type);
       if (candidate != null) {
         call.setDelegate(candidate);
         typeTokenCache.put(type, candidate);
         return candidate;
       }
     }
  ...
 }

这里是通过 ReflectiveTypeAdapterFactory 来构建具体的 adapter 的。

@Override public <T> TypeAdapter<T> create(Gson gson, final TypeToken<T> type) {
  Class<? super T> raw = type.getRawType();

  if (!Object.class.isAssignableFrom(raw)) {
    return null; // it's a primitive!
  }

  ObjectConstructor<T> constructor = constructorConstructor.get(type);
  return new Adapter<T>(constructor, getBoundFields(gson, type, raw));
}

重点看一下 constructorConstructor.get(type) 这个方法的实现：

public <T> ObjectConstructor<T> get(TypeToken<T> typeToken) {
    ...
    ObjectConstructor<T> defaultConstructor = newDefaultConstructor(rawType);
    if (defaultConstructor != null) {
      return defaultConstructor;
    }

    ObjectConstructor<T> defaultImplementation = newDefaultImplementationConstructor(type, rawType);
    if (defaultImplementation != null) {
      return defaultImplementation;
    }

    // finally try unsafe
    return newUnsafeAllocator(type, rawType);
  }

可以看到最终，有三个 Constructor

newDefaultConstructor 尝试获取了无参的构造函数，则通过 newInstance反射方式构建对象
newDefaultImplementationConstructor 集合类相关的构建，如果传入类的不是 Map、Collection等相关的类，则会返回 null,返回返回对应的集合。
newUnsafeAllocator 最后通过 unsafe 的方式来构建

我们主要看最后一个方法的实现：

private <T> ObjectConstructor<T> newUnsafeAllocator(
    final Type type, final Class<? super T> rawType) {
  return new ObjectConstructor<T>() {
    private final UnsafeAllocator unsafeAllocator = UnsafeAllocator.create();
    @SuppressWarnings("unchecked")
    @Override public T construct() {
      try {
        Object newInstance = unsafeAllocator.newInstance(rawType);
        return (T) newInstance;
      } catch (Exception e) {
        throw new RuntimeException(("Unable to invoke no-args constructor for " + type + ". "
            + "Registering an InstanceCreator with Gson for this type may fix this problem."), e);
      }
    }
  };
}

看起来就是通过 UnsafeAllocator.create(); 获得了一个构造器，最终通过调用 newInstance() 将其构造出来了，那么是什么样的构造器，竟然能跳过 kotlin 的空值判断，创建一个属性值为 null 的对象，下面来看其实现代码：

public static UnsafeAllocator create() {
  // try JVM
  // public class Unsafe {
  //   public Object allocateInstance(Class<?> type);
  // }
  try {
    Class<?> unsafeClass = Class.forName("sun.misc.Unsafe");
    Field f = unsafeClass.getDeclaredField("theUnsafe");
    f.setAccessible(true);
    final Object unsafe = f.get(null);
    final Method allocateInstance = unsafeClass.getMethod("allocateInstance", Class.class);
    return new UnsafeAllocator() {
      @Override
      @SuppressWarnings("unchecked")
      public <T> T newInstance(Class<T> c) throws Exception {
        assertInstantiable(c);
        return (T) allocateInstance.invoke(unsafe, c);
      }
    };
  } catch (Exception ignored) {
  }
  ...
}

看到着，终于发现 UnsafeAllocator 的庐山真面目了，原来就是他通过 sun.misc.Unsafe 类绕过了构造方法，直接构建了一个对象。

了解了他的实现原来之后，我们可以给予他，也创建过不需要执行构造方法的对象：

private fun testCreate() {
        val unsafeAllocator = UnsafeAllocator.create()
        val person1 = unsafeAllocator.newInstance(Person::class.java)
        person1.age = 112;
        Log.d(TAG, " person1 ${person1.name} and ${person1.age}")
}

当然，也可以完全不实用他的构建方法，自己通过 UnSafe实现也是一样。

Unsafe 类的作用

java 中的 CAS 操作也基本上是通过 unSafe 类来实现的，包括 AtomicInteger,``

参考文档

android中的类加载

发表于 2020-07-11 更新于 2020-07-18 分类于 android

带着问题看源码

TextView 的整体渲染流程
主要有 staticLayout（分块绘制）、（动作监听）、（文本渲染处理，展示成 ** 之类的）、（）
TextView 怎么做到自动换行，怎么修改换行策略
跑马灯的实现
TextView 在展示不下时，怎么处理的？··· 是怎么添加到末尾的？
待续
TextView 怎么做到在文字末尾添加一个图标（多语言适配）
待续

知识点：为什么不能在主线程更新 UI

设计考虑：如果在更新 UI 时需要考虑多线程安全问题的话，会导致性能降低，为了避免这种性能降低，所以规定只能在 UI 线程中更新界面，如果不在主线程中做更新界面的实现的话，就会主动抛出异常。

onMeasure

onLayout

onDraw

三种 mode
unspeceieied 没有指定大小，子布局要求多大就多大
exatly 指定进行精确的大小，父布局说多大就多大
at_most 最大多大，父布局设置的上线，子 view 最大的高度或者宽度

MeasureSpec.UNSPECIFIED（0）
、MeasureSpec.EXACTLY（1）
、和MeasureSpec.AT_MOST（2）

kotlin 中的拓展函数

发表于 2020-07-08 更新于 2020-07-18 分类于 kotlin ， let ， run

Kotlin 中的拓展函数

run

作用：执行传入的函数，并返回执行结果。
调用示例：

val test: String ?= "" 
test?.run { 
    print("run")
}

run 函数最终返回的是 block 执行的结果，run 函数内部没有指向调用者的 it.

实现源码：

@kotlin.internal.InlineOnly
public inline fun <R> run(block: () -> R): R {
    contract {
        callsInPlace(block, InvocationKind.EXACTLY_ONCE)
    }
    return block()
}

with

with语法糖不再是⼀个拓展函数了，⽽是需要在语法糖的第⼀个参数⾥⾯传⼊接收者对象的实例，第⼆个参数就是带接收者的函数
字⾯值实例，返回的也是 block 调⽤的结果，这⼀点和 run 语法糖类似。

调用示例:

val test: String ?= "" 
    with(test) {
       print("with")
    }

实现源码：

@kotlin.internal.InlineOnly
public inline fun <T, R> with(receiver: T, block: T.() -> R): R {
    contract {
        callsInPlace(block, InvocationKind.EXACTLY_ONCE)
    }
    return receiver.block()
}

apply

apply 函数内部会自带调用者，返回的是调用者本身。
调用示例：

val test: String ?= "" 
    test?.apply { 
       substring(1)
    }

实现源码：

@kotlin.internal.InlineOnly
public inline fun <T> T.apply(block: T.() -> Unit): T {
    contract {
        callsInPlace(block, InvocationKind.EXACTLY_ONCE)
    }
    block()
    return this
}

alos

alos 和 let 类似，区别在于 alos 的返回值是 caller 本身，而 let 返回的是 block 的执行结果。
调用示例:

val test: String ?= "" 
test?.also {
        it.length
    }

实现源码：

@kotlin.internal.InlineOnly
@SinceKotlin("1.1")
public inline fun <T> T.also(block: (T) -> Unit): T {
    contract {
        callsInPlace(block, InvocationKind.EXACTLY_ONCE)
    }
    block(this)
    return this
}

let

let 方法块中，可以通过 it 来调用 caller, 返回值是方法块的执行结果。

调用示例:

val test: String ?= "" 
test?.let {
        it.length
    }

源码：

@kotlin.internal.InlineOnly
public inline fun <T, R> T.let(block: (T) -> R): R {
    contract {
        callsInPlace(block, InvocationKind.EXACTLY_ONCE)
    }
    return block(this)
}

takeIf

takeIf 要求方法块执行结果为 Boolean,如果 block执行的结果为 ture,则 takeIf 返回值为 caller,否则为 ``null。

调用示例：

val test: String ?= "ii" 
    test?.takeIf { 
        !it.isBlank()
    }?.let { 
        print(it)
    }

源码：

@kotlin.internal.InlineOnly
@SinceKotlin("1.1")
public inline fun <T> T.takeIf(predicate: (T) -> Boolean): T? {
    contract {
        callsInPlace(predicate, InvocationKind.EXACTLY_ONCE)
    }
    return if (predicate(this)) this else null
}

takeUnless

takeUnless 和 takeIf 相反，当 block 执行结果为 false时，返回 caller，否则返回 null

调用示例：

val test: String ?= "ii" 
    test?.takeUnless { 
        it.isBlank()
    }?.let { 
        print(it)
    }

源码：

@kotlin.internal.InlineOnly
@SinceKotlin("1.1")
public inline fun <T> T.takeUnless(predicate: (T) -> Boolean): T? {
    contract {
        callsInPlace(predicate, InvocationKind.EXACTLY_ONCE)
    }
    return if (!predicate(this)) this else null
}

repeat

需要重复的 action 模版，传入需要执行的次数，和需要执行的 block 即可。
调用示例：

1	repeat(10) { print(it)}

实现源码：

@kotlin.internal.InlineOnly
public inline fun repeat(times: Int, action: (Int) -> Unit) {
    contract { callsInPlace(action) }

    for (index in 0 until times) {
        action(index)
    }
}

referrers:

Java 中的 trim() 和 kotlin 中的 trim()

发表于 2020-06-06 更新于 2020-07-18 分类于 kotlin

java 中 trim 方法的实现

源代码如下：

public String trim() {
    int len = value.length;
    int st = 0;
    char[] val = value;    /* avoid getfield opcode */

    while ((st < len) && (val[st] <= ' ')) {
        st++;
    }
    while ((st < len) && (val[len - 1] <= ' ')) {
        len--;
    }
    return ((st > 0) || (len < value.length)) ? substring(st, len) : this;
}

可以看到，在 java 实现中， trim方法截取掉了前后 Unicode 小于等于空格的所有控制字符。具体截取的字符可以参考 unicode 字符列表.

kotlin 中 trim() 方法的实现


@kotlin.internal.InlineOnly
public inline fun String.trim(): String = (this as CharSequence).trim().toString()

public fun CharSequence.trim(): CharSequence = trim(Char::isWhitespace)

public inline fun CharSequence.trim(predicate: (Char) -> Boolean): CharSequence {
    var startIndex = 0
    var endIndex = length - 1
    var startFound = false

    while (startIndex <= endIndex) {
        val index = if (!startFound) startIndex else endIndex
        val match = predicate(this[index])

        if (!startFound) {
            if (!match)
                startFound = true
            else
                startIndex += 1
        } else {
            if (!match)
                break
            else
                endIndex -= 1
        }
    }

    return subSequence(startIndex, endIndex + 1)
}

可以看到，kotlin 中的 trim 方法和 java 中的 trim 方法实现基本差不多，唯一的差别就是匹配的字符规则不一样，在 java 匹配的规则是 <= ' ', 而 kotlin 中匹配的规则是 Char::isWhitespace。

接下来我们看看 Char::isWhitespace 的具体实现：参考

String.kt
expect fun Char.isWhitespace(): Boolean

实现在 charJVM.kt
public actual fun Char.isWhitespace(): Boolean = Character.isWhitespace(this) || Character.isSpaceChar(this)

可以看到, 在 String.kt 中只是通过 expect 声明了这个方法，具体实现还是在 charJVM.kt 中。关于 expect 和 actual 的用法可以参考 kotlin 平台相关声明.

而在Charactr 类中，isWhitespace() 和 isSpaceChar()的实现如下：

public static boolean isWhitespace(char ch) {
    return isWhitespace((int)ch);
}

public static boolean isWhitespace(int codePoint) {
    return CharacterData.of(codePoint).isWhitespace(codePoint);
}


public static boolean isSpaceChar(char ch) {
    return isSpaceChar((int)ch);
}

public static boolean isSpaceChar(int codePoint) {
    return ((((1 << Character.SPACE_SEPARATOR) |
              (1 << Character.LINE_SEPARATOR) |
              (1 << Character.PARAGRAPH_SEPARATOR)) >> getType(codePoint)) & 1)
        != 0;
}

这里 isWhitespace() 和 isSpaceChar() 的实现其实比较复杂，简单介绍一下其区别。

isWhiteSpace()符合下面条件的字符将会返回 true

It is a Unicode space character ({@code SPACE_SEPARATOR}, {@code LINE_SEPARATOR}, or {@code PARAGRAPH_SEPARATOR}) but is not also a non-breaking space ({@code '\u005Cu00A0'}, {@code '\u005Cu2007'}, {@code '\u005Cu202F'}).

It is {@code '\u005Ct'}, U+0009 HORIZONTAL TABULATION.

It is {@code '\u005Cn'}, U+000A LINE FEED.

It is {@code '\u005Cu000B'}, U+000B VERTICAL TABULATION.

It is {@code '\u005Cf'}, U+000C FORM FEED.

It is {@code '\u005Cr'}, U+000D CARRIAGE RETURN.

It is {@code '\u005Cu001C'}, U+001C FILE SEPARATOR.

It is {@code '\u005Cu001D'}, U+001D GROUP SEPARATOR.

It is {@code '\u005Cu001E'}, U+001E RECORD SEPARATOR.

It is {@code '\u005Cu001F'}, U+001F UNIT SEPARATOR.

isSpaceChar()用于检查Unicodei分割符和空格，参考Unicode控制字符,分割符号包括

U+2028 line separator ，HTML： ，LSEP

U+2029 paragraph separator ，HTML： ，PSEP

总结

在 java 中和 kotlin 中，因为 trim 方法中使用到的匹配规则不一样，所以他们对同一个串进行处理之后，结果可能也是不一样的。所以为了保险起见，建议不要使用分别用 java 和 kotlin 语言 trim 之后的字符串在进行比较，可能会得有意料之外的结果。

参考链接

ConcurrentHashMap 详解

发表于 2020-05-17 更新于 2020-07-18 分类于 java

问题：

使用 Hashmap 进行 put 操作会引起死循环，导致CPU利用率接近100%，所以在并发情况下不能使用HashMap。
为什么会发生死循环？应该如何避免？

void transfer(Entry[] newTable, boolean rehash) {
         int newCapacity = newTable.length;
         for (Entry<K,V> e : table) {
             while(null != e) {
                 Entry<K,V> next = e.next;
                 if (rehash) {
                     e.hash = null == e.key ? 0 : hash(e.key);
                 }
                 int i = indexFor(e.hash, newCapacity);
                 e.next = newTable[i];
                 newTable[i] = e;
                 e = next;
             }
         }
     }

在多线程环境下，reset 方法中的 trasnsfer 函数中的复制，可能会导致链表成环。
因为在 while 循环中，会通过头插法，反序当前链表的顺序，在执行过程中可能会被另外一个线程错误的赋值，从而导致死循环。

HashTable 利用synchronized关键字来证原子性，但是效率差。
效率为什么会会差
答：因为所有访问HashTable的线程都必须竞争同一把锁
JDK 8 中ConcurrentHashMap 是怎么保证多线程的效率的呢？
答：通过 CAS 原子锁 + node + sync 来保证。
JDK 7 ConcurrentHashMap实现远离
答：segment 分段锁，size（）这类全局都需要锁住的元素会先按顺序获取分段锁，如果获取失败，在重试两次后，会获取全局 synchronized 锁。

Z 字形变换

发表于 2018-11-21 更新于 2020-04-12 分类于 algorithm

Z 字形变换

题目描述

将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 “LEETCODEISHIRING” 行数为 3 时，排列如下：

1
2
3

L   C   I   R
E T O E S I I G
E   D   H   N

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);
示例 1:

输入: s = “LEETCODEISHIRING”, numRows = 3
输出: “LCIRETOESIIGEDHN”
示例 2:

输入: s ="LEETCODEISHIRING", numRows = 4
输出: “LDREOEIIECIHNTSG”
解释:

L     D     R
E   O E   I I
E C   I H   N
T     S     G

解题思路

思路

通过从左向右迭代字符串，我们可以轻松地确定字符位于 Z 字形图案中的哪一行。

算法

我们可以使用 \text{min}( \text{numRows}, \text{len}(s))min(numRows,len(s)) 个列表来表示 Z 字形图案中的非空行。

从左到右迭代 ss，将每个字符添加到合适的行。可以使用当前行和当前方向这两个变量对合适的行进行跟踪。

只有当我们向上移动到最上面的行或向下移动到最下面的行时，当前方向才会发生改变。

##代码

public String convert(String s, int numRows) {
       if(numRows == 1){
           return s;
       }

       List<StringBuffer> list = new ArrayList<>();
       // 初始化数组
       for (int i = 0; i < Math.min(numRows, s.length()); i++) {
           list.add(new StringBuffer());
       }

       int row = 0;
       boolean isAdd = true;
       for (char c : s.toCharArray()) {
           list.get(row).append(c);
           if (isAdd){
               row++;
               if (row >= numRows-1){
                   isAdd = false;
               }
           } else{
               row--;
               if (row <= 0){
                   isAdd = true;
               }
           }
       }

       StringBuffer sb = new StringBuffer();
       for (StringBuffer stringBuffer : list) {
           sb.append(stringBuffer);
       }
       return sb.toString();
   }

无重复字符的最长子串

发表于 2018-11-19 更新于 2020-04-12 分类于 algorithm

无重复字符的最长子串

文章转载自https://leetcode-cn.com/articles/longest-substring-without-repeating-characters/

给定一个字符串，请你找出其中不含有重复字符的 *最长子串 *的长度。

示例 1:

输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是子串的长度，"pwke" 是一个_子序列，_不是子串。

解决方案

解决方案

方法一：暴力法

思路

逐个检查所有的子字符串，看它是否不含有重复的字符。

算法

假设我们有一个函数 boolean allUnique(String substring) ，如果子字符串中的字符都是唯一的，它会返回true，否则会返回false。我们可以遍历给定字符串 s 的所有可能的子字符串并调用函数 allUnique。如果事实证明返回值为true，那么我们将会更新无重复字符子串的最大长度的答案。

现在让我们填补缺少的部分：

为了枚举给定字符串的所有子字符串，我们需要枚举它们开始和结束的索引。假设开始和结束的索引分别为 iii 和 jjj。那么我们有 0≤i<j≤n0 \leq i \lt j \leq n0≤i<j≤n （这里的结束索引 jjj 是按惯例排除的）。因此，使用 iii 从0到 n−1n - 1n−1 以及 jjj 从 i+1i+1i+1 到 nnn 这两个嵌套的循环，我们可以枚举出 s 的所有子字符串。
要检查一个字符串是否有重复字符，我们可以使用集合。我们遍历字符串中的所有字符，并将它们逐个放入 set 中。在放置一个字符之前，我们检查该集合是否已经包含它。如果包含，我们会返回 false。循环结束后，我们返回 true。

复杂度分析

时间复杂度：O(n3)O(n^3)O(n3) 。

要验证索引范围在 [i,j)[i, j)[i,j) 内的字符是否都是唯一的，我们需要检查该范围中的所有字符。因此，它将花费 O(j−i)O(j - i)O(j−i) 的时间。

对于给定的 i，对于所有 j∈[i+1,n]j \in [i+1, n]j∈[i+1,n] 所耗费的时间总和为：

∑i+1nO(j−i) \sum_{i+1}^{n}O(j - i) i+1∑nO(j−i)

因此，执行所有步骤耗去的时间总和为：

O(∑i=0n−1(∑j=i+1n(j−i)))=O(∑i=0n−1(1+n−i)(n−i)2)=O(n3) O\left(\sum_{i = 0}^{n - 1}\left(\sum_{j = i + 1}^{n}(j - i)\right)\right) = O\left(\sum_{i = 0}^{n - 1}\frac{(1 + n - i)(n - i)}{2}\right) = O(n^3) O(i=0∑n−1(j=i+1∑n(j−i)))=O(i=0∑n−12(1+n−i)(n−i))=O(n3)
空间复杂度：O(min(n,m))O(min(n, m))O(min(n,m))，我们需要 O(k)O(k)O(k) 的空间来检查子字符串中是否有重复字符，其中 kkk 表示 Set 的大小。而 Set 的大小取决于字符串 nnn 的大小以及字符集/字母 mmm 的大小。

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int ans = 0;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j <= n; j++)
                if (allUnique(s, i, j)) ans = Math.max(ans, j - i);
        return ans;
    }

    public boolean allUnique(String s, int start, int end) {
        Set<Character> set = new HashSet<>();
        for (int i = start; i < end; i++) {
            Character ch = s.charAt(i);
            if (set.contains(ch)) return false;
            set.add(ch);
        }
        return true;
    }
}

方法二：滑动窗口

算法

暴力法非常简单。但它太慢了。那么我们该如何优化它呢？

在暴力法中，我们会反复检查一个子字符串是否含有有重复的字符，但这是没有必要的。如果从索引 iii 到 j−1j - 1j−1 之间的子字符串 sijs_{ij}sij 已经被检查为没有重复字符。我们只需要检查 s[j]s[j]s[j] 对应的字符是否已经存在于子字符串 sijs_{ij}sij 中。

要检查一个字符是否已经在子字符串中，我们可以检查整个子字符串，这将产生一个复杂度为 O(n2)O(n^2)O(n2) 的算法，但我们可以做得更好。

通过使用 HashSet 作为滑动窗口，我们可以用 O(1)O(1)O(1) 的时间来完成对字符是否在当前的子字符串中的检查。

滑动窗口是数组/字符串问题中常用的抽象概念。窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合，即 [i,j)[i, j)[i,j)（左闭，右开）。而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。例如，我们将 [i,j)[i, j)[i,j) 向右滑动 111 个元素，则它将变为 [i+1,j+1)[i+1, j+1)[i+1,j+1)（左闭，右开）。

回到我们的问题，我们使用 HashSet 将字符存储在当前窗口 [i,j)[i, j)[i,j)（最初 j=ij = ij=i）中。然后我们向右侧滑动索引 jjj，如果它不在 HashSet 中，我们会继续滑动 jjj。直到 s[j] 已经存在于 HashSet 中。此时，我们找到的没有重复字符的最长子字符串将会以索引 iii 开头。如果我们对所有的 iii 这样做，就可以得到答案。

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        Set<Character> set = new HashSet<>();
        int ans = 0, i = 0, j = 0;
        while (i < n && j < n) {
            // try to extend the range [i, j]
            if (!set.contains(s.charAt(j))){
                set.add(s.charAt(j++));
                ans = Math.max(ans, j - i);
            }
            else {
                set.remove(s.charAt(i++));
            }
        }
        return ans;
    }
}

复杂度分析

时间复杂度：O(2n)=O(n)O(2n) = O(n)O(2n)=O(n)，在最糟糕的情况下，每个字符将被 iii 和 jjj 访问两次。
空间复杂度：O(min(m,n))O(min(m, n))O(min(m,n))，与之前的方法相同。滑动窗口法需要 O(k)O(k)O(k) 的空间，其中 kkk 表示 Set 的大小。而Set的大小取决于字符串 nnn 的大小以及字符集/字母 mmm 的大小。

方法三：优化的滑动窗口

上述的方法最多需要执行 2n 个步骤。事实上，它可以被进一步优化为仅需要 n 个步骤。我们可以定义字符到索引的映射，而不是使用集合来判断一个字符是否存在。当我们找到重复的字符时，我们可以立即跳过该窗口。

也就是说，如果 s[j]s[j]s[j] 在 [i,j)[i, j)[i,j) 范围内有与 j′j'j′ 重复的字符，我们不需要逐渐增加 iii 。我们可以直接跳过 [i，j′][i，j'][i，j′] 范围内的所有元素，并将 iii 变为 j′+1j' + 1j′+1。

Java（使用 HashMap）

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>(); // current index of character
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; j++) {
            if (map.containsKey(s.charAt(j))) {
                i = Math.max(map.get(s.charAt(j)), i);
            }
            ans = Math.max(ans, j - i + 1);
            map.put(s.charAt(j), j + 1);
        }
        return ans;
    }
}

Java（假设字符集为 ASCII 128）

以前的我们都没有对字符串 s 所使用的字符集进行假设。

当我们知道该字符集比较小的时侯，我们可以用一个整数数组作为直接访问表来替换 Map。

常用的表如下所示：

int [26] 用于字母 ‘a’ - ‘z’或 ‘A’ - ‘Z’
int [128] 用于ASCII码
int [256] 用于扩展ASCII码

复杂度分析

时间复杂度：O(n)O(n)O(n)，索引 jjj 将会迭代 nnn 次。
空间复杂度（HashMap）：O(min(m,n))O(min(m, n))O(min(m,n))，与之前的方法相同。
空间复杂度（Table）：O(m)O(m)O(m)，mmm 是字符集的大小。

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        int[] index = new int[128]; // current index of character
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; j++) {
            i = Math.max(index[s.charAt(j)], i);
            ans = Math.max(ans, j - i + 1);
            index[s.charAt(j)] = j + 1;
        }
        return ans;
    }
}

两个数组的交集

发表于 2018-11-14 更新于 2020-04-12 分类于 algorithm

两个数组的交集

难度简单

给定两个数组，编写一个函数来计算它们的交集。

示例 1:

1 2	输入: nums1 = [1,2,2,1], nums2 = [2,2] 输出: [2]

示例 2:

1 2	输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出: [9,4]

说明:

输出结果中的每个元素一定是唯一的。
我们可以不考虑输出结果的顺序。

Solution

解题思路
计算数组间的交集，最简单的方式肯定是使用Set集合来做。我们将num1数组的数据添加到一个Set集合set中，然后遍历num2数据，只要num2数组有与set相同的数，就认为这个是相同的数，添加到另外一个Set集合res中，最终，res中所有的数据就是我们要返回的数据，将其转化成数组返回即可。

Language: Java

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
         if (nums1 == null || nums1.length ==0 || nums2 == null || nums2.length == 0){
            return new int[0];
        }
        Set<Integer> set = new HashSet<>();
        Set<Integer> res = new HashSet<>();
        for (int i = 0; i < nums1.length; i++) {
            set.add(nums1[i]);
        }
        for (int i = 0; i < nums2.length; i++) {
            if (set.contains(nums2[i])){
                res.add(nums2[i]);
            }
        }
        int num[] = new int[res.size()];
        int i = 0;
        for (Iterator it = res.iterator(); it.hasNext();){
            num[i++] = (int) it.next();
        }
        return num;
    }
}

Nim游戏

发表于 2018-11-13 更新于 2020-04-12 分类于 algorithm

Nim游戏

难度简单

你和你的朋友，两个人一起玩：桌子上有一堆石头，每次你们轮流拿掉 1 - 3 块石头。拿掉最后一块石头的人就是获胜者。你作为先手。

你们是聪明人，每一步都是最优解。编写一个函数，来判断你是否可以在给定石头数量的情况下赢得游戏。

示例:

**输入:** `4`
**输出:** false 
**解释:** 如果堆中有 4 块石头，那么你永远不会赢得比赛；
     因为无论你拿走 1 块、2 块 还是 3 块石头，最后一块石头总是会被你的朋友拿走。

结题思路

简单的罗列一下1-12个石子的情况，发现只有4的倍数才是false。

Solution

Language: Java

class Solution {
    public boolean canWinNim(int n) {
          return n%4!=0;
    }
}

方式论

发表于 2018-11-12 更新于 2020-07-18 分类于方法论

解bug思路

了解主流程，把握主要逻辑
按照现有流程思路，一步一步排查问题
主要主要问题，结合其实现，寻求解决方案
思考为什么会出现这种问题，思考如何避免再次出现这种问题。

注意排查bug最关键的地方可能就是，找不到bug的关键点在哪，这个时候要注意的是，我们可以先按照自己的思路去寻找其实现，当发现我们的思路和程序实现的思路不同时，我们不能再按照我们的思路，而是应该及时修正，按照程序的实现思路去走。并思考要这样实现，与我们设想的思路有什么差别，我们设想的思路可能会有哪些问题。

总的方法论：
目标、方法、资源、路径。

我们需要指定好合适的目标；指定的目标不能过高，即使自己再怎么努力也达不到要求，目标也不能过低，导致自己不需要努力也能达到。还有目标一定要量化，一定要细化，一定要可评估话。
例如，我的下一个目标是xx需求在一天内完成，这样的目标就比较适合，但是如果我的目标是开发能力提高10%，其实这样的目标就不是很好评估到底有没有完成。
在指定好合适的目标之后，我们需要通过合适的方法，适当的渠道去实现他。譬如xx需求在一天内完成这个目标的实现，我们就需要先分析当前这个需求，并确保自己的理解和要求是一致的，然后选择技术方案，最后开始实现，而不是一昧的上手就是干，一昧的上手就是干反而很难如愿按时完成。
大部分情况下，我们的目标仅仅靠我们自己本身的努力是不能完成的，这个时候我们就应该主动寻找合适的资源去协助我们完成目标。还是以xx需求在一天内完成这个目标为例，我们可能需要UI资源、或者服务端资源，或者其他的资源，这个时候我们就应该需要主动的去寻找这些资源，为自己的目标铺路。
当有了方法和资源之后，我们就只需要寻找一条通向目标的路径了。当然，这个寻找的过程可能需要经验的积累，但是相信，在成长的路上，我们一定会找到适合自己通向目标的路径的。

方法论：先钻深度、后拓广度。