LeetCode：两数之和+两数相加+字符串相乘+无重复字符的最长字串+寻找两个数组的中位数+Z字形变换+整数反转+字符串转换整数(atoi)

2024-03-23 02:58
文章标签 leetcode 数组 相加 字符串 转换 重复 最长 两个 字符 反转 整数 两数 相乘 寻找 变换 中位数 字串 atoi 字形

本文主要是介绍LeetCode：两数之和+两数相加+字符串相乘+无重复字符的最长字串+寻找两个数组的中位数+Z字形变换+整数反转+字符串转换整数(atoi)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

1. 两数之和

2. 两数相加

字符串相乘（大数相乘）

3. 无重复字符的最长字串

4. 寻找两个数组的中位数

5. Z字形变换

6.  整数反转

7. 字符串转换整数(atoi)

1. 两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9，所以返回 [0, 1]

思路：循环每个元素的差值，将每个元素与对应下标存入map，若当前元素的差值存在map中，则找到结果

class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer, Integer> map = new HashMap<>();for(int i = 0; i < nums.length; ++i){int num = target - nums[i];if(map.containsKey(num)){return new int[] {map.get(num), i};}map.put(nums[i], i);}return null;}
}

2. 两数相加

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

思路：根据加法的步骤，记录进位标志，浪费一个节点来提高代码可读性也未尝不可

加完后还有最后的进位也需要处理（carryFlag != 0）

/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/
class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {int carryFlag = 0;ListNode result = new ListNode(0);ListNode curr = result;while (l1 != null || l2 != null || carryFlag != 0) {int x = (l1 != null) ? l1.val : 0;int y = (l2 != null) ? l2.val : 0;int tmp = x + y + carryFlag;curr.next = new ListNode(tmp % 10);curr = curr.next;carryFlag = tmp / 10;if (l1 != null) {l1 = l1.next;}if (l2 != null) {l2 = l2.next;}}return result.next;}
}

字符串相乘（大数相乘）

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

输入: num1 = "123", num2 = "456"
输出: "56088"

思路：竖式乘法，num2的每一项与num1相乘，结果用stringBilder保存，然后相加。

注意的点：

1、num2向相乘时需要补0，如上图，num2的6与5相乘之前需要先给这一层的结果补0，最后反转就是结果所示

2、每层结果可以先根据竖式相乘的思想去做，最后将结果reverse即可

