Acceml

Acceml 查看完整档案

北京编辑哈尔滨工业大学  |  计算机科学与技术 编辑小米  |  软件工程师 编辑 www.zhihu.com/people/ludaifei/activities 编辑
编辑

码蹄疾,毕业于哈尔滨工业大学。
小米广告第三代广告引擎的设计者、开发者;
负责小米应用商店、日历、开屏广告业务线研发;
主导小米广告引擎多个模块重构;
关注推荐、搜索、广告领域相关知识;

个人动态

Acceml 发布了文章 · 2019-08-30

【Leetcode】142.环形链表 II

题目

给定一个链表,判断链表中是否有环。为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。

示例 1:

输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。

clipboard.png
示例 2:

输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。

clipboard.png
你能用O(1)(即,常量)内存解决此问题吗?

题解

这道题是上一道题目的升级版本,要找到环的入口,又要空间复杂度是常量。我们只能通过找规律。

假像在一个环形的足球场上,有两个运动员在跑步,一快一慢,只要时间足够长,他们两个肯定会相遇。快慢指针也是一样,假如链表有环,那么指针一快一慢,肯定会相遇。

遍历链表。循环结束条件是到达链表尾部(如果有环则用于达不到)。

相遇之后,一个指针slow从相遇点C继续走,另一个指针start从链表头开始走,则相遇点即为链表入口。

clipboard.png

代码层面的话,我们就在上一道题快慢指针相遇的地方,继续到start指针和slow指针相遇的地方就是链表入口。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) return null;
        ListNode slow = head;
        ListNode fast = head;
        ListNode start = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                // 上道题在这里返回,这道题继续找一下就OK了.
                while (start != slow) {
                    slow = slow.next;
                    start = start.next;
                }
                return slow;
            }
        }
        return null;
    }
}

图片描述

查看原文

赞 0 收藏 0 评论 0

Acceml 发布了文章 · 2019-08-26

【Leetcode名企之路】141. 环形链表

题目

给定一个链表,判断链表中是否有环。

为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

示例 1:

输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。

图片描述

示例 2:

输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。

图片描述

示例 3:

输入:head = [1], pos = -1
输出:false
解释:链表中没有环。

图片描述

你能用 O(1)(即,常量)内存解决此问题吗?

题解

链表的题目很多都是使用快慢指针来求解。本题很容易的直观反映是用hash来存储,但是这样的空间复杂度是O(n)。比如我们之前A过的一道题目,求链表的一半、1/3等都是可以用快慢指针解的。链表一般考察两类题目:

  • 快慢指针;
  • 链表的基本操作:断链、重新连接新链;

少量时候可能会用到递归,比如链表反转。而一般求解存不存在、判断是不是这类题目是用快慢指针解的。

假像在一个环形的足球场上,有两个运动员在跑步,一快一慢,只要时间足够长,他们两个肯定会相遇。快慢指针也是一样,假如链表有环,那么指针一快一慢,肯定会相遇。

遍历链表。循环结束条件是到达链表尾部(如果有环则用于达不到)。

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;
        ListNode fast = head;
        ListNode slow = head;
        boolean res = false;
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
            if (fast != null) {
                fast = fast.next;
            }
            if (slow == fast) {
                res = true;
                break;
            }
        }
        return res;
    }
}  

还可以参照另一个比较简洁的版本。循环结束条件是快慢指针相遇。

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }
}

Leetcode名企之路

查看原文

赞 0 收藏 0 评论 0

Acceml 发布了文章 · 2019-08-14

【Leetcode】139.拆分词句

图片描述

题目

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明:

拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例 1:

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

示例 2:

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
     注意你可以重复使用字典中的单词。

示例 3:

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

思路分析

暴力搜索

这道题最开始我们想的肯定是每个字符遍历, 然后去看是不是在wordDict里面。而wordDict是一个list,查找是o(N)的时间复杂度,需要把这个时间复杂度先降下来,用Set把每次查找的时间复杂度降到o(1)。

怎么去check一个字符串wordDict能不能被组成,一个很朴素的想法就是把每个字符串分作两段,然后递归。比如如下代码。

