649b2f9c85bd171608eaf5910bb15177.jpg

977. 有序數(shù)組的平方

可以使用兩個(gè)指針?lè)謩e指向位置 0 和 n-1，每次比較兩個(gè)指針對(duì)應(yīng)的數(shù)，選擇較大的那個(gè)逆序放入答案并移動(dòng)指針。

var sortedSquares = function(A) {
    let len = A.length
    let left = 0
    let right = len - 1
    let pos = len - 1
    let ans = []
    while(left <= right) {
        if (A[left] * A[left] > A[right] * A[right]) {
            ans[pos] = A[left] * A[left]
            left++
        } else {
            ans[pos] = A[right] * A[right]
            right--
        }
        pos--
    }
    return ans
};

189. 旋轉(zhuǎn)數(shù)組

將數(shù)組的元素向右移動(dòng) k 次后，尾部 k%n 個(gè)元素會(huì)移動(dòng)至數(shù)組頭部，其余元素向后移動(dòng) k%n 個(gè)位置?？梢韵葘⑺性胤D(zhuǎn)，這樣尾部的 k%n 個(gè)元素就被移至數(shù)組頭部，然后再翻轉(zhuǎn) [0, k%n-1]區(qū)間的元素和 [k%n, n-1]區(qū)間的元素即能得到最后的答案。

var rotate = function(nums, k) {
    k %= nums.length
    reverse(nums, 0, nums.length - 1)
    reverse(nums, 0, k -1)
    reverse(nums, k, nums.length - 1)
};

let reverse = function(nums, start, end) {
    while(start < end) {
        let temp = nums[start]
        nums[start] = nums[end]
        nums[end] = temp
        start++
        end--
    }
}

283.移動(dòng)零

使用雙指針，左指針指向當(dāng)前已經(jīng)處理好的序列的尾部，右指針指向待處理序列的頭部。右指針不斷向右移動(dòng)，每次右指針指向非零數(shù)，則將左右指針對(duì)應(yīng)的數(shù)交換，同時(shí)左指針右移。
注意：

1. 左指針左邊均為非零數(shù)

2. 右指針左邊直到左指針處均為零。

因此每次交換，都是將左指針的零與右指針的非零數(shù)交換，且非零數(shù)的相對(duì)順序并未改變。

var moveZeroes = function(nums) {
    if (nums == null || nums.length <= 1) {
        return
    }
    let left = 0, right = 0
    while(right < nums.length) {
        if (nums[right] !== 0) {
            swap(nums, left, right)
            left++
        }
        right++
    }
};

let swap = function(nums, left, right) {
    let temp = nums[left];
    nums[left] = nums[right];
    nums[right] = temp;
}

167. 兩數(shù)之和 II - 輸入有序數(shù)組

var twoSum = function(numbers, target) {
    let left = 0; right = numbers.length;
    while(left < right) {
        if (numbers[left] + numbers[right] === target) {
            let res = [left+1, right+1];
            return res;
        } else if (numbers[left] + numbers[right] < target) {
            left++;
        } else {
            right--;
        }
    }
};

344. 反轉(zhuǎn)字符串

var reverseString = function(s) {
    let left = 0, right = s.length - 1
    while(left <= right) {
        [s[left], s[right]] = [s[right], s[left]]
        left++
        right--
    }
};

557. 反轉(zhuǎn)字符串中的單詞 III

var reverseWords = function (s) {
  let arr = s.split(' ')
  let newArr = arr.map((item) => {
    return reverse(item)
  })
  return newArr.join(' ')
};

let reverse = function (s) {
  s = s.split('')
  let left = 0, right = s.length - 1
  while (left <= right) {
    [s[left], s[right]] = [s[right], s[left]]
    left++
    right--
  }
  return s.join('')
};

876. 鏈表的中間結(jié)點(diǎn)

使用快慢不同的兩個(gè)指針遍歷，快指針一次走兩步，慢指針一次走一步。當(dāng)快指針到達(dá)終點(diǎn)時(shí)，慢指針剛好走到中間

var middleNode = function(head) {
    let slow = head, fast = head

    while(fast && fast.next) {
        slow = slow.next
        fast = fast.next.next
    }
    return slow
};

19. 刪除鏈表的倒數(shù)第 N 個(gè)結(jié)點(diǎn)

假設(shè)設(shè)定了雙指針 fast 和 slow。當(dāng) fast 指向末尾的 null，fast 與 slow 之間相隔的元素個(gè)數(shù)為 n 時(shí)，那么刪除掉 slow 的下一個(gè)指針就完成了要求。

let removeNthFromEnd = function(head, n) {
  let prev = new ListNode(0)
  prev.next = head
  let fast = prev
  let slow = prev

  // fast 指針走到 n 的前面節(jié)點(diǎn)
  while(n--) {
    fast = fast.next
  }

  while(fast && fast.next) {
    slow = slow.next
    fast = fast.next
  }

  slow.next = slow.next.next

  return prev.next
}