leetcode刷题记录
github源码地址
https://github.com/lianxiaobao/LeetCode-learn
注释：demo 2 为官方思路，为了不重复造轮子我就不贴官方的思路直接贴链接了
每道题都写有自己的做法和官方的思路 某云的生活让我感受到了优化的重要性，同样的功能别人比自己要效率高很多，这是我们需要思考的地方
num 1
/**
* Created by IntelliJ IDEA.
* User: lianxiaobao
* Date: 2019-12-02
* Time: 22:16
*
*
*
* 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
*
* 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
*
* 示例:
*
* 给定 nums = [2, 7, 11, 15], target = 9
*
* 因为 nums[0] + nums[1] = 2 + 7 = 9
* 所以返回 [0, 1]
*/
- demo 1
package com.bcxiaobao.leetcode.algorithm;
import java.util.Arrays;
import java.util.HashMap;
public class TwoNumAdd {
public static void main(String[] args) {
int[] nums = new int[]{3, 2, 4, 15};
System.out.println(Arrays.toString(nums));
System.out.println(Arrays.toString(twoSumOrdinary(nums, 6)));
}
public static int[] twoSumOrdinary(int[] nums, int target) {
int[] num = new int[2];
for (int i = 0; i <nums.length ; i++) {
for (int j = nums.length-1; j >i ; j--) {
if((nums[i]+ nums[j]) == target){
num[0] = i;
num[1] = j;
return num;
}
}
}
return num;
}
}
- demo 2
/**
* leetcode 测试性能提高十倍
* @param nums
* @param target
* @return
*/
public static int[] twoSumByMap(int[] nums,int target){
int[] num = new int[2];
// 建立k-v ，一一对应的哈希表
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int i = 0; i < nums.length; i++){
if(map.containsKey(nums[i])){
num[0] = i;
num[1] = map.get(nums[i]);
return num;
}
// 将数据存入 key为补数 ，value为下标
map.put(target-nums[i],i);
}
return num;
}
num2
- 思路
方法：初等数学
我们使用变量来跟踪进位，并从包含最低有效位的表头开始模拟逐位相加的过程。
算法
就像你在纸上计算两个数字的和那样，我们首先从最低有效位也就是列表 l1 和 l2 的表头开始相加。由于每位数字都应当处于0…9 的范围内，我们计算两个数字的和时可能会出现 “溢出”。例如，5 + 7 = 12。在这种情况下，我们会将当前位的数值设置为 22，并将进位 carry = 1 带入下一次迭代。进位 carry 必定是 0 或 1，这是因为两个数字相加（考虑到进位）可能出现的最大和为 9 + 9 + 1 = 19。
伪代码如下：
- 将当前结点初始化为返回列表的哑结点。
- 将进位 carrycarry 初始化为 00。
- 将 pp 和 qq 分别初始化为列表 l1l1 和 l2l2 的头部。
- 遍历列表 l1l1 和 l2l2 直至到达它们的尾端。
- 将 xx 设为结点 pp 的值。如果 pp 已经到达 l1l1 的末尾，则将其值设置为 00。
- 将 yy 设为结点 qq 的值。如果 qq 已经到达 l2l2 的末尾，则将其值设置为 00。
- 设定 sum = x + y + carrysum=x+y+carry。
- 更新进位的值，carry = sum / 10carry=sum/10。
- 创建一个数值为 (sum \bmod 10)(summod10) 的新结点，并将其设置为当前结点的下一个结点，然后将当前结点前进到下一个结点。
- 同时，将 pp 和 qq 前进到下一个结点。
- 检查 carry = 1carry=1 是否成立，如果成立，则向返回列表追加一个含有数字 11 的新结点。
- 返回哑结点的下一个结点。
请注意，我们使用哑结点来简化代码。如果没有哑结点，则必须编写额外的条件语句来初始化表头的值。
请特别注意以下情况：
| 测试用例 | 说明 |
|---|---|
| l1=[0,1]，l2=[0,1,2] | 当一个列表比另一个列表长时 |
| l1=[] ，l2=[0,1] | 当一个列表为空时，即出现空列表 |
| l1=[9,9] ，l2=[1] | 求和运算最后可能出现额外的进位，这一点很容易被遗忘 |
/**
* Created by IntelliJ IDEA.
* User: lianxiaobao
* Date: 2019-12-03
* Time: 14:47
*/
/**
* 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
*
* 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
*
* 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
*
* 示例：
*
* 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
* 输出：7 -> 0 -> 8
* 原因：342 + 465 = 807
*
*/
- demo1
public class TwoNumAdd {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode start = new ListNode(0);
ListNode offset = start;
int carry =0;
while (l1 != null || l2 !=null || carry!=0){
//求和
int valuel1 = (l1 !=null) ? l1.val: 0;
int valuel2 = (l2 !=null) ? l2.val: 0;
int sum = valuel1 + valuel2 + carry;
//进位更新
carry = sum/10;
//求和后的该位值
ListNode sumnode = new ListNode(sum % 10);
offset.next = sumnode;
offset = sumnode;
//将l1、l2 进行下个位的运算
if( l1 != null){
l1 = l1.next;
}
if( l2 != null){
l2 = l2.next;
}
}
return start.next;
}
}
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
结果：
- demo2
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(0);
ListNode p = l1, q = l2, curr = dummyHead;
int carry = 0;
while (p != null || q != null) {
int x = (p != null) ? p.val : 0;
int y = (q != null) ? q.val : 0;
int sum = carry + x + y;
carry = sum / 10;
curr.next = new ListNode(sum % 10);
curr = curr.next;
if (p != null) p = p.next;
if (q != null) q = q.next;
}
if (carry > 0) {
curr.next = new ListNode(carry);
}
return dummyHead.next;
}
作者：LeetCode
复杂度分析
- 时间复杂度：O(max(m, n))，假设 m 和 n 分别表示 l1 和 l2 的长度，上面的算法最多重复 max(m,n) 次。
- 空间复杂度：O(max(m,n))， 新列表的长度最多为 max(m,n)+1。
num3
/**
* 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
*
* 示例 1:
*
* 输入: "abcabcbb"
* 输出: 3
* 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
* 示例 2:
*
* 输入: "bbbbb"
* 输出: 1
* 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
* 示例 3:
*
* 输入: "pwwkew"
* 输出: 3
* 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
* 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
*/
- demo 1
package com.bcxiaobao.leetcode.algorithm;
/**
* Created by IntelliJ IDEA.
* User: lianxiaobao
* Date: 2019-12-05
* Time: 23:46
*/
public class LengthOfLongestSubstring {
public static void main(String[] args) {
int substring = lengthOfLongestSubstring("bbbbb");
System.out.println(substring);
}
public static int lengthOfLongestSubstring(String s) {
char[] model = s.toCharArray();
int maxLenth = 0;
int leftModel = 0;
for (int i = 0; i < model.length; i++) {
for (int j = leftModel; j < i; j++) {
if(model[i] == model[j]){
//i - leftModel 表示的是一个不重复子串的长度，
// 然后拿这个长度跟maxLength比一下，
// 看它是不是比maxLength还要长，
// 如果是的话，maxLength就要更新
maxLenth = Math.max(maxLenth,i-leftModel);
leftModel = j+1;
break;
}
}
}
return Math.max(model.length-leftModel,maxLenth);
}
}
- demo 2
