【算法】两数相加(GoLang)

两数相加题目和测试地址: https://leetcode-cn.com/problems/add-two-numbers/

给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。
如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例:

输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807

最初实现绕了个弯,先把链表转为数字,数字相加后在转换为链表,这其中遇到了越界问题于是又手写了个大数相加函数,这样想来自然也快不起来,先展示下最初代码

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	num1 := BuildListSum(l1)
	num2 := BuildListSum(l2)
    numResult := AddTwoString(num1, num2)
	//fmt.Println(numResult)
	return BuildSumList(numResult)
}

func BuildListSum (listNote *ListNode) string {
	num1 := ""
	i := 0
	for e := listNote; e != nil; e = e.Next {
		num1 = fmt.Sprintf("%v%v", e.Val, num1)
		i++
	}
	return num1
}


func BuildSumList(num string) *ListNode {
	var listNote *ListNode
	count := len(num)
	for i := 0; i < count; i++ {
		//fmt.Println(numString[i:i+1])
		n,_ := strconv.Atoi(num[i:i+1])
		if listNote == nil {
			listNote = &ListNode{n, nil}
		} else {
			listNote = &ListNode{n, listNote}
		}
	}
	return listNote
}

func AddTwoString(num1, num2 string) string {
	result := ""
	if len(num1) ==0 && len(num2) ==0 {
		return "0"
	}
	if len(num2) > len(num1) {
		tmp := num1
		num1 = num2
		num2 = tmp
	}
	needInc := 0
	length1 := len(num1) -1
	length2 := len(num2) - 1
	for i := 0; i <= length2; i++ {
		tmp1 := num1[length1-i] - '0'
		tmp2 := num2[length2-i] - '0'
		tmpSum := int(tmp1) + int(tmp2) + needInc
		if tmpSum >= 10 {
			needInc = 1
		} else {
			needInc = 0
		}
		c3 := tmpSum % 10 + '0'
		result = fmt.Sprintf("%c%s",c3,result)
	}
	leftLength := length1 - length2
	for leftLength > 0 {
		c1 := num1[leftLength-1]-'0'
		sum :=  int(c1) + needInc
		if sum >= 10 {
			needInc = 1
		} else {
			needInc = 0
		}
		c3 := (sum %10) + '0'
		result = fmt.Sprintf("%c%s",c3,result)
		leftLength--
	}
	if needInc == 1 {
		result = fmt.Sprintf("1%s",result)
	}
	return result
}

执行用时 :20 ms, 在所有 golang 提交中击败了34.31%的用户
内存消耗 :6.1 MB, 在所有 golang 提交中击败了5.17%的用户

后面看到其他人的时间和内存都很小,才发现自己绕了一大圈,不需要转成数字,直接使用链表中的元素相加,注意进位就可以了,下面是做了一次优化的代码

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	result := &ListNode{}
	listNote := result
	left := 0
	for {
		e1 := l1
		e2 := l2
		if e1 == nil || e2 == nil {
			break
		}
		v := e1.Val + e2.Val + left
		if v >= 10 {
			left = 1
		} else {
			left = 0
		}
		n := v % 10
		listNote.Next = &ListNode{Val:n}
		l1 = l1.Next
		l2 = l2.Next
		listNote = listNote.Next
	}
	if l1 != nil {
		for e := l1; e != nil; e = e.Next {
			v := e.Val + left
			if v >= 10 {
				left = 1
			} else {
				left = 0
			}
			n := v % 10
			listNote.Next = &ListNode{Val:n}
			listNote = listNote.Next
		}
	}
	if l2 != nil {
		for e := l2; e != nil; e = e.Next {
			v := e.Val + left
			if v >= 10 {
				left = 1
			} else {
				left = 0
			}
			n := v % 10
			listNote.Next = &ListNode{Val:n}
			listNote = listNote.Next
		}
	}
	if left > 0 {
		listNote.Next = &ListNode{Val:1}
	}
	return result.Next
}

执行结果:

执行用时 :16 ms, 在所有 golang 提交中击败了63.46%的用户
内存消耗 :4.9 MB, 在所有 golang 提交中击败了94.01%的用户

发现还有人有更精简的代码,于是在重写下

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	result := &ListNode{}
	listNote := result
	left := 0
	for l1 != nil || l2 != nil || left > 0 {
		sum := left
		if l1 != nil {
			sum += l1.Val
			l1 = l1.Next
		}
		if l2 != nil {
			sum += l2.Val
			l2 = l2.Next
		}
		if sum >= 10 {
			left = 1
		} else {
			left = 0
		}
		listNote.Next = &ListNode{Val:sum % 10}
		listNote = listNote.Next
	}
	return result.Next
}

执行结果:

执行用时 :8 ms, 在所有 golang 提交中击败了97.50%的用户
内存消耗 :4.9 MB, 在所有 golang 提交中击败了94.01%的用户

从20ms到 8ms算是提升了不少,每次也从6.1M降至4.9M

