This is the 14th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

And are continuous sequences of positive numbers of S

Reference to Offer 57-II. And a sequence of consecutive positive numbers for S

Difficulty: Easy

Topic: leetcode-cn.com/problems/he…

Enter a positive integer target and print the sequence of consecutive positive integers (at least two numbers) that sum to target.

The numbers in the sequence are arranged from smallest to largest, and different sequences are arranged from smallest to largest according to the first number.

Example 1:

Output: [[2,3,4],[4,5]]Copy the code

Example 2:

Output: [[1,2,3,4,5],[4,5,6],[7,8]]Copy the code

Limit: 1 <= target <= 10^5

Answer key

The sliding window

As you can see, the last number in the array is target/2 if target is even, and target/2 if odd plus one.

/ * * *@param {number} target
 * @return {number[][]}* /
var findContinuousSequence = function (target) {
  let index = Math.ceil(target / 2);
  // res is the result, temp is each array in the result, and sum is used to determine whether it is equal to target
  let res = [],
    temp = [],
    sum = 0;
  for (let i = 1; i <= index; i++) {
    temp.push(i);
    sum += i;
    // If sum > target, push the temp header out and slide the window
    while (sum > target) {
      sum -= temp[0];
      temp.shift();
    }
    // If sum equals target during the loop, place temp in res
    if (sum === target) {
      temp.length >= 2&& res.push([...temp]); }}returnres; }; or/ / double pointer
var findContinuousSequence = function (target) {
  let l = 1,
    r = 2,
    sum = 3;
  let res = [];
  while (l < r) {
    if (sum === target) {
      let ans = [];
      for (let k = l; k <= r; k++) {
        ans[k - l] = k;
      }
      res.push(ans);
      // If equal to, you can move the window further to the right while shrinking the left
      sum = sum - l;
      l++;
    } else if (sum > target) {
      // If yes, narrow the window
      sum = sum - l;
      l++;
    } else {
      // If smaller, expand the windowr++; sum = sum + r; }}return res;
};
Copy the code
  • Time complexity: O(NNN)
  • Space complexity: O(111)

Flip word order

Finger Offer 58-i. Flip word order

Difficulty: Easy

Topic: leetcode-cn.com/problems/fa…

Enter a sentence in English and reverse the order of the words in the sentence, but not the order of the characters in the word. For simplicity, punctuation marks are treated like ordinary letters. For example, if the string “I am a student.” is entered, “student.

Example 1:

Input: "The sky is blue" Output:" Blue is sky the"Copy the code

Example 2:

Type: "Hello world! Output: "World! Explanation: The input string can contain extra Spaces before or after it, but not after characters reversed.Copy the code

Example 3:

Input: "a good example" Output: "example good a" Explanation: If there is extra space between two words, reduce the space between the inverted words to only one.Copy the code

Description:

  • Blank characters form a word.
  • An input string can contain extra Spaces before or after it, but not inverted characters.
  • If there is extra space between two words, reduce the space between the inverted words to only one.

Answer key

Method one uses the API

  • Trim () Deletes Spaces at both ends of the string
  • Split (“) splits Spaces into arrays
  • Filter () Filters whitespace in the array
  • Reverse () reverses the array
  • Join (“) is delimited by Spaces, array to string
/ * * *@param {string} s
 * @return {string}* /
var reverseWords = function (s) {
  let str = s.trim().split(' ').filter(item= >item ! =' ').reverse().join(' ');
  return str;
};
Copy the code
  • Time complexity: O(NNN)
  • Space complexity: O(NNN)

Method two double pointer

Steps:

  • The string s is traversed from back to front, with the leading and trailing Spaces removed, recording the left and right index boundaries I and j
  • Each time a word boundary is determined, the word is placed in the array RES
  • The array res is converted to a string and returned
var reverseWords = function (s) {
  // 1. Remove the leading and trailing Spaces
  s = s.trim();

  let j = s.length - 1,
    i = j;
  let res = [];

  while (j >= 0) {
    while (i >= 0&& s[i] ! = =' ') i--;// Search for Spaces
    res.push(s.slice(i + 1, j + 1)); // Add words
    while (j >= 0 && s[i] === ' ') i--; // Skip the space
    j = i; // j points to the next word
  }
  return res.join(' '); // Array to string
};
Copy the code
  • Time complexity: O(NNN)
  • Space complexity: O(NNN)

Practice every day! The front end is a new one. I hope I can get a thumbs up