MENU

【笔记】Leetcode题目:“两数之和”,“两数相加”

2021 年 02 月 19 日 • 阅读: 644 • 笔记

昨天做了 Leetcode 上的两道题目,”两数之和“,“两数相加”。


题目:

给定一个整数数组 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;
                    }
                }
            }
        }
    }
}
?>

提交结果如下图:

pic34

题目:

给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。

请你将两个数相加,并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外,这两个数都不会以 0 开头。

示例 1:

pic35

输入: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;
    }
}
?>

提交结果如下图:

pic36

最后编辑于: 2021 年 03 月 05 日
返回文章列表 文章二维码
本页链接的二维码
打赏二维码
添加新评论

已有 2 条评论
  1. 好家伙,你啥时候学的PHP

    1. @奥秘Sir啊这,最近半个月学了一些@(滑稽)