剑指offer

 # 从右上角开始遍历，如果目标值大于右上角的值，去掉所在的行，对所在的列进行遍历，反之，小于，去掉所在的列，对所在的行进行遍历
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        row = 0                   
        col = len(array[0])-1
        while row<len(array) and col>=0:
            if array[row][col] == target:
                return True
            elif array[row][col] > target:
                col -= 1
            else:
                row += 1
        return False

请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

# 首先从前往后遍历字符串，找出空格的个数，然后从后往前遍历字符串，找到空格并将其替换。
def replace_space(s):
    space_count = 0
    s_length = len(s)
    for i in s:
        if i.isspace():
            space_count += 1
    new_s_length = s_length + space_count * 2
    new_s_list = [" "] * new_s_length    # 创造一个新的列表储存新的字符串
    while s_length:
        if s[s_length-1].strip():
            new_s_list[s_length - 1 + space_count * 2] = s[s_length - 1]
            s_length -= 1
        else:
            new_s_list[s_length - 1 + space_count * 2] = "0"
            new_s_list[s_length - 1 + space_count * 2 - 1] = "2"
            new_s_list[s_length - 1 + space_count * 2 - 2] = "%"
            space_count -= 1
            s_length -= 1
    return "".join(new_s_list)


a = "I am nxr"
ret = replace_space(a)
print(ret)


更新版

def replace_space(str1):
    if len(str1) == 0:
        return ""
    lis = []
    for i in str1:
        if i.isspace():
            lis.append("%20")
        else:
            lis.append(i)
    return "".join(lis)


print(replace_space("we are happy"))

从一个字符串中找到有且只有出现过两次的字符，并将其索引返回。

def two_times(a):
    dic = {}
    for value, key in enumerate(a):
        if key in dic:
            if dic[key][1] == 2:
                dic.pop(key)
            else:
                dic[key][1] += 1
        else:
            dic[key] = [value, 1]
    for key in dic:
        if dic[key][1] == 2:
            return [key, dic[key][0]]

打印矩阵斜对角线上的数

def print_right(matrix):
    if not matrix:   # 检验输入的合法性
        return []
    row = len(matrix)
    col = len(matrix[0])
    k = 0       # 设置变量控制j的值
    result = []  # 存储结果
    for i in range(row):
        for j in range(k, col):
            lst = []   # 存储每一条对角线上的值
            i1, j1 = i, j  # 防止因i,j改变导致循环变量的出错
            while i1 <= row - 1 and j1 >= 0:
                lst.append(matrix[i1][j1])
                j1 -= 1
                i1 += 1
            result.append(lst)
            if i == 0 and j == col-1:  # 当遍历完右上角开头的一条对角线后，让j固定为col-1
                k = col-1
    return result

判断输入是否合法，例如“（【{}】）”

def func(a):
    dic = {"]": "[", ")": "(", "}": "{"}
    lis = []   # 堆栈

　　for i in a:
    　　if i not in dic:
        　　lis.append(i)
    　　elif not lis or dic[i] != lis.pop():  # 栈为空或左右扩号不匹配
        　　return False
　　return not lis

计算圆周率

蒙特卡罗方法 求圆周pi
import random as r


def func(n):
    count = 0
    for i in range(n):
        x = r.random()
        y = r.random()
        if x**2 + y**2 <= 1:
            count += 1
    pi = count/n * 4
    return pi

# 公式法 (pi**2)/6 = 1/1**2 + 1/2**2 + 1/3**3 + 1/4**4 + ......
from math import sqrt
def func(n):
    total = 0
    for i in range(1, n):
        total += 1/i**2
    return sqrt(total*6)


ret = func(10000)
print(ret)

斐波那契数列

def func(n):
    x, y = 1, 1
    for i in range(2, n):
        x, y = y, x + y
    return y

将字符串转化为整数 (注意各种异常情况的处理）

def StrToInt(str1):
    if len(str1) == 0 and str.isspace():
        return 0
    isNegitive = str1[0] == "-"
    ret = 0
    for i in range(len(str1)):
        c = str1[i]
        if i == 0 and (c == "-"or c == "+"):  # 符号判定
            continue
        if c < "0" or c > "9":  # 非法输入
            return 0
        ret = ret*10 + ord(c)-ord("0")  # 每循环一次就进一次位*10
    return -ret if isNegitive else ret  # 三目运算符


str1 = "0123"
print(strToint(str1))