购物网站开发文档mvc,海南哪家公司做网站,邮箱地址怎么注册,重庆住房和城乡建设部网站的打印准考证版本说明
当前版本号[20231112]。
版本修改说明20231112初版
目录 文章目录 版本说明目录字符串相乘题目解题思路代码思路补充说明参考代码 子集题目解题思路代码思路参考代码 删除链表的倒数第 N 个结点题目解题思路代码思路参考代码 字符串相乘
题目
给定两个以字符串形…版本说明
当前版本号[20231112]。
版本修改说明20231112初版
目录 文章目录 版本说明目录字符串相乘题目解题思路代码思路补充说明参考代码 子集题目解题思路代码思路参考代码 删除链表的倒数第 N 个结点题目解题思路代码思路参考代码 字符串相乘
题目
给定两个以字符串形式表示的非负整数 num1 和 num2返回 num1 和 num2 的乘积它们的乘积也表示为字符串形式。
示例 1:
输入: num1 “2”, num2 “3” 输出: “6”
示例 2:
输入: num1 “123”, num2 “456” 输出: “56088”
说明
num1 和 num2 的长度小于110。 num1 和 num2 只包含数字 0-9。 num1 和 num2 均不以零开头除非是数字 0 本身。 不能使用任何标准库的大数类型比如 BigInteger或直接将输入转换为整数来处理。
解题思路
首先判断输入的两个字符串是否为0如果是则直接返回0。获取两个字符串的长度m和n。创建一个长度为mn-1的整数数组intRes用于存储乘积的结果。使用两层循环遍历num1和num2的每一位数字将它们相乘并累加到intRes数组中对应的位置。从intRes数组的末尾开始向前遍历如果当前位置的值大于等于10则需要进位。将当前位置的值除以10并将余数加到前一位上。将intRes数组转换为字符串形式即为最终的乘积结果。
代码思路 首先判断输入的两个字符串是否为0如果是则直接返回0因为任何数与0相乘都等于0。 // 如果num1或num2为0则直接返回0if (num1.equals(0) || num2.equals(0))return 0;获取两个字符串的长度m和n分别表示num1和num2的位数。 // 获取num1的长度mint m num1.length();// 获取num2的长度nint n num2.length();创建一个长度为mn-1的整型数组intRes用于存储相乘结果的每一位数字。 // 创建一个长度为mn-1的整型数组intRes用于存储相乘结果的每一位数字int[] intRes new int[m n - 1];使用两层循环遍历num1和num2的每一位数字将它们相乘的结果累加到intRes数组中对应的位置上。这里需要注意的是由于num1和num2是字符串表示的整数所以在计算时需要将字符转换为对应的数字值通过减去字符’0’的ASCII码值。 // 使用两层循环遍历num1和num2的每一位数字for (int i 0; i m; i) {for (int j 0; j n; j) {// 将num1的第i位数字与num2的第j位数字相乘然后加上intRes数组中对应位置的值intRes[i j] (num1.charAt(i) - 48) * (num2.charAt(j) - 48);}}对intRes数组进行进位处理。从数组的最后一位开始向前遍历如果当前位的数字大于等于10则需要将其除以10并加上前一位的值。同时将当前位的值更新为除以10后的余数。 // 从intRes数组的最后一位开始向前遍历如果当前位的数字大于等于10则需要将其除以10并加上前一位的值for (int i intRes.length - 1; i 0; i--) {if (intRes[i] 10) {intRes[i - 1] intRes[i] / 10;intRes[i] % 10;}}最后将intRes数组中的每个元素转换为字符串拼接起来得到最终的相乘结果。拼接起来形成最终的乘积结果。这个结果被赋值给变量res并作为方法的返回值。 // 遍历intRes数组将每个元素转换为字符串并拼接到res中for (int i 0; i intRes.length; i) {res String.valueOf(intRes[i]);}// 返回最终的相乘结果return res;}补充说明
1、为什么在代码思路第3的步骤里创建一个整型数组intRes是长度为 mn-1 的呢
int[] intRes new int[m n - 1]; 在这段代码中m n - 1用于初始化一个长度为m n - 1的整数数组intRes。这个数组用于存储两个字符串num1和num2相乘的结果。
具体来说如果num1的长度为mnum2的长度为n那么num1和num2相乘的结果的最大位数就是m n - 1。
因此我们需要创建一个长度为m n - 1的数组来存储结果。
2、在代码思路第4的步骤里在计算时该怎么将字符转换为对应的数字值呢又是为什么要减去48呢 intRes[i j] (num1.charAt(i) - 48) * (num2.charAt(j) - 48); 这段代码的目的是将两个字符串表示的数字相乘并将结果存储在一个整数数组中。
(num1.charAt(i) - 48)/ (num2.charAt(j) - 48)将num1/num2的第i位字符转换为对应的数字值。
这里减去48是因为字符’0’的ASCII码值为48所以通过减去48可以将字符转换为对应的数字值例如字符’2’的ASCII码值为50减去48后得到数字2。
参考代码
这段代码是一个用于实现两个字符串表示的整数相乘的算法。
class Solution {public String multiply(String num1, String num2) {if (num1.equals(0) || num2.equals(0))return 0;int m num1.length();int n num2.length();int[] intRes new int[m n - 1];for (int i 0; i m; i) {for (int j 0; j n; j) {intRes[i j] (num1.charAt(i) - 48) * (num2.charAt(j) - 48);}}for (int i intRes.length - 1; i 0; i--) {if (intRes[i] 10) {intRes[i - 1] intRes[i] / 10;intRes[i] % 10;}}String res ;for (int i 0; i intRes.length; i) {res String.valueOf(intRes[i]);}return res;}
}子集
题目
给你一个整数数组 nums 数组中的元素 互不相同 。返回该数组所有可能的子集幂集。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1
输入nums [1,2,3] 输出[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2
输入nums [0] 输出[[],[0]]
提示
1 nums.length 10 -10 nums[i] 10 nums 中的所有元素 互不相同
解题思路
创建一个空的结果列表 res用于存储所有可能的子集。创建一个临时列表 tmp用于存储当前正在构建的子集。将空列表添加到结果列表 res 中。如果输入数组 nums 的长度为 0直接返回结果列表 res。调用辅助函数 helper传入输入数组 nums、起始索引 0、临时列表 tmp 和结果列表 res。在辅助函数 helper 中遍历输入数组 nums 从起始索引 start 开始的所有元素。 a. 将当前元素添加到临时列表 tmp 中。 b. 递归调用辅助函数 helper传入输入数组 nums、当前元素的下一个索引 i 1、临时列表 tmp 和结果列表 res。 c. 将当前临时列表 tmp 的副本添加到结果列表 res 中。 d. 移除临时列表 tmp 中的最后一个元素回溯到上一步。返回结果列表 res。
代码思路 定义一个名为Solution的类其中包含两个方法subsets和helper。 subsets方法是主方法它接受一个整数数组nums作为输入并返回一个包含所有子集的列表。 public ListListInteger subsets(int[] nums) 在subsets方法中首先创建一个空的结果列表res和一个临时列表tmp然后将tmp添加到res中。 ListListInteger res new ArrayListListInteger(); // 存储结果的列表ListInteger tmp new ArrayList(); // 临时列表用于存储当前子集res.add(tmp); // 将空子集添加到结果列表中如果输入数组nums的长度为0则直接返回结果列表res。 if (nums.length 0) // 如果输入数组为空直接返回结果列表return res;调用辅助方法helper传入输入数组nums、起始索引0、临时列表tmp和结果列表res。 helper(nums, 0, tmp, res); // 调用辅助函数生成子集helper方法是一个递归方法用于生成所有可能的子集。它接受四个参数输入数组nums、当前处理的起始索引start、临时列表tmp和结果列表res。 // 辅助函数递归生成子集public void helper(int[] nums, int start, ListInteger tmp, ListListInteger res) 在helper方法中使用一个循环从起始索引start开始遍历输入数组nums。 for (int i start; i nums.length; i)在每次循环中将当前元素添加到临时列表tmp中然后递归调用helper方法传入下一个索引i 1、更新后的临时列表tmp和结果列表res。 tmp.add(nums[i]); // 将当前元素添加到临时列表中helper(nums, i 1, tmp, res); // 递归调用辅助函数处理下一个元素在递归调用返回后将当前的临时列表tmp复制一份并将其添加到结果列表res中。 res.add(new ArrayListInteger(tmp)); // 将当前临时列表复制一份添加到结果列表中最后从临时列表tmp中移除最后一个元素以便在下一次循环中处理下一个元素。 tmp.remove(tmp.size() - 1); // 移除临时列表中的最后一个元素回溯到上一步当循环结束时所有的子集都已经生成并添加到结果列表res中最终返回该列表。
参考代码
这段代码是一个求解给定数组的所有子集的算法。它使用了回溯法来生成所有可能的子集并将它们存储在一个列表中返回。
class Solution {public ListListInteger subsets(int[] nums) {ListListInteger res new ArrayListListInteger();ListInteger tmp new ArrayList();res.add(tmp);if (nums.length 0)return res;helper(nums, 0, tmp, res);return res;}public void helper(int[] nums, int start, ListInteger tmp, ListListInteger res) {for (int i start; i nums.length; i) {tmp.add(nums[i]);helper(nums, i 1, tmp, res);res.add(new ArrayListInteger(tmp));tmp.remove(tmp.size() - 1);}}
}删除链表的倒数第 N 个结点
题目
给你一个链表删除链表的倒数第 n 个结点并且返回链表的头结点。
进阶你能尝试使用一趟扫描实现吗
示例 1 输入head [1,2,3,4,5], n 2 输出[1,2,3,5]
示例 2
输入head [1], n 1 输出[]
示例 3
输入head [1,2], n 1 输出[1]
提示
链表中结点的数目为 sz 1 sz 30 0 Node.val 100 1 n sz
解题思路
创建一个虚拟头节点v并将其指向原链表的头结点head。这样做的目的是方便处理边界情况例如当需要删除的是头结点时。使用一个循环遍历整个链表将每个节点添加到一个列表index中。这样我们可以方便地访问链表中的任意节点。计算要删除的节点的前一个节点和后一个节点在列表中的索引位置。前一个节点的索引为index.size() - n - 1后一个节点的索引为index.size() - n 1。根据计算出的索引位置更新前一个节点的next指针使其指向后一个节点或null如果后一个节点不存在。返回虚拟头节点v的下一个节点即删除倒数第n个节点后的链表头结点。
代码思路 创建一个虚拟头节点v并将其指向原链表头节点head。这样做是为了方便处理边界情况例如当需要删除的是头节点时。 // 移除链表中倒数第n个节点的方法public ListNode removeNthFromEnd(ListNode head, int n) {ListNode v new ListNode(0, head); // 创建一个虚拟头节点指向原链表头节点创建一个名为handle的指针指向虚拟头节点v。 ListNode handle v; // 创建一个指针指向虚拟头节点创建一个名为index的列表用于存储链表中所有节点的引用。 ListListNode index new ArrayList(); // 创建一个列表用于存储链表中所有节点的引用使用while循环遍历链表将每个节点的引用添加到index列表中。 // 遍历链表将每个节点的引用添加到列表中while (v ! null) {index.add(v);v v.next;}计算要删除的节点的前一个节点和后一个节点在index列表中的索引位置pre和next。 // 计算要删除的节点的前一个节点和后一个节点在列表中的索引位置int pre index.size() - n - 1;int next index.size() - n 1;根据pre和next的值更新前一个节点的next指针使其指向后一个节点或null如果后一个节点不存在。 // 更新前一个节点的next指针使其指向后一个节点或null如果后一个节点不存在index.get(pre).next next 0 next index.size() ? index.get(next) : null;返回处理后的链表头节点handle.next。 // 返回处理后的链表头节点return handle.next;参考代码
这段代码是用于删除链表中倒数第n个节点。
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 removeNthFromEnd(ListNode head, int n) {ListNode v new ListNode(0, head);ListNode handle v;ListListNode index new ArrayList();while (v ! null) {index.add(v);v v.next;}int pre index.size() - n - 1;int next index.size() - n 1;index.get(pre).next next 0 next index.size() ? index.get(next) : null;return handle.next;}
}
