ARTS #035

ARTS 035

Algorihm

11. Container With Most Water

Difficulty: Medium

Given n non-negative integers a<sub style=“display: inline;”>1</sub>, a<sub style=“display: inline;”>2</sub>, …, a<sub style=“display: inline;”>n </sub>, where each represents a point at coordinate (i, a<sub style=“display: inline;”>i</sub>). n vertical lines are drawn such that the two endpoints of line i is at (i, a<sub style=“display: inline;”>i</sub>) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

**Note: **You may not slant the container and n is at least 2.

<small style=“display: inline;”>The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.</small>

Example:

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

Solution

Language: Swift

最容易想出来的解决方案应该就是两层循环，不出意外会超时，一般两层循环的在leetcode都会超时。

class Solution {
    func maxArea(_ height: [Int]) -> Int {
        var maxArea = 0
        
        for i in 0..<height.count {
            let left = height[i]
            for j in (i + 1)..<height.count {
                let right = height[j]
                let rightIndex = j
                
                let tem = min(left, right) * (rightIndex - i)
                maxArea = max(maxArea, tem)
            }
        }
        return maxArea
    }
}

看了别人的提示后，发现了O(N)时间复杂度的解决办法，从数组的两端向中间移动。具体解决方案如下：

class Solution {
    func maxArea(_ height: [Int]) -> Int {
        var maxArea = 0
        var left = 0
        var right = height.count - 1
        var leftValue = 0
        var rightValue = 0
        while left < right {
            leftValue = height[left]
            rightValue = height[right]
            
            maxArea = max(maxArea, min(leftValue, rightValue) * (right - left))
            
            if leftValue > rightValue {
                right -= 1
            }
            else{
                left += 1
            }
        }
        return maxArea
    }
}

Review

程序员如何和HR谈Offer： https://dandan2009.github.io/2019/12/10/job-negotiation-for-programmers-the-basic-principles/

Tips

• Tips1: zsh alias 怎么加参数？

  我们知道alias可以简化命令，比如下面

  alias ios='cd /Users/dan/Documents/wanan/ios/iv && pod install --no-repo-update && open iv.xcworkspace'
  

  在终端输入

   ios         
  

  就可以执行三条命令。

  那么怎么alias 命令怎么带参数呢，答案就是用函数。

  deletefile() {
    rm -rf $1 
    
    echo rm -rf $1 
  }
  alias dele=deletefile
  

  在终端输入 dele 2.txt, 就会执行

   rm -rf  2.txt
   echo rm -rf  2.txt
   
  

• Tips2: iOS价格显示问题，用NSDecimalNumber 处理价格

  @property(nonatomic, strong) NSDecimalNumber* price;//< 单位：元
  

  接口返回是NSNumber类型，有些数字解析会有问题，比如实际数据是9.8，但是AFN返回的是9.800000000000001，导致显示有问题，

  解决办法，重写set方法，用NSDecimalNumberHandler处理一下。

  - (void)setPrice:(NSDecimalNumber *)price{
       NSDecimalNumberHandler *handler = [NSDecimalNumberHandler decimalNumberHandlerWithRoundingMode:NSRoundDown scale:2 raiseOnExactness:NO raiseOnOverflow:NO raiseOnUnderflow:NO raiseOnDivideByZero:NO];
      _price = [price decimalNumberByRoundingAccordingToBehavior:handler];
  };
  
  RoundingMode：  NSRoundDown只舍不入
  scale ： 2 保留两位小数
  
  

• Tips3: Mac ssh-key如何配置多个

  在 ~/.ssh 目录下新建config文件或者编辑config文件

  config文件内容如下：

  # github 的ssh-key
  Host github.com
  User xxxx@gmail.com
  PreferredAuthentications publickey
  IdentityFile ~/.ssh/github 
  
  
  # coding.net的ssh-key
  Host gitlab.coding.net
  User xxxx@qq.com
  PreferredAuthentications publickey
  IdentityFile ~/.ssh/id_rsa 
  

Share

你怎么看待华为251事件？