Code – 第75页

[swift] LeetCode 695. Max Area of Island

Given a non-empty 2D array grid of 0’s and 1’s, an island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)

Example 1:
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]
Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally.
Example 2:
[[0,0,0,0,0,0,0,0]]
Given the above grid, return 0.
Note: The length of each dimension in the given grid does not exceed 50.

func maxAreaOfIsland(_ grid: [[Int]]) -> Int {
    var i = 0, j = 0, v = 0
    var g = grid
    while i < grid.count {
        while j < grid[i].count {
            v = max(area(&g, i, j), v)
            j += 1
        }
        i += 1; j = 0
    }
    return v
}

private func area(_ g: inout [[Int]], _ i: Int, _ j: Int) -> Int {
    var v = 0
    if i < 0 || i >= g.count || j < 0 || j >= g[i].count {
        return 0
    }
    if g[i][j] == 1 {
        g[i][j] = 0; v = 1
        v += area(&g, i, j+1)
        v += area(&g, i+1, j)
        v += area(&g, i-1, j)
        v += area(&g, i, j-1)
    }
    return v
}

func maxAreaOfIsland(_ grid: [[Int]]) -> Int {

var i = 0, j = 0, v = 0

var g = grid

while i < grid.count {

while j < grid[i].count {

v = max(area(&g, i, j), v)

j += 1

}

i += 1; j = 0

}

return v

}

private func area(_ g: inout [[Int]], _ i: Int, _ j: Int) -> Int {

var v = 0

if i < 0 || i >= g.count || j < 0 || j >= g[i].count {

return 0

}

if g[i][j] == 1 {

g[i][j] = 0; v = 1

v += area(&g, i, j+1)

v += area(&g, i+1, j)

v += area(&g, i-1, j)

v += area(&g, i, j-1)

}

return v

}

[swift] LeetCode 657. Judge Route Circle

Initially, there is a Robot at position (0, 0). Given a sequence of its moves, judge if this robot makes a circle, which means it moves back to the original place.

The move sequence is represented by a string. And each move is represent by a character. The valid robot moves are R (Right), L (Left), U (Up) and D (down). The output should be true or false representing whether the robot makes a circle.

Example 1:
Input: “UD”
Output: true
Example 2:
Input: “LL”
Output: false

return moves.filter({$0 == "U"}).count == moves.filter({$0 == "D"}).count && moves.filter({$0 == "R"}).count == moves.filter({$0 == "L"}).count

1	return moves.filter({$0 == "U"}).count == moves.filter({$0 == "D"}).count && moves.filter({$0 == "R"}).count == moves.filter({$0 == "L"}).count

[swift] LeetCode 617. Merge Two Binary Trees

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.

You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.

Example 1:

Input: 
	Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
Output: 
Merged tree:
	     3
	    / \
	   4   5
	  / \   \ 
	 5   4   7

Input:

Tree 1 Tree 2

1 2

/ \ / \

3 2 1 3

/ \ \

5 4 7

Output:

Merged tree:

/ \

4 5

/ \ \

5 4 7

Note: The merging process must start from the root nodes of both trees.

func mergeTrees(_ t1: TreeNode?, _ t2: TreeNode?) -> TreeNode? {
    let root = mergeNote(t1, t2)
    root?.left = mergeTrees(t1?.left, t2?.left)
    root?.right = mergeTrees(t1?.right, t2?.right)

    return root
}

func mergeNote(_ t1: TreeNode?, _ t2: TreeNode?) -> TreeNode? {
    if let c1 = t1, let c2 = t2 {
        return TreeNode(c1.val + c2.val)
    } else if let c1 = t1 {
        return TreeNode(c1.val)
    } else if let c2 = t2 {
        return TreeNode(c2.val)
    } else {
        return nil
    }
}

func mergeTrees(_ t1: TreeNode?, _ t2: TreeNode?) -> TreeNode? {

let root = mergeNote(t1, t2)

root?.left = mergeTrees(t1?.left, t2?.left)

root?.right = mergeTrees(t1?.right, t2?.right)

return root

}

