LeetCode算法题0-50

第一题

思路

1
2
1.创建长度为nums的map。以值为key，下标为value
2.遍历nums，判断map的target-value作为key的下标值是否存在，存在则得出结论

代码

1
2
3
4
5
6
7
8
9
10
11
func twoSum(nums []int, target int) []int {
    index := make(map[int]int,len(nums))

    for k,v := range nums{
        if i ,ok := index[target-v];ok{
            return []int{i,k}
        }
        index[v] = k
    }
    return nil
}

第二题

思路

1
2
1.定义空链表，用两个参数指向同一个地址，一个写一个读
2.进位使用除法，当前位使用余数

代码

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
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    list1 := &ListNode{}
    list2 := list1
    carry := 0
    for l1!=nil||l2!=nil||carry>0{
        if l1!=nil{
            carry += l1.Val
            l1 = l1.Next
        }
        if l2!=nil{
            carry += l2.Val
            l2 = l2.Next
        }
                
        num := carry%10
        carry = carry/10

        list1.Next = &ListNode{Val:num}
        list1 = list1.Next
    }
    return  list2.Next

}

第三题

思路

1
2
使用map，字符串使用ASCII码，先定义所有ASCII码作为key的值都为-1
遍历字符串时，查看其作为key的值是否为-1，为-1则不存在，不为-1且位置大于left则重复

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func lengthOfLongestSubstring(s string) int {
    mapkey := make(map[int]int)
    for i := 0;i<128;i++{
        mapkey[i] = -1
    }
    // fmt.Print(int(s[0]))
   
    left,maxlen := 0,0
    for i := 0;i<len(s);i++{
        if mapkey[int(s[i])]>=left{
            left = mapkey[int(s[i])]  +1
        } 

        mapkey[int(s[i])]  = i
        if i - left +1 > maxlen{
            maxlen = i - left +1
        }
    }
    return maxlen
}

第四题

思路

1
2
1.要求时间复杂度为m+n，那么就为一次循环，长度为len1+len2
2.判断nums1和nums2的对应下标的值的大小、是否下标溢出、是否已经全部判断完毕

代码

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
34
35
36
37
38
39
40
41
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	nums := combine(nums1, nums2)
	return medianOf(nums)
}

func combine(mis, njs []int) []int {
	lenMis, i := len(mis), 0
	lenNjs, j := len(njs), 0
	res := make([]int, lenMis+lenNjs)

	for k := 0;k < lenMis+lenNjs;n++{
       	if i == lenMis ||
			(i < lenMis && j < lenNjs && mis[i] > njs[j]) {
			res[k] = njs[j]
			j++
			continue
		}

		if j == lenNjs ||
			(i < lenMis && j < lenNjs && mis[i] <= njs[j]) {
			res[k] = mis[i]
			i++
		}
    }

	return res
}

func medianOf(nums []int) float64 {
	l := len(nums)

	if l == 0 {
		panic("error")
	}

	if l%2 == 0 {
		return float64(nums[l/2]+nums[l/2-1]) / 2.0
	}

	return float64(nums[l/2])
}

第五题

思路

1
2
1.先向后找到相同的字符串，标记首尾
2.首尾前后移动，判断字符串是否相同，得出长度和开始位置，与最大长度比较

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func longestPalindrome(s string) string {
    maxlen := 0
    begin := 0
    for i:=0;i<len(s);i++{
        start,end := i,i
        for end < len(s)-1&&s[end] == s[end+1]{
            end ++
        }
        for end < len(s)-1 && start > 0 && s[end+1] == s[start-1]{
            end ++
            start --
        }
        if end-start+1 > maxlen{
            maxlen = end-start+1
            begin = start
        }

    }
    return s[begin:begin+maxlen]