class Solution {public String multiply(String num1, String num2) {if (num1.equals("0") || num2.equals("0")) {return "0";}String ans = "0";int m = num1.length(), n = num2.length();// 从右到左循环num2的每一项，与num1相乘for (int i = n - 1; i >= 0; i--) {StringBuffer curr = new StringBuffer();int add = 0;// 竖式相乘每层结果补0for (int j = n - 1; j > i; j--) {curr.append(0);}// 获取到num2本层循环的数值int y = num2.charAt(i) - '0';for (int j = m - 1; j >= 0; j--) {int x = num1.charAt(j) - '0';int product = x * y + add;curr.append(product % 10);add = product / 10;}// 最后一个进位if (add != 0) {curr.append(add % 10);}ans = addStrings(ans, curr.reverse().toString());}return ans;}// 字符串相加public String addStrings(String num1, String num2) {int i = num1.length() - 1, j = num2.length() - 1, add = 0;StringBuffer ans = new StringBuffer();while (i >= 0 || j >= 0 || add != 0) {int x = i >= 0 ? num1.charAt(i) - '0' : 0;int y = j >= 0 ? num2.charAt(j) - '0' : 0;int result = x + y + add;ans.append(result % 10);add = result / 10;i--;j--;}ans.reverse();return ans.toString();}
}

3. 无重复字符的最长字串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

思路：滑动窗口，i是窗口左边界，j是窗口右边界，将字符一个一个放入hashMap

注意的点：如果当前字符在map中，需要重新计算i的值：初始想法是将i设置为重复元素的下标+1，即i = map.get(s.charAt(j)) + 1

例如："abcdb"，当循环到第二个b时，也就是i=0，j=4时，i的值会被设置为1+1 = 2，得出最大长度为4-2+1 = 3，结果正确。

但是会有这种情况，"abba"，当遇到b重复时，i = 2，j = 2。但是再遇到a重复时，i 就会等于 1，也就是说将重复的元素包含进去了。所以i计算时，不能往回退。需要给i 与 map.get(s.charAt(j)) + 1 取最大值，即i = Math.max(map.get(s.charAt(j)) + 1, i);

还需要注意，每次遇到重复元素都会将之前重复的元素下标覆盖掉，因为之前的已经计算过了

class Solution {public int lengthOfLongestSubstring(String s) {HashMap<Character, Integer> map = new HashMap();int res = 0;for (int i = 0, j = 0; j < s.length(); ++j) {if (map.containsKey(s.charAt(j))) {i = Math.max(map.get(s.charAt(j)) + 1, i);}res = Math.max(res, j - i + 1);map.put(s.charAt(j), j);}return res;}
}

4. 寻找两个数组的中位数

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1：nums1 = [1, 3]，nums2 = [2]，则中位数是 2.0
示例 2：nums1 = [1, 2]，nums2 = [3, 4]，则中位数是 (2 + 3)/2 = 2.5

思路：先排序然后取中位数，排序类似合并两个有序链表（自己的初始想法，以下是初始代码）

但时间复杂度是为O(m+n)，空间复杂度为O(m+n)

class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {//先排序然后取中位数，排序类似合并两个有序链表int length1 = nums1.length;int length2 = nums2.length;int[] resArr = new int[length1 + length2];int i = 0;int j = 0;int n = 0;while (i < length1 || j < length2) {if (i >= length1) {resArr[n] = nums2[j++];} else if (j >= length2) {resArr[n] = nums1[i++];} else if (nums1[i] > nums2[j]) {resArr[n] = nums2[j++];} else {resArr[n] = nums1[i++];}++n;}int resLen = resArr.length;return resLen % 2 == 0 ? (double) (resArr[resLen / 2] + resArr[resLen / 2 - 1]) / 2 : resArr[resLen / 2];}
}

算法的时间复杂度为 O(log(min(m + n)))的解法

思路：首先，中位数：将一个集合划分为两个长度相等的子集，其中一个子集中的元素总是大于另一个子集中的元素。

将A，B两个数组分别切割，切割点分别为i、j，分为左AB和右AB，保证切割点满足A[i-1] <= B[j] && B[j-1] <= A[i]，从而保证左AB均小于等于右AB，并且，len(左AB)=len(总AB)-len(右AB)，从而i+j = m-i + n-j，此时，

当A、B两个数组的总长度为偶数时，中位数=(max(A[i-1], B[j-1]) + min(A[i] + B[j]))/2，左AB的最大值和右AB的最小值的均值；

当A、B两个数组的总长度为奇数时，中位数=max(A[i-1], B[j-1])，左AB的最大值

class Solution {public double findMedianSortedArrays(int[] A, int[] B) {int m = A.length;int n = B.length;if (m > n) {// 保证 m <= nreturn findMedianSortedArrays(B,A);}int iMin = 0;int iMax = m;while (iMin <= iMax) {int i = (iMin + iMax) / 2;int j = (m + n + 1) / 2 - i;if (j != 0 && i != m && B[j - 1] > A[i]) {iMin = i + 1;} else if (i != 0 && j != n && A[i - 1] > B[j]) {iMax = i - 1;} else {//满足以上两个切割点条件int maxLeft = 0;if (i == 0) {maxLeft = B[j - 1];} else if (j == 0) {maxLeft = A[i - 1];} else {maxLeft = Math.max(B[j - 1], A[i - 1]);}//奇数直接返回if ((m + n) % 2 == 1) {return maxLeft;}int minRight = 0;if (i == m) {minRight = B[j];} else if (j == n) {minRight = A[i];} else {minRight = Math.min(B[j], A[i]);}return (maxLeft + minRight) / 2.0;}}return 0.0;}
}

Q1：为什么m <= n？

由于 0 <= i <= m  且 j = (m+n+1)/2−i，必须确保 j 不是负数。如果 n < m，那么 j 将可能是负数，而这会造成错误的答案。

Q2：j = (m+n+1)/2−i，为什么要+1?

因为当 A 数组和 B 数组的总长度是奇数时，要保证左半部分的长度比右半部分大1，这样中位数才是左AB的最大值

所以i + j = m - i  + n - j  + 1也就是 j = ( m + n + 1) / 2 - i

5. Z字形变换

将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：

L   C   I   R
E T O E S I I G
E   D   H   N

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。请你实现这个将字符串进行指定行数变换的函数：string convert(string s, int numRows);
示例 1：输入: s = "LEETCODEISHIRING", numRows = 3，输出: "LCIRETOESIIGEDHN"
示例 2：输入: s = "LEETCODEISHIRING", numRows = 4，输出: "LDREOEIIECIHNTSG"

L     D     R
E   O E   I I
E C   I H   N
T     S     G

思路：1.每一行都创建一个StringBuilder；2.遍历字符串，将每个字符放到对应行，遇到第一行和最后一行，行走的方向变化；3.将每一行的StringBuilder拼接

class Solution {public String convert(String s, int numRows) {if (s.length() < numRows || numRows == 1) {return s;}//每一行都创建一个StringBuilderList<StringBuilder> rowlist = new ArrayList<>(numRows);for (int i = 0; i < numRows; ++i) {rowlist.add(new StringBuilder());}//遍历字符串，将每个字符放到对应行int curRow = 0;boolean growRow = false;for (char ch : s.toCharArray()) {rowlist.get(curRow).append(ch);//方向变化if (curRow == 0 || curRow == numRows - 1) {growRow = !growRow;}curRow += growRow ? 1 : -1;}//将每一行的StringBuilder拼接StringBuilder res = new StringBuilder();for (StringBuilder sb : rowlist) {res.append(sb);}return res.toString();}
}

6.  整数反转

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

示例 1:输入: 123输出: 321
示例 2:输入: -123输出: -321
示例 3:输入: 120输出: 21
注意:假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231,  231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。

思路：通过取余(%)获取每位数，通过res = res * 10 + pop一位位递进，中间需判断是否有溢出情况

class Solution {public int reverse(int x) {int res = 0;while (x != 0) {//每位数int pop = x % 10;//Integer范围：-2147483648～2147483647if (res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && pop > 7)) {return 0;}if (res < Integer.MIN_VALUE / 10 || (res == Integer.MIN_VALUE / 10 && pop < -8)) {return 0;}res = res * 10 + pop;x /= 10;}return res;}
}

7. 字符串转换整数(atoi)

首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。在任何情况下，若函数不能进行有效的转换时，请返回 0。

说明：假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231,  231 − 1]。如果数值超过这个范围，请返回  INT_MAX (231 − 1) 或 INT_MIN (−231) 。

示例 1:输入: "42"输出: 42
示例 2:输入: "   -42"输出: -42，解释: 第一个非空白字符为 '-', 它是一个负号。我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
示例 3:输入: "4193 with words"输出: 4193，解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。
示例 4:输入: "words and 987"输出: 0，解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
     因此无法执行有效的转换。
示例 5:输入: "-91283472332"输出: -2147483648解释: 数字 "-91283472332" 超过 32 位有符号整数范围，因此返回 INT_MIN (−231) 。

思路：1. 去掉字符串前后空格；2. 处理第一个字符为正负号的情况；3. 一个一个取数判断通过res * 10 + tmp凑数；4. 判断是否溢出同7整数反转（初始想法）

class Solution {public int myAtoi(String str) {str = str.trim();int res = 0;int i = 0;boolean negativeFlag = false;if (str.startsWith("-")) {i++;negativeFlag = true;}if (str.startsWith("+")) {i++;}char[] strArray = str.toCharArray();for (; i < strArray.length; ++i) {if (strArray[i] < '0' || strArray[i] > '9') {return negativeFlag ? -res : res;}int tmp = strArray[i] - '0';if (!negativeFlag && (res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && tmp > 7))) {return Integer.MAX_VALUE;}if (negativeFlag && (-res < Integer.MIN_VALUE / 10 || (-res == Integer.MIN_VALUE / 10 && tmp > 8))) {return Integer.MIN_VALUE;}res = res * 10 + tmp;}return negativeFlag ? -res : res;}
}

这篇关于LeetCode：两数之和+两数相加+字符串相乘+无重复字符的最长字串+寻找两个数组的中位数+Z字形变换+整数反转+字符串转换整数(atoi)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/836917。

相关文章

哈希leetcode-1

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素（O(1)） 当我们要频繁的查找某个元素，第一哈希表O(1)，第二，二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储，只要开26个c
阅读更多...
hdu2241（二分+合并数组）

hdu2241（二分+合并数组）

题意：判断是否存在a+b+c = x，a，b，c分别属于集合A,B,C 如果用暴力会超时，所以这里用到了数组合并，将b,c数组合并成d，d数组存的是b，c数组元素的和，然后对d数组进行二分就可以了 代码如下（附注释）： #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que
阅读更多...
poj2406（连续重复子串）

poj2406（连续重复子串）

题意:判断串s是不是str^n，求str的最大长度。 解题思路：kmp可解，后缀数组的倍增算法超时。next[i]表示在第i位匹配失败后，自动跳转到next[i]，所以1到next[n]这个串 等于 n-next[n]+1到n这个串。 代码如下； #include<iostream>#include<algorithm>#include<stdio.h>#include<math.
阅读更多...
poj3261（可重复k次的最长子串）

poj3261（可重复k次的最长子串）

题意：可重复k次的最长子串 解题思路：求所有区间[x,x+k-1]中的最小值的最大值。求sa时间复杂度Nlog(N),求最值时间复杂度N*N，但实际复杂度很低。题目数据也比较水，不然估计过不了。 代码入下： #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
hdu 1166 敌兵布阵（树状数组 or 线段树）

hdu 1166 敌兵布阵（树状数组 or 线段树）

题意是求一个线段的和，在线段上可以进行加减的修改。 树状数组的模板题。 代码： #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while
阅读更多...
PTA求一批整数中出现最多的个位数字

PTA求一批整数中出现最多的个位数字

作者 徐镜春 单位 浙江大学 给定一批整数，分析每个整数的每一位数字，求出现次数最多的个位数字。例如给定3个整数1234、2345、3456，其中出现最多次数的数字是3和4，均出现了3次。 输入格式： 输入在第1行中给出正整数N（≤1000），在第二行中给出N个不超过整型范围的非负整数，数字间以空格分隔。 输出格式： 在一行中按格式“M: n1 n2 ...”输出，其中M是最大次数，n
阅读更多...
整数Hash散列总结

整数Hash散列总结

方法：    step1  :线性探测  step2 散列   当 h(k)位置已经存储有元素的时候，依次探查(h(k)+i) mod S, i=1,2,3…，直到找到空的存储单元为止。其中，S为 数组长度。 HDU 1496   a*x1^2+b*x2^2+c*x3^2+d*x4^2=0 。 x在 [-100,100] 解的个数  const int MaxN = 3000
阅读更多...
pip-tools：打造可重复、可控的 Python 开发环境，解决依赖关系，让代码更稳定

pip-tools：打造可重复、可控的 Python 开发环境，解决依赖关系，让代码更稳定

在 Python 开发中，管理依赖关系是一项繁琐且容易出错的任务。手动更新依赖版本、处理冲突、确保一致性等等，都可能让开发者感到头疼。而 pip-tools 为开发者提供了一套稳定可靠的解决方案。 什么是 pip-tools？ pip-tools 是一组命令行工具，旨在简化 Python 依赖关系的管理，确保项目环境的稳定性和可重复性。它主要包含两个核心工具：pip-compile 和 pip
阅读更多...
leetcode-24Swap Nodes in Pairs

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2