385. Mini Parser

发表于 2018-01-21 | 分类于 leetcode |

385. Mini Parser

题目描述

Given a nested list of integers represented as a string, implement a parser to deserialize it.

Each element is either an integer, or a list – whose elements may also be integers or other lists.

Note: You may assume that the string is well-formed:

String is non-empty.
String does not contain white spaces.
String contains only digits 0-9, [, - ,, ].

Example 1:
Given s = "324",
You should return a NestedInteger object which contains a single integer 324.

Example 2:
Given s = "[123,[456,[789]]]",
Return a NestedInteger object containing a nested list with 2 elements:
1. An integer containing value 123.
2. A nested list containing two elements:
i.  An integer containing value 456.
ii. A nested list with one element:
a. An integer containing value 789.

题目大意

给定一个字符串表示嵌套列表，实现一个反序列化的解析器。
每个元素代表一个整数或者一个列表。
注意：

非空字符。
字符串不包含空格。
字符串只包含0-9的数字，[ - ] ，。

示例1：
给定 s = "324"

你应该返回一个包含单个数字324的NestedInteger对象

示例2：

给定s = "[123,[456,[789]]]"

你应该返回一个包含两个元素的嵌套列表的NestedInteger对象:

一个数字324
一个包含两个元素的嵌套列表:
- 一个数字456
- 一个包含一个元素的嵌套列表：
  - 一个数字789

解题思路

遍历字符串s，记当前字符为char。
如果char为0-9，则使用value数值。
如果char为-，则将符号变量symbol为-1。
如果char为[,则新建一个NestedInteger对象，并压栈。
如果char为]或者,：

如果value非空，则将value * symbol压栈。

将栈顶元素弹出，记为last，如果栈为空，则返回last；如果栈非空，则将last加入栈顶元素的嵌套列表

代码

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * class NestedInteger {
 *     // Return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public func isInteger() -> Bool
 *
 *     // Return the single integer that this NestedInteger holds, if it holds a single integer
 *     // The result is undefined if this NestedInteger holds a nested list
 *     public func getInteger() -> Int
 *
 *     // Set this NestedInteger to hold a single integer.
 *     public func setInteger(value: Int)
 *
 *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 *     public func add(elem: NestedInteger)
 *
 *     // Return the nested list that this NestedInteger holds, if it holds a nested list
 *     // The result is undefined if this NestedInteger holds a single integer
 *     public func getList() -> [NestedInteger]
 * }
 */
func deserialize(_ s: String) -> NestedInteger {
    var stack = [NestedInteger]()
    var value: Int? = nil
    var symbol = 1
    for char in s {
        let num = Int(String(char)) ?? -1
        if num >= 0 && num <= 9 {
            value = 10 * (value ?? 0) + num
        }else if char == "-" {
            symbol = -1
        }else if char == "[" {
            stack.append(NestedInteger())
        }else {
            if value != nil {
                let nestedInteger = NestedInteger()
                nestedInteger.setInteger(value! * symbol)
                stack.last?.add(nestedInteger)
                symbol = 1
                value = nil
            }
            if char == "]" {
                let last = stack.removeLast()
                if stack.isEmpty {
                    return last
                }else {
                    stack.last?.add(last)
                }
            }
        }
    }
    let nestedInteger = NestedInteger()
    nestedInteger.setInteger((value ?? 0) * symbol)
    return nestedInteger
}

687. Longest Univalue Path

发表于 2018-01-21 | 分类于 leetcode |

687. Longest Univalue Path

题目描述

Given a binary tree, find the length of the longest path where each node in the path has the same value. This path may or may not pass through the root.

Note: The length of path between two nodes is represented by the number of edges between them.

Example 1:
Input:
              5
             / \
            4   5
           / \   \
          1   1   5
Output:
2

Example 2:
Input:
              1
             / \
            4   5
           / \   \
          4   4   5
Output:
2

Note: The given binary tree has not more than 10000 nodes. The height of the tree is not more than 1000.

题目大意

求二叉树节点值全部相等的最长路径，路径不一定通过根节点。

解题思路