func mergeNote(_ t1: TreeNode?, _ t2: TreeNode?) -> TreeNode? {

if let c1 = t1, let c2 = t2 {

return TreeNode(c1.val + c2.val)

} else if let c1 = t1 {

return TreeNode(c1.val)

} else if let c2 = t2 {

return TreeNode(c2.val)

} else {

return nil

}

[swift] LeetCode 581. Shortest Unsorted Continuous Subarray

Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too.

You need to find the shortest such subarray and output its length.

Example 1:
Input: [2, 6, 4, 8, 10, 9, 15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.
Note:
Then length of the input array is in range [1, 10,000].
The input array may contain duplicates, so ascending order here means <=.

func findUnsortedSubarray(_ nums: [Int]) -> Int {
    if nums.count < 2 { return 0 }
    let sn = nums.sorted()
    var p = -1, q = -1
    for (i, v) in zip(sn, nums).enumerated() {
        if v.0 != v.1 {
            p == -1 ? (p = i) : (q = i + 1)
        }
    }
    return q - p
}

func findUnsortedSubarray(_ nums: [Int]) -> Int {

if nums.count < 2 { return 0 }

let sn = nums.sorted()

var p = -1, q = -1

for (i, v) in zip(sn, nums).enumerated() {

if v.0 != v.1 {

p == -1 ? (p = i) : (q = i + 1)

}

return q - p

}

[swift] LeetCode 572. Subtree of Another Tree

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node’s descendants. The tree s could also be considered as a subtree of itself.

Example 1:
Given tree s:

3
/ \
4 5
/ \
1 2
Given tree t:
4
/ \
1 2
Return true, because t has the same structure and node values with a subtree of s.
Example 2:
Given tree s:

3
/ \
4 5
/ \
1 2
/
0
Given tree t:
4
/ \
1 2
Return false.

func isSubtree(_ s: TreeNode?, _ t: TreeNode?) -> Bool {
    return ( maxDepth(s) >= maxDepth(t) )
        && ( isSameTree(s, t)
            || (s?.left != nil && isSubtree(s?.left, t))
            || (s?.right != nil && isSubtree(s?.right, t)) )
}

private func isSameTree(_ p: TreeNode?, _ q: TreeNode?) -> Bool {
    if let p = p, let q = q {
        return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
    } else {
        return p == nil && q == nil
    }
}

private func maxDepth(_ root: TreeNode?) -> Int {
    return root == nil ? 0 : 1 + max(maxDepth(root?.left), maxDepth(root?.right))
}

func isSubtree(_ s: TreeNode?, _ t: TreeNode?) -> Bool {

return ( maxDepth(s) >= maxDepth(t) )

&& ( isSameTree(s, t)

|| (s?.left != nil && isSubtree(s?.left, t))

|| (s?.right != nil && isSubtree(s?.right, t)) )

}

private func isSameTree(_ p: TreeNode?, _ q: TreeNode?) -> Bool {

if let p = p, let q = q {

return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right)

} else {

return p == nil && q == nil

}

private func maxDepth(_ root: TreeNode?) -> Int {

return root == nil ? 0 : 1 + max(maxDepth(root?.left), maxDepth(root?.right))

}

[swift] LeetCode 543. Diameter of Binary Tree

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:
Given a binary tree
1
/ \
2 3
/ \
4 5
Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

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

private var diameter = 0
private func diameterOfNode(_ root: TreeNode?) -> Int {
    var lv = 0, rv = 0

    if let l = root?.left {
        lv = 1 + diameterOfNode(l)
    }
    if let r = root?.right {
        rv = 1 + diameterOfNode(r)
    }
    diameter = max(diameter, lv + rv)
    return max(lv, rv)
}

func diameterOfBinaryTree(_ root: TreeNode?) -> Int {
    diameterOfNode(root)
    return diameter
}

private var diameter = 0

private func diameterOfNode(_ root: TreeNode?) -> Int {

var lv = 0, rv = 0

if let l = root?.left {

lv = 1 + diameterOfNode(l)

}

if let r = root?.right {

rv = 1 + diameterOfNode(r)

}

diameter = max(diameter, lv + rv)

return max(lv, rv)

}

func diameterOfBinaryTree(_ root: TreeNode?) -> Int {

diameterOfNode(root)

return diameter

}