通知设置 新通知
LeetCode刷题Day2：两数相加
zkbhj 发表了文章 • 0 个评论 • 2256 次浏览 • 2020-09-22 20:57
两数相加
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807LeetCode
首先发一下我的思路已经给出的最初答案（大部分情况是正确的，但是超出数字范围就会和预期结果不一致），总之先把分析思路分享出来。
思路一：常规思路
分别循环两个链表，因为高位是个位，所以不断乘以10的n次方，n代表循环次数，从0开始，直到循环结束，就得到了两个无符号整数。所以，这就要求对输入数字有范围限制的要求，否则数字太大，超出整数的最大范围，得到的结果会因为发生溢出而不符合预期。
然后将两个整数进行加法运算，得到最终结果对应的int数字。
然后再将这个整数转化成字符串，循环字符串，得到字符对应的ASCII码点，然后减去48即可“间接“得到对应的数字。并按序生成链表。
func myPow(a,n int) int {
result := int(1)
for i:= n; i >0 ; i >>= 1 {
if i&1 != 0 {
result *=a
}
a *=a
}
return result
}
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
var a,b,c,i,j int
p1 := l1
for p1!= nil {
a = a + p1.Val * myPow(10,i)
i++
p1 = p1.Next
}
p2 := l2
for p2!= nil {
b = b + p2.Val * myPow(10,j)
j++
p2 = p2.Next
}
c = a + b
str := strconv.Itoa(c)
headNode := new(ListNode)
current := headNode
current.Next = nil
for _,one := range str {
preNode := current
current.Val = int(one-48)
current = new(ListNode)
current.Next = preNode
}
return current.Next
}
思路一：高级思路（学习）
对应位置的数字相加，跟10取模，即可得到该位置上十进制数相加之后的数字，然后和10进行整除，如果两个数相加小于10，则整除之后是0，否则是1，即要进位的1，所以直到两个链表都循环完，或者最后没有进位时，停止循环，最终返回。
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
headList := new(ListNode)
head := headList
num := 0
for (l1 != nil || l2 != nil || num > 0) {
headList.Next = new(ListNode)
headList = headList.Next
if l1 != nil {
num = num + l1.Val
l1 = l1.Next
}
if l2 != nil {
num = num + l2.Val
l2 = l2.Next
}
headList.Val = (num) % 10
num = num / 10
}
return head.Next
}
查看全部
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807LeetCode
首先发一下我的思路已经给出的最初答案（大部分情况是正确的，但是超出数字范围就会和预期结果不一致），总之先把分析思路分享出来。
思路一：常规思路
分别循环两个链表，因为高位是个位，所以不断乘以10的n次方，n代表循环次数，从0开始，直到循环结束，就得到了两个无符号整数。所以，这就要求对输入数字有范围限制的要求，否则数字太大，超出整数的最大范围，得到的结果会因为发生溢出而不符合预期。
然后将两个整数进行加法运算，得到最终结果对应的int数字。
然后再将这个整数转化成字符串，循环字符串，得到字符对应的ASCII码点，然后减去48即可“间接“得到对应的数字。并按序生成链表。
func myPow(a,n int) int {
result := int(1)
for i:= n; i >0 ; i >>= 1 {
if i&1 != 0 {
result *=a
}
a *=a
}
return result
}
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
var a,b,c,i,j int
p1 := l1
for p1!= nil {
a = a + p1.Val * myPow(10,i)
i++
p1 = p1.Next
}
p2 := l2
for p2!= nil {
b = b + p2.Val * myPow(10,j)
j++
p2 = p2.Next
}
c = a + b
str := strconv.Itoa(c)
headNode := new(ListNode)
current := headNode
current.Next = nil
for _,one := range str {
preNode := current
current.Val = int(one-48)
current = new(ListNode)
current.Next = preNode
}
return current.Next
}
思路一：高级思路（学习）
对应位置的数字相加，跟10取模，即可得到该位置上十进制数相加之后的数字，然后和10进行整除，如果两个数相加小于10，则整除之后是0，否则是1，即要进位的1，所以直到两个链表都循环完，或者最后没有进位时，停止循环，最终返回。
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
headList := new(ListNode)
head := headList
num := 0
for (l1 != nil || l2 != nil || num > 0) {
headList.Next = new(ListNode)
headList = headList.Next
if l1 != nil {
num = num + l1.Val
l1 = l1.Next
}
if l2 != nil {
num = num + l2.Val
l2 = l2.Next
}
headList.Val = (num) % 10
num = num / 10
}
return head.Next
}
查看全部
两数相加
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807LeetCode
首先发一下我的思路已经给出的最初答案（大部分情况是正确的，但是超出数字范围就会和预期结果不一致），总之先把分析思路分享出来。
思路一：常规思路
分别循环两个链表，因为高位是个位，所以不断乘以10的n次方，n代表循环次数，从0开始，直到循环结束，就得到了两个无符号整数。所以，这就要求对输入数字有范围限制的要求，否则数字太大，超出整数的最大范围，得到的结果会因为发生溢出而不符合预期。
然后将两个整数进行加法运算，得到最终结果对应的int数字。
然后再将这个整数转化成字符串，循环字符串，得到字符对应的ASCII码点，然后减去48即可“间接“得到对应的数字。并按序生成链表。
func myPow(a,n int) int {
result := int(1)
for i:= n; i >0 ; i >>= 1 {
if i&1 != 0 {
result *=a
}
a *=a
}
return result
}
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
var a,b,c,i,j int
p1 := l1
for p1!= nil {
a = a + p1.Val * myPow(10,i)
i++
p1 = p1.Next
}
p2 := l2
for p2!= nil {
b = b + p2.Val * myPow(10,j)
j++
p2 = p2.Next
}
c = a + b
str := strconv.Itoa(c)
headNode := new(ListNode)
current := headNode
current.Next = nil
for _,one := range str {
preNode := current
current.Val = int(one-48)
current = new(ListNode)
current.Next = preNode
}
return current.Next
}思路一：高级思路（学习）
对应位置的数字相加，跟10取模，即可得到该位置上十进制数相加之后的数字，然后和10进行整除，如果两个数相加小于10，则整除之后是0，否则是1，即要进位的1，所以直到两个链表都循环完，或者最后没有进位时，停止循环，最终返回。
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
headList := new(ListNode)
head := headList
num := 0
for (l1 != nil || l2 != nil || num > 0) {
headList.Next = new(ListNode)
headList = headList.Next
if l1 != nil {
num = num + l1.Val
l1 = l1.Next
}
if l2 != nil {
num = num + l2.Val
l2 = l2.Next
}
headList.Val = (num) % 10
num = num / 10
}
return head.Next
}
LeetCode刷题Day1：两数之和
zkbhj 发表了文章 • 0 个评论 • 2250 次浏览 • 2020-09-22 20:55
从今天开始，把LeetCode刷题作为每天日常计划的一项。尽早做准备，同时也每天对算法和相关的技能知识通过刷题的形式进行潜移默化的提升和加深理解。其实身边已经有很多程序猿朋友都在LeetCode刷题了，再不参与进来，都要出圈儿了呀。
今天是Day1，从第一道题目开始：
两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例：
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]LeetCode
思路一：暴力遍历
也是最简单最原始的未经优化的方案思路。
首先明确题目要求，可以假设每种输入只会对应一个答案，即一定会有且只有一对符合要求的数据。
所以得到数组的长度，然后从第一个开始进行循环，将目标值target减去当前被循环的值，得到与之可以配对的值，然后在数组中进行寻找，如果找到，就返回2个符合要求的值的索引，否则继续下一次寻找，直到找到。
最外层循环的条件中 x&y异或之后如果为1，说明已经找到对应的结果，就不再循环。时间复杂度是O(n²)，空间复杂度是O(1)。
func twoSum(nums []int, target int) []int {
len := len(nums)
var x,y int
for i:=0; i < len && x|y == 0; i++ {
findNum := target - nums[i]
for j:=0; j < len; j++ {
if findNum == nums[j] {
x = i;
y = j;
}
}
}
return []int{x,y}
}
思路二：进一步提升效率，可以利用哈希表
从第一个思路中，可以看到其实在判断一个值在一个“表”中是否存在的时候，我们采用了遍历的方式，这样的话时间复杂度就是O(n)，但是大家肯定都知道，哈希表是最擅长做这个事情的。它可以把时间复杂度降到O(1)。所以，这样思路就很清晰了，我们需要先把传过来的数组生成对应的哈希结构，也就是Go里面的map字典，这样我们就可以快速的找到某值在还是不在了。我们把数组的value作为map的key，index作为map的value。代码实现如下。
func twoSum(nums []int, target int) []int {
var hashMap map[int]int
len := len(nums)
var x,y,found int
//初始化字典
hashMap = make(map[int]int)
for i:=0; i < len; i++ {
hashMap[nums[i]] = i
}
for j:=0; j < len && found == 0; j++ {
findNum := target - nums[j]
v, ok := hashMap[findNum]
if ok && v != j {
found = 1
x = j
y = v
}
}
return []int{x,y}
}
今天这道题的难度级别是简单，但是带我回顾了Go语言的数组、map的相关知识和用法，以及哈希表这一知识点。 查看全部
今天是Day1，从第一道题目开始：
两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例：
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]LeetCode
思路一：暴力遍历
也是最简单最原始的未经优化的方案思路。
首先明确题目要求，可以假设每种输入只会对应一个答案，即一定会有且只有一对符合要求的数据。
所以得到数组的长度，然后从第一个开始进行循环，将目标值target减去当前被循环的值，得到与之可以配对的值，然后在数组中进行寻找，如果找到，就返回2个符合要求的值的索引，否则继续下一次寻找，直到找到。
最外层循环的条件中 x&y异或之后如果为1，说明已经找到对应的结果，就不再循环。时间复杂度是O(n²)，空间复杂度是O(1)。
func twoSum(nums []int, target int) []int {
len := len(nums)
var x,y int
for i:=0; i < len && x|y == 0; i++ {
findNum := target - nums[i]
for j:=0; j < len; j++ {
if findNum == nums[j] {
x = i;
y = j;
}
}
}
return []int{x,y}
}
思路二：进一步提升效率，可以利用哈希表
从第一个思路中，可以看到其实在判断一个值在一个“表”中是否存在的时候，我们采用了遍历的方式，这样的话时间复杂度就是O(n)，但是大家肯定都知道，哈希表是最擅长做这个事情的。它可以把时间复杂度降到O(1)。所以，这样思路就很清晰了，我们需要先把传过来的数组生成对应的哈希结构，也就是Go里面的map字典，这样我们就可以快速的找到某值在还是不在了。我们把数组的value作为map的key，index作为map的value。代码实现如下。
func twoSum(nums []int, target int) []int {
var hashMap map[int]int
len := len(nums)
var x,y,found int
//初始化字典
hashMap = make(map[int]int)
for i:=0; i < len; i++ {
hashMap[nums[i]] = i
}
for j:=0; j < len && found == 0; j++ {
findNum := target - nums[j]
v, ok := hashMap[findNum]
if ok && v != j {
found = 1
x = j
y = v
}
}
return []int{x,y}
}
今天这道题的难度级别是简单，但是带我回顾了Go语言的数组、map的相关知识和用法，以及哈希表这一知识点。 查看全部
从今天开始，把LeetCode刷题作为每天日常计划的一项。尽早做准备，同时也每天对算法和相关的技能知识通过刷题的形式进行潜移默化的提升和加深理解。其实身边已经有很多程序猿朋友都在LeetCode刷题了，再不参与进来，都要出圈儿了呀。
今天是Day1，从第一道题目开始：
思路一：暴力遍历
也是最简单最原始的未经优化的方案思路。
首先明确题目要求，可以假设每种输入只会对应一个答案，即一定会有且只有一对符合要求的数据。
所以得到数组的长度，然后从第一个开始进行循环，将目标值target减去当前被循环的值，得到与之可以配对的值，然后在数组中进行寻找，如果找到，就返回2个符合要求的值的索引，否则继续下一次寻找，直到找到。
最外层循环的条件中 x&y异或之后如果为1，说明已经找到对应的结果，就不再循环。时间复杂度是O(n²)，空间复杂度是O(1)。
思路二：进一步提升效率，可以利用哈希表
从第一个思路中，可以看到其实在判断一个值在一个“表”中是否存在的时候，我们采用了遍历的方式，这样的话时间复杂度就是O(n)，但是大家肯定都知道，哈希表是最擅长做这个事情的。它可以把时间复杂度降到O(1)。所以，这样思路就很清晰了，我们需要先把传过来的数组生成对应的哈希结构，也就是Go里面的map字典，这样我们就可以快速的找到某值在还是不在了。我们把数组的value作为map的key，index作为map的value。代码实现如下。
今天这道题的难度级别是简单，但是带我回顾了Go语言的数组、map的相关知识和用法，以及哈希表这一知识点。
今天是Day1，从第一道题目开始：
两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例：
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]LeetCode
思路一：暴力遍历
也是最简单最原始的未经优化的方案思路。
首先明确题目要求，可以假设每种输入只会对应一个答案，即一定会有且只有一对符合要求的数据。
所以得到数组的长度，然后从第一个开始进行循环，将目标值target减去当前被循环的值，得到与之可以配对的值，然后在数组中进行寻找，如果找到，就返回2个符合要求的值的索引，否则继续下一次寻找，直到找到。
最外层循环的条件中 x&y异或之后如果为1，说明已经找到对应的结果，就不再循环。时间复杂度是O(n²)，空间复杂度是O(1)。
func twoSum(nums []int, target int) []int {
len := len(nums)
var x,y int
for i:=0; i < len && x|y == 0; i++ {
findNum := target - nums[i]
for j:=0; j < len; j++ {
if findNum == nums[j] {
x = i;
y = j;
}
}
}
return []int{x,y}
}
思路二：进一步提升效率，可以利用哈希表
从第一个思路中，可以看到其实在判断一个值在一个“表”中是否存在的时候，我们采用了遍历的方式，这样的话时间复杂度就是O(n)，但是大家肯定都知道，哈希表是最擅长做这个事情的。它可以把时间复杂度降到O(1)。所以，这样思路就很清晰了，我们需要先把传过来的数组生成对应的哈希结构，也就是Go里面的map字典，这样我们就可以快速的找到某值在还是不在了。我们把数组的value作为map的key，index作为map的value。代码实现如下。
func twoSum(nums []int, target int) []int {
var hashMap map[int]int
len := len(nums)
var x,y,found int
//初始化字典
hashMap = make(map[int]int)
for i:=0; i < len; i++ {
hashMap[nums[i]] = i
}
for j:=0; j < len && found == 0; j++ {
findNum := target - nums[j]
v, ok := hashMap[findNum]
if ok && v != j {
found = 1
x = j
y = v
}
}
return []int{x,y}
}
今天这道题的难度级别是简单，但是带我回顾了Go语言的数组、map的相关知识和用法，以及哈希表这一知识点。