stellarring/leetcodejournal

LeetCode 挑战日志

一、算法挑战

1、两数之和

分解思路：

• 将输入数组“复制”成两个数组:A[3,2,5],[3,2,5]
• 外层循环依次取A的每个元素
• 内存循环从外层循环的位置开始循环
• 循环过程中计算外层循环和内存循环当前的两数之和
• 如果满足条件，返回数组坐标
• 算法时间复杂度O(N^2)

2、两数相加

分解思路:

• 输入两个链表L1、L2
• 取L1第一个节点值和L2第二个节点值相加
• 如果节点为null，取其val为0
• 如果两数之和>9，采取next.val+1策略（递归循环检查）
• 根据链表选择器返回正确的链表
• 算法时间复杂度O(N)

3、无重复字符的最长子串

分解思路:

• 输入字符串S
• 循环取S字符串作为子串的头head
• 然后取head所在下标顺序取字符S0
• 如果S0不在子串内就拼接，否则读取最大子串长度
• 置空临时子串，进入下一次循环
• 算法时间复杂度O(N^2)

4、两个排序数组的中位数

分解思路:

• 利用归并排序的归并法将这两个有序数组（B、C）合并成一个有序数组（假设是A）
• 如果两个数组元素个数之和为奇数，返回(A[(A.len+1)/2])
• 如果两个数组元素个数之和为偶数，返回(（A[(A.len)/2]+ A[(A.len+1)/2]）/2)
• 算法优化：因为只需要寻找中位数，因此A的长度最大为（B.len+C.len）/2+1