public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        return helper(s, new HashSet<>(wordDict), 0);
    }
    public boolean helper(String s, Set<String> wordDict, int start) {
        if (start == s.length()) {
            return true;
        }
        for (int end = start + 1; end <= s.length(); end++) {
            if (wordDict.contains(s.substring(start, end)) 
                && helper(s, wordDict, end)) {
                return true;
            }
        }
        return false;
    }
}

很显然这种思路是行不通的,因为时间复杂度太高,有兴趣的同学可以试一下。

  • 时间复杂度: O(n^n)
  • 空间复杂度:O(n)

记忆化搜索

重复计算太多。哪里重复了?举个例子:

输入: s = "AAAleetcodeB", wordDict = ["leet", "code","A", "AA", "AAA"]
for 循环中:
首次递归: s = 'A' + helper('AAleetcodeB'), 最终检查不符合;
二次递归: s = 'AA' + helper('AleetcodeB'), 最终检查不符合;
三次递归: s = 'AAA' + helper('leetcodeB'), 最终检查不符合;

发现没, 上面每一次都重复计算了helper('leetcodeB')

节省时间的办法也很自然:要是我们能把搜索过的内容记下来就好了。记忆有两种办法可供参考:

  • 动态规划
  • 记忆化数组进行搜索

动态规划

我们先看动态规划,动态规划其实很好理解,最重要的是状态转移方程。不懂的同学,可以手动模拟一遍基本就理解了。

  • dp[i]表示[0, i] 子串是否能够由wordDict组成
  • dp[i] = 对于任意j, dp[j] && wordDict 包含 s[j + 1, i],其中j 属于区间 [0, i] 。

模拟一下动态规划的过程是:

输入: s = "AAAleetcodeB", wordDict = ["leet", "code","A", "AA", "AAA"]
dp[0] = true // 初始化.
首次dp: dp[1] = true, wordDict 包含'A';
二次dp: dp[2] = true, 
        dp[1] = true, wordDict 包含'A';
三次dp: dp[3] = true,
        dp[1] = true, wordDict 包含'AA';
...
最后一次dp: dp[12] = false,
        dp[1]= true wordDict 不包含'AAleetcodeB';
        dp[2]= true wordDict 不包含'AleetcodeB';
        dp[3]= true wordDict 不包含'leetcodeB';
        dp[7]= true wordDict 不包含'codeB';
        dp[11]= true wordDict 不包含'B'
        故,dp[12] = false.

java版本代码如下:

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        if (s == null) return false;
        Set<String> wordSet = new HashSet<>();
        for (int i = 0; i < wordDict.size(); i++) {
            wordSet.add(wordDict.get(i));
        }
        boolean[] dp = new boolean[s.length() + 1];
        // 状态开始
        dp[0] = true;
        // dp[i]表示能不能到达第i个字母的时候
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                String current = s.substring(j, i);
                if (dp[j] && wordSet.contains(current)) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}
  • 时间复杂度:O(n^2)。两层for循环。
  • 空间复杂度: O(n)。dp数组长度是n。

DFS

动态规划和记忆化搜索都是很常用的解法,本题我们可以用一个数组memoToEndContain 记下位置i到字符串结束能不能够由wordDict组成。还是我们最开始的例子:

输入: s = "AAAleetcodeB", wordDict = ["leet", "code","A", "AA", "AAA"]
首次for循环: 'A' 可以被 wordDict组成
        'AA' 可以被 wordDict组成
        ...
        'AAAleetcodeB'不可以被 wordDict组成
        这次深搜后记住:
        从第一个字母'A' 第二个字母'A', 第三个字母'A' ... 开始的子串都不能由wordDict组成;

java代码:

public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        if (s == null) return false;
        Set<String> wordSet = new HashSet<>(wordDict);
        // 记忆从i到字符串结束能不能搜索到.
        Boolean[] memoToEndContain = new Boolean[s.length()];
        return dfs(s, 0, wordSet, memoToEndContain);
    }

    public boolean dfs(String s,
                       int start,
                       Set<String> wordSet,
                       Boolean[] memoToEndContain) {
        // 搜索到最后.
        if (start == s.length()) {
            return true;
        }
        // 之前已经搜索过.
        if (memoToEndContain[start] != null) {
            return memoToEndContain[start];
        }

        for (int end = start + 1; end <= s.length(); end++) {
            if (wordSet.contains(s.substring(start, end)) 
                && dfs(s, end, wordSet, memoToEndContain)) {
                return memoToEndContain[start] = true;
            }
        }
        memoToEndContain[start] = false;
        return memoToEndContain[start];
    }
}
  • 时间复杂度:O(n^2)。搜索树的大小最多达到 n^2 。
  • 空间复杂度: O(n)。深度优先二叉搜索树深度最多是n。
