沒事的時候打算開始玩一玩leetcode，不然天天寫代碼，卻對算法沒啥認識還是有點尷尬的。雖說是做題，其實大部分就是為了看看別人牛逼的思路。盡量每天一題把～
創(chuàng)新互聯(lián)公司專注于企業(yè)網(wǎng)絡(luò)營銷推廣、網(wǎng)站重做改版、巴中網(wǎng)站定制設(shè)計、自適應(yīng)品牌網(wǎng)站建設(shè)、H5響應(yīng)式網(wǎng)站、商城網(wǎng)站制作、集團公司官網(wǎng)建設(shè)、成都外貿(mào)網(wǎng)站制作、高端網(wǎng)站制作、響應(yīng)式網(wǎng)頁設(shè)計等建站業(yè)務(wù)，價格優(yōu)惠性價比高，為巴中等各大城市提供網(wǎng)站開發(fā)制作服務(wù)。
重慶分公司
重慶分公司
給定一個整數(shù)數(shù)組和一個目標值，找出數(shù)組中和為目標值的兩個數(shù)。
你可以假設(shè)每個輸入只對應(yīng)一種答案，且同樣的元素不能被重復(fù)利用。
例：
給定 nums = [2, 7, 11, 15], target = 9
因為 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]第一種方法就是便利數(shù)組，隨著數(shù)組長度增加，執(zhí)行時間指數(shù)型增加。
#時間復(fù)雜度：O(n^2)
#空間復(fù)雜度：O(1)
func twoSum(nums []int, target int) []int {
for firstIndex,firstNum := range nums{
for secondIndex,secondNum := range nums{
if firstIndex != secondIndex && firstNum + secondNum == target{
return []int{firstIndex, secondIndex}
}
}
}
return nil
}第二種方式是以空間換時間，把數(shù)據(jù)存在哈希表里面，最多只用完全遍歷一次數(shù)組，就能得到結(jié)果。
#時間復(fù)雜度：O(n)
#空間復(fù)雜度：O(n)
func twoSumHash(nums []int, target int) []int {
m := make(map[int]int)
for index,num := range nums{
i,ok := m[target - num]
if ok {
return []int{i,index}
}
m[num] = index
}
return nil
}題目鏈接：https://leetcode-cn.com/problems/two-sum/description/
給定兩個非空鏈表來表示兩個非負整數(shù)。位數(shù)按照逆序方式存儲，它們的每個節(jié)點只存儲單個數(shù)字。將兩數(shù)相加返回一個新的鏈表。
你可以假設(shè)除了數(shù)字 0 之外，這兩個數(shù)字都不會以零開頭。
示例：
輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出：7 -> 0 -> 8
原因：342 + 465 = 807這個題主要有兩個地方卡了我一下，第一，輸入的兩個鏈表可能是不一樣長的，第二，最后一位相加可能會進1，所以此時，輸出比輸入多一位數(shù)字，就是多一個節(jié)點。
我在思考次題目時候，想方設(shè)法的想把輸出鏈表的第一個節(jié)點，填入數(shù)字，其實可以這樣。鏈表第一個節(jié)點可以為空，然后從第二個節(jié)點賦值，最后return時候，返回head.Next?？瓤龋缫淹洰?dāng)年學(xué)數(shù)據(jù)結(jié)構(gòu)的時候，就是這么干的。
我的答案：
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
l := new(ListNode)
temp := l
lsum := 0
for {
if l1 != nil{
lsum += l1.Val
l1 = l1.Next
}
if l2 != nil{
lsum += l2.Val
l2 = l2.Next
}
temp.Val = lsum % 10
lsum = lsum / 10
if lsum != 0 || l1 != nil || l2 != nil{
nextNode := new(ListNode)
temp.Next = nextNode
temp = temp.Next
}else{
break
}
}
return l
}網(wǎng)站給出的答案：
func addTwoNumbers2(l1 *ListNode, l2 *ListNode) *ListNode{
dummyHead := new(ListNode)
p,q,curr := l1,l2,dummyHead
carry := 0
for p !=nil || q != nil{
x,y := 0,0
if p != nil {
x = p.Val
}
if q != nil {
y = q.Val
}
sum := x + y + carry
carry = sum /10
curr.Next = new(ListNode)
curr = curr.Next
curr.Val = sum % 10
if p !=nil{
p = p.Next
}
if q !=nil{
q = q.Next
}
}
if carry > 0{
curr.Next = &ListNode{Val:carry}
}
return dummyHead.Next
}網(wǎng)站的答案會把l1和l2賦值給一個臨時變量，這樣就不會影響函數(shù)外的l1，l2，這是我所忽略的。
網(wǎng)站的答案，把sum和carry分成兩個變量，增強了可讀性，我放在一起，基本上就看不出來為啥，除以10賦值給sum。然后我變量命名過于隨意。
看見字符串匹配的題的就慫，所以卡了好幾天不敢做。我自己的答案倒是嘗試快10次了。才通過所有的測試?？拥狞c還是不少的。說下我的實現(xiàn)思路吧。
func lengthOfLongestSubstring(s string) int {
filter := make(map[int32]int) // 比較喜歡用哈希表統(tǒng)計重復(fù)
lastKey := 0 // 記錄重復(fù)時，與本次重復(fù)的上一次重復(fù)點的下一位的index（非重復(fù)開始的位置）
//比如當(dāng)前字母的index為10，與之重復(fù)的字母的index為5，那么lastKey的值就賦值為5
max := 0 //大連續(xù)不重復(fù)字串的長度
for k,v := range s{ //遍歷字串
index,ok := filter[v] //判斷是否發(fā)生重復(fù)
if ok { //發(fā)生重復(fù)
if k - lastKey >max{ //計算重復(fù)點到上一個重復(fù)點的長度
max = k - lastKey
}
for i := lastKey;i max{ //有可能中間某個點，到最后一個字母都沒有重復(fù)，所以不會觸發(fā)ok里面的檢測，因此判斷非重復(fù)點到最后一個字母的距離。
max = len(s) - lastKey
}
return max
} 網(wǎng)站給的答案：
# i和j就是字串的開始坐標和結(jié)束坐標。遍歷字符串s，如果當(dāng)前字母，在字串i，j中沒有重復(fù)，則j加1，即字串長度加一，如果當(dāng)前字母在i，j中有重復(fù)的，則刪除字串的第一個字母。因為有可能重復(fù)的字母在i，j中間，所以就會一直刪除字串的第一個字母，直到刪除至子串中沒有重復(fù)的字母。就得到了，非重復(fù)字串。
#思路是真的好呀。之前我一直糾結(jié)怎么，當(dāng)字串中有重復(fù)字母的時候，怎么確定，map中刪除哪些key，網(wǎng)站的思路就很流暢呀?。?！贊！
func lengthOfLongestSubstring(s string) int {
filter := make(map[uint8]int)
n := len(s)
i,j,max := 0,0,0
for i < n && j < n {
_,ok := filter[s[j]]
if !ok{
filter[s[j]] = 0
j++
if j - i > max{
max = j - i
}
}else {
delete(filter,s[i])
i++
}
}
return max
}#其實放入map中的值并不需要刪除....對比一下，我寫的答案太low了。。。
func lengthOfLongestSubstring(s string) int {
filter := make(map[uint8]int)
n := len(s)
max := 0
for i,j := 0,0; j < n; j++ {
index,ok := filter[s[j]] #判斷當(dāng)前字母是否在map中已存在
if ok{ #如果存在，就把index賦值給i
if index > i { #比如map中有一個字母a，他的index為3,如果當(dāng)前字母也為a，就吧之前a的index保存到i中
i = index #為什么判斷大小呢？假如a的index為3，他前面有一個字母b，當(dāng)前字母為a，所以i為3，如果下一個字母為b，因為上一個a之前有一個b，所以b是存在的，但是上一個b的在字母a前面，所以i不變。這就是map不用刪除key的原因
}
}
if j - i +1 > max{
max = j - i + 1
}
filter[s[j]] = j+1
}
return max
}題目：給兩個有序的數(shù)組，取兩個長度為n,m的數(shù)組的中位數(shù)，并且時間復(fù)雜度為Olog(min(n,m))
例1：
nums1 = [1, 3]
nums2 = [2]
中位數(shù)是 2.0例2:
nums1 = [1, 2]
nums2 = [3, 4]
中位數(shù)是 (2 + 3)/2 = 2.5其實這道題考的排序算法，所以哪個排序算法的時間復(fù)雜度是O(log n)呢，還給了兩個有序的數(shù)組，第一想到的就是歸并排序的最后一步。
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
i,j := 0,0
sorted := make([]int,0)
for i < len(nums1) && j < len(nums2){
if nums1[i] > nums2[j]{
sorted = append(sorted,nums2[j])
j++
}else {
sorted = append(sorted,nums1[i])
i++
}
}
sorted = append(sorted,nums1[i:]...)
sorted = append(sorted,nums2[j:]...)
n := len(sorted)
if n % 2 ==0{
return (float64(sorted[n/2-1]) + float64(sorted[n/2]))/2
}
return float64(sorted[(n-1)/2])
}嚶嚶嚶，網(wǎng)站答案看的腦殼疼。。。。
看完網(wǎng)站的答案，我掐指一算，我的時間復(fù)雜度是O(min(n,m)),想要時間復(fù)雜度為O(log(mint(n,m))),就得用二分法。分析過程好復(fù)雜，腦殼疼。實現(xiàn)也復(fù)雜，要考慮的因素好多。。。。
創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國云服務(wù)器，動態(tài)BGP最優(yōu)骨干路由自動選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證， 機房獨有T級流量清洗系統(tǒng)配攻擊溯源，準確進行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動現(xiàn)已開啟，新人活動云服務(wù)器買多久送多久。