递归遍历左右子树，寻找左右子树节点值全部相等的最长路径。

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */
class Solution {
    func longestUnivaluePath(_ root: TreeNode?) -> Int {
        var ans = 0
        func longestPath(_ root: TreeNode?) -> Int {
            guard let tree = root else { return 0 }
            let lc = longestPath(tree.left)
            let rc = longestPath(tree.right)
            var ll = 0, rl = 0
            if let left = tree.left, left.val == tree.val { ll = lc + 1 }
            if let right = tree.right, right.val == tree.val { rl = rc + 1 }
            ans = max(rl + ll, ans)
            return max(rl, ll)
        }
        longestPath(root)
        return ans
    }
}

637. Average of Levels in Binary Tree

发表于 2018-01-21 | 分类于 leetcode |

637. Average of Levels in Binary Tree

题目描述

Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.

Example 1: 
Input: 
    3 
   / \ 
  9  20 
    /  \ 
   15   7 
Output: [3, 14.5, 11]
Explanation:
The average value of nodes on level 0 is 3,  on level 1 is 14.5, and on level 2 is 11. Hence return [3, 14.5, 11].

Note:
The range of node’s value is in the range of 32-bit signed integer.

题目大意

计算每层的平均数

解题思路

层次遍历

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */
class Solution {
    func averageOfLevels(_ root: TreeNode?) -> [Double] {
        guard let tree = root else { return [] }
        var ans = [Double]()
        var queue = [tree]
        while !queue.isEmpty {
            var sum = 0
            var tmp = [TreeNode]()
            for tree in queue {
                sum += tree.val
                if let left = tree.left { tmp.append(left) }
                if let right = tree.right { tmp.append(right) }
            }
            ans.append(Double(sum) / Double(queue.count))
            queue = tmp
        }
        return ans
    }
}

747. Largest Number At Least Twice of Others

发表于 2018-01-21 | 分类于 leetcode |

747. Largest Number At Least Twice of Others

题目描述

In a given integer array nums, there is always exactly one largest element.

Find whether the largest element in the array is at least twice as much as every other number in the array.

If it is, return the index of the largest element, otherwise return -1.

Example 1:
Input: nums = [3, 6, 1, 0]
Output: 1
Explanation: 6 is the largest integer, and for every other number in the array x,
6 is more than twice as big as x.  The index of value 6 is 1, so we return 1.

Example 2:
Input: nums = [1, 2, 3, 4]
Output: -1
Explanation: 4 isn't at least as big as twice the value of 3, so we return -1.

Note:
nums will have a length in the range [1, 50].
Every nums[i] will be an integer in the range [0, 99].

题目大意

找出数组内的最大值，并且最大值至少是其他数值的二倍。如果存在，则返回最大值下标，否则返回-1。

解题思路

找出最大值，遍历数组，是否符合题目条件。

代码

class Solution {
    func dominantIndex(_ nums: [Int]) -> Int {
        guard !nums.isEmpty else { return -1 }
        
        var max = nums.max()!
        var index = -1
        
        for (i, num) in nums.enumerated() where num * 2 > max {
            guard num != max else {
                index = i
                continue
            }
            return -1
        }
        return index
    }
}

556. Next Greater Element III

发表于 2018-01-21 | 分类于 leetcode |

Given a positive 32-bit integer n, you need to find the smallest 32-bit integer which has exactly the same digits existing in the integer n and is greater in value than n. If no such positive 32-bit integer exists, you need to return -1.

1
2
3

Example 1:
Input: 12
Output: 21

1
2
3

Example 2:
Input: 21
Output: -1

题目大意

给一数值n，满足以下条件的值 ans ：

不大于0x7FFFFFFF
大于n
ans包含n中所有的数。

符合条件则返回ans，否则返回-1。

解题思路

转n为数组。
反向遍历数组，找到最后一个递增下标index。
如果存在递增下标，则反向遍历数组，将nums[index - 1]，与最后一个大于nums[index - 1]进行替换。
由于index之后的元素呈递减序列，所以采用双指针的方式交换元素。

代码

class Solution {
     func nextGreaterElement(_ n: Int) -> Int {
        var index = 0
        var s = Array("\(n)")
        
        for i in (1..<s.count).reversed() {
            if s[i - 1] < s[i] {
                index = i
                break
            }
        }
        
        if index > 0 {
            for i in (0..<s.count).reversed() {
                if s[i] > s[index - 1] {
                    s.swapAt(index - 1, i)
                    break
                }
            }
        }
        
        for i in 0..<(s.count - index) / 2 {
            s.swapAt(index + i, s.count - i - 1)
        }
        let ans = Int(String(s))!
        return ans > n && ans <= 0x7FFFFFFF ? ans : -1
    }
}