posted in 分布式系统  译文  Redis 

译文,原文链接
分布式锁是一种非常有功的工具来帮助我们处理多进程环境下不同进程必须独占式的操作共享资源的需求。
已经有非常多的库与博客文章分别实现与描述了如何使用Redi实现一个分布式锁管理工具(DLM),但是这些库与文章使用了不同的实现方式,很多实现方式有着较低的可靠性,其他的实现方式又较为复杂。
本文章将试着提供一种使用Redis实现分布式锁的更为通用的算法。我们提出名为红锁(RedLock)的算法,我们认为该算法将会比使用单一Redis实例实现的算法更为安全。我们希望Redis社区可以分析该算法,提供试用反馈,并且将其作为更复杂或其他实现的起点。

实现

在我们介绍算法前,现在已经有一些实现可以作为参考了。

安全性与可用性保证

我们将会使用三个属性来对我们的设计做定性,在我们看来,这三个属性是分布式锁所需的最基本的属性。

  1. 安全性:互斥。在任意时间,只有一个客户端可以持有一个锁。
  2. 可用性A:无死锁。最终所有客户端都有机会获得锁,即使目前已经获得锁的客户端宕机或者发生了网络分区。
  3. 可用性B:容错性。只要大部分的Redis节点在运行,客户端就可以获取与释放锁。

为什么只有故障转移的实现是不够的

为了理解我们需要提升什么,我们先分析一下当前大部分使用Redis实现的分布式锁的库的现状。
使用Redis实现锁的最简单的方式是在一个Redis实例中创建一个key。这个key通常会附带有一个存活时间,通过Redis的过期策略实现,因此锁最终会被释放(上面提到的属性2)。当需要释放资源时,客户端会删除掉这个key。
表面上看这个算法可以很好的工作,但是仍然是有这么一个问题:在系统架构中存在一个单点gu故障问题。如果Redis主节点宕机会发生什么?好吧,我们可以加一个从节点!并且当主节点宕机时使用该节点。但不幸的是,这并不可行。使用这种方式(注:即主从切换)我们无法保证互斥的这一安全性条件,因为Redis的主从复制是异步操作。
这里有一个非常明显的竟态条件在这种模型中:

  1. 客户端A在主节点上获取到锁
  2. 主节点宕机,宕机前没有将key传输到从节点上
  3. 从节点提升为主节点
  4. 客户端B获取到了客户端A已经持有的同一把锁。违反了安全性!

在某些特殊情况下,比如系统故障时,多个客户端同时持有一把锁是可以被接受的。如果是这种情况,完全可以使用主从复制的解决方案来实现分布式锁。否则,我们建议使用在本文中介绍的解决方案。

正确使用单实例实现分布式锁

在我们试着解决上面提到的单实例实现方式的局限性前,我们先探讨一下在这种简单的场景下,如何正确的实现分布式锁,因为这是一种在竟态条件可以被接受的条件下实际可行的分布式锁的实现方式,并且,在单实例中的加锁方法是我们接下来要讨论的分布式锁算法的基础。
我们使用如下方式获取一个锁:

 SET resource_name my_random_value NX PX 30000

这个命令只会在key不存在的时候(NX选项)才会设置key,并且将key的过期时间设置为30000毫秒(PX选项)。这个key的值被设置为”myrandomvalue”。这个值必须在所有申请这个锁的客户端中保持唯一。
这个随机值是用来安全的释放掉锁的,我们会使用一个脚本通知Redis:只有当key存在,并且key对应的值与我期望的值相同时才删除掉这个key。下面的Lua脚本实现了这个方式:

if redis.call("get",KEYS[1]) == ARGV[1] then
    return redis.call("del",KEYS[1])
else
    return 0
end

