ARTS #032

ARTS 032

This is article 32

ARTS is an activity initiated by 由左耳朵耗子--陈皓: Do at least one leetcode algorithm question every week, read and comment on at least one English technical article, learn at least one technical skill, and share an article with opinions and thoughts. (That is, Algorithm, Review, Tip, and Share are referred to as ARTS).

Since April, because my personal affairs have taken up all my spare time, arts has been suspended for almost 5 months. I started picking it up this week. The previous algorithm questions were all implemented in C language. From this article, they are implemented in swift language.

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].

Given an array of integers, return the indices of two numbers such that their sum equals a specific target. You can assume that there will be only one solution for each input and that you cannot use the same element twice.

Solution

For this problem of the sum of two numbers, the solution that everyone can think of is to use a two-level loop. So is there a better solution? This problem can be transformed into a known sum of two numbers and a number, and finding another number; finding a number in an array requires one-to-one comparison, which is relatively inefficient. Is there a good way? There is a data structure in object-oriented languages - a dictionary, which can meet our needs. You can first convert the array into a dictionary, use value as the key, and the array subscript is value. Since it can be assumed that each input will have only one solution, it does not matter if there are duplicate values ​​in the array. The specific implementation is as follows

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. 1 <= length of the array <= 20.
2. Any scores in the given array are non-negative integers and will not exceed 10,000,000.
3. If the scores of both players are equal, then player 1 is still the winner.

Solution

Solution: dynamic programming

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

This article talks about the builder design pattern through code

https://dandan2009.github.io/2019/10/17/design-patterns-by-tutorials-the-power-of-OOP-part-1/

Tips

When we are debugging, sometimes we need to break points for system methods, such as break points for the setFrame method of UIView, but we do not have .m files for system methods. In this case, we can use the following method to break points.

Here $arg1 represents the object sending the message, $arg2 represents the method, $arg3 represents the first parameter, and $arg4 represents the second parameter.

$arg1==0x7ff965544230; in the above figure means that the address of the object sending the message must be 0x7ff965544230; to trigger the breakpoint

Share

I recently went to Thailand. Thailand is a Buddhist country. What surprised me is that their battery cars and motorcycles are not locked. When paying, the cashier will not identify the authenticity of the money, even if it is 1,000 denominations. I heard that there is no counterfeiting and theft in Thailand. If a country does not have counterfeiting and theft, it can save a lot of resources. Without theft, there will be various anti-theft things, such as locks, which can save a lot of resources. Without counterfeiting, there will be various things to identify counterfeiting. The energy and resources spent on counterfeiting and identifying counterfeiting can be used in useful ways. If you think about it this way, many human resources are actually wasted. If there is no war, we would not have to raise an army or develop various weapons. Instead, we can invest the money and people used to raise the army and develop weapons to improve the living environment of mankind.