leetcode-explore-learn-數(shù)據(jù)結(jié)構(gòu)-數(shù)組3-字符串

• 1.簡(jiǎn)述
• 2.例題
• • 2.1 二進(jìn)制求和
  • 2.2實(shí)現(xiàn)strStr()
  • 2.3最長(zhǎng)公共前綴

本系列博文為leetcode-explore-learn子欄目學(xué)習(xí)筆記，如有不詳之處，請(qǐng)參考leetcode官網(wǎng)：https://leetcode-cn.com/explore/learn/card/array-and-string/198/introduction-to-array/768/

1.簡(jiǎn)述

字符串是字符構(gòu)成的數(shù)組。

字符串一些常用的函數(shù)：
(1)比較函數(shù)，Python支持云算法重載，可以使用"=="來(lái)比較字符串。
(2)可修改性，在Python中字符串是一個(gè)不可改寫(xiě)的數(shù)組；一經(jīng)定義只能訪問(wèn)字符串中的元素，而不能直接改變某個(gè)元素。在C++中字符串是可修改的。
(3)字符串連接，python 中支持兩個(gè)字符串直接相加操作進(jìn)行字符串連接

2.例題

2.1 二進(jìn)制求和

給一個(gè)二進(jìn)制字符串，返回他們的和，用二進(jìn)制表示。
基本思想:
兩個(gè)字符串諸位相加，設(shè)置一個(gè)符號(hào)位flag用于存儲(chǔ)進(jìn)位信息
難點(diǎn)邊界條件的確定：char=int(a[i])+int(b[i])+flag，chat的可能取值：0,1,2,3
（1）i=[-1,-2,-l_min]遍歷相加逐個(gè)元素至較短字符串遍歷完成
(2) i=[-l_min-1,-l_min-2m,…,-l_max]:char=flag+int(a[i])，char的可能取值：0,1,2
(3)最后還需要檢查是否有進(jìn)位情況

class Solution(object):def addBinary(self, a, b):""":type a: str:type b: str:rtype: str"""res=[]l_a=len(a)l_b=len(b)l_min=min(l_a,l_b)l_max=max(l_a,l_b)flag=0for i in range(-1,-l_min-1,-1):char=int(a[i])+int(b[i])+flagflag=0if char==0:res.append(0)elif char==1:res.append(1)elif char==2:res.append(0)flag=1else:res.append(1)flag=1print (res,flag)if l_a>l_b:for i in range(-l_min-1,-l_max-1,-1):#print(i,res,flag)char=flag+int(a[i])flag=0if char==0:res.append(0)elif char==1:res.append(1)elif char==2 :res.append(0)flag=1if l_a<l_b:#print(l_min,l_max)for i in range(-l_min-1,-l_max-1,-1):#print(i,flag,res)char=flag+int(b[i])flag=0if char==0:res.append(0)elif char==1:res.append(1)elif char==2:res.append(0)flag=1#print(res,flag)if flag==1:res.append(1)l_res=len(res)res_s=""for i in range(l_res-1,-1,-1):res_s+=str(res[i])return res_

2.2實(shí)現(xiàn)strStr()

給定一個(gè)haystack字符串和一個(gè)needle字符串，在haystack字符串中找出needle字符串出現(xiàn)的第一個(gè)位置。如果不存在則返回0.

思路，遍歷haystack字符串，找出needle字符串的第一個(gè)字符，然后依次往后找，直至所有都匹配上然后返回結(jié)果。

注意點(diǎn)：
（1）當(dāng)needle是空時(shí)，如果返回-1（說(shuō)明在一個(gè)字符串中找不到空字符串）；如果返回0(說(shuō)明haysta[0]開(kāi)始的字符串匹配了空字符串)–c++語(yǔ)言中是這么定義的
（2）兩個(gè)都為空時(shí)，返回0
（3）len(haystack)<len(needle)直接返回-1

class Solution(object):def strStr(self, haystack, needle):""":type haystack: str:type needle: str:rtype: int"""l_s=len(haystack)l_n=len(needle)if l_n==0:return 0if l_s==0:return -1if l_s<l_n:return -1for i in range(l_s-l_n+1): # i:[0,1,...,l_s-l-n]for j in range(l_n): # i:[0,1,...,l_n-1]l-s-l_n#print(i,j)if haystack[i+j]!=needle[j]:breakif j==l_n-1:return ireturn -1

2.3最長(zhǎng)公共前綴

編寫(xiě)一個(gè)函數(shù)來(lái)查找字符串?dāng)?shù)組中的最長(zhǎng)公共前綴。
如果公共前綴前綴不存在，返回空字符串""
用一個(gè)win區(qū)存公用前綴，找最短的字符串，將其元素依次加入win中。判斷剩余字符串是否有該前綴字符。

class Solution(object):def longestCommonPrefix(self, strs):""":type strs: List[str]:rtype: str"""n=len(strs)if n==0:return ""short_index=-1l_min=float("INF")for i in range(n):if len(strs[i])<l_min:l_min=len(strs[i])short_index=iwin=""i=0while(i<l_min):win=strs[short_index][:i+1]for j in range(n):if strs[j][:i+1]!=win:return win[:i]i+=1return win

總結(jié)

以上是生活随笔為你收集整理的算法(5)-leetcode-explore-learn-数据结构-字符串的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。