LeetCode-746-Min Cost Climbing Stairs

链接在此。

解题思路:输入的 cost 向量的长度 len即为台阶的级数。我们可以生成一个长度为len+1的向量 dp,dp[i]表示跳到第 i 个位置(从0开始计数)需要的费用。例如 dp[0]表示跳到第0个位置的cost,为0;dp[1]表示跳到第1个位置的 cost,因为起始 index 可以为1,所以 dp[1] = 0;dp[2]表示跳到第2个位置的 cost,因为一次可以跳一步或者两步,因此 dp[2]的值有两种可能:

* 从第0个位置跳过来,所以 dp[2] = dp[0] + cost[0];
* 从第1个位置跳过来,所以 dp[2] = dp[1] + cost[1];
因此我们应该取这两种情况中较小的那一个:dp[2] = min(dp[2-2] + cost[2-2], dp[2-1]+cost[2-1]);

下面我们来推导状态转移方程:
dp[i]表示跳到第 i 个位置,它的值有两种可能:
* 从第 i-2 个位置跳过来,因此dp[i] = dp[i-2]+cost[i-2]
* 从第 i-1 个位置跳过来,因此dp[i] = dp[i-1]+cost[i-1]

因此,dp[i] = min(dp[i-1]+cost[i-1], dp[i-2] + cost[i-2])。这即为本题的状态转移方程。根据该方程,我们不难写出下面的代码:

解决 MacBook Pro 2015 款睡眠导致电量耗尽的问题

我的电脑是 Macbook Pro (Retina, Early 2015)款,最近遇上了几次合盖前电量90+,睡眠一两天后再打开电量耗尽的现象。第一次我打了电话给技术支持,但是没有得到任何有效的建议。而今早我的 MacBook 又出现了这种现象,在网上搜索一番后,我找到了如下的解决方案

  1. 重启 Macbook,在启动的时候按住 command + R,等待一会后系统会进入 Recovery 模式。
  2. 从菜单栏的实用工具中选择打开终端。
  3. 输入 csrutil disable 禁掉 SIP,然后正常重启 Macbook。
  4. 打开终端,输入 ioreg -l | grep board-id 查看并记住这个board-id。
  5. 打开 Finder,按住 command+shift+g,进入目录 /System/Library/Extensions/IOPlatformPluginFamily.kext/Contents/PlugIns/X86PlatformPlugin.kext/Contents/Resources,然后找到上一步中的 board-id 对应的 .plist 文件。
  6. 用管理员权限编辑该 plist 文件。
  7. TCPKeepAliveDuringSleep 修改为 false, 然后保存。
  8. 重启 MacBook,再次进入 Recovery 模式,打开终端输入csrutil enable以重启SIP服务。
    <key>TCPKeepAliveDuringSleep</key> 
    <false/> 
    <key>NotificationWake</key> 
    <false/> 
    <key>DNDWhileDisplaySleeps</key> 
    <true/> 

最近几次电脑睡眠后,再打开时电量相比之前只下降1%~2%,因此上述方法是有效的。

二叉树的 Morris 遍历

转载自:Morris Traversal方法遍历二叉树(非递归,不用栈,O(1)空间),有所修改。

Morris 遍历是由 Joseph Morris 于1979年发明的,这种遍历方法与递归以及非递归遍历方法相比,其时间复杂度为 O(n),而空间复杂度只要 O(1)。在某些场合下,其空间复杂度为常数的特性非常有用,因此我们有必要了解和掌握它是如何实现的。 继续阅读“二叉树的 Morris 遍历”

LeetCode-9-Palindrome Number

题目要求:判断一个数字是否是回文数字。
思路:通过res = res * 10 + x % 10; x /= 10;我们就能取出x的右半边逆序后的数字。当x的位数是奇数时,如x = 12321, 那么很容易验证循环退出时res = 123,此时判断x ?= res/10,如果相等则x是回文数,否则不是;当x的位数是偶数时,如x = 123321,那么循环退出时res = 123,此时判断x ?= res,如果相等则x是回文数。
代码如下:

bool isPalindrome(int x) {
    if (x < 0 || (x % 10 == 0 && x != 0)) {
        return false;LinkedList
    }
    int res = 0;
    while(x > res) {
        res = res * 10 + x % 10;
        x = x / 10;
    }
    return res == x || x == res/10;
}

二叉树的深度和高度

二叉树的深度和高度是非常相似的两个量,经常会让人分不清他们的区别。它们的准确定义如下:

  • 深度:这个定义是针对每个节点来说的,一个节点的深度是从根节点到该节点经过的边的数量
  • 高度:对于一个节点来说,一个节点的高度是从这个节点到最深的叶子经过的边的数量;对一棵树来说,树的高度就是根节点的高度

继续阅读“二叉树的深度和高度”

SDWebImage 源代码剖析-网络部分

前面两篇博文中,简要对SDWebImage的缓存部分多线程部分进行了分析。建议在阅读本篇内容前先看下缓存策略那篇,以对SDWebImage的基本内容有所了解。在本篇中,我们将对它的网络策略进行分析。我们知道SDWebImage的主要功能就是从远程主机上下载图片,所以前面的几个策略都是为这一目的提供支持的,而网络策略的好坏将直接决定库的性能。不过SDWebImage以GitHub上接近20000的star数向我们证明了它不俗的实力,下面就让我们一起看看吧。 继续阅读“SDWebImage 源代码剖析-网络部分”