查看原文

赞 0 收藏 0 评论 0

Acceml 发布了文章 · 2019-07-31

关于 MySQL 百万数据量的 count(*) 查询如何优化?

明确需求

对这个问题有兴趣是源于一次开发中遇到要统计人数的需求。类似于“得到”专栏的订阅数。

clipboard.png

但是我的数据量比这个大很多,而对数据的准确性要求就不那么高。所以首先要明确需求。其他答案有的说了用缓存,有的答案对比了count(*)、count(1)的区别,都很好,但是我认为还是要看一下题主的场景。我根据我实际开发的经验总结如下几个方面,FYI。

clipboard.png

数据量大/准确性要求低/请求量大

  1. 这种场景一般是C端产品,比如上面说的得到APP的订阅数目,如果对一致性要求不高,可以直接在内存中使用缓存,用guava在内存中做一个缓存定时刷新即可,百万量级count(*)有缓存的频率还不至于有啥性能问题;
  2. 但是内存内缓存有一个问题就是不同服务器之间的缓存数量是不一致的,可以考虑用redis作为计数,一般这种场景是大多数同学遇到的,简单粗暴搞定即可;
  3. 用show table status。这个建议还是不要用了,翻了下mysql 的doc,40%的误差概率,碰上就有点大了呀。
TABLE_ROWS
The number of rows. Some storage engines, such as MyISAM, store the exact count. For other storage engines, such as InnoDB, this value is an approximation, and may vary from the actual value by as much as 40% to 50%. In such cases, use SELECT COUNT(*) to obtain an accurate count.

数据量大/准确性要求高/请求量一般

这种场景一般出现在账务上,比如有多少人打款。而且估计DAU在亿级别的公司可能才会遇到。这里最关键的问题还是一致性的要求。在并发系统中,看看我们用redis,我们看看会出现什么样的一致性问题:

时间       A processor         B processor
T1         插入数据
T2                             1.redis#get计数器;2. 查询最新的N条数据
T3         redis#incr

在T2的时间点的时候会出现数据不一致,B看到的是数据已经更新,但是数据库还没更新。我们就在想,如果放到一个事务里面,就可以完美解决这个问题了呀。由于事务,innoDB不支持像MyISAM准确计数,解铃还须系铃人,所以我们建一个计数表(count_table)+事务,解这个问题了。

时间         会话A                            会话B
T1         begin;
           在计数表中插入一条数据;
T2                                          begin;
                                            1. 读count_table;
                                            2. 查询最新的N条数据
                                            commit;
T3         更新conut_table;
           commit;

在T1的时候,如果采用Mysql默认的事务隔离级别:读提交。因为T1事务还没有提交,所以插入的数据,B是读不到的,所以从逻辑上来说是一致的。

数据量大/准确性要求高/请求量特别高

抱歉,没遇到过。如果你觉得你遇到了,你的架构需要你重新design and review,相信我。

带条件count(*)

很多时候我们的业务场景不是数据量多,而是条件复杂。这其实就是一个查询优化的问题了,和是不是count(*)没有关系,那么有以下两招常用,这个得具体问题具体分析了。比如时间维度可以加一个索引来优化;

select * from table_name where a = x and b = x;
  • 加索引
  • 业务拆分

count性能比较

  • count(primary key)。遍历整个表,把主键值拿出来,累加;
  • count(1)。遍历整个表,但是不取值,累加;
  • count(非空字段)。遍历整个表,读出这个字段,累加;
  • count(可以为空的字段)。遍历整个表,读出这个字段,判断不为null累加;
  • count(*)。遍历整个表,做了优化,不取值,累加。

结合mysql的一些索引查询知识,我们可以大致得出如下结论。

clipboard.png

建议直接使用count(*)。

Leetcode名企之路

查看原文

赞 10 收藏 8 评论 3

Acceml 发布了文章 · 2019-07-04

【Leetcode】137.只出现一次的数字 II

题目

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现了三次。找出那个只出现了一次的元素。

说明:

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

示例 1:

