1. Algorithm: 每周至少做一个 LeetCode 的算法题

笔者的文章：

算法：回溯和动态规划解决每次移动一步最终回到原地1269. Number of Ways to Stay in the Same Place After Some Steps

LeetCode全集请参考：LeetCode Github 大全



题目

1269. Number of Ways to Stay in the Same Place After Some Steps



You have a pointer at index 0 in an array of size arrLen. At each step, you can move 1 position to the left, 1 position to the right in the array or stay in the same place (The pointer should not be placed outside the array at any time).



Given two integers steps and arrLen, return the number of ways such that your pointer still at index 0 after exactly steps steps.



Since the answer may be too large, return it modulo 10^9 + 7.



Example 1:



Input: steps = 3, arrLen = 2
Output: 4
Explanation: There are 4 differents ways to stay at index 0 after 3 steps.
Right, Left, Stay
Stay, Right, Left
Right, Stay, Left
Stay, Stay, Stay



Example 2:



Input: steps = 2, arrLen = 4
Output: 2
Explanation: There are 2 differents ways to stay at index 0 after 2 steps
Right, Left
Stay, Stay



Example 3:



Input: steps = 4, arrLen = 2
Output: 8



Constraints:



1 <= steps <= 500
1 <= arrLen <= 10^6



回溯递归解决

分析：移动的三种方案可以转换为数字右移+1，不动0，左移-1。 很容易就想到用回溯递归的方式解决。退出的条件有两个：

1. 步数用完steps == 0 ，如果位置为0则表示一种方案，返回1，否则表示不符合要求，返回0；

2. 超过边界sum < 0 || sum >= arrLen，实际上还有优化的空间最大步数不超过steps的一半，或者arrLen。Math.min(steps/2 + 1, arrLen)



public int numWays(int steps, int arrLen) {
    return helper(steps, arrLen, 0);
  }
  private int helper(int steps, int arrLen, int sum) {
    // check edge
    if (sum < 0 || sum >= arrLen) {
      return 0;
    }
    // exit
    if (steps == 0) {
      return sum == 0 ? 1 : 0;
    }
    int next = steps - 1;
    return helper(next, arrLen, sum + 1) + helper(next, arrLen, sum) + helper(next, arrLen, sum - 1);
  }



这里不考虑时间复杂度，可以解决问题，在LeetCode提交会超时。



动态规划

如果我们将dp状态选择为dp[steps][position]，则可以从该状态选择：



• 不动。然后我们消耗一步，并停留在同一位置=>dp[steps-1][position]

• 向右走。然后，我们走了一步，然后向右走=>dp[steps-1][position+1]

• 向左走（如果不在零位置）。然后我们消耗一步，然后向左走=>if position > 0 then dp[steps-1][position-1]



然后我们的状态可以计算为：dp[steps][position] = dp[steps-1][position] + dp[steps-1][position+1] + dp[steps-1][position-1]。



当只有一步作为基本案例时，我们可以使用该案例。这些情况是：



• 我们处于零位，只有一步，那么只有一种方法（停留）=> dp[1][0] = 1

• 我们处于第一位置，只有一步，然后只有一种方法（向左走）=> dp[1][1] = 1



请注意，我们只能进行尽可能多的步骤。例如，对于500步，我们只能到达第500个位置，而arrLen是否为99999999则无关紧要。因此，我们使用它来避免内存/时间限制。min(steps,arrLen)



public int numWaysWithDP(int steps, int arrLen) {
    //int MOD = 1000_000_007;
    final int MOD = (int)1e9 + 7;
    int maxPos = Math.min(steps / 2 + 1, arrLen);
    long[][] dp = new long[steps + 1][maxPos + 1];
    dp[1][0] = 1;
    dp[1][1] = 1;
    for (int i = 2; i <= steps; i++) {
      for (int k = 0; k < maxPos; k++) {
        dp[i][k] = (dp[i - 1][k] + dp[i - 1][k + 1] + (k > 0 ? dp[i - 1][k - 1] : 0)) % MOD;
      }
    }
    return (int) dp[steps][0];
  }



2. Review: 阅读并点评至少一篇英文技术文章

笔者文章：

翻译：Swift中的Operations和OperationQueues入门



说明

Swift中的操作是一种强大的方法，可以在跟踪进度和依赖项的同时将职责划分为多个类。它们的正式名称为NSOperations，并与结合使用OperationQueue。



确保首先阅读我在Swift中关于并发的文章 ，这样您就知道队列和调度的基础知识。操作与调度块有很多共同点，但还有更多好处。让我们开始吧！



Swift中的Operation是什么？

操作通常负责单个同步任务。这是一个抽象类，从未直接使用过。您可以使用系统定义的BlockOperation子类或通过创建自己的子类。您可以通过将操作添加到OperationQueue或手动调用start方法来启动操作。但是，强烈建议您全权负责OperationQueue管理状态。



使用系统定义的BlockOperation外观如下：



