leetcode题解

数组

No1.两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

明确题目

每种输入只会对应一个答案可以理解为，不需要对数组的长度进行校验。

不能重复利用这个数组中同样的元素：需要进行校验。

所有可能解

蛮力法

通过两次loops，外层循环枚举 x，内层循环枚举 y，然后逐次判断 x + y 是否等于 target。

public int[] twoSum(int[] nums, int target) {
  if(nums.length < 2) return new int[0];

  for(int i = 0; i < nums.length -1; i++) {
    for(int j = i+1; j < nums.length;j++) {
      if(nums[i] + nums[j] == target) {
        return new int[]{i, j};
      }
    }
  }
  return new int[0];
}

复杂度分析：

时间复杂度为：O(n^2)，空间复杂度：O(1)；

HashMap

public int[] twoSum(int[] nums, int target) {
  if(nums.length < 2) return new int[0];
  Map<Integer, Integer> store = new HashMap<>();

  for(int i = 0; i < nums.length; i++) {
    if(store.containsKey(target - nums[i]) && store.get(target - nums[i]) != nums[i]) {
      return new int[]{store.get(target - nums[i]), i};
    } else {
      store.put(nums[i], i);
    }
  }
  return new int[0];

}

复杂度分析：

时间复杂度为：只遍历一次数组，O(N)，空间复杂度为：O(N)，最坏的情况下，HashMap中要存放所有数组数据。

链表

No206.反转链表

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

明确题目

当前节点指向它的前一节点。

所有可能解

#####记录当前节点和前一个节点

public ListNode reverseList(ListNode head) {
  ListNode prev = null;
  ListNode curr = head;
  while(curr != null) {
    ListNode temp = curr.next;
    curr.next = prev;
    prev = curr;
    curr = temp;
  }
  return prev;
}

复杂度分析：

时间复杂度：O(n)，空间复杂度为：O(1)。

No141.环形链表

给定一个链表，判断链表中是否有环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

明确题目

有环的链表的特点是一直会有next节点，同时还有一个特点是，存在一个节点是两个节点的后继节点，无环的链表特点是会有next节点为null。

所有可能解

蛮力法

读取链表下一个节点，直到为null。不可取。

Set存储节点

每次读取下一个节点的时候，判断Set中是否存在该节点，若存在则表示存在环。

public boolean hasCycle(ListNode head) {
  ListNode curr = head;
  Set<ListNode> store = new HashSet<>();
  while(curr != null) {
    if(store.contains(curr)) {
      return true;
    } else {
      store.add(curr);
      curr = curr.next;
    }
  }
  return false;
}

复杂度分析：

时间复杂度为：O(N)，空间复杂度为：O(N)。

快慢指针

慢指针步长为1，快指针步长为2。

public boolean hasCycle(ListNode head) {
  if(head == null || head.next == null) {
    return false;
  }
  ListNode slow = head;
  ListNode fast = head.next;
  while(slow != fast) {
    if(fast == null || fast.next == null) {
      return false;
    }
    slow = slow.next;
    fast = fast.next.next;
  }
  return true;
}

判断的时候判断快指针就可以了。

复杂度分析：

时间复杂度为：O(N)，空间复杂度为：O(1)。

No160.相交链表

找到两个单链表相交的起始节点。

明确题目

相交的单链表特点：

• 存在两个节点的后继节点为一个节点。

• 链表A和链表B未相交部分分别为：A：a1->a2 B：b1->b2->b3，相交部分为：c1->c2->c3，则有

  a1->a2->c1->c2->c3->null->b1->b2->b3->c1 长度等于 b1->b2->b3->c1->c2->c3->null->a1->a2->c1。

所有可能解

蛮力法

遍历链表A，嵌套遍历链表B，判断每个A中的节点是否在B中存在。

复杂度分析：

时间复杂度：O(mn)，空间复杂度：O(1)

Set存储节点

Set存储链表A所有节点，遍历B链表，能否找到Set中包含的节点。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
  Set<ListNode> store = new HashSet<>();
  ListNode currA = headA;
  ListNode currB = headB;
  while(currA != null) {
    store.add(currA);
    currA = currA.next;
  }
  while(currB != null) {
    if(store.contains(currB)) {
      return currB;
    }
    currB = currB.next;
  }
  return null;
}

复杂度分析：

时间复杂度：分别对A链表和B链表进行了遍历，即O(M + N)，空间复杂度为：O(M)或O(N)。

两个指针

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
  ListNode pA = headA;
  ListNode pB = headB;
  while(pA != pB) {
    pA = pA == null ? headB : pA.next;
    pB = pB == null ? headA : pB.next;
  }
  return pA;
}

复杂度分析：

时间复杂度：O(M+N)，空间复杂度为：O(1)。

合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

明确题目

从两个链表的第一个节点开始进行比对，判断下一个节点大小，进而进行next指针的指向。

所有可能解

递归

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
  if(l1 == null) return l2;
  if(l2 == null) return l1;

  if(l1.val < l2.val) {
    l1.next = mergeTwoLists(l1.next, l2);
    return l1;
  } else {
    l2.next = mergeTwoLists(l1, l2.next);
    return l2;
  }
}