Java 100道经典机试笔试题(12)——附可运行代码
2021/10/24 9:09:53
本文主要是介绍Java 100道经典机试笔试题(12)——附可运行代码,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
导语
每篇将有两道经典Java机试题,每道题后面均为大家附上代码,每一道题目力求:
- 能够在JDK11环境下编译
- 在Eclipse JavaIDE中运行通过
- 思路易想易懂易学
- 重点代码有注释
第023题 两数之和(难度:★☆☆☆☆)
题目描述:
给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出和为目标值 target 的那两个整数,并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。如果不存在,则返回[-1,-1]
提示:
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案
输入输出示例:
输入:nums = [2,7,11,15], target = 9
输出:[0,1]
输入:nums = [3,2,4], target = 6
输出:[1,2]
输入:nums = [3,3], target = 6
输出:[0,1]
思路
一种比较直接的思路是,遍历数组,获得每一个值,然后用target减去当前值,并遍历数组,找到该结果的下标
代码
import java.util.Scanner; public class Main { public static void main(String[] args) { /* 辅助输入验证代码 Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int target = scanner.nextInt(); int [] nums = new int[n]; for (int i = 0; i < n; i++) { nums[i] = scanner.nextInt(); } scanner.close(); Solution solution = new Solution(); int [] reslut = solution.twoSum(nums, target); System.out.println("[" + reslut[0] + "," + reslut[1] + "]"); */ } } //解决函数 class Solution { public int[] twoSum(int [] nums, int target) { for (int i = 0; i < nums.length; i++) { int a = nums[i]; int result = target - a; for (int j = 0; j < nums.length; j++) { if (j != i && nums[j]== result) { int[] e = {i, j}; return e; } } } int [] r = {-1, -1}; return r; } }
运行结果
第024题 链表求和(难度:★★☆☆☆)
题目描述:
给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。
请你将两个数相加,并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外,这两个数都不会以 0 开头。
提示:
每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零
输入输出示例:
输入:l1 = [2,4,3], l2 = [5,6,4]
输出:[7,0,8]
解释:342 + 465 = 807.
输入:l1 = [0], l2 = [0]
输出:[0]
解释:0 + 0 = 0.
输入:l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出:[8,9,9,9,0,0,0,1]
解释:9999999 + 9999 = 1009998
思路
如果你试图将给的单个数字拼成一个整数字,直接相加得出结果的话,那么你会发现,数位少的时候是行得通的,但是当数位很多时,很容易就内存溢出了,所以不能简单的处理,我们需要换一种思路。思考两个数字相加,我们是按位相加,然后得出结果,而按位相加其实只存在两种关系,直接相加和相加完再加上来自低位的进位。比如:12+47,个位和个位相加:2 + 7 = 9,十位和十位相加:1 + 4 = 5,此时低位没有进位,所以结果直接是59;再比如:14 + 57,个位和个位相加:4 + 7 = 11,十位和十位相加:1 + 5 = 6;那么此时,个位相加结果只保留个位,多出的十位进位添加到十位的结果计算中:即 6 + 1 = 7结果71。由此,我们得出本题解决方式:按链表顺序依次相加,并使用标记range来标明,当前位数相加是否有超过10,用来决定下一位相加时是否需要进位,十进制相加,产生的进位一定是1。
最后,如果某个链表个数小于另一个链表,那么可以默认补一个0,继续相加。注意最后一位相加时如果超过10,结果里还要再往后添加一个1;
代码
关键在核心解决函数Solution(),其他代码为辅助验证输入链表、构造链表、及构造链表数据结构使用
import java.util.Scanner; public class Main { public static void main(String[] args) { ListNode l1 = null; ListNode l2 = null; ListNode l1Point = null; ListNode l2Point = null; Scanner scanner = new Scanner(System.in); //输入链表1的长度 int n1 = scanner.nextInt(); //输入链表1 for (int i = 0; i < n1; i++) { if (l1 == null) { l1 = new ListNode(scanner.nextInt()); l1Point = l1; } else if (l1Point.next == null) { l1Point.next = new ListNode(scanner.nextInt()); l1Point = l1Point.next; } } //输入链表2的长度 int n2 = scanner.nextInt(); //输入链表2 for (int i = 0; i < n2; i++) { if (l2 == null) { l2 = new ListNode(scanner.nextInt()); l2Point = l2; } else if (l2Point.next == null) { l2Point.next = new ListNode(scanner.nextInt()); l2Point = l2Point.next; } } scanner.close(); Solution solution = new Solution(); ListNode result = solution.addTwoNumbers(l1, l2); System.out.println(result.toString()); } } //链表数据结构 class ListNode { int val; //存放当前节点的值 ListNode next; //存放当前节点的下一节点 //无参构造 ListNode() { } //一参构造 ListNode(int val) { this.val = val; } //二参构造 ListNode(int val, ListNode next) { this.val = val; this.next = next; } public String toString() { ListNode currentListNode = this; String s = "[" + currentListNode.val; while (currentListNode.next != null) { currentListNode = currentListNode.next; s = s + "," + currentListNode.val; } s = s + "]"; return s; } } //核心解决函数 class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { int range = 0; //标记上一位是否有进位 ListNode resultListNode = null; //最后要返回的结果链表 ListNode tempListNode = null; //临时指向的链表节点 while (l1 != null || l2 != null) { int sum = 0; //谁空了,谁就取0.否则就取自己本身的节点值 if (l1 == null) { sum = 0 + l2.val+ range; } else if (l2 == null) { sum = l1.val + 0 + range; } else { sum = l1.val + l2.val + range; } //如果结果节点是空的,那么要新建一个链表 if (resultListNode == null) { resultListNode = new ListNode(sum % 10); tempListNode = resultListNode; } else { //否则直接在链尾添加新的节点 tempListNode.next = new ListNode(sum % 10); tempListNode = tempListNode.next; } //标记本次相加是否有进位 if (sum >= 10) { range = 1; } else { range = 0; } //l1不空就继续取下一个节点 if (l1 != null) { l1 = l1.next; } //l2不空就继续取下一个节点 if (l2 != null) { l2 = l2.next; } } //最后如果最高位相加仍有进位,那么需要再添加一个进位节点 if (range == 1) { tempListNode.next = new ListNode(range); } return resultListNode; } }
运行结果
链表输入:[2,4,3] 、[5,6,4]
链表输入:[0]、[0]
链表输入[9,9,9,9,9,9,9]、[9,9,9,9]
以上是本次两道Java机试题
如有不足,欢迎批评指正
欢迎阅读上一篇:Java 100道典型机试笔试题(11)
欢迎阅读下一篇:Java 100道典型机试笔试题(13)
作者:小南瓜
日期:2021年10月24日09:00
这篇关于Java 100道经典机试笔试题(12)——附可运行代码的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)