8000 add pow(x,n) · jiaxinhuang/python-test-code@a7b7d0a · GitHub
[go: up one dir, main page]
Skip to content

Commit a7b7d0a

Browse files
jiaxinhuangjiaxinhuang
committed
add pow(x,n)
1 parent b3d3396 commit a7b7d0a

File tree

6 files changed

+208
-0
lines changed

6 files changed

+208
-0
lines changed

‎leetcode/GroupAnagrams.md

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
# 题目说明
2+
3+
这题是从给定的一个字符串数组中根据字符串含有的字符进行聚合，这题的关键在于将字符串有序化，具体步骤是将之从字符串变为列表，然后排序再变成字符串的过程，这里使用了`lambda`函数进行转化，直接变换的方式在排序一步总会出错。实现代码如下：
4+
5+
```python
6+
class Solution(object):
7+
def groupAnagrams(self, strs):
8+
"""
9+
:type strs: List[str]
10+
:rtype: List[List[str]]
11+
"""
12+
m = {}
13+
res = []
14+
for i, str in enumerate(strs):
15+
str = ''.join((lambda x:(x.sort(), x)[1])(list(str)))
16+
if str not in m:
17+
m[str] = [i]
18+
else:
19+
m[str].append(i)
20+
21+
for key in m:
22+
temp = []
23+
for i in m[key]:
24+
temp.append(strs[i])
25+
res.append(temp)
26+
return res
27+
```
28+

‎leetcode/GroupAnagrams.py

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
#-*- coding:utf-8 -*-
2+
'''
3+
Created on 2017年5月25日
4+
5+
@author: huangjiaxin
6+
'''
7+
class Solution(object):
8+
def groupAnagrams(self, strs):
9+
"""
10+
:type strs: List[str]
11+
:rtype: List[List[str]]
12+
"""
13+
m = {}
14+
res = []
15+
for i, str in enumerate(strs):
16+
str = ''.join((lambda x:(x.sort(), x)[1])(list(str)))
17+
if str not in m:
18+
m[str] = [i]
19+
else:
20+
m[str].append(i)
21+
22+
for key in m:
23+
temp = []
24+
for i in m[key]:
25+
temp.append(strs[i])
26+
res.append(temp)
27+
return res
28+
29+
if __name__ == '__main__':
30+
strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
31+
print Solution().groupAnagrams(strs)

‎leetcode/Powxn.md

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
# 题目说明
2+
3+
这题就是求一个幂运算，最大的问题是一个超时的问题。
4+
5+
只用递归方式，超时：
6+
7+
```python
8+
def myPow(self, x, n):
9+
"""
10+
:type x: float
11+
:type n: int
12+
:rtype: float
13+
"""
14+
if n == 0:
15+
return 1
16+
half = self.myPow(x, n/2)
17+
if n%2 == 0:
18+
return half * half
19+
else:
20+
return half*half*x
21+
```
22+
23+
改进的递归：
24+
25+
```python
26+
class Solution(object):
27+
def myPow(self, x, n):
28+
"""
29+
:type x: float
30+
:type n: int
31+
:rtype: float
32+
"""
33+
if n == 0:
34+
return 1
35+
elif n < 0:
36+
return 1/self.myPow(x, -n)
37+
elif n % 2:
38+
return x * self.myPow(x, n-1)
39+
return self.myPow(x*x, n/2)
40+
```
41+
42+
按位进行运算：
43+
44+
```python
45+
class Solution(object):
46+
def myPow(self, x, n):
47+
"""
48+
:type x: float
49+
:type n: int
50+
:rtype: float
51+
"""
52+
if n < 0:
53+
x = 1/x
54+
n = -n
55+
res = 1
56+
while n:
57+
if n & 1:
58+
res *= x
59+
x *= x
60+
n >>= 1
61+
return res
62+
```
63+
64+
65+

‎leetcode/Powxn.py

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
#-*- coding:utf-8 -*-
2+
'''
3+
Created on 2017年5月25日
4+
5+
@author: huangjiaxin
6+
'''
7+
class Solution(object):
8+
def myPow(self, x, n):
9+
"""
10+
:type x: float
11+
:type n: int
12+
:rtype: float
13+
"""
14+
if n < 0:
15+
x = 1/x
16+
n = -n
17+
res = 1
18+
while n:
19+
if n & 1:
20+
res *= x
21+
x *= x
22+
n >>= 1
23+
return res
24+
25+
26+
if __name__ == '__main__':
27+
print pow(2, 2)

‎leetcode/RotateImage.md

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
# 题目说明
2+
3+
这题可以理解为是求一个矩阵顺时针旋转$90^\circ$，这里的难点在于找到交换元素的顺序，这里采用的一种二段翻转方法，先沿着两条对角线中的一条交换元素，再沿着一条中线翻转即可。实现代码如下：
4+
5+
```python
6+
class Solution(object):
7+
def rotate(self, matrix):
8+
"""
9+
:type matrix: List[List[int]]
10+
:rtype: void Do not return anything, modify matrix in-place instead.
11+
"""
12+
L = len(matrix)
13+
for i in range(L):
14+
for j in range(L-i-1):
15+
print matrix[i][j],matrix[L-j-1][L-i-1]
16+
tmp = str(matrix[i][j])
17+
matrix[i][j] = matrix[L-j-1][L-i-1]
18+
matrix[L-j-1][L-i-1] = int(tmp)
19+
for i in range(L/2):
20+
for j in range(L):
21+
tmp = matrix[i][j]
22+
matrix[i][j] = matrix[L-i-1][j]
23+
matrix[L-i-1][j] = tmp
24+
return
25+
```
26+
27+
注意：这里有一个更直接和直观的方法，就是直接重新构造一个矩阵，提取每一列的数据构造一个新的行，但是这里需要不使用其他内存和其他放回地址，所以只能使用交换原矩阵对应位置元素的值。

‎leetcode/RotateImage.py

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
#-*- coding:utf-8 -*-
2+
'''
3+
Created on 2017年5月25日
4+
5+
@author: huangjiaxin
6+
'''
7+
class Solution(object):
8+
def rotate(self, matrix):
9+
"""
10+
:type matrix: List[List[int]]
11+
:rtype: void Do not return anything, modify matrix in-place instead.
12+
"""
13+
L = len(matrix)
14+
for i in range(L):
15+
for j in range(L-i-1):
16+
print matrix[i][j],matrix[L-j-1][L-i-1]
17+
tmp = str(matrix[i][j])
18+
matrix[i][j] = matrix[L-j-1][L-i-1]
19+
matrix[L-j-1][L-i-1] = int(tmp)
20+
for i in range(L/2):
21+
for j in range(L):
22+
tmp = matrix[i][j]
23+
matrix[i][j] = matrix[L-i-1][j]
24+
matrix[L-i-1][j] = tmp
25+
return
26+
27+
if __name__ == '__main__':
28+
matrix = [[1,2,3], [4,5,6], [7,8,9]]
29+
Solution().rotate(matrix)
30+
print matrix

0 commit comments

Comments
 (0)
0