1、根據數字返回相應位置數字?
def get_digit(num, i):# i=0 個位 1 十位 2 百位...return num // (10 ** i) % 10# print(get_digit(12345, 6))2、列表反轉，不用內置函數
def reverse_list(li):n = len(li)for i in range(n // 2):li[i], li[n-i-1] = li[n-i-1], li[i]return li# print(reverse_list([1,2,3,4,5,6]))?3、數字反轉，不用切片，不用內置函數
# 123->321 12300->321
def reverse_int(num):is_neg = Falseif num < 0:is_neg = Truenum = -1 * numres = 0while num > 0:res = res * 10res += num % 10num = num // 10if is_neg:res = res * -1return res# print(reverse_int(-123001))4、數字轉列表
def int2list(num):li = []while num > 0:li.append(num % 10)num = num // 10li.reverse()return li# print(int2list(123456))5、一段n個臺階組成的樓梯,小明從樓梯的最底層向最高層處前進,他可以一次邁一階或兩階,問:他有多少種不同的走法?
def func(n):if n==0 or n==1:return 1else:return f(n-1)+f(n-2)
6、按照單詞反轉給定句子。例如，輸入"what is your name"，返回"name your is what"。請不要使用諸如''.split, [::-1]等時間/空間復雜度不是O(1)的函數
def str_reverse(str,i,j):while i<j:str[i],str[j]=str[j],str[i]i+=1j-=1
def sentence_reverse(sentence):sent_list = list(sentence)i=0len_list = len(sent_list)while i<len_list:if sent_list[i] !=' ':start = iend=start+1while (end<len_list) and (sent_list[end]!=' '):end += 1str_reverse(sent_list,start,end-1)i = endelse:i+=1sent_list.reverse()return(''.join(sent_list))棧，隊列相關
括號匹配問題：給一個字符串，其中包含小括號、中括號、大括號，求該字符串中的括號是否匹配
def brace_match(s):stack = []d = {'(':')', '[':']', '{':'}'}for ch in s:if ch in {'(', '[', '{'}:stack.append(ch)elif len(stack) == 0:print('多了右括號%s' % ch)return Falseelif d[stack[-1]] == ch:stack.pop()else:print('括號%s處不匹配' % ch)return Falseif len(stack) == 0:return Trueelse:print("剩余左括號未匹配")return Falseprint(brace_match('[]{{}[]{()})}'))用兩個棧實現隊列
class QueueStack(object):def __init__(self):self.l1 = []self.l2 = []def push(self,a):self.l1.append(a)def pop(self):if not self.l2:for i in range(len(self.l1)):a = self.l1.pop()self.l2.append(a)if self.l2:return self.l2.pop()else:return False一行代碼模擬 Linux 中的 tail
# import queue # 不能設置大小
from collections import deque# q = deque() # 雙向隊列，可以設置大小，超過大小，后進隊的數據會使前進隊的數據被丟掉
# q.append(1)
# q.append(2)
# q.append(3)
# print(q.popleft())
# head tail# print(deque(open('test.txt', 'r', encoding='utf-8'), 5))?給兩個字符串s和t，判斷t是否為s的重新排列后組成的單詞：
- ns?= "anagram",?t?= "nagaram", return true.
- ns?= "rat",?t?= "car", return false.
class Solution:def isAnagram(self, s, t):dict1 = {} # 用字典來維護字符的數量dict2 = {}for ch in s:dict1[ch] = dict1.get(ch, 0) + 1 # 沒有就新建，有就加1for ch in t:dict2[ch] = dict2.get(ch, 0) + 1return dict1 == dict2"""
輸入："anagram"，"nagaram"
輸出：true
Runtime: 32 ms
"""給定一個m*n的二維列表，查找一個數是否存在。
列表有下列特性：
- 每一行的列表從左到右已經排序好。
- 每一行第一個數比上一行最后一個數大。
- leetcode地址：https://leetcode.com/problems/search-a-2d-matrix/description/
class Solution:def searchMatrix(self, matrix, target):h = len(matrix) # 高if h == 0:return Falsew = len(matrix[0]) # 列if w == 0:return Falseleft = 0right = w * h - 1while left <= right:mid = ((left + right)) // 2i = mid // wj = mid % w if matrix[i][j] == target:return Trueelif matrix[i][j] > target:right = mid - 1else:left = mid + 1else:return False給定一個列表和一個整數，設計算法找到兩個數的下標，使得兩個數之和為給定的整數。保證肯定僅有一個結果。
- leetcode地址：https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/
- 例如，列表[1,2,5,4]與目標整數3，1+2=3，結果為(0,1).
# [2,1,3,5] 4
# 第一種：循環 O(n^2)
def two_sum_1(li, num):for i in range(len(li)):for j in range(len(li)):if i != j:if li[i] + li[j] == num:return i, jreturn -1,-1# 循環減半O(n^2)
def two_sum_1_1(li, num):for i in range(len(li)):for j in range(i+1, len(li)):if li[i] + li[j] == num:return i, jdef bin_search(li, val, low, high):while low <= high: # 只要候選區不空,繼續循環mid = (low + high) // 2if li[mid] == val:return midelif li[mid] < val:low = mid + 1else: # li[mid] > valhigh = mid - 1return -1# 第二種：固定一個，查找一個，查找用二分，要求有序 O(nlogn)
def two_sum_2(li, num):for i in range(len(li)):a = li[i]b = num - aj = bin_search(li, b, i+1, len(li)-1)if j >= 0:return i, j# 第三種：左右互搏，要求有序 O(n)
def two_sum_3(li, num):i = 0j = len(li)-1while i < j:s = li[i] + li[j]if s == num:return i, jelif s < num:i += 1elif s > num:j -= 1return -1,-1# 第四種：用字典，字典是O(1),不要求有序 O(n)
def two_sum_4(li, num):dic = {}for i in range(len(li)):a = li[i]b = num - li[i]if b not in dic:dic[a] = ielse:return dic[b], i# 2-sum問題
# 無序列表: 4哈希表(最優)
# 有序列表: 3兩邊找(最優)# 3-sum問題
# 1.暴力枚舉法 O(n^3)
# 2.二分查找 O(n^2logn)
# 3.兩邊找 O(n^2) (最優,不占空間)
# 4.哈希表 O(n^2) (次優)# 2-sub問題
# 哈希表 O(n) 定住一個找兩個?
