[数据结构]散列表、字符串

发表于
参加Datawhale的编程计划的第4个任务，涉及散列表、字符串，用python实现。。

散列表

练习：两数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    # @return a tuple, (index1, index2)
    def twoSum(self, num, target):
        index = []
        numtosort = num[:]; numtosort.sort()
        i = 0; j = len(numtosort) - 1
        while i < j:
            if numtosort[i] + numtosort[j] == target:
                for k in range(0,len(num)):
                    if num[k] == numtosort[i]:
                        index.append(k)
                        break
                for k in range(len(num)-1,-1,-1):
                    if num[k] == numtosort[j]:
                        index.append(k)
                        break
                index.sort()
                break
            elif numtosort[i] + numtosort[j] < target:
                i = i + 1
            elif numtosort[i] + numtosort[j] > target:
                j = j - 1

        return (index[0]+1,index[1]+1)

字符串

练习：Reverse String （反转字符串）

1
2
3
class Solution(object):
    def reverseString(self, s):
        return s[::-1]

Reverse Words in a String（翻转字符串里的单词）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    # @param s, a string
    # @return a string
    def reverseWords(self, s):
        words = s.split(' ')
        
        if len(words) < 2 :
            return s
        
        tmp = ""
        for word in words:
            word = word.replace(' ','')
            if word != "" :
                tmp = word + " " + tmp
        
        tmp = tmp.strip()
        
        return tmp

String to Integer (atoi)（字符串转换整数 (atoi)）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
    # @return an integer
    def atoi(self, str):
        INT_MAX = 2147483647; INT_MIN = -2147483648
        sum = 0
        sign = 1
        i = 0
        if str == '':
            return 0
        while i < len(str) and str[i].isspace():
            i += 1
        if i < len(str) and str[i] == '-':
            sign = -1
        if i < len(str) and (str[i] == '-' or str[i] == '+'):
            i += 1
        while i < len(str) and str[i].isdigit():
            digit = int(str[i])
            if INT_MAX/10 >= sum:
                sum *= 10
            else:
                if sign == 1:
                    return INT_MAX
                else:
                    return INT_MIN
            if INT_MAX - digit >= sum:
                sum += digit
            else:
                if sign == 1:
                    return INT_MAX
                else:
                    return INT_MIN
            i += 1
        return sign*sum

相关链接

编程计划的第4个任务
第四次任务 打卡表格