【算法】两数之和(GoLang)

两数之和 题目和测试地址: https://leetcode-cn.com/problems/two-sum/

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。
示例:

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

GoLang 实现如下

func twoSum(nums []int, target int) []int {
	count := len(nums)
	if count < 2 {
		return []int{}
	}
	hashMap := make(map[int]int)
	for index, num := range nums {
		another_num := target - num
		if _,ok := hashMap[another_num]; ok {
			return []int{hashMap[another_num], index}
		}
		hashMap[num] = index
	}
	return []int{}
}

执行用时 :4 ms, 在所有 golang 提交中击败了97.99%的用户
内存消耗 :3.7 MB, 在所有 golang 提交中击败了46.55%的用户

解决golang xorm连接数据库 default addr for network localhost:3306 unknown

仅解决default addr for network unknown的错误,直接看代码

       var Orm *xorm.Engine
       var err error
       connection := fmt.Sprintf("%s:%s@tcp(%s:%d)/%s?charset=%s",
		mysqlConfig["MysqlUser"].(string),
		mysqlConfig["MysqlPass"].(string),
		mysqlConfig["MysqlHost"].(string),
		mysqlConfig["MysqlPort"].(int),
		mysqlConfig["MysqlDb"].(string),
		mysqlConfig["MysqlCharSet"].(string),
	)
	fmt.Println(connection)
	Orm, err = xorm.NewEngine("mysql", connection)
	if err != nil {
		fmt.Println(err.Error())
	}
	Orm.ShowSQL(true)
	iris.RegisterOnInterrupt(func() {
		Orm.Close()
	})
即使用的字符串应该是
dbuser:dbpassword@tcp(dbhost:dbport)/databasename?charset=utf8

变量参考如下

  #Database
  #Mysql database
  MySql:
    MysqlUser: root
    MysqlPass: root
    MysqlHost: localhost
    MysqlPort: 3306
    MysqlDb: mydatabase
    MysqlCharSet: utf8mb4

以上解决

使用CodeIgniter4(CI4)遇到的BUG(2) curl_setopt_array cannot represent a stream of type Output as a STDIO FILE

使用CodeIgniter 的 curl

$this->curlClient = \Config\Services::curlrequest();
$result = $this->curlClient->request('GET', $list_domain, [
            CURLOPT_SSL_VERIFYHOST  =>  2,
            CURLOPT_SSL_VERIFYPEER  =>  1,
            CURLOPT_TRANSFERTEXT    =>  false,
        ]);

返回的报错信息是:

ErrorException
curl_setopt_array(): cannot represent a stream of type Output as a STDIO FILE*

导致此问题的 curlopt 是

define ('CURLOPT_STDERR', 10037);

找到 sendRequest函数, 在 system/HTTP/CURLRequest.php的805行

$ch = curl_init();
unset($curl_options[CURLOPT_STDERR]);  //添加此行
curl_setopt_array($ch, $curl_options);

这样就可以解决 cannot represent a stream of type Output as a STDIO FILE* 的错误了。

使用CURL的实例如下

$list_domain = str_replace('https', 'http', $list_domain);
$options = [
	'allow_redirects' => [
		'max'       => 15,
	],
	CURLOPT_SSL_VERIFYPEER  =>  false,
	CURLOPT_SSL_VERIFYHOST  =>  false,
	'headers' => [
		'User-Agent'    =>  'Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/74.0.3729.169 Safari/537.36',
		'Accept'        =>  'text/html',
		'Referer'       =>  $list_domain,
	],
];
try {
	$result = $this->curlClient->request('GET', $list_domain, $options);
	$content = $result->getBody();
} catch (\Exception $e) {
	log_message_file('curl', $e->getMessage());
	//var_dump($e->getMessage());
	$context = null;
	if( substr($list_domain, 0, 5) == 'https') {
		$list_domain = str_replace('https://', 'http://', $list_domain);
		$options = array(
			'http' => array(
				'method' => 'GET',
				'header' => [
					'Content-type: text/html;charset=UTF-8',
					'User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/74.0.3729.169 Safari/537.36',
					'Referer: ' . $list_domain,
				],
			),
			// 解决SSL证书验证失败的问题
			"ssl"=>array(
				"verify_peer"=>false,
				"verify_peer_name"=>false,
			)
		);
		$context = stream_context_create($options);
	}
	$content = file_get_contents($list_domain, false, $context);
}
return $content;

仅记录使用CodeIgniter4(CI4)遇到的BUG(1)

1.System/Entity.php 173行报错,报错原因使用的变量没有定义

"title": "ErrorException",
"type": "ErrorException",
"code": 500,
"message": "Undefined index: xxxx",
"file": "/system/Entity.php",
"line": 173,

修复此BUG,修改此行

if ($onlyChanged && $this->_original[$key] === null && $value === null)

修改为

if ($onlyChanged && ! isset($this->_original[$key]) && $value === null)

因为变量 $this->_original[$key] 不存在,直接使用会抛出异常。