LeetCode算法题 顶
第1题https://leetcode-cn.com/problems/two-sum/
两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
常规算法
public class Solution {
public int[] twoSum(int[] nums, int target) {
int[] result = new int[2];
res:
for (int i = 0;i < nums.length;i++) {
for (int j = i + 1;j < nums.length;j++) {
if (nums[i] + nums[j] == target) {
result[0] = i;
result[1] = j;
break res;
}
}
}
return result;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] a = {2,7,11,15};
int[] result = solution.twoSum(a,9);
for (int i = 0;i < result.length;i++) {
System.out.println(result[i]);
}
}
}运行结果
0 1
但该算法的时间复杂度为O(n^2)的，所以我们考虑将该算法降低到O(n)级别
public class Solution1 {
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> map = new HashMap<>(nums.length);
for (int i = 0;i < nums.length;i++) {
int pre = target - nums[i];
Integer preIndex = map.get(pre);
if (preIndex != null) {
return new int[] {preIndex,i};
}
map.put(nums[i],i);
}
return null;
}
public static void main(String[] args) {
Solution1 solution = new Solution1();
int[] a = {2,7,11,15};
int[] result = solution.twoSum(a,9);
for (int i = 0;i < result.length;i++) {
System.out.println(result[i]);
}
}
}运行结果
0 1
第2题https://leetcode-cn.com/problems/add-two-numbers/
两数相加
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807正面刚
/**
* 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) {
String a = "";
while (l1 != null) {
a += l1.val;
l1 = l1.next;
}
a = new StringBuffer(a).reverse().toString();
String b = "";
while (l2 != null) {
b += l2.val;
l2 = l2.next;
}
b = new StringBuffer(b).reverse().toString();
String result = "";
boolean add = false;
int d = 0;
int len;
if (a.length() < b.length()) {
len = b.length();
}else {
len = a.length();
}
for (int i = 0;i < len;i++) {
if (add) {
if (i < a.length() && i < b.length()) {
d = Integer.parseInt(a.substring(a.length() - 1 - i, a.length() - i))
+ Integer.parseInt(b.substring(b.length() - 1 - i, b.length() - i)) + 1;
}else if (i >= a.length()) {
d = Integer.parseInt(b.substring(b.length() - 1 - i, b.length() - i)) + 1;
}else if (i >= b.length()) {
d = Integer.parseInt(a.substring(a.length() - 1 - i, a.length() - i)) + 1;
}
}else {
if (i < a.length() && i < b.length()) {
d = Integer.parseInt(a.substring(a.length() - 1 - i, a.length() - i))
+ Integer.parseInt(b.substring(b.length() - 1 - i, b.length() - i));
}else if (i >= a.length()) {
d = Integer.parseInt(b.substring(b.length() - 1 - i, b.length() - i));
}else if (i >= b.length()) {
d = Integer.parseInt(a.substring(a.length() - 1 - i, a.length() - i));
}
}
if (d >= 10) {
result += String.valueOf(d).substring(1,2);
add = true;
}else {
result += String.valueOf(d);
add = false;
}
}
if (add) {
result += 1;
}
ListNode node = new ListNode(Integer.parseInt(result.substring(0,1)));
ListNode ret = node;
for (int i = 1;i < result.length();i++) {
node.next = new ListNode(Integer.parseInt(result.substring(i,i + 1)));
node = node.next;
}
return ret;
}
}第2题的优化
根据上面比较复杂的写法，根据其原理做了极简优化
/**
* 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) {
boolean add = false;
ListNode dummyHead = new ListNode(-1);
ListNode node = dummyHead;
while (l1 != null && l2 != null) {
int sum;
if (add) {
sum = l1.val + l2.val + 1;
}else {
sum = l1.val + l2.val;
}
if (sum >= 10) {
add = true;
}else {
add = false;
}
node.next = new ListNode(sum % 10);
node = node.next;
l1 = l1.next;
l2 = l2.next;
}
while (l1 != null) {
if (add) {
node.next = new ListNode((l1.val + 1) % 10);
if (l1.val + 1 >= 10) {
add = true;
}else {
add = false;
}
}else {
node.next = new ListNode(l1.val);
}
node = node.next;
l1 = l1.next;
}
while (l2 != null) {
if (add) {
node.next = new ListNode((l2.val + 1) % 10);
if (l2.val + 1 >= 10) {
add = true;
}else {
add = false;
}
}else {
node.next = new ListNode(l2.val);
}
node = node.next;
l2 = l2.next;
}
if (add) {
node.next = new ListNode(1);
}
return dummyHead.next;
}
}晒一下成绩
第3题https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。这道题使用暴力解题是会超时的。比方说这样
public class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Set<Character>,Integer> map = new HashMap<>();
Set<Character> key = new HashSet<>();
int from = 0;
String s1 = s;
while (!s.equals("")) {
for (int i = 0; i < s.length(); i++) {
if (!key.contains(s.charAt(i))) {
key.add(s.charAt(i));
map.put(key, key.size());
} else {
map.put(key, key.size());
key.clear();
key.add(s.charAt(i));
}
}
from++;
s = s1.substring(from);
key.clear();
}
return map.values().stream().max(Comparator.comparing(x -> x)).orElse(0);
}
}滑动窗口法：使用一个带边界的集合来不断调整边界范围来获取我们需要的结果
public class Solution {
public int lengthOfLongestSubstring(String s) {
Set<Character> set = new HashSet<>();
int n = s.length();
int maxlen = 0;
int i = 0;
int j = 0;
while (i < n && j < n) {
if (!set.contains(s.charAt(j))) {
set.add(s.charAt(j));
j++;
maxlen = Math.max(maxlen,j - i);
}else {
set.remove(s.charAt(i));
i++;
}
}
return maxlen;
}
}第4题https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
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之前我以为这道题是不允许重复值的
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
SortedSet<Integer> set = new TreeSet<>();
SortedMap<Integer,Integer> map = new TreeMap<>();
double ret;
for (int i = 0;i < nums1.length;i++) {
set.add(nums1[i]);
}
for (int i = 0;i < nums2.length;i++) {
set.add(nums2[i]);
}
int len = set.size();
for (int i = 1;i <= len;i++) {
map.put(i,set.first());
set.remove(set.first());
}
if ((map.size() & 1) == 0) {
if (map.size() > 2) {
SortedMap<Integer, Integer> subMap = map.subMap(map.size() / 2, map.size() / 2 + 2);
ret = (subMap.get(subMap.firstKey()) + subMap.get(subMap.lastKey())) / 2.0;
}else {
ret = (map.get(map.firstKey()) + map.get(map.lastKey())) / 2.0;
}
}else {
if (map.size() > 1) {
SortedMap<Integer, Integer> subMap = map.subMap(map.size() / 2 + 1, map.size() / 2 + 2);
ret = subMap.get(subMap.firstKey());
}else {
ret = map.get(map.firstKey());
}
}
return ret;
}
}但是提交给leetCode是不能通过的，实际上它允许重复值。
现在改用归并排序，结果可以通过了，但实际上在归并排序中的时间复杂度为O(m+n)，并不能满足时间复杂度的要求
class Solution1 {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int i = 0;
int j = 0;
int[] data = new int[nums1.length + nums2.length];
for (int k = 0;k < data.length;k++) {
if (i >= nums1.length) {
data[k] = nums2[j];
j++;
}else if (j >= nums2.length) {
data[k] = nums1[i];
i++;
}else if (nums1[i] < nums2[j]) {
data[k] = nums1[i];
i++;
}else {
data[k] = nums2[j];
j++;
}
}
if ((data.length & 1) == 1) {
return data[data.length / 2];
}else {
return (data[data.length / 2 - 1] + data[data.length / 2]) / 2.0;
}
}
}
之后我们会改用二分查找法才能真正满足算法复杂度的要求。
第70题https://leetcode-cn.com/problems/climbing-stairs/
70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶这道题就是一道可以用动态规划来解决的题
class Solution {
public int climbStairs(int n) {
int[] memo = new int[n + 1];
memo[0] = 1;
memo[1] = 1;
for (int i = 2;i <=n;i++) {
memo[i] = memo[i - 1] + memo[i - 2];
}
return memo[n];
}
}
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读