[2-5]Leetcode 1021. 删除最外层的括号 lee

题目Leetcode 1021. 删除最外层的括号
时间：2019年5月21日10:19:07
难度：简单
编号：2
进度：2/5 20/52
语言：python3

---

有效括号字符串为空 ("")、"(" + A + ")" 或 A + B，其中 A 和 B 都是有效的括号字符串，+ 代表字符串的连接。例如，""，"()"，"(())()" 和 "(()(()))" 都是有效的括号字符串。

如果有效字符串 S 非空，且不存在将其拆分为 S = A+B 的方法，我们称其为原语（primitive），其中 A 和 B 都是非空有效括号字符串。

给出一个非空有效字符串 S，考虑将其进行原语化分解，使得：S = P_1 + P_2 + ... + P_k，其中 P_i 是有效括号字符串原语。

对 S 进行原语化分解，删除分解中每个原语字符串的最外层括号，返回 S 。

思路：利用栈
   python中list是天然的栈结构。
  从头开始遍历，遇到左括号入栈，遇到右括号，list弹出栈顶元素。
  当栈为空的时候，意味着已经找到一个完整的原语
  删除原语最外层的括号即可: data = data[1:-1]

具体实现如下

class Solution:
    def removeOuterParentheses(self, S: str) -> str:
        data = []
        ans = ""
        cur = ""
        for each in S:
            cur +=each
            if each == "(":
                data.append(each)
            else:
                data.pop()
            
            if len(data) == 0:
                ans += cur[1:-1]
                cur = ""
        
        return ans 

执行用时 : 88 ms, 在Remove Outermost Parentheses的Python3提交中击败了20.19% 的用户
内存消耗 : 13 MB, 在Remove Outermost Parentheses的Python3提交中击败了100.00% 的用户

832. 翻转图像

时间：2019年5月23日14:57:48
难度：简单
编号：3
进度：4/5 20/52
语言：python3

---

思路：最朴素的方法
先把1替换别的数字，比如2
在将0替换成1
最后将1替换成2

class Solution:
    def flipAndInvertImage(self, A: List[List[int]]) -> List[List[int]]:
        A  = [[2 if x==1 else x for x in each] for each in A]
        A  = [[1 if x==0 else x for x in each] for each in A]
        A  = [[0 if x==2 else x for x in each] for each in A]
        
        A = [each [::-1] for each in A]
        
        return A

执行用时 : 68 ms, 在Flipping an Image的Python3提交中击败了70.38% 的用户
内存消耗 : 12.8 MB, 在Flipping an Image的Python3提交中击败了99.80% 的用户

fancy 一点的写法：

[[j ^ 1 for j in i[::-1]] for i in A]

执行用时 : 68 ms, 在Flipping an Image的Python3提交中击败了70.38% 的用户
内存消耗 : 13 MB, 在Flipping an Image的Python3提交中击败了92.90% 的用户

804. 唯一摩尔斯密码词

时间：2019年5月23日14:57:48
难度：简单
编号：4
进度：4/5 20/52
语言：python3

---

思路：最朴素的方法设置字典

class Solution:
    def uniqueMorseRepresentations(self, words: List[str]) -> int:
        data = {"a":".-","b":"-...","c":"-.-.","d":"-..","e":".","f":"..-.","g":"--.","h":"....","i":"..","j":".---","k":"-.-","l":".-..","m":"--","n":"-.","o":"---","p":".--.","q":"--.-","r":".-.","s":"...","t":"-","u":"..-","v":"...-","w":".--","x":"-..-","y":"-.--","z":"--.." }
        
        ans  = {}
        for each in words:
            line = ""
            for letter in each:
                line +=data[letter]
            if line not in ans:
                ans[line] = 1
        return len(ans)

执行用时 : 48 ms, 在Unique Morse Code Words的Python3提交中击败了94.53% 的用户
内存消耗 : 13.1 MB, 在Unique Morse Code Words的Python3提交中击败了85.46% 的用户

657. 机器人能否返回原点

时间：2019年5月25日10:15:16
难度：简单
编号：5
进度：6/5 20/52
语言：python3

---

思路：x轴y轴各设一个标记，两个轴都为0则走回原点
代码：

class Solution:
    def judgeCircle(self, moves: str) -> bool:
        stepUD =0
        stepLR = 0
        for each in moves:
            if each =='L' :
                stepLR+=1
            elif each == 'U':
                stepUD+=1
            elif each == 'R':
                stepLR-=1
            else:
                stepUD-=1
        return stepUD==0 and stepLR==0

执行用时 : 76 ms, 在Robot Return to Origin的Python3提交中击败了63.73% 的用户
内存消耗 : 13.2 MB, 在Robot Return to Origin的Python3提交中击败了80.58% 的用户