输入: [2,2,3,2]
输出: 3

示例 2:

输入: [0,1,0,1,0,1,99]
输出: 99

题解

根据上一道题目的经验,我们很明确的知道不能用数数字的办法去解。考虑位运算的办法,找相关的性质。

这个题其实就是求,在其他数都出现k次的数组中有一个数只出现一次,求出这个数。

而上面那个k次的是有通用解法的。

使用一个32维的数组,用这个32维的数组存储:

[第31位1的总数, 第30位1的个数,…, 第1位1的个数]

  • 假如第0位1的个数是k的倍数,那么要求的这个数在该位一定是0;
  • 若不是k的倍数,那么要求的这个数在该位一定是1。

    因为假如说数组中的某些数在该位置是1,那么因为这个数要么出现k次,那么出现1次。

这样我们就可以找出只出现一次那个数的二进制表示形式。二进制如何转化为10进制呢?

假如,按照上面的规则,最招找到的二进制为:

A = [0, 0, 0, 0, 0, …, 1]

因为异或操作是:相同为0,不同为1。

那么久可以依次用 1, 2, 4, 8… 和依次每一位异或,即可得到最终答案。

第二部分可能不好理解,可以手动模拟下。

class Solution {
    public int singleNumber(int[] nums) {
        // 有多少个相同的数字
        int N = 3;
        // [高位1的个数,...,低位1的个数]
        int[] bitNum = new int[32];
        
        for (int i = 0; i < nums.length; i++) {
            int compare = 1;
            int num = nums[i];
            for (int j = bitNum.length - 1; j >= 0; j--) {
                if ((compare&num) != 0) {
                    bitNum[j]++;
                }
                compare = compare << 1;
            }
        }
        
        int compare = 1;
        int res = 0;
        for(int i = bitNum.length - 1; i >= 0; i--) {
            if(bitNum[i] % N != 0) {
                res = res ^ compare;
            }
        }
        return res;
   }
}

热门阅读

Leetcode名企之路

查看原文

赞 0 收藏 0 评论 0

Acceml 发布了文章 · 2019-07-01

【Leetcode】135.分发糖果

# 题目

老师想给孩子们分发糖果,有 N 个孩子站成了一条直线,老师会根据每个孩子的表现,预先给他们评分。

你需要按照以下要求,帮助老师给这些孩子分发糖果:

每个孩子至少分配到 1 个糖果。
相邻的孩子中,评分高的孩子必须获得更多的糖果。
那么这样下来,老师至少需要准备多少颗糖果呢?

示例 1:

输入: [1,0,2]
输出: 5
解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。

示例 2:

输入: [1,2,2]
输出: 4
解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。
     第三个孩子只得到 1 颗糖果,这已满足上述两个条件。

题解

  1. 我们首先给每一个小朋友都发糖果,保证每位喜至少分配到一个糖果;
  2. 从左到右遍历,考虑右边的小朋友比左边小朋友排名高的情况,此时更新为 candy[i] = candy[i - 1] + 1,暂时不考虑左边比右边高的情况;
  3. 从右到左遍历,考虑左边比右边高的情况,希望左边比右边高,但是又需要考虑不破坏第二点中的已经满足的规则,所以更新条件为candy[i] = max(candy[i], candy[i + 1] + 1);
  4. 把所有的分配加起来;
class Solution {
    public int candy(int[] ratings) {
        if (ratings == null || ratings.length == 0) return 0;
        int[] resCandy = new int[ratings.length];
        for (int i = 0; i < resCandy.length; i++) {
            resCandy[i] = 1;
        }
        
        for (int i = 1; i < ratings.length; i++) {
            // 比左边的小朋友排名更高.
            if (ratings[i] > ratings[i - 1]) {
                resCandy[i] = resCandy[i - 1] + 1;
            }
        }

        for (int i = ratings.length - 2; i >= 0; i--) {
            // 当前比右边的小朋友排名更高.resCandy[i] = resCandy[i + 1] + 1
            // 同时需要保证不破坏当前比左边小朋友高的规则
            if (ratings[i] > ratings[i + 1]) {
                resCandy[i] = Math.max(resCandy[i + 1] + 1, resCandy[i]);
            }
        }
        int res = 0;
        for (int i = 0; i < resCandy.length; i++) {
            res += resCandy[i];
        }
        return res;
    }
}

