昨天做了 Leetcode 上的两道题目,”两数之和“,“两数相加”。
- 第一道题:两数之和
- 难度:简单
- 代码用时:4ms
- 占用内存:15.5MB
- 语言:PHP
- 题目链接:https://leetcode-cn.com/problems/two-sum
题目:
给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 的那 两个 整数,并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。
你可以按任意顺序返回答案。
示例 1:
输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。
示例 2:
输入:nums = [3,2,4], target = 6
输出:[1,2]
示例 3:
输入:nums = [3,3], target = 6
输出:[0,1]
思路:
使用 for (
$i
)循环,令$x
等于$nums[$i]
, 查询$target-$nums[$i]
在$nums
中是否存在,存在则返回下标给$key
不存在(为 null 但不为 0)则跳过循环。存在的情况下,再从下标为
$key
开始使用 for ($ii
)循环,当$nums[$ii]+$x==$target
且下标$ii
不等于$i
时,返回数组[$i,$ii]
即可。
代码如下:
<?php
class Solution {
public function twoSum($nums, $target) {
$len = count($nums);
for ($i=0;$i<=$len-1;$i++){
$x = $nums[$i];
$y = $target - $x;
$key = array_search($y,$nums);
if ($key == null and $key !== 0){
continue;
}else{
for ($ii=$key;$ii<=$len-1;$ii++){
if ($nums[$ii]+$x==$target and $ii != $i){
return [$i,$ii];
}else{
continue;
}
}
}
}
}
}
?>
提交结果如下图:
- 第二道题:两数相加
- 难度:中等
- 代码用时:8ms
- 占用内存:15.1MB
- 语言:PHP
- 题目链接:https://leetcode-cn.com/problems/add-two-numbers/
题目:
给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。
请你将两个数相加,并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例 1:
输入:l1 = [2,4,3], l2 = [5,6,4]
输出:[7,0,8]
解释:342 + 465 = 807
示例 2:
输入:l1 = [0], l2 = [0]
输出:[0]
示例 3:
输入:l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出:[8,9,9,9,0,0,0,1]
思路:
首先我们需要了解“链表”类(ListNode)。
然后根据类进行计算。
1.计算顺序,因为题目要求满 10 进 1,向右进一,所以我们从左向右算起。
2.计算方法,采用 while 循环对每一节考虑。令
$l1
等于链表 1 的每一节,$value1
等于链表 1 每一节的值,每执行一次 value 的赋值,就令$l1
等于下一个节。链表 2 同理。$sum
等于$value1
和$value2
的和。$last
是进位值,$sum
大于等于 10 时为 1,小于 10 时为 0。$new
是新的链节,当$sum
大于等于 10 时,将$sum-10
储存在链节,并给$last
赋值为 1,进而记作下一节计算时的进位 1;当$sum
小于 10 时,将$sum
储存在链节中并给$last
赋值为 0,进而记作下一节计算时的进位 0。
代码如下:
<?php
/**
* Definition for a singly-linked list.
* class ListNode {
* public $val = 0;
* public $next = null;
* function __construct($val = 0, $next = null) {
* $this->val = $val;
* $this->next = $next;
* }
* }
*/
class Solution {
/**
* @param ListNode $l1
* @param ListNode $l2
* @return ListNode
*/
function addTwoNumbers($l1, $l2) {
$result = '';
$new = &$result;
$last = 0;
while (true){
//如果最后一位相加满10,将进位1(last变量的值)记作链节的值
if ($l1 == null and $l2 == null){
if ($last){
$new = new ListNode($last);
}
break;
}
//如果l1链节的值不为空 l1链节的值赋值给value1变量,否则为0
if ($l1 != null){
$value1 = $l1->val;
$l1 = $l1->next;
}else{
$value1 = 0;
}
//同理l1链节
if ($l2 != null){
$value2 = $l2->val;
$l2 = $l2->next;
}else{
$value2 = 0;
}
$sum = $value1 + $value2 + $last;
//如果总和满10,减去10的值记为新链节的值,进位1赋值给last变量,不满10,直接作为新链节的值,进位0赋值给last变量
if ($sum >= 10){
$new = new ListNode($sum-10);
$last = 1;
}else{
$new = new ListNode($sum);
$last = 0;
}
$new = &$new->next;
}
return $result;
}
}
?>
提交结果如下图:
好家伙,你啥时候学的PHP
啊这,最近半个月学了一些@(滑稽)