使用这种方式是为了避免删除掉其他客户端获取到的锁。例如,一个客户端获取到了锁,然后在接下来的操作中使用了超过锁可用时间(可用时间过后key会自动过期)的时间,然后删除掉了已经被其他客户端获取到的锁。仅仅使用DEL命令会误删除别的客户端获取到的锁,因此是不安全的。通过使用上面的脚本以及使用一个随机串对锁进行“签名”,可以保证锁只会被持有该锁的客户端释放。
如何生成随机串呢?我们认为从/dev/urandom中获取20个字节就可以了,你也可以针对你的任务使用其他更为轻量的生成方式。例如使用/dev/urandom作为种子的RC4算法产生一个伪随机流。一个更简单的方式是使用微秒级的unix系统时间组合客户端ID来生成一个随机串,这并不能认为是安全的,但是大部分场景下这已经足够使用。
我们将key的存活时间称为锁可用时间(lock validity time)。这个时间既是锁的自动释放时间,又是获得锁的客户端在另一个客户端在不违反互斥性保证的前提下可以获得锁之前的可操作时间区间,这个时间受限于从获取锁的瞬间开始的一段时间窗口。
所以我们有一种很好的获取与释放锁的方法了。如果我们假设Redis单实例永远可用,那么这个非分布式系统可以认为是安全的。但是我们无法保证上面的假设,因此我们将会扩展一下该系统。

RedLock 算法

分布式环境下,我们假设有N个Redis实例。这些实例之间互相完全独立,我们不会使用主从备份或者其他隐含的协调系统。我们已经介绍了如何安全的在一个实例上获取与释放锁。我们在RedLock算法中也会使用这种方式从一个实例上获取与释放锁。我们假设有5台Redis实例,这个数字是比较合理的数字,因此我们需要5台独立的计算机或者虚拟机来启动这5台Redis实例,来模拟他们独立宕机的场景。
客户端需要进行如下的步骤来获取一个锁:

  1. 客户端获取当前时间的毫秒数
  2. 客户端尝试使用相同的key与随机串从全部N个Redis实例顺序的获取锁。当尝试从每一个Redis实例中获取锁时,客户端将会设置一个尝试超时时间,这个时间将会远小于锁的自动释放时间。例如,如果申请一个10秒后自动释放的锁,那么尝试超时时间将会设置在5~50毫秒之间。这将会方式一个客户端在尝试连接一个已经宕机的Redis实例耗时过长:当一个实例无法访问,我们应该马上去尝试访问下一个实例。
  3. 客户端通过计算当前时间与第一步获取的时间间隔来计算获取锁这一步骤使用了多长时间。当且仅当客户端在大部分实例上成功获取到了锁(本例中最少为3台Redis实例),并且获取锁的时间小于锁可用时间(lock validity time),我们才认为客户端成功获取到了锁。
  4. 如果锁被成功获取,那么这个锁的可用时间为初始的锁可用时间间去第三步中的尝试加锁的流逝时间。
  5. 如果客户端因为某种原因没有成功获取到锁(无论是因为没有成功从N/2+1个实例中获取到锁还是因为剩余的锁可用时间小于0),客户端均会尝试去所有Redis实例中释放锁(即使客户端在该实例上没有能够获得锁)。

这个算法是异步算法吗?

本算法基于这样一个假设:虽然不同服务间,没有一个同步的时钟,但是每个服务的本地时钟均按相同的频率前进,并且之间相差的时间相对于锁的自动释放时间来说可以忽略不计。这个假设接近于实际的计算机:每台计算机内部均有一个本地时钟,并且我们可以认为不同计算机之间的时钟偏差非常小。
基于这一点,我们需要再次强调我们的互斥性规则:只有持有锁的客户端可以在锁可用时间(第三步中的到的时间)减去一小段时间(几毫秒的时间,用以抵消不同系统之间的时钟漂移导致的时间差异)内结束自己的工作,锁的互斥性才会得到保障。
想要了解更多的关于时钟漂移的信息,可以参考这篇论文Leases: an efficient fault-tolerant mechanism for distributed file cache consistency.

失败重试

