Valid Anagram 題目 思路與解答 答案 Valid Palindrome 題目 思路與解答 答案 Valid Palindrome II 題目 思路與解答 答案 Valid Parentheses 題目 思路與解答 答案 Valid Perfect Square 題目 思路與解答 答案 ...
註意,答案只是代表是他人寫的代碼,正確,但不一定能通過測試(比如超時),列舉出來只是它們擁有著獨到之處,雖然大部分確實比我的好
1. Valid Anagram
題目
Given two strings s and t, write a function to determine if t is an anagram of s.
For example,
s = “anagram”, t = “nagaram”, return true.
s = “rat”, t = “car”, return false.
Note:
You may assume the string contains only lowercase alphabets.
Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?
思路與解答
不是很懂啥意思?
是s和t使用了相同的字元?
set嘍
好像還要求字元數相等?
dict唄
1 ds,dt = {},{} 2 for w in s: 3 ds[w] = ds.get(w,0)+1 4 for w in t: 5 dt[w] = dt.get(w,0)+1 6 return ds == dt
答案
啊,我也想過用sorted做。。。但是一閃而過又忘記了?
return sorted(s) == sorted(t)
return all([s.count(c)==t.count(c) for c in string.ascii_lowercase])
return collections.Counter(s)==collections.Counter(t)
真是各種一行方案啊
看到有人說一個dict就能解決,想了一下是的。
#是我寫的 d = {} for w in s: d[w] = d.get(w,0)+1 for w in t: d[w] = d.get(w,0)-1 if not d[w]:del d[w] return not d
2. Valid Palindrome
題目
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For example,
“A man, a plan, a canal: Panama” is a palindrome.
“race a car” is not a palindrome.
Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.
For the purpose of this problem, we define empty string as valid palindrome.
思路與解答
那個例子舉得我有些不懂呢???
“A man, a plan, a canal: Panama” is a palindrome.
Why???
哦,只要求字母對稱就可以了啊
判斷是不是字母我記得有個函數來著
n=[i.lower() for i in s if i.isalnum()] return n == n[::-1]
答案
指針方案,沒有去考慮這麼寫(因為畢竟麻煩)
def isPalindrome(self, s): l, r = 0, len(s)-1 while l < r: while l < r and not s[l].isalnum(): l += 1 while l <r and not s[r].isalnum(): r -= 1 if s[l].lower() != s[r].lower(): return False l +=1; r -= 1 return True
3. Valid Palindrome II
題目
Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.
Example 1:
Input: “aba”
Output: True
Example 2:
Input: “abca”
Output: True
Explanation: You could delete the character ‘c’.
Note:
The string will only contain lowercase characters a-z. The maximum length of the string is 50000.
思路與解答
卧槽,如果每刪一個對比一次。。。感覺會超時的吧
不對,先比較迴文,出錯再考慮方案
這樣就要用到之前的指針方案了
在處理第一個錯誤那裡出現了問題,怎麼保證你刪的那個是對的呢。。。感覺要完全比較下去。
def huiwen(n,f): l,r = 0, len(n)-1 while l < r: if n[l]!= n[r]: if f: return huiwen(n[l+1:r+1],0) or huiwen(n[l:r],0) else: return False l += 1 r -= 1 return True return huiwen(s,1)
因為要套幾遍,所以我直接寫個函數了
可惜速度不行啊
答案
emmmm為啥我要去用指針呢?
1 rev = s[::-1] 2 if s == rev: return True 3 l = len(s) 4 for i in xrange(l): 5 if s[i] != rev[i]: 6 return s[i:l-i-1] == rev[i+1:l-i] or rev[i:l-i-1] == s[i+1:l-i] 7 return False
差不多的方案
1 def validPalindrome(self, s): 2 i = 0 3 while i < len(s) / 2 and s[i] == s[-(i + 1)]: i += 1 4 s = s[i:len(s) - i] 5 return s[1:] == s[1:][::-1] or s[:-1] == s[:-1][::-1]
4. Valid Parentheses
題目
Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.
The brackets must close in the correct order, “()” and “()[]{}” are all valid but “(]” and “([)]” are not.
思路與解答
堆棧?
如何將字典里的兩個括弧關聯起來?
不能根據values查找key。。。。
d.items()怎麼不對??
好像可以去掉,後面還有判斷的
1 stack=[] 2 d={")":"(","}":"{","]":"["} 3 for n in s: 4 if n in d.values(): 5 stack.append(n) 6 elif n in d.keys(): 7 if not stack:return False 8 x = stack.pop() 9 if x != d[n]: 10 return False 11 else: 12 return False 13 return stack == []
速度還行
答案
差不多嘛(但是比我的短)
1 stack = [] 2 pairs = {'(': ')', '{': '}', '[': ']'} 3 for char in s: 4 if char in pairs: 5 stack.append(pairs[char]) 6 else: 7 if len(stack) == 0 or stack.pop() != char: 8 return False 9 return not stack
5. Valid Perfect Square
題目
Given a positive integer num, write a function which returns True if num is a perfect square else False.
Note: Do not use any built-in library function such as sqrt.
Example 1:
Input: 16
Returns: True
Example 2:
Input: 14
Returns: False
思路與解答
意思是這個數是不是其它整數的平方?
感覺需要搜一下判斷方法
完全平方數等於1+3+5+7+9+….+2n-1
比暴力版快
1 n=1 2 while num > 0: 3 num -= n+n-1 4 n += 1 5 return num == 0
別人有更快的,估計是方法不一樣
答案
emmm就是之前的某個公式,居然比我的快。
1 def isPerfectSquare(self, num): 2 x = num 3 r = x 4 while r*r > x: 5 r = (r + x/r) / 2 6 return r*r == x