ARTS 032
这是第32篇
ARTS是
由左耳朵耗子--陈皓发起的一个活动: 每周至少做一个leetcode的算法题、阅读并点评至少一篇英文技术文章、学习至少一个技术技巧、分享一篇有观点和思考的文章。（也就是Algorithm、Review、Tip、Share简称ARTS）。
从4月份开始，由于自己的私事把业余时间都占用了，所以arts暂停了差不多5个月了，从本周开始捡起来，之前算法题都是用C语言实现的，从这篇开始用swift语言实现。
Algorihm
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
给定一个整数数组，返回两个数字的索引，使它们加起来等于一个特定的目标。 您可以假设每个输入将只有一个解决方案，并且不能两次使用相同的元素。
Solution
这个两数之和的题，每个人都能想到的方法是用两层循环解决，那么有没有更好的解决办法呢，这个题目可以转化为已知两数之和和一个数，查找另一个数；在数组中查找一个数需要一一比较，这样效率比较低；有没有好的方法呢，在面向对象的语言中有一种数据结构–字典，可以满足我们的需求。可以先把数组转换为字典，用value做key，数组下标最为value，由于可以假设每个输入将只有一个解决方案，所以数组中有重复的value也没有关系。具体实现如下
class Solution {
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
var numbersDictionary: [Int: Int] = [:]
for index in 0...(nums.count - 1){
let number = nums[index]
numbersDictionary[number] = index
}
for index in 0...(nums.count - 1) {
let number = nums[index]
let remainder = target - number
let indexOfTarget = numbersDictionary[remainder]
if let indexOfTarget = indexOfTarget {
if(indexOfTarget != index){
return [indexOfTarget, index]
}
}
}
return []
}
}
486. Predict the Winner
Difficulty: Medium
Given an array of scores that are non-negative integers. Player 1 picks one of the numbers from either end of the array followed by the player 2 and then player 1 and so on. Each time a player picks a number, that number will not be available for the next player. This continues until all the scores have been chosen. The player with the maximum score wins.
Given an array of scores, predict whether player 1 is the winner. You can assume each player plays to maximize his score.
Example 1:
Input: [1, 5, 2]
Output: False
Explanation: Initially, player 1 can choose between 1 and 2\. If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5\. If player 2 chooses 5, then player 1 will be left with 1 (or 2). So, final score of player 1 is 1 + 2 = 3, and player 2 is 5\. Hence, player 1 will never be the winner and you need to return False.
Example 2:
Input: [1, 5, 233, 7]
Output: True
Explanation: Player 1 first chooses 1\. Then player 2 have to choose between 5 and 7\. No matter which number player 2 choose, player 1 can choose 233.Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win.
Note:
- 1 <= length of the array <= 20.
- Any scores in the given array are non-negative integers and will not exceed 10,000,000.
- If the scores of both players are equal, then player 1 is still the winner.
Solution
解决思路：动态规划
Language: Swift
class Solution {
// var dp1 = ()
var dp = [[Int]]()
func PredictTheWinner(_ nums: [Int]) -> Bool{
if (nums.count%2==0){
return true;
}
dp = [[Int]](repeating: [Int](repeating: 0, count: nums.count), count: nums.count)
return recur(nums,0,nums.count-1)>=0;
}
func recur(_ nums: [Int], _ start:Int, _ end:Int) -> Int{
if (start == end){
return nums[start];
}
if dp[start][end] != 0 {
return dp[start][end];
}
let left:Int = nums[start] - recur(nums, start+1, end);
let right:Int = nums[end] - recur(nums, start, end-1);
dp[start][end] = max(left, right);//ma.max(left, right);
return dp[start][end];
}
}
Review
这篇文章通过代码讲了builder设计模式
https://dandan2009.github.io/2019/10/17/design-patterns-by-tutorials-the-power-of-OOP-part-1/
Tips
我们调试的时候，有时需要给系统方法打断点，比如给UIView 的settFrame 方法打断点 ，但是系统方法我们没有.m文件，这时我们可以用下面的方法打断点。
这里$arg1, 代表发消息的对象， $arg2,代表方法 $arg3代表第1个参数，$arg4代表第2个参数
上图的$arg1==0x7ff965544230; 表示发消息的对象的地址必须是0x7ff965544230;才会触发断点
Share
最近去了一次泰国，泰国是是一个佛教国家，让我意外的地方他们的电瓶车和摩托车是不上锁的，付钱的时候收银员也不会去鉴别钱的真假，即使是1000面额的；听说泰国是没有造假和偷盗的；如果一个国家没有造假和偷盗，是可以节省很多资源的，没有偷盗就不会有各种防偷盗的东西，比如锁，能够节省很多资源；没有造假就不会有各种识别造假的东西。就可以把造假和识别造假的精力和资源用到有用的地方。这么想想其实人类很多资源是浪费的，入职军队和各种武器研发，如果没有战争，我们就不用养军队，不用取研发各种武器；就可以把养军队和研发武器的财物和人投入到改善人类生存环境的地方。
-
Previous
Design patterns by Tutorials— The power of OOP (part 1) -
Next
Design patterns by Tutorials— The power of OOP (part 2)