热门阅读

Leetcode

查看原文

赞 0 收藏 0 评论 0

Acceml 发布了文章 · 2019-05-26

【Leetcode】130. 被包围的区域

题目

给定一个二维的矩阵,包含 'X''O'字母 O)。

找到所有被 'X' 围绕的区域,并将这些区域里所有的 'O''X' 填充。

示例:

X X X X
X O O X
X X O X
X O X X

运行你的函数后,矩阵变为:

X X X X
X X X X
X X X X
X O X X

解释:

被围绕的区间不会存在于边界上,换句话说,任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上,或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻,则称它们是“相连”的。

题解

这道题我们拿到基本就可以确定是图的dfs、bfs遍历的题目了。题目中解释说被包围的区间不会存在于边界上,所以我们会想到边界上的o要特殊处理,只要把边界上的o特殊处理了,那么剩下的o替换成x就可以了。问题转化为,如何寻找和边界联通的o,我们需要考虑如下情况。

X X X X
X O O X
X X O X
X O O X

这时候的o是不做替换的。因为和边界是连通的。为了记录这种状态,我们把这种情况下的o换成#作为占位符,待搜索结束之后,遇到o替换为x(和边界不连通的o);遇到#,替换回o(和边界连通的o)。

如何寻找和边界联通的o? 从边界出发,对图进行dfs和bfs即可。这里简单总结下dfs和dfs。

  • bfs递归。可以想想二叉树中如何递归的进行层序遍历。
  • bfs非递归。一般用队列存储。
  • dfs递归。最常用,如二叉树的先序遍历。
  • dfs非递归。一般用stack。

那么基于上面这种想法,我们有四种方式实现。

dfs递归

class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length == 0) return;
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 从边缘o开始搜索
                boolean isEdge = i == 0 || j == 0 || i == m - 1 || j == n - 1;
                if (isEdge && board[i][j] == 'O') {
                    dfs(board, i, j);
                }
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
                if (board[i][j] == '#') {
                    board[i][j] = 'O';
                }
            }
        }
    }

    public void dfs(char[][] board, int i, int j) {
        if (i < 0 || j < 0 || i >= board.length  || j >= board[0].length || board[i][j] == 'X' || board[i][j] == '#') {
            // board[i][j] == '#' 说明已经搜索过了. 
            return;
        }
        board[i][j] = '#';
        dfs(board, i - 1, j); // 上
        dfs(board, i + 1, j); // 下
        dfs(board, i, j - 1); // 左
        dfs(board, i, j + 1); // 右
    }
}

dfs 非递归

非递归的方式,我们需要记录每一次遍历过的位置,我们用stack来记录,因为它先进后出的特点。而位置我们定义一个内部类Pos来标记横坐标和纵坐标。注意的是,在写非递归的时候,我们每次查看stack顶,但是并不出stack,直到这个位置上下左右都搜索不到的时候出Stack。

class Solution {
    public class Pos{
        int i;
        int j;
        Pos(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }
    public void solve(char[][] board) {
        if (board == null || board.length == 0) return;
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 从边缘第一个是o的开始搜索
                boolean isEdge = i == 0 || j == 0 || i == m - 1 || j == n - 1;
                if (isEdge && board[i][j] == 'O') {
                    dfs(board, i, j);
                }
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
                if (board[i][j] == '#') {
                    board[i][j] = 'O';
                }
            }
        }
    }

    public void dfs(char[][] board, int i, int j) {
        Stack<Pos> stack = new Stack<>();
        stack.push(new Pos(i, j));
        board[i][j] = '#';
        while (!stack.isEmpty()) {
            // 取出当前stack 顶, 不弹出.
            Pos current = stack.peek();
            // 上
            if (current.i - 1 >= 0 
                && board[current.i - 1][current.j] == 'O') {
                stack.push(new Pos(current.i - 1, current.j));
                board[current.i - 1][current.j] = '#';
              continue;
            }
            // 下
            if (current.i + 1 <= board.length - 1 
                && board[current.i + 1][current.j] == 'O') {
                stack.push(new Pos(current.i + 1, current.j));
                board[current.i + 1][current.j] = '#';      
                continue;
            }
            // 左
            if (current.j - 1 >= 0 
                && board[current.i][current.j - 1] == 'O') {
                stack.push(new Pos(current.i, current.j - 1));
                board[current.i][current.j - 1] = '#';
                continue;
            }
            // 右
            if (current.j + 1 <= board[0].length - 1 
                && board[current.i][current.j + 1] == 'O') {
                stack.push(new Pos(current.i, current.j + 1));
                board[current.i][current.j + 1] = '#';
                continue;
            }
            // 如果上下左右都搜索不到,本次搜索结束,弹出stack
            stack.pop();
        }
    }
}

