五个实用的Python案例题,非常有用!

2018-07-10 00:03:40来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

  • 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

 


			   
			   

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:《11招玩转网络安全》之第三招:Web暴力破解-Low级别

下一篇:俄罗斯方块(三):&quot;流动&quot;的方块