当一个客户端无法成功获取到锁时,客户端需要等待一小段随机时间后再进行尝试获取锁,这是因为防止多个客户端在同一时间尝试获取同一把锁(这可能会导致没有客户端能获取到锁的脑裂情况的发生)。另外如果客户端更快的尝试获取锁,那么将会缩短发生脑裂(以及需要再次重试)的时间窗口,因此理想情况下,客户端应该并行的向N个Redis实例发送SET命令。
需要强调的一点是,当客户端没有成功获取到锁时,客户端应该马上释放掉自己在所有Redis节点中获取到的(部分)锁,因此其他客户端无需等待这些节点上的锁过期释放后才可以再次申请锁(然而如果发生了网络分区,客户端无法与Redis实例通讯的话,我们仍然需要等待自动过期机制过期掉相关的锁)。

锁的释放

锁的释放非常简单,只需要申请释放掉所有Redis实例上的锁即可,而不管客户端是否在这个实例上是否加锁成功。

安全争议

这个算法是否安全?我们可以通过了解在不同场景下将会发生什么来得到答案。
让我们从假设一个客户端已经成功获得了绝大多数的锁开始。所有的Redis实例会保存一个相同存活时间(time to live)的key。然而,这个key是在不同时间下设置的,因此key会在不同的时间点过期。假设T1为客户端设置第一个key的起始时间(客户端在发送请求到第一个Redis实例前的时间点),T2为客户端收到最后一个Redis实例返回值的时间,我们可以认为第一个Redis实例中的key将会至少存活MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT时间。所有其他的实例将会在稍后过期掉这个key,因此我们可以确定客户端最少会持有这个锁MIN_VALIDITY时间。
在一个客户端在大部分Redis实例已经加锁的时间段内,其他客户端无法成功获取锁,这是因为至少N / 2 + 1个Redis实例中已经存在锁。同时当一个客户端已经申请到了锁,这个客户端无法同一时间再次申请这把锁(违反了互斥性)(译注:无可重入性)。
然而我们同时希望多个客户端同时申请同一把锁时,不能多个都成功。
如果客户端获取大部分实例锁所花费的时间接近或者超过了锁的最大可用时间(使用SET命令中的参数TTL),客户端会认为锁已经失效了,并且会释放掉这个锁。因此,我们仅需要关注客户端获取锁的时间小于锁可用时间这样一种场景。在这种场景中,我们已经解释了在MIN_VALIDITY这个时间段内,不会有客户端能够获取到锁。因此只有一种情况会出现多个客户端同时获取到锁,那就是获取锁的时间超过了锁的存活时间,这样取得的锁也是无效的。
如果你能提供关于现有的类似算法的一个正式证明(指出正确性),或者是发现这个算法的bug? 我们将非常感激.

可用性争论

本系统的可用性依赖于如下三个主要特性:

  1. 锁的自动释放(因为key过期了):最终锁可以被再次获取。
  2. 客户端会在锁没有被获取到或者锁被使用完后,配合删除掉锁,使得后面等待锁的客户端无需等待锁自动过期就能及时的获取到锁。
  3. 当客户端需要重新尝试获取锁时,客户端会等待一段时间,这段时间会远大于获取锁所需要的时间,以最大限度的降低脑裂情况的发生。

然而,当网络分区时,系统将会在TTL时间段内无法工作,因此如果有持续的网络分区的发生,系统将无法在有限的时间内恢复工作。这会发生在每当客户端获取到了锁并且在删除锁之前就产生网络分区。
因此,如果网络分区持续,本算法可能会持续的无法正常工作。

性能, 故障恢复 与 fsync