bfs 非递归

dfs非递归的时候我们用stack来记录状态,而bfs非递归,我们则用队列来记录状态。和dfs不同的是,dfs中搜索上下左右,只要搜索到一个满足条件,我们就顺着该方向继续搜索,所以你可以看到dfs代码中,只要满足条件,就入Stack,然后continue本次搜索,进行下一次搜索,直到搜索到没有满足条件的时候出stack。而bfs中,我们要把上下左右满足条件的都入队,所以搜索的时候就不能continue。大家可以对比下两者的代码,体会bfs和dfs的差异。

class Solution {
    public class Pos{
        int i;
        int j;
        Pos(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }
    public void solve(char[][] board) {
        if (board == null || board.length == 0) return;
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 从边缘第一个是o的开始搜索
                boolean isEdge = i == 0 || j == 0 || i == m - 1 || j == n - 1;
                if (isEdge && board[i][j] == 'O') {
                    bfs(board, i, j);
                }
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
                if (board[i][j] == '#') {
                    board[i][j] = 'O';
                }
            }
        }
    }

    public void bfs(char[][] board, int i, int j) {
        Queue<Pos> queue = new LinkedList<>();
        queue.add(new Pos(i, j));
        board[i][j] = '#';
        while (!queue.isEmpty()) {
            Pos current = queue.poll();
            // 上
            if (current.i - 1 >= 0 
                && board[current.i - 1][current.j] == 'O') {
                queue.add(new Pos(current.i - 1, current.j));
                board[current.i - 1][current.j] = '#';
                  // 没有continue.
            }
            // 下
            if (current.i + 1 <= board.length - 1 
                && board[current.i + 1][current.j] == 'O') {
                queue.add(new Pos(current.i + 1, current.j));
                board[current.i + 1][current.j] = '#';      
            }
            // 左
            if (current.j - 1 >= 0 
                && board[current.i][current.j - 1] == 'O') {
                queue.add(new Pos(current.i, current.j - 1));
                board[current.i][current.j - 1] = '#';
            }
            // 右
            if (current.j + 1 <= board[0].length - 1 
                && board[current.i][current.j + 1] == 'O') {
                queue.add(new Pos(current.i, current.j + 1));
                board[current.i][current.j + 1] = '#';
            }
        }
    }
}

bfs 递归

bfs 一般我们不会去涉及,而且比较绕,之前我们唯一A过的用bfs递归的方式是层序遍历二叉树的时候可以用递归的方式。

并查集

并查集这种数据结构好像大家不太常用,实际上很有用,我在实际的production code中用过并查集。并查集常用来解决连通性的问题,即将一个图中连通的部分划分出来。当我们判断图中两个点之间是否存在路径时,就可以根据判断他们是否在一个连通区域。 而这道题我们其实求解的就是和边界的O在一个连通区域的的问题。

并查集的思想就是,同一个连通区域内的所有点的根节点是同一个。将每个点映射成一个数字。先假设每个点的根节点就是他们自己,然后我们以此输入连通的点对,然后将其中一个点的根节点赋成另一个节点的根节点,这样这两个点所在连通区域又相互连通了。
并查集的主要操作有:

  • find(int m):这是并查集的基本操作,查找m的根节点。
  • isConnected(int m,int n):判断m,n两个点是否在一个连通区域。
  • union(int m,int n):合并m,n两个点所在的连通区域。
class UnionFind {
    int[] parents;

    public UnionFind(int totalNodes) {
        parents = new int[totalNodes];
        for (int i = 0; i < totalNodes; i++) {
            parents[i] = i;
        }
    }
        // 合并连通区域是通过find来操作的, 即看这两个节点是不是在一个连通区域内.
    void union(int node1, int node2) {
        int root1 = find(node1);
        int root2 = find(node2);
        if (root1 != root2) {
            parents[root2] = root1;
        }
    }

