本文共 2810 字，大约阅读时间需要 9 分钟。

463 Island Perimeter

method#1: Math

Since the adjacent edge cannot be counted into perimeter, and each island cell has four edges, what we need to do is counting how many island cells(ones) and pairs of neighbor(two adjacent island called one pair of neighbor), and the answer is 4 * island_num - 2 * neighbor_num(subtracting 2 * neighbor_num because 4 * cell_num counts adjacent edges twice)

method#2: Iteration

The most intuitive way. Just iterate each cell, if it is an island, then check its surroundings(up, down, left, right), and there are two cases:

1 when the cell sits in boundary, its boundary edge should counted into perimeter 2 when the cell does not sit in boundary, only when its neighbor is water then that edge can be counted into perimeter

method#3: Another Iteration way

This method is kind of wired but excellent. The thought is similar to method#2, but more concise and elegant. Since each pair of neighbor cells (the edge between them) with different values is part of the perimeter, just count the differing pairs horizontally and vertically. When it comes to vertical iteration, one simple way is to transpose the matrix. In python, map(list,zip(*matrix)) can easily and effectively transpose a matrix.

Author:

Code

import operatorclass Solution:    def islandPerimeter(self, grid: 'List[List[int]]') -> 'int':        # math        land, neighbor = 0, 0         for i in range(len(grid)):            for j in range(len(grid[i])):                if grid[i][j]==1:                    land+=1                    if i+1

136 Single Number

This question is pretty simple if no restrictions. But when it comes to requirement of linear running time complexity and no use of extra memory, it becomes kind of tricky. One approach meets the requirement is using XOR operation. Since:

x ^ 0 == xx ^ x == 0x ^ y ^ x == y

The code comes easily and clearly:

code

class Solution:    def singleNumber(self, nums):        x = 0        for num in nums:            x ^= num        return x

953 Verifying Alien Dictionary

Approach

Actually, as long as the order is given, whether it is earth or alien does not matter. Then compare every two pair of words, from head to tail. (It works since if a<b, b<c, then a<c)

class Solution:    def isAlienSorted(self, words, order):        m = {
   c: i for i, c in enumerate(order)}        for i in range(len(words)-1):            if not self.compare(words[i], words[i+1], m):                return False        return True        def compare(self, s1, s2, m):        len1, len2 = len(s1), len(s2)        for i in range(min(len1,len2)):            if m[s1[i]] > m[s2[i]]:                return False            elif m[s1[i]] == m[s2[i]]:                if len1>len2:                    return False            else:                return True

转载地址：http://ywksi.baihongyu.com/