许多用户为了更低的获取与释放锁的响应时间、更高的每秒钟可以有多少此获取/释放锁的操作而使用Redis作为锁服务。为了满足这种需求,我们需要同时请求N个Redis服务器来降低延迟。
然而如果我们希望系统能够在崩溃中恢复,我们需要考虑数据的持久化。
我们假设这样一种情况,我们完全没有设置Redis的持久化。一个客户端在5个Redis实例中的3个实例下获取到了锁。这3个实例中的一个发生了重启,在这种情况下,系统中又有了3个实例可以获取同一把锁,此时另一个客户端就可以获取到锁,这违反了我们系统的互斥性。
如果我们开启了AOF持久化,情况会好转一点。例如,我们可以通过向一个Redis实例发送SHUTDOWN指令并重启该实例来升级它。因为Redis的过期是语义实现,所以当Redis服务关闭时,时间仍然在流逝,因此我们的需求是可以满足的。然而只有当服务是优雅关闭的前提下,系统才不会受到影响。系统断电会发生什么?如果Redis是使用默认配置,即每一秒钟使用fsync写盘的话,我们可能会在系统重启时丢失锁信息。理论上,如果我们希望无论是什么情况下的系统重启,我们都需要保证所得安全性的话,我们需要设置将持久化设置fsync=always。这将会让系统性能降低到其他类似的保证CP的系统同一水平。
然而实际情况会比一开始想象的情况要好。当一个节点宕机重启后,只要它不参与到任意当前活动的锁中去时,系统的安全性会得到保证。
为了保证这种安全性,我们只需要让宕机的实例,在超过TTL的时间后再启动即可,这段时间内将会把所有的系统宕机前已存在的锁释放掉。使用延迟启动(delayed restarts)可以让我们在不使用Redis持久化的前提下满足安全性要求,然而这里需要注意的是,这可能导致系统进入无法正常提供锁服务的状态。例如,如果大部分实例宕机,系统将会在最少TTL时间段内完全(这里完全的意思是这段时间没有任何资源能够被锁定)无法提供服务。

锁续期,将本算法变得更为可靠

如果客户端的工作可以拆分成很多小的步骤,那么可以默认使用一个很短的锁可用时间,并且通过实现锁续期的机制来对锁的租约时间进行延长。例如客户端在工作进行中发现锁将会很快到期,那么可以通过一个Lua脚本来对锁进行续期操作,这个Lua脚本将会发送到全部的Redis实例中,让锁的有效期延长一段时间,前提是客户端在实例中仍然持有这把锁。
客户端在续期时,需要判断自己持有锁数量是否仍然超过半数,以及这些锁仍然在可用时间内(续期算法与获取锁算法非常相似)。
这在技术上没有修改这个算法,因此不能无限次数的对锁进行续期操作,因为这会导致可用性属性遭到破坏。

想要参与?

如果你深入了解分布式系统,我们非常欢迎你提出你的观点/分析。使用其他语言实现本算法将会非常宝贵。
提前感谢大家!

针对RedLock的分析

  1. Martin Kleppmann 针对 Redlock 的分析文章. 我针对该文章的反驳
posted in 二叉树  leetcode 

问题

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

例如,给定如下二叉搜索树:  root = \([6,2,8,0,4,7,9,null,null,3,5]\)

示例 1:

\(输入:\) root = \([6,2,8,0,4,7,9,null,null,3,5]\), p = \(2\), q = \(8\)
\(输出:\) 6
\(解释:\) 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:

\(输入:\) root = \([6,2,8,0,4,7,9,null,null,3,5]\), p = 2, q = 4
\(输出:\) 2
\(解释:\) 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明:

  • 所有节点的值都是唯一的。
  • p、q 为不同节点且均存在于给定的二叉搜索树中。

解法

比较简单,递归判断当前节点是否在p、q之间即可。不过需要注意的是,测试用例中有p>q的,所以,需要先进行一次反转。

代码

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        //如果p>q先进行一次反转
        if (p.val > q.val) {
            return lowestCommonAncestor(root, q,p);
        }
        if (p.val <= root.val && q.val >=root.val) {
            return root;
        }
        if (p.val > root.val) {
            return lowestCommonAncestor(root.right, p,q);
        } else {
            return lowestCommonAncestor(root.left,p,q);
        }
    }
}

问题

给定一个二叉树,它的每个结点都存放一个 0-9 的数字,每条从根到叶子节点的路径都代表一个数字。

例如,从根到叶子节点路径 \(1->2->3\) 代表数字 \(123\)。

计算从根到叶子节点生成的所有数字之和。

说明: 叶子节点是指没有子节点的节点。
示例 1:
输入: \([1,2,3]\)

    1
   / \
  2   3

