463. Island Perimeter

class Solution(object):
    def islandPerimeter(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        closeLine=0

        n=0
        sum1=0
        while n<len(grid):
            k=0
            while k<len(grid[n]):
                if grid[n][k]==1:
                    sum1+=4
                    if k>0 and grid[n][k]==grid[n][k-1]:
                        closeLine+=2
                k+=1
            q=0
            while q<len(grid[n]):
                if n>0 and grid[n][q]==1 and grid[n][q]==grid[n-1][q]:
                    closeLine+=2
                q+=1
            n+=1
         
        return sum1-closeLine
         
         
         
还算比较顺利吧，跑了两次就跑出来了，思路是正确的，果然这个题目还是个小学奥数题……貌似没怎么考算法。结果就是总陆地数量乘4减去2倍的相同边界数。
         
但是速度似乎太慢了，只击败了36%的人……虽然最快的也只比我快50%（只？！！！！？？？(╯‵□′)╯︵┻━┻）

最快解法：
class Solution(object): def islandPerimeter(self, grid): """ :type grid: List[List[int]] :rtype: int """ if not grid: return 0 s = 0 for i in range(len(grid)): for j in range(len(grid[i])): if grid[i][j]==1: s+=4 if i!=0: if grid[i-1][j]>0: s -=2 if j!=0: if grid[i][j-1]>0: s -=2 return s

 注意学习，在循环的时候获取list索引的一种很好的写法就是，
for i in range(len(grid))，即用list的长度来生成一个新的range类.
这个解法是判断了如下几种情况：右下角的点和正上方以及正左方的点进行比较；左边缘正下方的点和正上方的点进行比较，上边缘正右方的点和正左方的点进行比较。

 我的解法是，从第一行开始，正右方的点和正左方的点进行比较，然后从第一列开始，正下方的点和正上方的点进行比较，然后再继续比较第二行以及第二列，再递进。

 这个答案只用到了两个变量来循环，即i和j。

 但是！！！为毛我按这个最快的答案进去跑，尼玛时间和我一样啊？当然我感觉实际上也是这样，真是醉了，不知道leetcode的时间是怎么算的。。大概这道题没啥优化的余地吧，可能就看心情返回运算时间？？
（然后我把我的答案又反复提交了几次，居然速度超过了60%的人……醉了）

评论

发表评论

此博客中的热门博文

225 Implement Stack using Queues

OA: class MyStack { Queue<Integer> queue; /** Initialize your data structure here. */ public MyStack () { queue = new LinkedList<>(); } /** Push element x onto stack. */ public void push ( int x) { queue.offer(x); int k = queue.size() - 1 ; while (k > 0 ) { queue.offer(queue.poll()); k--; } } /** Removes the element on top of the stack and returns that element. */ public int pop () { return queue.poll(); } /** Get the top element. */ public int top () { return queue.peek(); } /** Returns whether the stack is empty. */ public boolean empty () { return queue.isEmpty(); } } oa是push一次就逆序排一次（相当于每次push一个之后都把新push进去的那个排到最前面，这样下次pop的时候就是pop的这一个。） ma在top和pop的时候才把最后一个调到前面来，而且每次都要重新排。（感觉其实差不多，要看这个这个stack是pop和top用得多还是push用得多） MA: class MyStack { ArrayDeque<Integer> ...
阅读全文

232. Implement Queue using Stacks

MA: class MyQueue {     Stack<Integer> simQ=new Stack<Integer>();     Stack<Integer> buffer=new Stack<Integer>();     /** Initialize your data structure here. */     public MyQueue() {     }         /** Push element x to the back of queue. */     public void push(int x) {         simQ.push(x);     }         /** Removes the element from in front of queue and returns that element. */     public int pop() {         while(!simQ.empty()){             buffer.push(simQ.pop());         }         int temp=buffer.pop();         while(!buffer.empty()){             simQ.push(buffer.pop());         }         return temp;     } ...
阅读全文

20. Valid Parentheses

OA: class Solution { public boolean isValid (String s) { char [] stack = new char [s.length()]; int head = 0 ; for ( char c : s.toCharArray()) { if (c == '(' ) { stack[head++] = c; } else if (c == '[' ) { stack[head++] = c; } else if (c == '{' ) { stack[head++] = c; } else if (c == ')' ) { if (head == 0 ) return false ; if (stack[--head] != '(' ) return false ; } else if (c == ']' ) { if (head == 0 ) return false ; if (stack[--head] != '[' ) return false ; } else if (c == '}' ) { if (head == 0 ) return false ; if (stack[--head] != '{' ) return false ; } } return head == 0 ; } } OA比MA快一倍。 String有个toCharArray()...
阅读全文