LeetCode刷题<1>:两数之和、两数相加、无重复字符的最长子串、最长的回文子串、删除链表的低N个结点、合并两个有序链表

1. 两数之和

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
  let map = new Map()
  for (let i=0;i<=nums.length;i++){
    let cha = target - nums[i]
    if (map.has(cha)) {
      // 如果找到了就返回这个下标
      return [map.get(cha),i]
    } else {
      map.set(nums[i],i)
    }
  }
  return null
};

2. 两数相加

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
  let dummy = new ListNode()
  let curr = dummy 
  let carry = 0 // 进位标志
  let sum = 0
  while (l1 !== null | l2 !== null ){
    sum = 0 // 每轮循环sum置零
    if (l1 !== null){
      sum+=l1.val
      l1 = l1.next
    }
    if (l2 !==null){
      sum+=l2.val
      l2 = l2.next
    }
    sum = sum + carry
    curr.next = new ListNode(sum % 10)
    curr = curr.next
    carry = Math.floor(sum / 10)
  }
  if (carry > 0){
    curr.next = new ListNode(carry)
  }
  return dummy.next
};

这个重难点在于最后的进位操作容易被忽略

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

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
  let set = new Set()
  let maxLength = 0
  let i = 0
  let j = 0
  for (i=0;i<s.length;i++){
    if (!set.has(s[i])){
      set.add(s[i])
      maxLength = Math.max(set.size,maxLength)
    } else {
      while (set.has(s[i])){
        set.delete(s[j])
        j++
      }
      set.add(s[i])
    }
  }
  return maxLength
};

滑动窗口问题

5. 最长回文子串

/**
 * @param {string} s
 * @return {string}
 */
  var longestPalindrome = function (s) {
    if (s.length < 2) {
      return s
    }
    let start = 0
    let maxLength = 1
    const expandAroundCenter = (left, right) => {
      while (left>=0 && right<s.length && s[left] === s[right] ){
        if (right - left + 1 > maxLength){
          start = left
          maxLength = right - left + 1
        }
        left--
        right++
      }
    }
    for (let i = 0;i<s.length;i++){
      expandAroundCenter(i,i+1)
      expandAroundCenter(i-1,i+1)
    }
    return s.substring(start,start+maxLength)
  }

15. 三数之和

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
  var threeSum = function (nums) {
    let res = [] // 用于返回结果
    // 首先应该对数组进行排序
    nums.sort(function (a, b) {
      return a - b
    })
    for (let i = 0; i < nums.length - 2; i++) {
      let start = i + 1
      let end = nums.length - 1
      if (i===null || nums[i]!==nums[i-1]){
         while (start < end) {
        if (nums[i] + nums[start] + nums[end] > 0) {
          end--
        } else if (nums[i] + nums[start] + nums[end] < 0) {
          start++
        } else {
          res.push([nums[i], nums[start], nums[end]])
          start++
          end--
          while (nums[end] === nums[end + 1]) {
            end--
          }
          while (nums[start] === nums[start - 1]) {
            start++
          }
        }
      }
    }
      }   
    return res
  }

这个的重难点在于如何判断重复的数组

19. 删除链表的倒数第 N 个结点

<script>
  /** 双指针
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
  let dummy = new ListNode()
  dummy.next = head
  let p1 = dummy
  let p2 = dummy
  for (let i = 0; i<=n;i++){
    p2 = p2.next
  }
  while (p2 !== null){
    p1 = p1.next
    p2 = p2.next
  }
  p1.next = p1.next.next
  return dummy.next
};
</script>

双指针问题

20. 有效的括号

<script>
  /**
   * @param {string} s
   * @return {boolean}
   */
  var isValid = function (s) {
    let map = new Map()
    map.set('[', ']')
    map.set('{', '}')
    map.set('(', ')')
    let stack = []
    for (let i = 0; i < s.length; i++) {
      if (map.has(s[i])) {
        stack.push(map.get(s[i]))
      } else {
        if (stack.pop() !== s[i]) {
          return false
        }
      }
    }
    if (stack.length !== 0) {
      return false
    }
    return true
  }
</script>

21. 合并两个有序链表

<script>
  /**将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
   * Definition for singly-linked list.
   * function ListNode(val, next) {
   *     this.val = (val===undefined ? 0 : val)
   *     this.next = (next===undefined ? null : next)
   * }
   */
  /**
   * @param {ListNode} list1
   * @param {ListNode} list2
   * @return {ListNode}
   */
  var mergeTwoLists = function (list1, list2) {
    let curr = new ListNode()
    let dummy = curr
    while (list1 !== null && list2 !== null) {
      if (list1.val < list2.val) {
        curr.next = list1
        curr = curr.next
        list1 = list1.next
      } else {
        curr.next = list2
        curr = curr.next
        list2 = list2.next
      }
    }
    if (list1 === null) {
      curr.next = list2
    }
    if (list2 === null) {
      curr.next = list1
    }
    return dummy.next
  }
</script>