let blockOperation = BlockOperation {
    print("Executing!")
}
let queue = OperationQueue()
queue.addOperation(blockOperation)

也可以通过直接在队列上添加块来完成：

queue.addOperation {
  print("Executing!")
}

给定的任务将添加到中OperationQueue，该任务将尽快开始执行。

创建自定义操作

您可以使用自定义操作创建关注点分离。例如，您可以创建一个用于导入内容的自定义实现，以及一个用于上载内容的自定义实现。



以下代码示例显示了用于导入内容的自定义子类：



final class ContentImportOperation: Operation {
    let itemProvider: NSItemProvider
    init(itemProvider: NSItemProvider) {
        self.itemProvider = itemProvider
        super.init()
    }
    override func main() {
        guard !isCancelled else { return }
        print("Importing content..")
        
        // .. import the content using the item provider
    }
}

该类接受项目提供程序，并在main方法中导入内容。该main()函数是同步操作唯一需要覆盖的方法。将操作添加到队列，并设置完成块以跟踪完成：

let fileURL = URL(fileURLWithPath: "..")
let contentImportOperation = ContentImportOperation(itemProvider: NSItemProvider(contentsOf: fileURL)!)
contentImportOperation.completionBlock = {
    print("Importing completed!")
}
queue.addOperation(contentImportOperation)
// Prints:
// Importing content..
// Importing completed!

这将所有将内容导入到单个类中的逻辑转移到了一个类上，您可以在该类上跟踪进度，完成情况，并且可以轻松为此编写测试！

操作的不同状态

一个操作可以根据当前执行状态处于几种状态。



• Ready： 准备开始

• Executing： 任务当前正在运行

• Finished： 流程完成后

• Canceled： 任务已取消



重要的是要知道一个操作只能执行一次。无论何时处于完成或取消状态，您都无法再重新启动同一实例。



在自定义实现中，您需要在执行之前手动检查已取消状态，以确保任务已取消。是否知道在同时开始和取消操作时会发生数据争用。您可以在我的博客文章Thread Sanitizer解释中详细了解数据竞赛 ：Swift中的数据竞赛。



在OperationQueue一旦成为完成，这两个执行或取消后会自动从队列中删除该任务。

利用依赖

仅在内容导入完成后才开始上传。它没有考虑取消，这意味着如果取消导入操作，上传仍将开始。您必须执行检查以查看依赖关系是否已取消：

final class UploadContentOperation: Operation {
    override func main() {
        guard !dependencies.contains(where: { $0.isCancelled }), !isCancelled else {
            return
        }
        print("Uploading content..")
    }
}

使用操作的好处是使用依赖项。您可以轻松地在两个实例之间添加依赖项。例如，要在导入内容后开始上传：



let fileURL = URL(fileURLWithPath: "..")
let contentImportOperation = ContentImportOperation(itemProvider: NSItemProvider(contentsOf: fileURL)!)
contentImportOperation.completionBlock = {
    print("Importing completed!")
}
let contentUploadOperation = UploadContentOperation()
contentUploadOperation.addDependency(contentImportOperation)
contentUploadOperation.completionBlock = {
    print("Uploading completed!")
}
queue.addOperations([contentImportOperation, contentUploadOperation], waitUntilFinished: true)
// Prints:
// Importing content..
// Uploading content..
// Importing completed!
// Uploading completed!

结论

希望您对开始在Swift中实现操作感到兴奋。这是一个隐藏的瑰宝，可让您分离问题，在任务之间添加依赖关系并跟踪完成情况。



这篇文章是系列文章的一部分：



1. Swift中的Operations和OperationQueues入门(本文)

2. 在Swift中编写并发解决方案的异步操作

3. 通过使用泛型进行高级异步操作



也可以以Swift Playground的形式找到：https : //github.com/AvdLee/AsyncOperations



