LeetCodeProblemsSolutionsInGo（一）

发表于 |  阅读次数
字数统计: 1.2k | 阅读时长 ≈ 6

写在前面

  • Go语言中文网的站长组织了一个通过golang实现LeetCode题目的项目，每天两道，无特殊情况日日更。
  • 项目代码仓库：https://github.com/studygolang/leetcode
  • 仓库里有不同Coder的解题思路，可以参考其他人的思路
  • 写这个系列blog的目的很简单，记录并督促自己好好刷题

001-twoSum

分类：Easy

题目

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

解题思路

利用map

  1. key是传入列表的元素
  2. value是元素的下标
  3. tmp是对应的元素，相加等于target

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func twoSum(nums []int, target int) []int{
	
	res := make(map[int]int)

	for i, v := range nums {
		// 找到对应的元素
		tmp := target - v

		j, ok := res[tmp]
		if ok {
			// 在 map 找到直接回传
			return []int{j, i}
		}
		// 找不到就把自己加入到 map 里面
		res[v] = i
	}
	//如果没有满足条件的回传｛-1，-1｝
	return []int{-1, -1}
}

002-addTwoNumbers

分类：Medium

题目

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

1
2
3
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

解题思路

同步遍历两个链表，对位相加并用一个变量flag记录进位，当两个列表的笑一个节点都为nil并且无进位时，返回结果

代码

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
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	r := &ListNode{}
	res := r
	flag :=0

	for l1 != nil || l2 != nil || flag != 0{

		if l1 != nil{
			res.Val += l1.Val
			l1 = l1.Next
		}
		if l2 != nil{
			res.Val += l2.Val
			l2 = l2.Next
		}

		res.Val += flag
		flag = res.Val / 10
		res.Val %= 10

		if l1 == nil && l2 == nil && flag == 0{
            //注意这里返回的是 r
			return r
		}
		//res和r同时创建链表的第二个节点，因为res和r指向的内存地址相同
		res.Next = &ListNode{}
        //res指向新的内存地址，即链表的下一个节点内存地址
		res = res.Next
	}
	return nil
}

026-Remove Duplicates from Sorted Array

分类：Easy

题目

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

1
2
3
4
5
Given nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.

It doesn't matter what you leave beyond the returned length.

Example 2:

1
2
3
4
5
Given nums = [0,0,1,1,1,2,2,3,3,4],

Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.

It doesn't matter what values are set beyond the returned length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

1
2
3
4
5
6
7
8
// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

解题思路

因为给定的整型数组已排序，所以不需要排序操作。这个算法有个缺点：破坏了传入数组内的数据了

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func removeDuplicates(nums []int) int {
	leng := 0
	res := nums[0:1]
	if len(nums) == 0{
		return leng
	}
	for _,v :=range nums{
		if v != res[leng]{
			res = append(res,v)
			leng++
		}
	}
	leng++
	return leng
}

027-Remove Element

分类：Easy

题目

Given an array nums and a value val, remove all instances of that value in-place and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example 1:

1
2
3
4
5
Given nums = [3,2,2,3], val = 3,

Your function should return length = 2, with the first two elements of nums being 2.

It doesn't matter what you leave beyond the returned length.

Example 2:

1
2
3
4
5
6
7
Given nums = [0,1,2,2,3,0,4,2], val = 2,

Your function should return length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4.

Note that the order of those five elements can be arbitrary.

It doesn't matter what values are set beyond the returned length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

1
2
3
4
5
6
7
8
// nums is passed in by reference. (i.e., without making a copy)
int len = removeElement(nums, val);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

解题思路

和026很像，遍历数组就完事了

代码

1
2
3
4
5
6
7
8
9
10
func removeElement(nums []int, val int) int {
    res := 0
    for _, v := range nums{
        if v !=  val{
            nums[res] = v
            res++
        }
    }
    return res
}