    int find(int node) {
        while (parents[node] != node) {
            // 当前节点的父节点 指向父节点的父节点.
            // 保证一个连通区域最终的parents只有一个.
            parents[node] = parents[parents[node]];
            node = parents[node];
        }

        return node;
    }

    boolean isConnected(int node1, int node2) {
        return find(node1) == find(node2);
    }
}

我们的思路是把所有边界上的O看做一个连通区域。遇到O就执行并查集合并操作,这样所有的O就会被分成两类

  • 和边界上的O在一个连通区域内的。这些O我们保留。
  • 不和边界上的O在一个连通区域内的。这些O就是被包围的,替换。

由于并查集我们一般用一维数组来记录,方便查找parants,所以我们将二维坐标用node函数转化为一维坐标。

public void solve(char[][] board) {
        if (board == null || board.length == 0)
            return;

        int rows = board.length;
        int cols = board[0].length;

        // 用一个虚拟节点, 边界上的O 的父节点都是这个虚拟节点
        UnionFind uf = new UnionFind(rows * cols + 1);
        int dummyNode = rows * cols;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (board[i][j] == 'O') {
                    // 遇到O进行并查集操作合并
                    if (i == 0 || i == rows - 1 || j == 0 || j == cols - 1) {
                        // 边界上的O,把它和dummyNode 合并成一个连通区域.
                        uf.union(node(i, j), dummyNode);
                    } else {
                        // 和上下左右合并成一个连通区域.
                        if (i > 0 && board[i - 1][j] == 'O')
                            uf.union(node(i, j), node(i - 1, j));
                        if (i < rows - 1 && board[i + 1][j] == 'O')
                            uf.union(node(i, j), node(i + 1, j));
                        if (j > 0 && board[i][j - 1] == 'O')
                            uf.union(node(i, j), node(i, j - 1));
                        if (j < cols - 1 && board[i][j + 1] == 'O')
                            uf.union(node(i, j), node(i, j + 1));
                    }
                }
            }
        }

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (uf.isConnected(node(i, j), dummyNode)) {
                    // 和dummyNode 在一个连通区域的,那么就是O;
                    board[i][j] = 'O';
                } else {
                    board[i][j] = 'X';
                }
            }
        }
    }

    int node(int i, int j) {
        return i * cols + j;
    }
}

热门阅读

Leetcode名企之路

查看原文

赞 0 收藏 0 评论 0

Acceml 发布了文章 · 2019-05-20

【Leetcode】128.最长连续序列

题目

给定一个未排序的整数数组,找出最长连续序列的长度。

要求算法的时间复杂度为 O(n)

示例:

输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

题解

这道题目最开始大家想的肯定是sort,然后计数计算最长序列。但是要求时间复杂度为:o(n),就不能用sort了。一般在leetcode中,对时间复杂度有要求,就用空间来换,对空间复杂度有要求,就用时间来换。

基于这种思路我们就想要求最长的,就是要记录下有没有相邻的元素,比如遍历到100这个元素,我们需要查看[99, 101]这两个元素在不在序列中,这样去更新最大长度。而记录元素有没有这个事我们太熟悉了,用set这种数据结构,而set这种数据结构是需要o(n)的空间来换取的,这就是我们刚才说的用空间来换时间。

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> numsSet = new HashSet<>();
        for (Integer num : nums) {
            numsSet.add(num);
        }
        int longest = 0;
        for (Integer num : nums) {
            if (numsSet.remove(num)) {
                // 向当前元素的左边搜索,eg: 当前为100, 搜索:99,98,97,...
                int currentLongest = 1;
                int current = num;
                while (numsSet.remove(current - 1)) current--;
                currentLongest += (num - current);
                                // 向当前元素的右边搜索,eg: 当前为100, 搜索:101,102,103,...
                current = num;
                while(numsSet.remove(current + 1)) current++;
                currentLongest += (current - num);
                        // 搜索完后更新longest.
                longest = Math.max(longest, currentLongest);
            }
        }
        return longest;
    }
}

热门阅读

Leetcode名企之路

查看原文

赞 0 收藏 0 评论 0

Acceml 发布了文章 · 2019-05-12

【Leetcode】120.三角形最小路径和

题目

给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如,给定三角形:

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。

说明:

如果你可以只使用 O(n) 的额外空间(n 为三角形的总行数)来解决这个问题,那么你的算法会很加分。

题解

这道题目和之前A过的杨辉三角差不多,一看就是动态规划。
动态规划最主要的是确定状态表达式。而要求在o(n)的空间复杂度来解决这个问题,最主要的是要想清楚,更新状态的时候,不破坏下一次计算需要用到的状态。
我们采用"bottom-up"的动态规划方法来解本题。

状态表达式为:
dp[j] = min(dp[j], dp[j+1]) + triangle[j];

图片描述

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int row = triangle.size();
        List<Integer> res = new LinkedList<>(triangle.get(row - 1));
        for (int i = row - 2; i >= 0; i--) {
            List<Integer> currentRow = triangle.get(i);
            for (int j = 0; j < currentRow.size(); j++) {
                res.set(j, Math.min(res.get(j), res.get(j + 1)) + currentRow.get(j));
            }
        }
        return res.get(0);
    }
}

热门阅读

Leetcode名企之路

查看原文

赞 0 收藏 0 评论 0

Acceml 发布了文章 · 2019-04-24

【Leetcode】116. 填充同一层的兄弟节点2

题目

给定一个完美二叉树,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:

struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。

初始状态下,所有 next 指针都被设置为 NULL。

示例:

示例

输入:{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":{"$id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right":{"$id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}

输出:{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":{"$id":"5","left":null,"next":{"$id":"6","left":null,"next":null,"right":null,"val":7},"right":null,"val":6},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"7","left":{"$ref":"5"},"next":null,"right":{"$ref":"6"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"7"},"val":1}

解释:给定二叉树如图 A 所示,你的函数应该填充它的每个 next 指针,以指向其下一个右侧节点,如图 B 所示。

题解

方法一: 层序遍历

使用层序遍历,遍历的时候把同层的节点连接起来;

层序遍历

class Solution {
    public Node connect(Node root) {
        if (root == null) return null;
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            Node current = null;
            while (size > 0) {
                Node node = queue.poll();
                if (node.right != null) queue.add(node.right);
                if (node.left != null) queue.add(node.left);
                node.next = current;
                current = node;
                size--;
            }
        }
        return root;
    }
}

方法二:递归

递归的时候我们通常就分解为递归子问题和递归结束条件。

递归子问题

  • 左右子树分别连起来

递归结束条件

  • node == null, 直接返回
  • node.left != null, 把left.next连到node.right
  • node.right != null && node.next != null, 把node的right 连到 node.next的left。例如遍历到2这个节点,把5连接到6.

递归

class Solution {
    public Node connect(Node root) {
        // o(1) space.
        if (root == null) return null;
        if (root.left != null) root.left.next = root.right;
        if (root.right != null && root.next != null) root.right.next = root.next.left;
        connect(root.left);
        connect(root.right);    
        return root;
    }
}

方法三: 层序遍历 o(1)空间复杂度

层序遍历我们之前用队列来做,但是有时候我们会要求层序遍历用常数的空间复杂度来解。这种方法最关键的地方在于理解如何从上一层切换到下一层的。dummy的作用用于记录上一层的第一个节点是谁,每当遍历完一层之后,切到下一层.
常数空间层序遍历

class Solution {
    public Node connect(Node root) {
        Node dummy = new Node(0);
        Node pre = dummy;
        Node currentRoot = root;
        while (currentRoot != null) {
            if (currentRoot.left != null) {
                pre.next = currentRoot.left;
                pre = pre.next;
            }
            if (currentRoot.right != null) {
                pre.next = currentRoot.right;
                pre = pre.next;
            }
            currentRoot = currentRoot.next;
            if (currentRoot == null) {
                // 切换层.
                pre = dummy;
                currentRoot = dummy.next;
                dummy.next      = null;
            }
        }
        return root;
    }
}

热门阅读

Leetcode名企之路

有问题加手撕代码群讨论

查看原文

赞 0 收藏 0 评论 0

认证与成就

  • 获得 81 次点赞
  • 获得 1 枚徽章 获得 0 枚金徽章, 获得 0 枚银徽章, 获得 1 枚铜徽章

擅长技能
编辑

开源项目 & 著作
编辑

(゚∀゚ )
暂时没有

注册于 2015-12-22
个人主页被 914 人浏览