如果您想进一步提高Swift知识，请查看 Swift类别页面。随意 与我联系 或鸣叫我在 [Twitter的](https://www.twitter.com/twannl) ，如果您有任何额外的提示或反馈。



谢谢！



参考

https://www.avanderlee.com/swift/operations/



3. Tips: 学习至少一个技术技巧

笔者的文章：

IntelliJ IDEA 查看类结构，查看类图，继承关系，查看package包关系

IntelliJ IDEA 查看类结构，查看类图，继承关系，查看package包关系

1. 在包上面右键 > Diagrams > Show Diagrams...（快捷键 Command + Option + Shift + u）

1. 选择 Java Class Diagrams即可

1. 笔者用Junit4的源码查看的类图结构如下。

1. 如果要查看包package结构，在层级更上面的package上右键，用上面的方法即可。



1. 如果选择了popup出来，就弹出了一个新弹框 （快捷键 Command + Option + u）



4. Share: 分享一篇有观点和思考的技术文章

笔者的文章：

成功要素：富兰克林的13条必要美德！ 与 狗熊掰棒子



富兰克林的“十三条修身计划”(Benjamin Franklin 13-point plan for honest living)



These names of virtues, with their precepts, were:



1. TEMPERANCE. Eat not to dullness; drink not to elevation.

一、节制，食不过饱，饮酒不醉。



1. SILENCE. Speak not but what may benefit others or yourself; avoid trifling conversation.

二、少言，言必于人于已有益，避免无益的闲聊。



1. ORDER. Let all your things have their places; let each part of your business have its time.

三、秩序，每样东西应放在一定的地方，每件事物应有一定的时限。



1. RESOLUTION. Resolve to perform what you ought; perform without fail what you resolve.

四、决心，当做必做，决定之事，持之不懈。



1. FRUGALITY. Make no expense but to do good to others or yourself; i.e., waste nothing.

五、节俭，于人于已有利之事方可花费，勿浪费一切东西。



1. INDUSTRY. Lose no time; be always employed in something useful; cut off all unnecessary actions.

六、勤勉，勿浪费时间，时刻做些有用的事，杜绝一切不必要的行动。



1. SINCERITY. Use no hurtful deceit; think innocently and justly, and, if you speak, speak accordingly.

七、诚实，不虚伪骗人，思想要公正纯洁，讲话亦如此。



1. JUSTICE. Wrong none by doing injuries, or omitting the benefits that are your duty.

八、公正，不做有损他人的事，不要忘记你应尽的义务，做对人有益之事。



1. MODERATION. Avoid extremes; forbear resenting injuries so much as you think they deserve.

九、中庸，不走极端，容忍别人给予的伤害，将此视作应该承受之事。



1. CLEANLINESS. Tolerate no uncleanness in body, cloths, or habitation.

十、清洁，力求身体、衣服和住所整洁。



1. TRANQUILLITY. Be not disturbed at trifles, or at accidents common or unavoidable.

十一、镇静，勿因小事、平常的或不可避免的事故而惊慌失措。



1. CHASTITY. Rarely use venery but for health or offspring, never to dullness, weakness, or the injury of your own or another’s peace or reputation.

十二、节欲，为了健康或生育后代起见，不常行房事。切忌过度伤体，以免损害自己或他人的安宁与名誉。



1. HUMILITY. Imitate Jesus and Socrates.

十三、谦虚，效法耶稣和苏格拉底。



狗熊掰棒子

狗熊掰棒子的故事大意是：

狗熊走进玉米地里，掰了个棒子夹到腋下，走了几步又掰了个棒子夹到腋下，但原先的棒子却掉了。狗熊在玉米地里忙活了半天，最终手上就只有一两个棒子。



总结

要做有积累的事情，就算袋鼠🦘蹦的很高，每次都会到原地，没有积累，也上不了天。鸟儿飞的时候，择木而息，最终可以飞上天。



对于如何获得这些美德，富兰克林的建议是：

>My intention being to acquire the habitude of all these virtues, I judg’d it would be well not to distract my attention by attempting the whole at once, but to fix it on one of them at a time; and, when I should be master of that, then to proceed to another, and so on, till I should have gone thro’ the thirteen; and, as the previous acquisition of some might facilitate the acquisition of certain others, I arrang’d them with that view, as they stand above. Temperance first, as it tends to procure that coolness and clearness of head, which is so necessary where constant vigilance was to be kept up, and guard maintained against the unremitting attraction of ancient habits, and the force of perpetual temptations. This being acquir’d and establish’d, Silence would be more easy; and my desire being to gain knowledge at the same time that I improv’d in virtue, and considering that in conversation it was obtain’d rather by the use of the ears than of the tongue, and therefore wishing to break a habit I was getting into of prattling, punning, and joking, which only made me acceptable to trifling company, I gave Silence the second place.

>我的目的是想养成这一切美德的习惯，所以我认为，为了不至于分散注意力，最好还是不要立刻全面去尝试，而是在一段时期内集中精力于其中某一个。当我掌握了那项美德之后，接着再开始注意另外一项，如此这样，直到我做到了13条为止。因为先获得的一些美德可以方便其他美德的培养，所以我就按照这个主张把它们排列起来，就像上面的次序那样。“节制”被我放在第一位，因为它可以使我保持头脑冷静和思想清楚。为了保持经常性的警惕，抵抗旧习惯不断的吸引力和无穷无尽的诱惑力，这种冷静的头脑和清晰的思想是大有必要的。在获得和养成了这项美德之后，养成“沉默”的美德就容易得多了。在改进品德的同时，我还想增进知识；而且我认为，在谈话时与其用嘴，还不如用耳朵更能增进知识，因此我想打破我当时正在形成的喜欢喋喋不休、爱说俏皮话、喜欢开玩笑的习惯，这种习惯只能使我和轻浮的人为伍，因此我将“沉默”放在第二位。



参考

https://zhuanlan.zhihu.com/p/42480588



https://www.jianshu.com/p/6498cd125a26