华为OD刷题C卷 - 每日刷题 1

1、（两数之和）：

这段代码是针对力扣（LeetCode）上的“两数之和”问题。它提供了一个Java类Solution，其中包含一个方法twoSum，该方法接收一个整数数组nums和一个整数目标值target。目的是找出数组中两个整数的和等于目标值target，并返回这两个整数的数组下标。

代码中首先定义了一个HashMap<Integer, Integer>，用来存储数组中的每个数字及其对应的下标。然后，通过遍历数组，对于每个元素，检查HashMap中是否存在一个值，使得这个值与当前元素的和等于目标值target。如果存在，就将对应的下标和当前元素的下标存入数组ans中，并中断循环。最后返回ans数组。

这段代码使用了哈希表来优化查找过程，使得算法的时间复杂度为O(n)，而不是暴力解法的O(n^2)。

2、（两数相加）：

这段代码是针对力扣（LeetCode）上的“两数相加”问题。它提供了一个Java类Solution，其中包含一个方法addTwoNumbers，该方法接收两个表示非负整数的链表l1和l2。这些整数是逆序存储的，每个节点存储一位数字。

addTwoNumbers方法首先初始化了头结点head和尾结点tail，并定义了一个变量carry来存储进位。然后，它使用一个循环来遍历两个链表，直到两个链表都遍历完毕。在每次循环中，它计算两个链表当前节点的值加上进位的和，然后更新进位carry。接着，它创建一个新的链表节点，其值为sum % 10（即和的个位数），并将其链接到结果链表的末尾。如果head为null，说明这是结果链表的第一个节点，因此同时更新head和tail；否则，只更新tail。

循环结束后，如果还有进位（carry > 0），则在链表末尾添加一个新的节点，其值为carry。最后，返回头结点head，它指向表示两个数之和的链表。

这段代码通过模拟加法运算的过程，逐位相加并处理进位，从而实现了两个链表表示的整数相加的功能。

package Code1;import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Scanner;/*** @description 两数之和* @level 简单* @score* @url https://leetcode.cn/problems/two-sum/description/*/
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);}
}class Solution {public int[] twoSum(int[] nums, int target) {//转为Listint[] ans = new int[2];//暴力//for (int i = 0; i < nums.length; i++) {//    for (int j = i + 1; j < nums.length; j++) {//        if (nums[i] + nums[j] == target) {//            ans = new int[]{i, j};//            break;//        }//    }//}//使用哈希表 数字，对应下标HashMap<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums.length; i++) {//如果存在对应结果if (map.containsKey(target - nums[i])) {ans = new int[]{map.get(target - nums[i]), i};break;}map.put(nums[i], i);}return ans;}
}

package Code2;import java.util.Scanner;/*** @description 两数相加* @level 中等* @score* @url https://leetcode.cn/problems/add-two-numbers/description/*/
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);}
}/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {//头结点，尾结点ListNode head = null, tail = null;//进位int carry = 0;while (l1 != null || l2 != null) {int x = l1 == null ? 0 : l1.val;int y = l2 == null ? 0 : l2.val;int sum = x + y + carry;carry = sum / 10;//初始化，头节点和尾结点是同一个节点if (head == null) {head = tail = new ListNode(sum % 10);} else {//否则，就加在尾结点后面tail.next = new ListNode(sum % 10);tail = tail.next;}//遍历l1下一个节点if (l1 != null) {l1 = l1.next;}//遍历l2下一个节点if (l2 != null) {l2 = l2.next;}}//如果最后还有进位if (carry > 0) {tail.next = new ListNode(carry);tail = tail.next;}return head;}public static class ListNode {int val;ListNode next;public ListNode(int val) {this.val = val;}public ListNode(int val, ListNode next) {this.val = val;this.next = next;}}
}