Copyright © 2015 Powered by MWeb, Theme used GitHub CSS.
给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
**注意：**两个节点之间的路径长度由它们之间的边数表示。
示例 1:
输入:
5
/ \
4 5
/ \ \
1 1 5
输出 \(2\)
示例 2:
输入:
1
/ \
4 5
/ \ \
4 4 5
输出: \(2\)
注意: 给定的二叉树不超过\(10000\)个结点。 树的高度不超过\(1000\)。
基本想法就是深度优先遍历。遍历时，判断左右儿子的值与自己的值是否相等，相等则result++，否则置为0即可。没有什么难度。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private int result = 0;
public int longestUnivaluePath(TreeNode root) {
if (root != null) {
dfs(root);
}
return result;
}
private int dfs(TreeNode root) {
if (root ==null) {
return 0;
}
//计算左子树的同值路径
int left = dfs(root.left);
//判断左儿子与自己的值是否相等，相等则++ 否则置为0
if (root.left == null || root.val !=root.left.val) {
left = 0;
} else {
left ++;
}
//计算右子树的同值路径
int right = dfs(root.right);
//同左儿子的判断
if (root.right == null || root.val !=root.right.val) {
right = 0;
} else {
right ++;
}
//需要注意的是这里的max为left+right与result的判断。
result = Math.max(left + right,result);
return Math.max(left, right);
}
}
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。
示例 :
给定二叉树
digraph G {
{
node [margin=0 width=0.1 shape=circle style=filled]
1 -> 2 [arrowhead=none]
1 -> 3 [arrowhead=none]
2 -> 4 [arrowhead=none]
2 -> 5 [arrowhead=none]
}
}
返回\(3\),它的长度是路径 \([4,2,1,3]\) 或者 \([5,2,1,3]\)。
**注意：**两结点之间的路径长度是以它们之间边的数目表示。
此题是二叉树深度搜索的扩展，考虑设置一个全局变量result，每次递归时判断一次左子树深度+右子树深度 是否大于result，如果大于，那么将result替换成和，递归完成时，返回result即可。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private int result = 0;
public int diameterOfBinaryTree(TreeNode root) {
// 深度优先遍历+判断一次result大小即可。
dfs(root);
return result;
}
private int dfs(TreeNode root) {
if (root == null) {
return 0;
}
//递归左子树
int right = dfs(root.right);
//递归右子树
int left = dfs(root.left);
//左子树深度+右子树深度就是走过当前节点的直径长度
if (left + right > result) {
result = left + right;
}
//返回当前节点深度+1.递归到上一层参与计算
return Math.max(left, right) + 1;
}
}
在阅读Dubbo源码时发现Dubbo针对java的spi机制做了扩展。那么spi究竟是什么呢？
SPI全称为Service Provider Interface，是Java提供的用来加载第三方实现的service的API。
比如java.sql.Driver接口，第三方厂商比如MySql，PostgreSql均会实现这个接口来提供接入数据库的实现，Java的SPI机制就可以某个接口寻找服务实现。
当服务提供者实现了一种接口后，需要在classpath的META-INF/services中创建一个以服务接口名命名的文件，文件的内容是这个接口的具体实现类。当调用者需要用到这个服务时，就会查找对应jar包下的META-INF/services中的配置，如果找到了，那么就会实例化这个实现类，调用者就可以调用对应的服务了。Java中，查找实现类的工具类是java.util.ServiceLoader。
接下来我们自己实现一个简单的SPI服务，从中可以学习到SPI的机制。
People的interface,提供一个hello的方法
Jack与Jenny为People的实现module，各自继承People接口，并实现自己的代码逻辑，本例为了简单只是单纯的输出了各自的名字,如下所示:
META-INF/services文件夹，并且在该文件夹下创建一个名为io.wkz.People的文件，文件内容分别为Jack与Jenny的全限定名。其结构如下：
ServiceLodaer加载People的实现类，并且分别调用hello方法，如下所示：
观察main函数会发现，我们并没有在main函数下实例化Jack或Jenny,但是我们在调用服务时，仍然调用到了这两个类的实例。从这里可以发现，SPI的核心思想其实就是解耦。
既然在上一个例子里我们是使用的ServiceLoader来获取不同的服务提供者，那么我们就进入ServiceLoader源码探索一番吧。
首先查看一下ServiceLoader的属性字段
public final class ServiceLoader<S>
implements Iterable<S>
{
//看属性名可知此字段就是查找配置文件的前缀文件夹名，从这里也了解了为什么必须要在META-INF/services下新增配置文件。
private static final String PREFIX = "META-INF/services/";
// 代表被加载的类或者接口
private final Class<S> service;
// 类加载器，用于加载并实例化服务
private final ClassLoader loader;
// 创建ServiceLoader时采用的访问控制上下文
private final AccessControlContext acc;
// 实例化后的服务缓存，用的是LinkedHashMap，所以是按顺序排列的，具体排列顺序是按实例化的先后顺序
private LinkedHashMap<String,S> providers = new LinkedHashMap<>();
// 迭代器，Lazy代表是懒的
private LazyIterator lookupIterator;
...
}
属性字段上比较简单，接下来我们看一下ServiceLoader.load方法，跟踪代码发现其最终是实例化了一个ServiceLoader类并返回。继续进入构造方法
private ServiceLoader(Class<S> svc, ClassLoader cl) {
service = Objects.requireNonNull(svc, "Service interface cannot be null");
loader = (cl == null) ? ClassLoader.getSystemClassLoader() : cl;
acc = (System.getSecurityManager() != null) ? AccessController.getContext() : null;
reload();
}
构造函数里前面三行属于防御式编程，将null处理掉，要么报错，要么设置默认值。最后一行的reload方法是清空providers，并且实例化一个LazyIterator用于后期迭代。
LazyIterator也比较简单，看名字就是实现了Iterator接口的。比较关键的方法是nextService
private S nextService() {
//防御式编程
if (!hasNextService())
throw new NoSuchElementException();
//nextName是在hasNextService方法中赋值的，这里获取到就置空
String cn = nextName;
nextName = null;
Class<?> c = null;
try {
//使用当前的ClassLoader加载类
c = Class.forName(cn, false, loader);
} catch (ClassNotFoundException x) {
//加载失败，抛错。
fail(service,
"Provider " + cn + " not found");
}
//判断加载的类是不是当前service的子类或者实现类。
if (!service.isAssignableFrom(c)) {
fail(service,
"Provider " + cn + " not a subtype");
}
try {
//实例化类。注意这里，这步表明我们实现的service必须要有一个无参构造函数
S p = service.cast(c.newInstance());
//进行缓存。这里可以看ServiceLoader的Iterator实现。是先判断的providers是不是hasNext，如果不是，则进入到本LazyIterator中，从一定程度上解决了创建时就加载全部实现类的问题，但是并没有治本。
providers.put(cn, p);
return p;
} catch (Throwable x) {
fail(service,
"Provider " + cn + " could not be instantiated",
x);
}
//防御式编程
throw new Error(); // This cannot happen
}
从代码层面上看，我们可以得出几点结论：
Java提供的SPI机制，优势在于解耦，调用方不需要明确耦合第三方实现类，而是交由ServiceLoader提供。当程序需要使用另一种第三方实现类时，直接替换依赖就可以，无需重构代码。
缺点其实在上面说到了。这里就不赘述了。Dubbo其实也是针对这些默认SPI的缺点才自己实现了Dubbo SPI。
面试时，很多人都会被问到关于ThreadLocal的内容，如果没有看过ThreadLocal相关的代码的话，关于这方面的面试题都会回答的很混乱。今天，我们就从ThreadLocal的源代码入手，来彻底解开ThreadLocal的原理。
我们知道，看java的源码时，一般都是先去看一个类上面的注释，类上的注释会表明该类是用来做什么的。下面节选一部分ThreadLocal的类注释：
/**
* This class provides thread-local variables. These variables differ from
* their normal counterparts in that each thread that accesses one (via its
* {@code get} or {@code set} method) has its own, independently initialized
* copy of the variable. {@code ThreadLocal} instances are typically private
* static fields in classes that wish to associate state with a thread (e.g.,
* a user ID or Transaction ID).
*/
翻译过来的意思就是：
该类提供了线程局部 (thread-local) 变量。这些变量不同于它们的普通对应物，因为访问某个变量（通过其get 或 set方法）的每个线程都有自己的局部变量，它独立于变量的初始化副本。ThreadLocal实例通常是类中的 private static 字段，它们希望将状态与某一个线程（例如，用户 ID 或事务 ID）相关联。
很多人以为ThreadLocal是用来解决线程同步的问题的，其实这是非常大的误解。ThreadLocal虽然提供了一种多线程下成员变量问题的解决方式，但是它并不是用来解决多线程共享变量问题的。线程同步机制是多个线程共享同一个成员变量，而ThreadLocal是为每一个线程创建独立的变量，每一个线程都可以独立的修改自己的变量而不需要担心会修改其他线程的变量。
ThreadLocal常用的一共有4种方法
public T get() 返回此线程局部变量的当前线程副本中的值。public void set(T value) 将此线程局部变量的当前线程副本中的值设置为指定值。public void remove() 移除此线程局部变量当前线程的值。private T setInitialValue() 返回此线程局部变量的当前线程的“初始值”。同时，ThreadLocal下有一个内部类叫做ThreadLocal.ThreadLocalMap，这个类才是实现线程隔离机制的核心，上面的get set remove最终操作的数据结构都是该内部类。看ThreadLocalMap的名字也能大概猜出该类是基于键值对的方式存储的，key是当前的ThreadLocal实例，value是对应线程的变量副本。
所以从上面的说明来看，我们可以得出如下两个结论
下图是两者的关系
public class SeqCount {
private static ThreadLocal<Integer> seqCount = new ThreadLocal<Integer>(){
// 实现initialValue()
public Integer initialValue() {
return 0;
}
};
public int nextSeq(){
seqCount.set(seqCount.get() + 1);
return seqCount.get();
}
public static void main(String[] args){
SeqCount seqCount = new SeqCount();
SeqThread thread1 = new SeqThread(seqCount);
SeqThread thread2 = new SeqThread(seqCount);
SeqThread thread3 = new SeqThread(seqCount);
SeqThread thread4 = new SeqThread(seqCount);
thread1.start();
thread2.start();
thread3.start();
thread4.start();
}
private static class SeqThread extends Thread{
private SeqCount seqCount;
SeqThread(SeqCount seqCount){
this.seqCount = seqCount;
}
public void run() {
for(int i = 0 ; i < 3 ; i++){
System.out.println(Thread.currentThread().getName() + " seqCount :" + seqCount.nextSeq());
}
}
}
}
运行结果为
可以看到，三个线程是分别累加的自己的独立的数据，相互之间没有任何的干扰。
我们先从get方法入手
/**
* Returns the value in the current thread's copy of this
* thread-local variable. If the variable has no value for the
* current thread, it is first initialized to the value returned
* by an invocation of the {@link #initialValue} method.
*
* @return the current thread's value of this thread-local
*/
public T get() {
Thread t = Thread.currentThread();
ThreadLocalMap map = getMap(t);
if (map != null) {
ThreadLocalMap.Entry e = map.getEntry(this);
if (e != null) {
@SuppressWarnings("unchecked")
T result = (T)e.value;
return result;
}
}
return setInitialValue();
}
get方法流程是首先获取当前的线程t,然后通过getMap(t)获取到ThreadLocalMap实例map，如果map不为null，那么就通过map.getEntry获取ThreadLocalMap.Entry实例e，如果e不为null,那么就返回e.value,否则调用setInitialValue获取默认值。
getMap方法源码：
/**
* Get the map associated with a ThreadLocal. Overridden in
* InheritableThreadLocal.
*
* @param t the current thread
* @return the map
*/
ThreadLocalMap getMap(Thread t) {
return t.threadLocals;
}
可以看到方法只有一行，非常的简洁，就是返回了Thread实例t的threadLocals变量。那么这个变量又是什么呢？继续跟踪到Thread类的源码中，
/* ThreadLocal values pertaining to this thread. This map is maintained
* by the ThreadLocal class. */
ThreadLocal.ThreadLocalMap threadLocals = null;
就是一个ThreadLocal.ThreadLocalMap的实例，默认为null。
ThreadLocalMap内部利用Entry来实现键值对的存储，Entry的源码如下：
/**
* The entries in this hash map extend WeakReference, using
* its main ref field as the key (which is always a
* ThreadLocal object). Note that null keys (i.e. entry.get()
* == null) mean that the key is no longer referenced, so the
* entry can be expunged from table. Such entries are referred to
* as "stale entries" in the code that follows.
*/
static class Entry extends WeakReference<ThreadLocal<?>> {
/** The value associated with this ThreadLocal. */
Object value;
Entry(ThreadLocal<?> k, Object v) {
super(k);
value = v;
}
}
可以看到Entry是一个WeakReference弱引用，其key是ThreadLocal实例，关于弱引用这里不再赘述，可以参考其他文章。
ThreadLocalMap的方法比较多，我们着重介绍两个方法getEntry与set方法
/**
* Get the entry associated with key. This method
* itself handles only the fast path: a direct hit of existing
* key. It otherwise relays to getEntryAfterMiss. This is
* designed to maximize performance for direct hits, in part
* by making this method readily inlinable.
*
* @param key the thread local object
* @return the entry associated with key, or null if no such
*/
private Entry getEntry(ThreadLocal<?> key) {
//获取key的hash值，用于在table中查找对应的Entry
int i = key.threadLocalHashCode & (table.length - 1);
Entry e = table[i];
//当当前位置一次找到了对应的Entry，直接返回
if (e != null && e.get() == key)
return e;
else
//当当前位置为null或者当前位置存储的并不是要找的Entry时，进入此方法查找
return getEntryAfterMiss(key, i, e);
}
getEntry没有太大的难度，与HashMap.get的初始思路比较一致，都是先计算hash，然后去对应的位置查找。但是ThreadLocalMap与HashMap不一致的地方在于，HashMap针对hash碰撞所采用的方式是链表法（即，将所有hash冲突的元素保存在一个链表中），而ThreadLocalMap所采用的方式是开放定址法(即，当发现冲突时，遍历table到接下来的一个空位，将其存储在这里。)。读者可以思考一下为什么同是散列表的实现，为什么这两者要使用不同的hash冲突解决方式。
由于ThreadLocalMap使用的开放定址法，因此当查找不到时会调用getEntryAfterMiss方法，源码如下：
private Entry getEntryAfterMiss(ThreadLocal<?> key, int i, Entry e) {
Entry[] tab = table;
int len = tab.length;
while (e != null) {
ThreadLocal<?> k = e.get();
if (k == key)
return e;
if (k == null)
expungeStaleEntry(i);
else
i = nextIndex(i, len);
e = tab[i];
}
return null;
}
整体也没有难度，需要注意的一点是当遍历到k == null时，会调用expungeStaleEntry方法会rehash当前节点到下一个null节点之间的键值对，辅助gc。
/**
* Sets the current thread's copy of this thread-local variable
* to the specified value. Most subclasses will have no need to
* override this method, relying solely on the {@link #initialValue}
* method to set the values of thread-locals.
*
* @param value the value to be stored in the current thread's copy of
* this thread-local.
*/
public void set(T value) {
Thread t = Thread.currentThread();
ThreadLocalMap map = getMap(t);
if (map != null)
map.set(this, value);
else
createMap(t, value);
}
与get方法类似，也是先获取当前线程的ThreadLocalMap,当ThreadLocalMap不为null时，调用ThreadLocalMap.set方法保存；当ThreadLocalMap为null时，调用createMap方法初始化ThreadLocalMap实例，并写入一个键值对。ThreadLoalMap.set方法不多赘述，只要了解了开放定址法就很简单了。
/**
* Removes the current thread's value for this thread-local
* variable. If this thread-local variable is subsequently
* {@linkplain #get read} by the current thread, its value will be
* reinitialized by invoking its {@link #initialValue} method,
* unless its value is {@linkplain #set set} by the current thread
* in the interim. This may result in multiple invocations of the
* {@code initialValue} method in the current thread.
*
* @since 1.5
*/
public void remove() {
ThreadLocalMap m = getMap(Thread.currentThread());
if (m != null)
m.remove(this);
}
跟上面的set或get方法类似，只不过最后不需要考虑ThreadLocalMap为空的情况。
protected T initialValue() {
return null;
}
默认是返回null，我们可以根据业务不同设置不同的返回值即可。
前面提到每个Thread都有一个ThreadLocal.ThreadLocalMap的map，该map的key为ThreadLocal实例，它为一个弱引用，我们知道弱引用有利于GC回收。当ThreadLocal的key == null时，GC就会回收这部分空间，但是value却不一定能够被回收，因为他还与Current Thread存在一个强引用关系。
由于存在这个强引用关系，会导致value无法回收。如果这个线程对象不会销毁那么这个强引用关系则会一直存在，就会出现内存泄漏情况。所以说只要这个线程对象能够及时被GC回收，就不会出现内存泄漏。如果碰到线程池，那就更坑了。
那么要怎么避免这个问题呢？
在前面提过，在ThreadLocalMap中的setEntry()、getEntry()，如果遇到key == null的情况，会对value设置为null。当然我们也可以显示调用ThreadLocal的remove()方法进行处理。
给定一个非负整数数组 \(A\)， \(A \)中一半整数是奇数，一半整数是偶数。
对数组进行排序，以便当\(A[i]\)为奇数时，\(i \)也是奇数；当 \(A[i]\) 为偶数时，\(i\)也是偶数。
你可以返回任何满足上述条件的数组作为答案。
示例：
输入：\([4,2,5,7]\)
输出：\([4,5,2,7]\)
解释：\([4,7,2,5]，[2,5,4,7]，[2,7,4,5]\) 也会被接受。
提示：
2 <= A.length <= 20000
A.length % 2 == 0
0 <= A[i] <= 1000
这道题挺简单的。使用两个指针分别从索引位置\(0\)与\(1\)处前进即可，遇到不满足条件的地方就停止，然后交换两个索引的值，一直走下去就行了。解法也众多，不一而足。姑且写一个
class Solution {
public int[] sortArrayByParityII(int[] A) {
int i = 0, j = 1;
while (i < A.length - 1 && j < A.length) {
while (i < A.length - 1 && A[i]%2 == 0) {
i += 2;
}
while (j < A.length && A[j]%2 == 1) {
j += 2;
}
//这里需要注意的一点是这个if的存在，仔细观察对i的while循环，是可以因为i超过数组长度而跳出的。这里就是为了防止ArrayOutOfBound异常做的处理。
if (i < A.length - 1) {
int temp = A[i];
A[i] = A[j];
A[j] = temp;
i += 2;
j += 2;
}
}
return A;
}
}
给定一个按照升序排列的整数数组 \(nums\)，和一个目标值 \(target\)。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是\(O(log_n)\)级别。
如果数组中不存在目标值，返回 \([-1, -1]\)。
示例 1:
输入: \(nums = [5,7,7,8,8,10], target = 8\)
输出: \([3,4]\)
示例 2:
输入: \(nums = [5,7,7,8,8,10], target = 6\)
输出: \([-1,-1]\)
这个题乍一看就是二分查找的变种，考虑二分查找解决。
基本步骤如下：
使用二分法查找，假设\(start\)与\(end\)为数组起始位置与结束位置，有\(mid = (start + end)/2\)。此时，有三种情况会出现，我们首先排除掉\(nums[mid]!=target\)的两种情况：
class Solution {
public int[] searchRange(int[] nums, int target) {
int start = 0, end = nums.length - 1;
int[] result = new int[]{-1,-1};
while (start <= end) {
//首先需要二分法查询到nums[mid]==target的情况
int mid = (start + end)/2;
if (nums[mid] == target) {
int temp = mid;
while (start<mid) {
int ml = (start+mid)/2;
if (nums[ml] < target) {
start = ml+1;
} else {
mid = ml;
}
}
result[0] = start;
mid = temp;
while (mid < end) {
int mr = (end + mid)/2 + 1;
if (nums[mr] >target) {
end = mr -1;
} else {
mid = mr;
}
}
result[1] = end;
return result;
} else if (nums[mid] < target) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return result;
}
}
给定一个正整数数组 \(nums\)。
找出该数组内乘积小于 \(k\) 的连续的子数组的个数。
示例 1:
输入: \(nums = [10,5,2,6], k = 100\)
输出: \(8\)
解释: \(8\)个乘积小于\(100\)的子数组分别为: \([10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]\)。
需要注意的是 \([10,5,2]\) 并不是乘积小于100的子数组。
说明:
第一想法是使用双指针一直乘，当结果小于\(k\)时，将\(fast\)指针与\(slow\)指针之间的子数组数量加到结果\(result\)中。但是难点在于如何排重。
我们会注意到这样一种规律：
此时会发现，\(fast\)与\(fast-1\)子数组的区别仅在于是否包含\(nums[fast]\)元素，而包含全部\(nums[fast]\)元素的子数组数量为\(fast-slow+1\)，这个值，就排除了重复的子数组，\(result\)对这个数字进行暂存就可以在循环结束后直接得到数组数量。
可能说的有些乱，下面给出一个例子，\([1,2,3]\)数组，当\(slow=0,fast=2\)时，此时,全部的子数组为\([1],[2],[1,2]\)，当\(slow=0,fast=3\)时，此时的子数组为\([1],[2],[1,2],[1,2,3],[2,3],[3]\)，对比两个子数组可以发现，两者的区别就在于多了包含\(fast\)的元素的数组。
当乘积不满足条件时，乘积除以\(slow\)指针元素，\(slow\)指针前进，
class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
// slow为慢指针，mul为slow与fast之间的乘积，result为满足条件的数组个数.
int slow = 0, mul = 1, result = 0;
for (int fast = 0; fast < nums.length; fast++) {
// fast指针前移，mul计算新的乘积。
mul *= nums[fast];
//此时判断mul是否已经大于k了，当大于时，需要除slow元素直到满足条件为止
while (mul >= k && slow <= fast) {
mul /= nums[slow++];
}
//这里可能会有疑问需不需要判断slow与fast的大小，其实这里不需要判断，前一步如果slow超过fast了，下一轮时，fast会赶上来。而且slow最多比fast多1，两者相减再加一等于0，符合数组数量为0，不用担心减成负数
result += fast - slow + 1;
}
return result;
}
}
给定一个含有 \(n\) 个正整数的数组和一个正整数 \(s \)，找出该数组中满足其和 \(≥ s \)的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回\( 0\)。
示例:
输入: \(s = 7, nums = [2,3,1,2,4,3]\)
输出: \(2\)
解释: 子数组 \([4,3]\) 是该条件下的长度最小的连续子数组。
进阶:
如果你已经完成了\(O(n)\) 时间复杂度的解法, 请尝试\( O(n log n)\) 时间复杂度的解法。
连续子数组，考虑使用双指针\(start\)与\(end\)滑动窗口来判断.设置一个\(sum\)值，表示滑动窗口中的和，每一轮循环，判断\(sum\)与\(s\)的关系，有两种情况：
class Solution {
public int minSubArrayLen(int s, int[] nums) {
// 注意这里的end的起始位置
int start = 0, end = -1;
int result = Integer.MAX_VALUE, sum = 0;
// 开始循环，循环跳出的条件是start指针循环到数组尾部了
while (start < nums.length) {
// 这里需要注意判断条件
if (sum < s && end + < nums.length) {
end++;
sum += nums[end];
} else {
sum -= nums[start];
start++;
}
if (sum >= s) result = result < end - start + 1 ? result : end - start + 1;
}
return result == Integer.MAX_VALUE ? 0 : result;
}
}
给定两个字符串 \(s1 \)和 \(s2\)，写一个函数来判断 \(s2\) 是否包含 \(s1\) 的排列。
换句话说，第一个字符串的排列之一是第二个字符串的子串。
示例1:
输入: \(s1 = "ab" s2 = "eidbaooo"\)
输出: \(True\)
解释: \(s2\) 包含 \(s1\) 的排列之一 \(("ba")\).
示例2:
输入: \(s1= "ab" s2 = "eidboaoo"\)
输出: \(False\)
注意：
题目乍一看似乎没什么好办法，暴力遍历总是行得通。但是时间复杂度嘛，嘿嘿。
接下来深挖一下题目，既然是判断\(s2\)是否包含\(s1\)，那么我们总是可以排除一些明显不满足条件的地方：
接下来，我们假设\(s2\)中有\(s1\)的排列\(a\)，那么这个排列\(a\)的长度肯定是\(s1\)的长度\(length\)，实际上就是判断这两个字符串不管字母顺序是否相同，
判断两个字符串是否相同可以用一个长度为26的数组，遍历第一个，将字母出现的次数记下来，然后遍历另一个字符串将数组中字母出现的次数减小一，当次数减小到-1时，代表不相同，直接返回false。当遍历完仍然没有返回时，那么两个字符串肯定是相同的。
我们可以设置两个指针，一个起始指针\(start\)，一个结束指针\(end\)，并且有\(end = start +length - 1\)。此时，从\(end\)指针处往回判断。至于为什么从\(end\)处往回走而不是从\(start\)处往前走是因为，我们注意到这样一种情况，当\(end\)处的字符在数组中出现次数已经减到0时，\(end\)处的字符必然不在排列\(a\)中，此时，\(start\)可以直接跳到\(end+1\)处，可以直接过滤掉部分字符。这样也就不用遍历必然失败的场景了。
class Solution {
public boolean checkInclusion(String s1, String s2) {
// 特殊情况直接跳出
if (s1 == null || s2 == null || s2.length() < s1.length()) {
return false;
}
// 初始化一个数组，将s1的字母出现次数保存在这个数组中去。
int[] map = new int[26];
int length = s1.length();
//遍历s1放入map
for (int i = 0; i < length; i++) {
map[s1.charAt(i) - 'a']++;
}
//遍历s2，此时注意到这样一个情况，如果s2包含s1，那么s2子串的长度必然等于s1，因此，可以设置两个指针。
int start = 0, end = length - 1;
while (end < s2.length()) {
// 这里是一个注意点，需要注意不能直接用map处理，否则会导致第一次false后，后面的判断全是false
int[] temp = map.clone();
while (end >= start) {
if (temp[s2.charAt(end) - 'a']-- == 0) {
break;
}
end--;
}
//上一层有两种跳出方式，一种break；一种是正确判断完了。需要区分一下。
if (end < start) {
//这种是正常判断完成了。直接返回true
return true;
} else {
//此时注意到这样一种情况，end处必然不能在s2子串中出现。那么start = end+1,end = start+length-1 可以跳过start与end之间的字符，因为这部分字符必然不满足条件。
start = end + 1;
end = start + length - 1;
}
}
return false;
}
}
编写一个函数，其作用是将输入的字符串反转过来。
示例 1:
输入: "hello"
输出: "olleh"
示例 2:
输入: "A man, a plan, a canal: Panama"
输出: "amanaP :lanac a ,nalp a ,nam A"
使用双指针分别从字符串开始位置转到字符串结束位置就可以了。整体没有难度。
class Solution {
public String reverseString(String s) {
char[] chars = s.toCharArray();
int start= 0, end = chars.length - 1;
while (start < end) {
char temp = chars[start];
chars[start++] = chars[end];
chars[end--] = temp;
}
return String.valueOf(chars);
}
}
Copyright © 2015 Powered by MWeb, Theme used GitHub CSS.