目录
前言
应之前里的flag 今天开始更新每日算法专栏
题库 - 力扣 (LeetCode) 全球极客挚爱的技术成长平台
这套题难度比例大概是1:2:1 总共145道，有两道要开会员就不做了。本人实力有限，尽可能做到较好理解的方法去解题，后期对于算法的知识补全后会进行更新
做题安排
3+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]
我们要做的就是在一个数组中到能相加得到目标数字的两个数字的下标,一般看到有值有下标的数组题就要反应过来使用Map来解题，这个题我们是要得到下标我们就把下标设为value ,让数字的值作为Key 。
代码实现
class Solution {
public int[] twoSum(int[] nums, int target) {
//本题涉及数组值与下标，采用Map来解题
Map<Integer,Integer> map = new HashMap<>();//下标与值都是整型
for(int i = 0; i < nums.length ;i++){
/*遍历数组，一边把数据以<数字，下标>的形式存入map中，
一边存一边判断如果map中存在key和当前数字能构成目标数字的key，
返回value和当前遍历的下标
*/
if(map.get(target-nums[i]) != null){
return new int[]{map.get(target-nums[i]),i};
}
map.put(nums[i],i);
}
//没有符合的返回0,0
return new int[]{0,0};
}
}13. 罗马数字转整数
罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。
示例 1:
输入: s = "III"
输出: 3
示例 2:
输入: s = "IV"
输出: 4
示例 3:
输入: s = "IX"
输出: 9
示例 4:
输入: s = "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.
示例 5:
输入: s = "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.
对于这个题我们也考虑去使用map存罗马数字和它所对应的阿拉伯数字，题中传入的字符串是罗马数字那我们就用罗马数字作为key。这个题用到两个方法:
1 map.containsKey（key），map中的containsKey（key）方法是判断该key在map中是否有key存在。如果存在则返回true。如果不存在则返回false。
2 s.substring() substring() 方法用于提取字符串中介于两个指定下标之间的字符。
代码实现
class Solution {
public int romanToInt(String s) {
Map<String, Integer> map = new HashMap<>();
//所有可能的都列出来，罗马数字大的在左边就是直接加，大的在右边是相减
map.put("I", 1);
map.put("IV", 4);
map.put("V", 5);
map.put("IX", 9);
map.put("X", 10);
map.put("XL", 40);
map.put("L", 50);
map.put("XC", 90);
map.put("C", 100);
map.put("CD", 400);
map.put("D", 500);
map.put("CM", 900);
map.put("M", 1000);
int res = 0;
for (int i = 0; i < s.length(); ) {
//先截取两个字符，如果这两个字符存在于map中，就表示他们是一个整体。否则就截取一个
if (i + 1 < s.length() && map.containsKey(s.substring(i, i + 2))) {
res += map.get(s.substring(i, i + 2));
i += 2;
} else {
res += map.get(s.substring(i, i + 1));
i++;
}
}
return res;
}
}14. 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1：
输入：strs = ["flower","flow","flight"]
输出："fl"
示例 2：
输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。
这题就是找到相同的前缀，比较简单，看注释就差不多能理解了 indesOf就是返回的下标，false返回-1 true时我们要找的前缀是从头开始也就是0。
class Solution {
public String longestCommonPrefix(String[] strs) {
//判空
if(strs == null || strs.length == 0){
return("");
}
//题的前提条件是字符串是从小到大排的，我们直接将第一个字符串当做前缀
String pre = strs[0];
int i = 1;
while (i < strs.length) {
//不符合就往前截一位
while (strs[i].indexOf(pre) != 0)
pre = pre.substring(0, pre.length() - 1);
i++;
}
return pre;
}
}2. 两数相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]
示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]
直接将它看成两个整数相加，只不过数字是反过来写的。我们考虑让节点相加，相加的的值对10取模 ，有进位就把进位放到下一个节点接着加。判断时只要两个链表一个没结束我们就不停止。这里新建一个链表去存值就好。
代码实现
/**
* 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 blindNode = new ListNode(0);
//pre为当前节点的前一个节点
ListNode preNode = blindNode;
int curry = 0;//curry来放进位的数
while(l1 != null || l2 != null || curry != 0){
int sum = curry;//
if(l1 != null){//第一个链表
sum = sum + l1.val;
l1 = l1.next;
}
if(l2 != null){//第二个
sum = sum + l2.val;
l2 = l2.next;
}
preNode.next = new ListNode(sum % 10);//个位
curry = sum /10;//十位
preNode = preNode.next;
}
return blindNode.next;
}
}总用时50分钟。