闲暇之际敲敲代码，记录Leetcode刷题Day-01
文章目录
- 前言
- 一、两数之和
- 1.1 问题描述
- 1.2 思路分析
- 二、整数反转
- 2.1 问题描述
- 2.2 思路分析
- 三、额外题目
- 3.1 问题描述
- 3.2 思路分析
前言
利用闲暇之际敲敲代码，提升编程技能及提高算法能力。
一、两数之和
1.1 问题描述
给定一个整数数组nums和一个整数目标值target,请你在该数组中找出和为目标值 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]
1.2 思路分析
1.2.1 暴力解法： 将数组的内的元素两两依次相加，相加之和与target值进行比较。若相等则返回该两数的数组下标。如示例2：target = 6，先nums[0] + nums[1] = 5 ! = targe，继续寻找下一个元素进行相加：nums[0] + nums[2] = 7 != target。内层 for 循环完毕调至外层 for 循环 nums[1] + nums[2] = 6 = target 输出：[1,2]，若整个循环结束仍没有查到这两个数则返回：[ ]。复杂度分析：时间复杂度：O(N^2)，其中 N 是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次。空间复杂度：O(1)。
代码实现：
public class TwoNumSum {
public static void main(String[] args) {
int[] array = {12, 4, 5, 6, 8, 3, 4, 89, 80, 23, 45, 88};
int tar = 169;
System.out.println("输入：" + Arrays.toString(array) + "target = " + tar);
int[] array1 = twoNumSum(array, tar);
System.out.println("输出：" + Arrays.toString(array1));
}
public static int[] twoNumSum(int[] array, int target) {
int[] array1;
for (int i = 0; i < array.length - 1; i++) {
for (int j = i + 1; j < array.length - 1; j++) {
if (array[j] + array[i] == target) {
return array1 = new int[]{i, j};
}
}
}
return new int[0];
}
}
输出结果：
输入：[12, 4, 5, 6, 8, 3, 4, 89, 80, 23, 45, 88] target = 169
输出：[7, 8]
Process finished with exit code 0
target = 1000 时：
输入：[12, 4, 5, 6, 8, 3, 4, 89, 80, 23, 45, 88] target = 1000
输出：[]
Process finished with exit code 0
1.2.2 哈希表解法： 注意到方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N) 降低到 O(1)。这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。
代码实现：
public class TwoSum {
public static void main(String[] args) {
int []array = {12,4,5,6,8,3,4,89,80,23,45,88};
int tar = 7;
System.out.println("输入："+Arrays.toString(array) + "target = " + tar1);
int []arr = twoSum(array,tar);
System.out.println("输出："+Arrays.toString(arr));
}
public static int[] twoSum(int[] nums, int target){
int[] res = new int[2];
if(nums == null || nums.length == 0){
return res;
}
Map<Integer,Integer> map = new HashMap<>();
for(int i = 0; i < nums.length; i++){
int temp = target - nums[i];
//判断map中是否存在temp
if(map.containsKey(temp)){
res[1] = i;
res[0] = map.get(temp);
}
//如果不存在将nums[i],i存入map中
map.put(nums[i],i);
}
if (res[0] != 0 && res[1] != 0) {
return res;
}
return new int[2];
}
}
输出结果：
输入：[12, 4, 5, 6, 8, 3, 4, 89, 80, 23, 45, 88] target = 7
输出：[5, 6]
Process finished with exit code 0
输入：[12, 4, 5, 6, 8, 3, 4, 89, 80, 23, 45, 88] target = 1000
输出：[]
Process finished with exit code 0
二、整数反转
2.1 问题描述
给你一个32位的有符号整数x,返回将x中的数字部分反转后的结果。
如果反转后整数超过32位的有符号整数的范围[−231, 231 − 1],就返回0。
假设环境不允许存储64位整数(有符号或无符号)。
示例 1：
输入：x = 123
输出：321
示例 2：
输入：x = -123
输出：-321
示例 3：
输入：x = 120
输出：21
示例 4：
输入：x = 0
输出：0
提示:-231 <= x <= 231 - 1
2.2 思路分析
2.2.1 思路分析
将整数x值转为字符串str便于处理，判断字符串第0个字符是否等于’ - '，若相等则表明x为负数，记录start = “-”，截取字符串str从1到str.length() - 1的字符串进行下一步处理。从str.length() - 1逆序循环遍历字符，定义字符串s进行接收做拼接处理。循环遍历结束则将整数x逆序处理完毕，符号问题在拼接上start，最后Integer.parseInt(s)字符串转数字即可。
代码实现
public static int reverseInt(int x) {
String str = String.valueOf(x);
String start = "";
if (str.charAt(0) == '-') {
start = "-";
str = str.substring(1);
}
String s = "";
int length = str.length() - 1;
for (int i = length;i >= 0;i--) {
s+= str.charAt(i);
}
s = start + s;
try {
return Integer.parseInt(s);
}catch (Exception e){
return 0;
}
}
输出结果
输入：-802210
输出：-12208
Process finished with exit code 0
三、额外题目
3.1 问题描述
写一段小程序用于统计字符串str中连续出现字母的个数,例如"AAAABBBCCDFD"变为"4A3B2C1D1F1D"
3.2 思路分析
3.2.1 思路分析
如上图所示我们只需要比较相邻两个字符是否相等，定义一个变量count用于记录相等字符个数，初始值为1。若相邻两个字符相等则count加一，不相等则表明连续字符不在连续，count重置为一并使用StringBuilder对象进行count和字符的拼接。
注意点：循环次数应该是i < str.length() - 1 不能是i < str.length()若i < str.length() 则str.charAt(i) == str.charAt(i + 1)出现越界情况。也就是说最后的str.charAt(i + 1)要单独处理，而count是已经处理过的了，如上图最后两个D比较：str.char(20) == str.char(21) 相等则count = 4，不相等count = 1。综上str.charAt(str.length() - 1)单独处理再拼接count即可。
代码实现
public static String getLettersAndNum(String str) {
String res = "";
if (StringUtils.isEmpty(str)){
return res;
}
int count = 1;
StringBuilder builder = new StringBuilder();
for (int i = 0; i < str.length() - 1; i++) {
if (str.charAt(i) == str.charAt(i + 1)){
count++;
}else{
builder = builder.append(count).append(str.charAt(i));
count = 1;
}
}
res = builder.append(count).append(str.charAt(str.length() - 1)).toString();
return res;
}