输出: 25
解释:
从根到叶子节点路径 \(1->2\) 代表数字 \(12\).
从根到叶子节点路径 \(1->3\) 代表数字 \(13\).
因此,数字总和 = \(12 + 13 = 25\).
示例 2:
输入:\([4,9,0,5,1]\)

    4
   / \
  9   0
 / \
5   1

输出: \(1026\)
解释:
从根到叶子节点路径 \(4->9->5\) 代表数字 \(495\).
从根到叶子节点路径 \(4->9->1\) 代表数字 \(491\).
从根到叶子节点路径 \(4->0\) 代表数字 \(40\).
因此,数字总和 = \(495 + 491 + 40 = 1026\).

解法

整体难度不大,使用深度优先搜索算法递归即可

代码

java

/**
 * 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 sumNumbers(TreeNode root) {
        dfs(root,0);
        return result;
    }
    
    private void dfs(TreeNode root, int curr) {
        if (root == null) {
            return;
        }
        //需要注意的是这里要乘10再加。
        curr = curr *10 + root.val;
        if(root.left ==null && root.right == null) {
            result += curr;
            return;
        }
        //递归左子树
        bfs(root.left, curr);
        //递归右子树
        bfs(root.right,curr);
    }
}
posted in leetcode  二叉树 

问题

翻转一棵二叉树。
示例:
输入:

     4
   /   \
  2     7
 / \   / \
1   3 6   9

输出:

     4
   /   \
  7     2
 / \   / \
9   6 3   1

解法

很简单的递归调用即可。

代码

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root ==null) {
            return root;
        }
        invert(root);
        return root;
        
    }
    
    private void invert(TreeNode root) {
        if (root ==null) {
            return;
        }
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        invert(root.left);
        invert(root.right);
    }
}

逸闻

这道题是HomeBrew的作者 Max Howell 的一条推特中的题。

给定一个二叉树,返回它的中序 遍历。

示例:
输入: \([1,null,2,3]\)

   1
    \
     2
    /
   3

输出: \([1,3,2]\)

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

解法(递归)

经典的算法题,没什么可说的。

代码(递归)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        mid(root, result);
        return result;
    }
    private void mid(TreeNode root, List<Integer> result) {
        if (root ==null) {
            return;
        }
        //先递归左子树
        mid(root.left,result);
        //递归完成后加入本节点
        result.add(root.val);
        //再递归右子树
        mid(root.right, result);
    }
}

解法(迭代)

构建一个栈,只要有左子树就一直压栈,直到左子树为空,出栈后将结果加入到result,然后将当前指针指向当前节点的右子树,进行下一轮压栈处理。

代码(迭代)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.empty()) {
            //左子树一直压栈
            while(root != null) {
                stack.push(root);
                root = root.left;
            }
            //出栈
            root = stack.pop();
            result.add(root.val);
            //切换到右子树进行下一轮
            root = root.right;
        }
        return result;
    }
}
posted in leetcode 

问题

给定字符串 \(S\),找出最长重复子串的长度。如果不存在重复子串就返回 \(0\)。
示例 1:

输入:\("abcd"\)
输出:\(0\)
解释:没有重复子串。

示例 2:

输入:\("abbaba"\)
输出:\(2\)
解释:最长的重复子串为 \("ab"\) 和 \("ba"\),每个出现 \(2\) 次。

示例 3:

输入:\("aabcaabdaab"\)
输出:\(3\)
解释:最长的重复子串为 \("aab"\),出现 \(3\) 次。

示例 4:

输入:\("aaaaa"\)
输出:\(4\)
解释:最长的重复子串为 \("aaaa"\),出现 \(2\) 次。
 

提示:

  • 字符串 \(S\) 仅包含从 \(a\) 到 \(z\) 的小写英文字母。
  • \(1 <= S.length <= 1500\)

解法1(暴力循环)

\(O(n^3)\)的解决方案。三层循环,最里面一层判断是否为重复子串。

代码1(暴力循环)

class Solution {
    public int longestRepeatingSubstring(String str) {
        int len = str.length();
        int res = 0;
        // 大循环
        for (int i = 0; i < len; i++) {
            // 控制相同字符串第二串的起始索引,注意是i+1的。
            for (int j = i + 1; j < len; j++) {
                // 本层循环里面的重复字符串长度
                int currLen = 0;
                for (int k = 0; j + k < len; k++) {
                    // 第三个变量向前推进,直到不相等为止
                    if (str.charAt(i + k) == str.charAt(j + k)) {
                        currLen++;
                        //判断长度与保存的长度大小
                        res = Math.max(res, currLen);
                    } else {
                        //不符合直接跳出该层循环
                        break;
                    }
                }
            }
        }
        return res;
    }
}

解法2(动态规划)

设\(f(i,j)\)为\(S[i:i+k]与S[j:j+k]\)重复字符串的长度,并且\(S[i] == S[j]\),那么会有
\(f(i,j) = f(i - 1, j - 1) + 1\)。
换句话说就是,如果\(S[i]==S[j]\),那么\(i-1\)与\(j-1\)原有的重复字符串长度需要\(+1\)。
这一考虑的空间复杂度为\(O(N)\),时间复杂度为\(O(N^2)\)

代码2(动态规划)

class Solution {
    public int longestRepeatingSubstring(String str) {
        int len = str.length();
        char[] chars = str.toCharArray();
        int res = 0;
        //第一层没什么特殊的,直接循环即可,需要注意的一点是跳出条件为len-res,因为当i超过len-res时,已经绝对不可能再出现大于res的结果了。直接跳出即可。
        for (int i = 0; i < len - res; i++) {
            int curr = 0;
            //注意这里j要从i+1开始计算,因为重复字符串肯定不能从相同起始索引比较起
            for (int j = i + 1, k = 0; j < len - res + curr; j++, k++) {
                // 注意这里比较的是k与j,
                if (chars[k] == chars[j]) {
                    curr++;
                    res = Math.max(res, curr);
                } else {
                    curr = 0;
                }
            }
        }
        return res;
    }
}
posted in leetcode 

问题

请你来实现一个 \(atoi\) 函数,使其能将字符串转换成整数。

首先,该函数会根据需要丢弃无用的开头空格字符,直到寻找到第一个非空格的字符为止。

当我们寻找到的第一个非空字符为正或者负号时,则将该符号与之后面尽可能多的连续数字组合起来,作为该整数的正负号;假如第一个非空字符是数字,则直接将其与之后连续的数字字符组合起来,形成整数。

该字符串除了有效的整数部分之后也可能会存在多余的字符,这些字符可以被忽略,它们对于函数不应该造成影响。

注意:假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时,则你的函数不需要进行转换。

在任何情况下,若函数不能进行有效的转换时,请返回 0。

说明:

假设我们的环境只能存储 32 位大小的有符号整数,那么其数值范围为 \([−2^{31},  2^{31} − 1]\)。如果数值超过这个范围,qing返回  INT_MAX (\(2^{31} − 1\)) 或 INT_MIN (\(−2^{31}\)) 。

解法

注意看说明,首先我们可以排除一些特殊情况,字符串为空或者长度为0,直接返回0即可。
接下来注意到需要丢弃掉开头的空格字符串。那么可以先用一个while循环,来处理应该跳过的字符数量,在接下来的循环中作为初始索引进行循环。这里还需要注意的一点是可能字符串全是空格,这也是个跳出点。不要进入后面的循环了。
接下来,判断初始索引的第一个字符是什么,如果是'+'(没错,用例中真有+1这种奇葩字符,要当成正数1来处理)或'-',还需要一个特殊处理,设置一个boolean值,代表正负号,并且索引值前进1,如果不是数字,那么需要跳出循环处理。
接下来拼接数字,拼接比较简单,假设\(num\)为当前索引指代的数字,无非就是\(result = result * 10 + num\)。但是,有可能溢出,所以需要考虑如何处理溢出,我们知道Integer.MAX_VALUE = \(2^{31}-1\) 即\(2147483647\), 那么如何才会溢出呢?必然是result > MAX_VALUE/10或者 result == MAX_VALUE && num>7时才会溢出,那么溢出后,判断返回值的正负,直接返回对应的值就可以了。
跳出循环后直接返回result即为结果。

代码

java

class Solution {
    public int myAtoi(String str) {
        //处理特殊情况
        if (str == null || str.length() == 0) {
            return 0;
        }
        
        int i = 0;
        // 排除前面空格
        while(i < str.length() && str.charAt(i) == ' ') {
            i++;
        }
        
        // 处理字符串全为空格的情况
        if (i == str.length()) {
            return 0;
        }
        
        // 当接下来的第一个字符为正负号或者在0~9之间时,进入循环
        if (str.charAt(i) == '-' || str.charAt(i) == '+' || (str.charAt(i)>='0' && str.charAt(i) <= '9')) {
            // 未溢出时的返回值
            int result = 0;
            // 正负的判断
            boolean negative = str.charAt(i) == '-';
            // 判断溢出的情况
            int overflowCtl = Integer.MAX_VALUE / 10;
            // 如果为正负号,索引需要前进一步
            if (str.charAt(i) == '-' || str.charAt(i) == '+') i++;
            
            //开始循环
            while (i < str.length()) {
                // 如果是数字
                if (str.charAt(i) >= '0' && str.charAt(i) <= '9') {
                    //获得当前的数字
                    int num = str.charAt(i++) - '0';
                    // 如果溢出,那么返回最大最小值
                    if (result > overflowCtl || (result  == overflowCtl && num>7)) {
                        if (negative) {
                            // 如果是负数,返回最小值
                            return Integer.MIN_VALUE;
                        } else {
                            // 否则返回最大值
                            return Integer.MAX_VALUE;
                        }
                    }
                    // 没溢出 直接累加
                    result = result * 10 + num;
                } else {
                    // 非数字,直接跳出
                    break;
                }
            }
            // 注意正负号就可以了
            return negative? -result : result;
        }
        // 兜底策略
        return 0;
    }
}

问题

给定一个二叉树,返回它的 前序 遍历。

示例:
输入: \([1,null,2,3]\)

   1
    \
     2
    /
   3 

输出: \([1,2,3]\)

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

解法

没什么可说的。直接上代码吧。

代码

递归

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private List<Integer> result = new LinkedList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null) {
            return result;
        }
        preorder(root);
        return result;
    }
    
    public void preorder(TreeNode root) {
        if (root == null) {
            return;
        }
        //先将root.val加入result
        result.add(root.val);
        //递归左子树
        preorder(root.left);
        //递归右子树
        preorder(root.right);
    }
}

迭代

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private List<Integer> result = new LinkedList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null) {
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            result.add(node.val);
            //需要注意这里right要先压栈 其他的基本无压力。
            if (node.right !=null) {
                stack.push(node.right);
            }
            if (node.left !=null) {
                stack.push(node.left);
            }
        }
        return result;
    }
}
posted in leetcode  数组 

问题

数组 \(A\) 是 \([0, 1, ..., N - 1]\) 的一种排列,\(N\) 是数组 \(A\) 的长度。全局倒置指的是 \(i,j\) 满足 \(0 <= i < j < N\) 并且 \([i] > A[j]\) ,局部倒置指的是 \(i\) 满足 \(0 <= i < N\) 并且 \(A[i] > A[i+1]\) 。

当数组 \(A\) 中全局倒置的数量等于局部倒置的数量时,返回 \(true\) 。

示例 1:

输入: \(A = [1,0,2]\)
输出: \(true\)
解释: 有 1 个全局倒置,和 1 个局部倒置。

示例 2:

输入: \(A = [1,2,0]\)
输出: false
解释: 有 2 个全局倒置,和 1 个局部倒置。

注意:

  • \(A\) 是 \([0, 1, ..., A.length - 1]\) 的一种排列
  • \(A\) 的长度在 \([1, 5000]\)之间
  • 这个问题的时间限制已经减少了。

解法

一开始想法比较简单,既然是求逆序对的数量,那么双层for循环一个\(O(n^2)\)的解法就完了。但是第三项注意事项中说了时间限制已经减少,所以毫无意外的超时了。
此时考虑逆序对的性质,全局倒置一定是局部倒置。
对一个\([0,1,...,A.length - 1]\)的排序数组而言,索引\(i\),如果满足\(abs(A[i]-i) <=1\),那么,说明\(i\)只是左移或者右移了一位(或者没变),全局倒置与局部倒置至少同时加一(或者保持不变),仍然满足条件;如果\(abs(A[i] - i) >= 2\),那么,说明\(A[i]\)至少左移或者右移了两位,意味着右边至少有两个比自己小的数(或者左边必然有来2个比自己大且不相邻的数,其中至少一个不相邻)局部(必然<)全局所以造成一定不等,此时不满足条件,直接返回false。

代码

java

class Solution {
    public boolean isIdealPermutation(int[] A) {
        if (A.length <3) {
            return true;
        }
        for (int i = 0; i < A.length; i++) {
            if (Math.abs(A[i] - i) >= 2) {
                return false;
            }
        }
        return true;
    }
}
posted in leetcode  数组  双指针 

问题

给定两个数组,编写一个函数来计算它们的交集。
示例 1:

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

示例 2:

输入: nums1 = \([4,9,5]\), nums2 = \([9,4,9,8,4]\)
输出: [4,9]

说明:

  • 输出结果中每个元素出现的次数,应与元素在两个数组中出现的次数一致。
  • 我们可以不考虑输出结果的顺序。

进阶:

  • 如果给定的数组已经排好序呢?你将如何优化你的算法?
  • 如果 nums1 的大小比 nums2 小很多,哪种方法更优?
  • 如果 nums2 的元素存储在磁盘上,磁盘内存是有限的,并且你不能一次加载所有的元素到内存中,你该怎么办?

解法

问题比较简单。可以遍历两个数组,获得数字出现的频次,然后对比两个频次即可。或者可以直接排序两个数组,然后使用两个指针分别遍历数组即可。

解法

频次法

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        if(nums1.length > nums2.length) {
            return intersect(nums2, nums1);
        }
        //这里使用hashmap,因为数字是不定长的。
        Map<Integer, Integer> map1 = new HashMap<>(nums1.length);
        for (Integer i: nums1) {
            Integer count = map1.get(i);
            if (count == null) {
                map1.put(i, 1);
            } else {
                map1.put(i, count+1);
            }
        }
        Map<Integer, Integer> map2 = new HashMap<>(nums2.length);
        for (Integer i: nums2) {
            Integer count = map2.get(i);
            if (count == null) {
                map2.put(i, 1);
            } else {
                map2.put(i, count+1);
            }
        }
        Iterator iter = map1.entrySet().iterator(); 
        List<Integer> result = new LinkedList();
        //遍历两个频次map即可,这里使用小的那个map遍历。可以减少查询次数
        while(iter.hasNext()) {
            Map.Entry<Integer, Integer> entry = (Map.Entry) iter.next(); 
            Integer key = entry.getKey(); 
            Integer val1 = entry.getValue(); 
            Integer val2 = map2.get(key);
            if(val2 != null) {
                int count = Math.min(val1, val2);
                while (count-- > 0) {
                    result.add(key);
                }
            }
        }
        
        //最终生成结果,因为没有用从List到int[]的方便转换方法。
        int[] res = new int[result.size()];
        for(int m=0;m<res.length;m++)
        {
            res[m]=result.get(m);
        }
        return res;
    }
}

排序遍历法

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        if(nums1.length > nums2.length) {
            return intersect(nums2, nums1);
        }
        List<Integer> result = new LinkedList();
        
        //排序两个数组
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        //遍历两个数组
        for (int i = 0,j=0; i<nums1.length && j<nums2.length;) {
            //相等则加入result
            if (nums1[i] == nums2[j]) {
                result.add(nums1[i]);
                i++;
                j++;
            } else if (nums1[i] < nums2[j]){
                // 这里注意只有其中一个往前推进。
                i++;
            } else {
                j++;
            }
        }
        
        int[] res = new int[result.size()];
        for(int m=0;m<res.length;m++)
        {
            res[m]=result.get(m);
        }
        return res;
    }
}