String arrangement

• Title description:

Enter a string and print out all permutations of the characters in the string in lexicographical order. For example, if you enter the string ABC, you print out all the strings ABC, ACb, BAC, BCA, CAB, and CBA that can be arranged by characters A, B, and C.

• Input description:

Enter a string of up to 9 characters (there may be duplicate characters). The characters contain only upper and lower case letters.

JavaScript implementation ideas are very clear, I super like to see this code solution, but his original code is unable to compile through the ox guest network, the reason is that the subject requires dictionary order

• Note: recursive results need to be reordered

function Permutation(str)
{
    var result = [];
    // Initial condition: length 1
    if (str.length < 2) {
        return str;
    } else {
        // Find the full arrangement of the remaining substring
        var preResult = Permutation(str.slice(1)); 
        // Iterate over the full array
        for (var j = 0; j < preResult.length; j++) { 
            for (var k = 0; k < preResult[j].length + 1; k++) {
                // Insert the first letter into position k
                var temp = preResult[j].slice(0, k) + str[0] + preResult[j].slice(k); result.push(temp); }}// sort + deduplicate
        returnunique(result).sort(); }}/ / to heavy
function unique(arr){
    var res = [];
    for (var i = 0; i< arr.length; i++){
        if (res.indexOf(arr[i]) === -1){ res.push(arr[i]); }}return res;
}
Copy the code

The number that occurs more than half The Times in an array

• Title description:

Find a number that occurs more than half the length of the array. For example, enter an array of length 9 {1,2,3,2,2,2,5,4,2}. Since the number 2 appears in the array five times, more than half the length of the array, 2 is printed. Prints 0 if none exists.

• Ideas:
  1. Sort an array
  2. If such a number exists, it must be in the median of the sorted array, so find num
  3. Iterate through the array to see if the median occurs more than half the length of the array
     • If so, return num;
     • If not, return 0;

function MoreThanHalfNum_Solution(numbers)
{
    var len = numbers.length;
    if (len < 1) {return 0;
    }
    // Array sort
    var sort_nums = numbers.sort();
    // Get the median
    var num = sort_nums[Math.floor(len/2)];
    // Check the number of occurrences of the median
    var count = 0;
    for (var i = 0; i < len; i++){
        if(numbers[i] === num){ count++; }}if (count > len/2) {return num;
    } else {
        return 0; }}Copy the code

The smallest number of K

Title description:

Enter n integers and find the smallest K number. For example, if you enter the eight digits 4,5,1,6,2,7,3,8, the smallest four digits are 1,2,3,4.

function GetLeastNumbers_Solution(input, k)
{
    if (k < 1 || k > input.length){
        return [];
    }
    // Sort the array from smallest to largest;
    var sortArr = input.sort(function(a, b){
        return a - b;
    });
    return sortArr.slice(0,k);
}
Copy the code

Maximum sum of contiguous subarrays

• Topic describes

HZ occasionally tries to fool non-computer majors with professional questions. Today, after the test group meeting, he spoke again: in the old one-dimensional pattern recognition, it is often necessary to calculate the maximum sum of continuous subvectors, when the vectors are all positive, the problem is easily solved. But if the vector contains negative numbers, should it include some negative number and expect the positive number next to it to make up for it? For example: {6-3-2, 7, 15,1,2,2}, the largest and continuous vector son is 8 (starting from 0, until the third). Given an array, return the sum of its largest contiguous subsequence, would you be fooled by it? (The length of the subvector is at least 1)

• Translation:

Enter an array of positive and negative numbers (note that it may be all negative numbers). An array consisting of one or more consecutive integers. Find the maximum sum of all subarrays. The time required is order n.

• Note: InitialmaxMust bearray[0]If initialized to 0, it will return 0 if the array is all negative, which is an error.

function FindGreatestSumOfSubArray(array)
{
    // Error handling
    if (array === null || array.length < 1) {
        return false;
    }
    var max = array[0]; // Store the sum of the largest contiguous subsequence
    var sum = 0; // Stores the maximum sum of the subsequence ending in the i-th digit
    for (var i = 0; i < array.length; i++) {
        if (sum < 0){
            sum = array[i];
        } else {
            sum += array[i];
        }
        
        if(max < sum) { max = sum; }}return max;
}
Copy the code

The number of occurrences of 1 in an integer (from 1 to n)

Topic describes

How many times does 1 occur in integers 1, 13, and how many times does 1 occur in integers 100, 1300? He specifically counted the numbers 1, 10, 11, 12, and 13 from 1 to 13, so there were six occurrences, but he couldn’t figure out what to do about the latter question. ACMer wants you to help him out, and make it a little bit more general, to be able to quickly figure out how many times 1 occurs in any interval of non-negative integers from 1 to n.

• Violent solution

function NumberOf1Between1AndN_Solution(n)
{
    var count = 0;
    for (var i = 0; i <= n; i++){
        let num = i;
        while(num){
            if (num%10 === 1){
                count++;
            }
            num = Math.floor(num/10);
        }
    }
    return count;
}
Copy the code

Arrange the array to the smallest number

Topic describes

Enter an array of positive integers, concatenate all the numbers in the array into a number, and print the smallest number that can be concatenated. For example, if you enter the array {3,32,321}, the smallest number that can be printed is 321323.

• Define a new collation, that is, concatenate the previous number with the next number, and then compare the lexicographical order with the number concatenated with the previous number

function PrintMinNumber(numbers)
{
    numbers.sort(function(a, b){
        let c1 = `${a}${b}`;
        let c2 = `${b}${a}`;
        return c1 > c2;
    })
    var min = '';
    numbers.forEach(item => {
        min += item;
    });
    return min;
}
Copy the code

Number of ugly

Topic describes

Numbers containing only the prime factors 2, 3, and 5 are called Ugly numbers. For example, 6 and 8 are ugly numbers, but 14 is not, because it contains the prime factor 7. We traditionally think of 1 as the first ugly number. Find the NTH ugly number in ascending order.

It is mainly to understand the concept of ugly number. The number that only contains factors 2, 3 and 5 is called ugly number. Then we can first separate factors 2, 3 and 5, and then the rest is other factors to see if it is 1. If it’s not 1, it means there are other factors, so it’s not ugly.

• The first violent solution, the disadvantage is that even non ugly number also calculate force, will time out.

function GetUglyNumber_Solution(index) {
  if (index <= 1) return 0;
  let count = 0;
  let num = 0;
  while (count < index) {
    num++;
    if (isUgly(num)) {
      count++;
    }
  }
  return num;
}
function isUgly(num) {
  while (num % 2 === 0) num /= 2;
  while (num % 3 === 0) num /= 3;
  while (num % 5 === 0) num /= 5;
  return num === 1;
}
Copy the code

• The second uses the idea of dynamic programming, storing the ugly numbers in front and generating the ugly numbers behind. Count2,count3,count5 are the judgment points, which determine where to start and multiply the factor will definitely be greater than the maximum number of ugliness in the current array, regardless of the preceding number.

function GetUglyNumber_Solution(index)
{
    if (index < 1){
        return 0;
    }
    let res = [1];
    let count2 = 0, count3 = 0, count5 = 0;
    for(var i = 1; i < index; i++){
        res[i] = Math.min(res[count2]*2, res[count3]*3, res[count5]*5);
        if (res[i]===res[count2]*2){ count2++; }
        if (res[i]===res[count3]*3){ count3++; }
        if (res[i]===res[count5]*5){ count5++; }
    }
    return res[i-1];
}
Copy the code

The first character that occurs only once

Topic describes

Find the first character that occurs only once in a string (0<= string length <=10000, all letters) and return its position, or -1 (case sensitive) if none exists.

The idea in “Sword Finger Offer” is to create a hash table in the form of key-value. Key is used to store each character and value is the number of occurrences of the character. The algorithm traverses the string twice:

• First: Counts the number of occurrences of each character
• Second: Finds the first occurrence of a 1 character and returns it

But it’s too easy to do this with JS because we have a way of doing it.

function FirstNotRepeatingChar(str)
{
    var length = str.length;
    for(var i = 0; i < length; i++){
        if(str.indexOf(str[i])===str.lastIndexOf(str[i])){
            return i;
            break;
        }
    }
    return -1;
}
Copy the code

Pairs of inversions in an array

Topic describes

Two digits in an array form a reverse pair if the preceding digit is larger than the following digit. Enter an array and find the total number of inversions P in the array. And output the result of P modulo to 1000000007. The output P % 1000000007

Input description: The problem ensures that the input array does not have the same number

Data range:

For %50 data,size<=10^4

For %75 data,size<=10^5

For %100 data,size<=2*10^5

答 案 :(this question is a little difficult)

The first reaction is to use brute force, but it’s bound to run out of time

Code first;

function InversePairs(data) {
  if(! data || data.length <2) return 0;
  const copy = data.slice();
  let count = 0;
  count = mergeCount(data, copy, 0, data.length - 1);
  return count % 1000000007;
}
function mergeCount(data, copy, start, end) {
  if (start === end) return 0;
  const mid = end - start >> 1,
    left = mergeCount(copy, data, start, start + mid), // Copy is passed as data
    right = mergeCount(copy, data, start + mid + 1, end); // Copy is passed as data
  let [p, q, count, copyIndex] = [start + mid, end, 0, end];
  while (p >= start && q >= start + mid + 1) {
    if (data[p] > data[q]) {
      copy[copyIndex--] = data[p--];
      count = count + q - start - mid;
    } else{ copy[copyIndex--] = data[q--]; }}while (p >= start) {
    copy[copyIndex--] = data[p--];
  }
  while (q >= start + mid + 1) {
    copy[copyIndex--] = data[q--];
  }
  return count + left + right;
}
Copy the code

Implementation idea:

Take the array {7,5,6,4} as an example to analyze the process of statistical inversions. Every time we scan a number, instead of comparing it to every subsequent number, which would be O(n^2), we could consider comparing two adjacent numbers first.

• (a) Split an array of length 4 into two subarrays of length 2;
• (b) Split an array of length 2 into two subarrays of length 1;
• (c) Merge, sort, and count inversions of subarrays of length 1;
• (d) Merge, sort, and count inversions of subarrays of length 2;

The process of merging subarrays and counting inversions is shown below:We start with two Pointers to the end of each subarray and compare the numbers each time.

• If the number in the first subarray is greater than the number in the second array, it constitutes an inversion pair, and the number of inversions is equal to the number of digits remaining in the second subarray, as shown in figures (a) and (c) below.
• If the number in the first array is less than or equal to the number in the second array, it does not constitute an inversion pair, as shown in Figure B.

Each time we compare, we copy the larger numbers from the back forward into a secondary array, making sure that the secondary array (called copy) is in ascending order. After the larger number is copied into the auxiliary array, the corresponding pointer is moved forward one bit for the next round of comparison.

Write the code step by step:

The input is an array, and the output is the total number of reverse pairs in the array P%1000000007, so the general framework of the function should look like this:

function InversePairs(data) {
  if(! data || data.length <2) return 0;
  let count = 0;
  
  
  return count % 1000000007;
}
Copy the code

Then, make sure you use merge sort to solve the problem. We need an auxiliary array copy, and assume that mergeCount can calculate count, the total number of inversions of subarrays in data.

function InversePairs(data) {
  if(! data || data.length <2) return 0;
  const copy = data.slice();
  let count = 0;
  // mergeCount(data, copy, start, end)
  count = mergeCount(data, copy, 0, data.length - 1); 
  return count % 1000000007;
}
Copy the code

Mergecount () mergecount() : mergecount() : mergecount() : mergecount() : mergecount() : mergecount() : mergecount()

function mergeCount(data, copy, start, end) {
  if (start === end) return 0;
}
Copy the code

Now let’s consider merge counting. Without being too subtle, the total number of inversions in a subarray can consist of three parts

• Inversions in the split left subarray
• Inversions in the split right subarray
• The left is larger than the right to form an inverse pair

Don’t forget what mergecount() does, give me a subarray and return the inverse logarithm of that subarray.

function mergeCount(data, copy, start, end) {
  if (start === end) return 0;
  const mid = Math.floor((end - start)/2);
  var left = mergecount(copy, data, start, start + mid); // Copy is passed as data
  var right = mergeCount(copy, data, start + mid + 1, end); // Copy is passed as data
  var count = 0;
  
  return count + left + right;
}
Copy the code

So let’s focus on merge sort, and count the inverse logarithm of the left subarray being larger than the right subarray.

As shown in the figure above, we need three Pointers p, q, and copyIndex, starting at the end of the two subarrays and the end of the auxiliary array, respectively

function mergeCount(data, copy, start, end) {
  if (start === end) return 0;
  const mid = Math.floor((end - start)/2);
  var left = mergecount(copy, data, start, start + mid); // Copy is passed as data
  var right = mergeCount(copy, data, start + mid + 1, end); // Copy is passed as data
  var [p, q, count, copyIndex] = [start + mid, end, 0, end];
  
  return count + left + right;
}

Copy the code

If the number in the first subarray is greater than the number in the second array, it constitutes an inversion pair, and the number of inversions is equal to the number of digits remaining in the second subarray, as shown in figures (a) and (c) below. If the number in the first array is less than or equal to the number in the second array, it does not constitute an inversion pair, as shown in Figure B.

function mergeCount(data, copy, start, end) {
  if (start === end) return 0;
  const mid = end - start >> 1,
    left = mergeCount(copy, data, start, start + mid), // Copy is passed as data
    right = mergeCount(copy, data, start + mid + 1, end); // Copy is passed as data
  let [p, q, count, copyIndex] = [start + mid, end, 0, end];
  while (p >= start && q >= start + mid + 1) {
    if (data[p] > data[q]) {
      copy[copyIndex--] = data[p--]; // Update the auxiliary array
      count = count + q - start - mid; // The statistics are in reverse order
    } else{ copy[copyIndex--] = data[q--]; }}return count + left + right;
}
Copy the code

When one subarray has been iterated, if there are elements in the other subarray that have not been iterated, the remaining elements can be placed in the auxiliary array. So far, copy is an ordered array from start to end.

function mergeCount(data, copy, start, end) {
  if (start === end) return 0;
  const mid = end - start >> 1,
    left = mergeCount(copy, data, start, start + mid), // Copy is passed as data
    right = mergeCount(copy, data, start + mid + 1, end); // Copy is passed as data
  let [p, q, count, copyIndex] = [start + mid, end, 0, end];
  while (p >= start && q >= start + mid + 1) {
    if (data[p] > data[q]) {
      copy[copyIndex--] = data[p--];
      count = count + q - start - mid;
    } else{ copy[copyIndex--] = data[q--]; }}while (p >= start) {
    copy[copyIndex--] = data[p--];
  }
  while (q >= start + mid + 1) {
    copy[copyIndex--] = data[q--];
  }
  return count + left + right;
}
Copy the code

And that’s the end of the problem

The first common node of two linked lists

Topic describes

Enter two linked lists and find their first common node.

Algorithm analysis

Compare simple, first run on the long list, until the long and short as long, and then run together, judge the node is equal to the time can be

Specific steps

The first step is to find the length len1 and Len2 of the two lists

Step 2. Then determine which is the long list and which is the short list, and then determine the length difference

Step 3. Long lists take the length difference first, so that the two lists can be followed at the same time

Step 4. One layer loops until the two lists reach the same node and then returns

/*function ListNode(x){ this.val = x; this.next = null; } * /
function FindFirstCommonNode(pHead1, pHead2)
{
    var len1 = getListLength(pHead1);
    var len2 = getListLength(pHead2);
    var pLongHead, pShortHead, nLengthDif;
    if (len1 > len2){
        pLongHead = pHead1;
        pShortHead = pHead2;
        nLengthDif = len1 - len2;
    } else {
        pLongHead = pHead2;
        pShortHead = pHead1;
        nLengthDif = len2 - len1;
    }
    // A long list goes several more nodes first
    for (var i = 0; i < nLengthDif; i++){
        pLongHead = pLongHead.next;
    }
    / / go together
    while(pLongHead! = =null&&! pShortHead! = =null&& pLongHead ! == pShortHead){ pLongHead = pLongHead.next; pShortHead = pShortHead.next; }return pLongHead;
    
}
// Calculate the list length
function getListLength(head){
    var len = 0;
    var node = head;
    while(node ! = =null){
        len++;
        node = node.next;
    }
    return len;
}
Copy the code

There’s an even simpler way, which is clever, the shortest code, you don’t have to remember the length

Scan “two linked lists” with two Pointers, and eventually both Pointers reach null or a common node.

I didn’t understand it very well at first, but later I understood it like this: this method does not need to calculate the length of the two lists, because it is linked together, and the length and sum of the two lists must be equal

• The first pointer P1 scans for: first list -> NULL -> second list
• The second pointer p2 scans: second list -> NULL -> first list

In fact, the algorithm is finalizing the length so that eventually both Pointers must reach the common node or null at the same time

function FindFirstCommonNode(pHead1, pHead2)
{
    // write code here
    var p1 = pHead1;
    var p2 = pHead2;
    while(p1 ! = p2){ p1 = (p1 ==null ? pHead2 : p1.next);
        p2 = (p2 == null ? pHead1 : p2.next);
    }
    return p1;
}
Copy the code

The number of occurrences of a number in a sorted array

Topic describes

Count the number of occurrences of a number in a sorted array.

Method 1: Use the JS API

function GetNumberOfK(data, k)
{
    var index = data.indexOf(k);
    if (index === -1) {return 0;
    } else {
        return data.lastIndexOf(k) - data.indexOf(k) + 1; }}Copy the code

Method two: use binary search, determine the starting position and the end position

function GetNumberOfK(data, k)
{
    var number = 0;
    if (data.length == 0) {return number;
    }
    var firstIndex = getFirstIndex(data, k, 0, data.length);
    if (firstIndex === -1) {
        return number;
    }
    var lastIndex = getLastIndex(data, k, firstIndex, data.length);
    if(firstIndex ! = = -1&& lastIndex ! = = -1) {return lastIndex - firstIndex + 1;
	}
    return number;
};

function getFirstIndex(data, k, start, end){
    if (start > end){
        return -1;
    }
    var mid = parseInt((end + start)/2);
    if (data[mid] > k){
        // The first k is in the first half of the array
        end = mid - 1;
    } else if (data[mid] < k){
        // The first k is in the last part of the array
        start = mid + 1;
    } else {
        if ((mid > 0 && data[mid - 1] !== k) || mid === 0) {return mid;
        } else {
            end = mid - 1; }}return getFirstIndex(data, k, start, end);
}
function getLastIndex(data, k, start, end){
    if (start > end){
        return -1;
    }
    var mid = parseInt((end + start)/2);
    if (data[mid] > k){
        // The first k is in the first half of the array
        end = mid - 1;
    } else if (data[mid] < k){
        // The first k is in the last part of the array
        start = mid + 1;
    } else {
        if ((mid < data.length - 1 && data[mid + 1] !== k) || mid === data.length - 1) {return mid;
        } else {
            start = mid + 1; }}return getLastIndex(data, k, start, end);
}
Copy the code

The depth of a binary tree

Topic describes

Input a binary tree and find the depth of the tree. Nodes (including root and leaf nodes) that pass from root to leaf form a path of the tree. The longest path length is the depth of the tree.

Method one: recursion

/* function TreeNode(x) { this.val = x; this.left = null; this.right = null; } * /
function TreeDepth(pRoot)
{
    if(! pRoot)return 0;
    let nLeft = TreeDepth(pRoot.left);
    let nRight = TreeDepth(pRoot.right);
    return Math.max(nLeft, nRight) + 1;
}
Copy the code

Method 2: hierarchical traversal

Using the first-in, first-out (FIFO) feature of the queue structure, maintain a queue, each time all nodes of layer N pop up, layer N +1 all queue, concrete implementation:

• For each layer, round is used to record the node number of the layer, that is, the length of the current ARR. Then, the count node of the queue is visited in turn, ejected from the queue, and its left and right children are added to the queue.
• If count ==== round is set, it indicates that the last node of the current layer has been traversed. In this case, reset the counter count = 0 and reset the queue length round
• For each layer traversed, the depth of the binary tree is res++;

function TreeDepth(pRoot)
{
    if(! pRoot)return 0;
    
    let arr = [pRoot]; // Initialize the queue
    let res = 0; // Initialization depth =0
    let count = 0, round = 1; // Initialize counter =0, queue length =1
    while(arr.length){ 
        count++;
        let parent = arr.shift();
        if(parent.left){arr.push(parent.left)};
        if(parent.right){arr.push(parent.right)};
        if(count === round){ // The layer has been traversed
            count = 0; round = arr.length; res++; }}return res;
}
Copy the code

Balanced binary trees

Topic describes

Input a binary tree to determine whether the binary tree is a balanced binary tree.

In this case, we only have to worry about its balance, not whether it’s a sorted binary tree

title

• Properties of balanced binary trees
  1. It is an empty tree or the absolute value of the height difference between its left and right subtrees is no more than 1
  2. Both the left and right subtrees are a balanced binary tree

Idea: Use the above binary tree depth function to solve the depth of the left and right subtrees, and then recurse

/* function TreeNode(x) { this.val = x; this.left = null; this.right = null; } * /
function IsBalanced_Solution(pRoot)
{
    if(! pRoot)return true;
    
    if (Math.abs(TreeDepth(pRoot.left) - TreeDepth(pRoot.right)) > 1) {return false;
    } else {
        returnIsBalanced_Solution(pRoot.left) && IsBalanced_Solution(pRoot.right); }}// Binary tree depth
function TreeDepth(pRoot)
{
    if(! pRoot)return 0;
    let nLeft = TreeDepth(pRoot.left);
    let nRight = TreeDepth(pRoot.right);
    return Math.max(nLeft, nRight) + 1;
}
Copy the code

The number that appears only once in the array

Topic describes

All but two digits in an integer array appear twice. Write a program to find these two numbers that appear only once.

function FindNumsAppearOnce(array)
{    
    let res = [];
    for (let i = 0; i < array.length; i++){
        if(array.indexOf(array[i]) === array.lastIndexOf(array[i])){ res.push(array[i]); }}return res;
}
Copy the code

And are continuous sequences of positive numbers of S

Topic describes

Xiao Ming likes math very much. One day when he is doing math homework, he asks to calculate the sum of 9~16. He immediately writes down the correct answer is 100. But he wasn’t satisfied. He wondered how many consecutive sequences of positive numbers could add up to 100(including at least two numbers). It wasn’t long before he had another series of consecutive positive numbers that added up to 100 :18,19,20,21,22. Now for you, can you also quickly find all the consecutive sequences of positive numbers that sum to S? Good Luck!

Output description

Prints all sequences of consecutive positive numbers that sum to S. Within the sequence, the order is from small to large, and between the sequences, the order is from small to large

The continuous positive numbers are listed in the arithmetic sequence. The arithmetic sequence is summed by the formula of sum = (A1 + an) * n/2. Solving an arithmetic sequence can be transformed to solving the first and last digits of the sequence. Initialize first = 1, last = 2

1. [left, ..., right]When the sum of is <sum, last is small, so last++
2. [left, ..., right]If the sum of is greater than sum, the sequence is too long and the smallest element is removed, so first++
3. [left, ..., right]When the sum of is =sum, the correct arithmetic sequence is found, and the left is enlarged to find a new sequence
4. whenleft = rightIs, indicating that there is no more sequence that meets the condition.

function FindContinuousSequence(sum)
{
    let res = [];
    let first = 1;
    let last = 2;
    while(first < last){
        if((first + last) * (last - first + 1) < 2 * sum){
            last++;
        } else if ((first + last) * (last - first + 1) > 2 * sum){
            first++;
        } else {
            let arr = [];
            for(leti = first; i <= last; i++){ arr.push(i); } res.push(arr); first++; }}return res;
}
Copy the code

And two numbers of S

Topic describes

Enter an incrementally-sorted array and a number S, and find two numbers in the array so that their sum is exactly S. If there are multiple pairs of numbers that sum to S, output the smallest product of two numbers.

Output description:

Output two numbers for each test case, the smallest first.

The sum of two consecutive positive numbers is the sum of S.

• Incrementing arrays use double Pointers, one to the head of the array and one to the tail.

function FindNumbersWithSum(array, sum)
{
    let res = [];
    let i = 0, j = array.length - 1;
    while(i < j){
        if(array[i] + array[j] > sum){
            j--;
        }
        
        if(array[i] + array[j] < sum){
            i++;
        }
        
        if(array[i] + array[j] === sum){ res.push([array[i], array[j]]); i++; }}let min = res.length && res[0];
    for(let i = 0; i < res.length; i++){
        if(res[i][0]*res[i][1] < min[0]*min[1]){ min = res[i]; }}return min;
}
Copy the code

Left rotation string

Topic describes

A simple task in assembly language is to simulate the result of a shift instruction called loop left shift (ROL) with a string. For a given character sequence S, you loop the sequence output K bits to the left. For example, the character sequence S= “abcXYZdef” requires that the output loop be shifted three bits to the left, i.e., “XYZdefabc”. Isn’t that easy? OK, fix it!

function LeftRotateString(str, n)
{
    if(! str)return ' ';
    const len = str.length;
    const num = n % len;
    const start = str.slice(0, num);
    const end = str.slice(num);
    return end + start;
}
Copy the code

Flip word order

Topic describes

Fish, a new employee of Niuke, has recently arrived. Every morning, he always takes an English magazine and writes some sentences in it. Cat, one of his colleagues, was very interested in Fish’s writing. One day, he borrowed it from Fish to read it, but he could not understand it. For example, “student. A am I”. Later I realized that the guy had reversed the order of the words in the sentence and that the correct sentence should be “I am a student.” Cat is not good at flipping these word orders. Can you help him?

function ReverseSentence(str)
{
    if(! str)return ' ';
    let arr = str.split(' ');
    const len = arr.length;
    for(let i = 0; i < Math.floor(len/2); i++){
        let temp = arr[i];
        arr[i] = arr[len - i - 1];
        arr[len - i - 1] = temp;
    }
    return arr.join(' ');
}
Copy the code

Poker order

Topic describes

LL: I’m in a really good mood today, because I bought a deck of cards and found that there were 2 Kings and 2 small Kings in it. He randomly picked out 5 cards, want to test their luck, see if they can draw a straight, if so, he decided to buy a sports lottery ticket, hey hey!! “Ace of hearts, 3 of spades, xiao Wang, King, 5 of diamonds”, “Oh My God!” Not straight….. LL was not happy. He thought about it for A while and decided that big, small and small could be any number, and A could be 1,J was 11,Q was 12 and K was 13. The top five cards can become “1,2,3,4,5”, “So Lucky!” . LL: I’m going to buy a sports lottery ticket. Now, you are asked to use this card to simulate the above process, and then tell us LL’s luck, printing true if the card forms a straight, false otherwise. For convenience, you can think of big wang as 0.

Subject abstract

Given an array of length 5 (excluding an empty vector) containing 0 to 13, determine if the tolerance is 1.

Their thinking

The set + traversal

Let’s think about it in two different ways,

If the vector does not contain 0: There are no duplicates, and the difference between the maximum and minimum should be less than 5.

If the vector contains 0, the method is the same as in 1.

Therefore, according to the above two conditions, the algorithm process is as follows:

1. Initialize a set, max_ = 0, min_ = 14
2. Iterates through the set of numbers, for integers greater than 0 that do not appear in set, add to set, and update max_, min_
3. If it appears in set, return false
4. After iterating through the array, check whether the difference between the maximum value and minimum value is less than 5

function IsContinuous(numbers)
{
    // write code here
    if(numbers.length ! = =5) return false;
    let set = new Set(a);let max = 0, min = 14;
    for(let item of numbers){
        if(item>0) {if(set.has(item)) return false;
            set.add(item);
            max = Math.max(max, item);
            min = Math.min(min, item); }}return (max-min)<5;
}
Copy the code

Children’s play (last number left in circle)

Topic describes

Every June 1 Children’s Day, niuke will prepare some small gifts to visit the children in the orphanage, this year is the same. HF, as the senior veteran of Niuke, naturally also prepared some small games. Among them, there is a game like this: first, let the children form a big circle. Then, he randomly assigned a number m, let the number of 0 children began to count. Each time the child who calls m-1 sings a song, he or she can choose any gift from the gift box, and does not return to the circle, starting with his or her next child, continue to 0… M – 1 count off… And so on…. Until the last child left, can not perform, and get the cow guest expensive “detective Conan” collector’s edition (quota limited oh!! ^_^). Please try to think, which child will get this gift? (Note: Children are numbered from 0 to N-1)

If there are no children, return -1

N people (numbered from 0 to (n-1)) count off from 0, report for (m-1) to quit, and the rest continue counting off from 0. Get the winner’s number.

A little difficult

Resolution:

Mathematical induction

The first person is numbered m%n-1, and n-1 person is left, forming a new Joseph ring (starting with number K =m%n).

k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... K minus 2 and 0 starting at kCopy the code

Let’s convert their numbers to n minus 1 person count subproblem

k --> 0 k+1 --> 1 k+2 --> 2 ... . k-2 --> n-2 k-1 --> n-1Copy the code

If we know the solution to the subproblem f(n-1), the winner’s number should be

F (n) = [f (n-1) + k] % nCopy the code

To the k = m % n, f (n) = [f (n – 1) + m % n] % n = [f (n – 1) + m] % n

The final code is as follows:

function LastRemaining_Solution(n, m)
{
    // write code here
    if(n === 0) {return -1;
    }
    if(n === 1) {return 0;
    }
    return (LastRemaining_Solution(n-1, m) + m)%n;
}
Copy the code

For 1 + 2 + 3 +… +n

Topic describes

For 1 + 2 + 3 +… +n, do not use multiplication, division, for, while, if, else, switch, case and other keywords and condition statement (A? B, C).

/ / recursion
function Sum_Solution(n)
{
    return n ? Sum_Solution(n - 1) + n: 0;
}
Copy the code

You don’t have to add, subtract, multiply and divide

Topic describes

Write a function to find the sum of two integers, requiring that no +, -, *, / operation symbols in the function.

Even though it looks like we’re using bits to do this problem, we still haven’t done it

(1) decimal addition consists of three steps :(take 5+17=22 as an example)

1. When you add the digits, the result is 12(the units digit 5 and 7 add up to 2, and the tens digit 0 and 1 add up to 1).
2. Carry, 5+7 has carry, the carry value is 10;
3. Repeat 1,2 until no carry is generated, adding the first two results, 12+10=22

(2) These three steps also apply to binary operations

Because of the peculiarities of binary, addition and multiplication can also be replaced with bitwise operations.

• Xor by bit: 1^1=0 0^0=0 1^0=1 0^1=1
• By bit and: 1&1=1 0&0=0 1&0=0 0&1=0

Summary: bitwise exclusive or equivalent to addition without regard to carry, bitwise and left-shifting 1 bit are equivalent to carry values

1. Do not consider adding each bit of carry ==> xor operation;
2. Consider the carry ==> bit and operation, then move one bit to the left;
3. The first two steps are repeated until no carry is generated.

function Add(num1, num2)
{
    // num2 stores carry values, num1 stores the result of addition regardless of carry
    while(num2){
        var t = num1 ^ num2    // Do not add the digits
        num2 = (num1 & num2) << 1   // The same 1 carries
        num1 = t
    }
    return num1
}
Copy the code

Convert strings to integers

Topic describes

To convert a string to an integer requires library functions that cannot use string to convert integers. Returns 0 if the value is 0 or the string is not a valid value

Input description:

Enter a string, including alphanumeric symbols, that can be null

Output description:

Returns the number if it is a valid numeric representation, or 0 otherwise

Method 1: Leverage existing apis

function StrToInt(str)
{
    return Number(str)? parseInt(str):0
}
Copy the code

Method 2: Natively implement a function like Number() or parseInt()

1. Boundary condition: String does not exist or is empty, return 0
2. If the value is not a + – digit, return 0 directly
3. Return 0 (charCodeAt(0))
4. Numeric strings are converted to numbers

function StrToInt(str)
{
    // write code here
    // Boundary conditions
    if(! str) {return 0
    }
    // Normal condition
    let plus = true
    let result = ' '
    // First judgment
    if (str[0= = ='+') {
        result += ' '
    } else if (str[0= = =The '-') {
        result += ' '
        plus = false
    } else if (str[0].charCodeAt(0) > =48 && str[0].charCodeAt(0) < =57) {
        result += str[0]}else {
        return 0
    }
    // Return 0 as long as it is not a numeric character
    for (let i = 1; i < str.length; i++) {
        if (str[i].charCodeAt(0) > =48 && str[i].charCodeAt(0) < =57) {
            result += str[i]
        } else {
            return 0}}// Convert to a number
    let front = 1
    let sum = 0
    for (let j = result.length - 1; j >= 0; j--) {
        let current = (result[j].charCodeAt(0) - 48) * front
        front *= 10
        sum += current
    }
    return plus ? sum : -sum
}
Copy the code

Duplicate numbers in an array

Topic describes

All the numbers in an array of length N are in the range 0 to n minus 1. Some numbers in the array are duplicated, but it is not known how many are duplicated. I don’t know how many times I repeat each number. Please find any duplicate number in the array. For example, if you input an array of length 7 {2,3,1,0,2,5,3}, the corresponding output is the first repeated number 2.

function duplicate(numbers, duplication)
{
    // write code here
    // Find an arbitrary duplicate value and assign it to duplication[0]
    // The function returns True/False
    for(let i = 0; i < numbers.length; i++){
        let num = numbers[i];
        if(numbers.indexOf(num) ! == numbers.lastIndexOf(num)){ duplication[0] = num;
            return true; }}return false;
}
Copy the code

Building product Arrays

Topic describes

Given an array A [0, 1,…, n – 1), please build an array B [0, 1,…, n – 1), including the elements in the B B = [I] A [1] [0] * *… *A[i-1]*A[i+1]*… * A [n – 1). You can’t use division. (Note: B[0] = A[1] * A[2] *… * A[n-1], B[n-1] = A[0] * A[1] *… * A/n – 2)

For the case where A is of length 1, B is meaningless and therefore cannot be built, so the case does not exist

Method one:

Can’t use division, normal multiplication time complexity is O(n^2), very inefficient.

function multiply(array)
{
    let B = [];
    for(let i = 0; i < array.length; i++){
        B[i] = 1;
        for(let j = 0; j < array.length; j++){
            if(j === i){
                continue; } B[i] *= array[j]; }}return B;
}
Copy the code

Method 2:

Considering that every B[I] calculation will be repeated, consider the connection between B[I], find out the rule, improve efficiency.As shown in the figure above, it can be found that:

• The left part of B[I] (the red part) is related to B[I -1]C = C [I] [I - 1) * A [] I - 1).
• The right part of B[I] (the purple part) is related to B[I +1][I] D = D [I + 1) * A [I + 1)).

Calculate the left half of each B[I] from 0 to n-1. B[I]*=temp; B[I]*=temp; B[I] =temp;

function multiply(array)
{
    if(! array || array.length <2) {return null }
    let B = [];
    B[0] = 1;
    for (let i = 1; i < array.length; i++){
        B[i] = B[i-1]*array[i-1];
    }
    
    let temp = 1;
    for(let i = array.length - 2; i >= 0; i--){
        temp *= array[i+1];
        B[i] *= temp;
    }
    return B;
}
Copy the code

Regular expression matching

Topic describes

Implement a function to match regular expressions including ‘.’ and ”. The character ‘.’ in the pattern represents any character, and the character ” indicates that the character preceding it can occur any number of times (including zero). In this case, matching means that all characters in a string match the entire pattern. For example, the string “aaa” matches the patterns “A.a” and “ab*ac*a”, but not “aa.a” and “ab*a”

parsing

1. When the second character in a pattern is not an * :

• If the first character in the string matches the first character in the pattern, then both the string and pattern move one character later and match the rest.
• If the first character in the string does not match the first character in the pattern, return false.

2. When the second character in the pattern is “*” :

• If the first character of the string does not match the first character of the pattern (there is still a chance that the first character of the string is ignored; * represents 0 occurrences of x), the pattern moves two characters later and continues to match.

• If the first character of the string matches the first character of the pattern x, there are three ways to match:

  A. String moves back 1 character, mode moves back 2 characters (x appears once)

  B. String moves back 1 character, mode does not change (x appears multiple times)

  C. String does not move, mode moves two characters after (x occurs 0 times)

Note: the second character is * and the second character is not * are not mutually exclusive, there is no second character, so the second character is * first

function match(s, pattern)
{
    if (s == null || pattern == null) return false;
    if(pattern === '*') return true;
    return check(s, pattern, 0.0);
}

function check(s, pattern, i, j){
    // The next character is checked
    if(i === s.length && j === pattern.length) return true;
    
    / / check
    if(i ! == s.length && j === pattern.length) {// pattern has been matched, s has unmatched character, false
        return false
    };
    
    // The second character is *
    if(pattern[j + 1] && pattern[j + 1= = =The '*') {if(pattern[j] === s[i] || pattern[j] === '. '&& i ! == s.length){// The first character matches, three cases
            return check(s, pattern, i, j + 2) || check(s, pattern, i + 1, j + 2) || check(s, pattern, i + 1, j);
        } else {
            // The first character does not match
            return check(s, pattern, i, j + 2)}}/ / character is the second to * | | no second character
    if(pattern[j] === s[i] || pattern[j] === '. '&& i ! == s.length){// The first character matches, with pattern and s followed by a check
        return check(s, pattern, i + 1, j + 1);
    } else {
        // The first character does not match
        return false; }}Copy the code

A string representing a numeric value

Topic describes

Implement a function to determine whether a string represents a numeric value (both integer and decimal). For example, the string “+ 100”, “5 e2”, “123”, “3.1416” and “1 e – 16” numerical value. But “12e”,” 1A3.14 “,”1.2.3″,”+-5” and “12E +4.3” are not.

Their thinking

Regular match

• * 0 or more times
• ? Zero or one
• + more than once
• [] or

/ / s string
function isNumeric(s)
{
    let reg = new RegExp(/ ^ (+ -)? \d*\.? \d*(e[+-]? \d+)? $/i);
    return reg.test(s);
}
Copy the code

The first non-repeating character in a character stream

Topic describes

Implement a function to find the first character in a character stream that occurs only once. For example, when only the first two characters “go” are read from the character stream, the first character that appears only once is “g”. When the first six characters “Google” are read from this character stream, the first character that appears only once is “L”.

Output description:

If the current stream does not have a character that occurs once, the # character is returned.

//Init module if you need
let map;
function Init()
{
    // write code here
    map = {};
}
//Insert one char from stringstream
function Insert(ch)
{
    // write code here
    if(map[ch]){
        map[ch] += 1;
    } else {
        map[ch] = 1; }}//return the first appearence once char in current stringstream
function FirstAppearingOnce()
{
    // write code here
    for(var key in map){
        if(map[key] === 1) {
            returnkey; }}return The '#';
}
Copy the code

The entry node in the middle of the list

Topic describes

Given a linked list, find the entry node of the linked list’s ring if it contains rings, otherwise, null.

title

With regard to rings of singly linked lists, the following questions are generally involved:

1. Given a single linked list, determine whether there is a ring in it;
2. If there is a ring, find the entry point of the ring;
3. If there are rings, find the number of nodes on the rings;
4. If there are rings, find the length of the linked list;
5. If there is a ring, find the farthest point (opposite node) on the ring from any node;
6. (Extension) How to determine whether two acyclic lists intersect;
7. (expansion) If the intersection, find the first intersection node;

The problem of determining whether there are rings in a linked list —– the problem of rings in a single linked list gives the solution to all the problems

Only the first two questions are involved

1. Check for rings

Adopt the method of “fast and slow pointer”. That is, there are two Pointers fast and slow. Both Pointers point to the head of the list at the beginning, and slow goes one step forward in each step: slow = slow->next, and fast goes two steps forward in each step: fast = fast->next-> Next.

Since fast moves faster than slow, if there is a loop, FAST must enter the loop first, while slow enters the loop later. When both Pointers enter the ring, they must meet on the ring after a certain number of steps, and slow has not yet gone around the ring, that is, it must meet before slow completes its first turn.

• Prove that the two must meet on the ring.

Each pointer may be in the above position when slow first enters the ring, then slow and fast move forward respectively, i.e. :

if(slow ! = NULL && fast->next ! = NULL) { slow = slow -> next ; fast = fast -> next -> next ; }Copy the code

In other words, for every step slow takes, FAST is chasing two steps forward, so for each step, the distance between Fast and Slow is reduced by one step, and this further reduces the distance between the two:… , 5, 4, 3, 2, 1, 0 -> meet.

• Prove “meet before the first turn of slow”

And because the distance between fast and slow in the same ring can’t be greater than the length of the ring, slow must not have gone all the way around by the time they meet (or right after, which is the case when fast and Slow are both at the entrance to the ring at the beginning).

let slow = fast = head ; 
while(slow ! = NULL && fast -> next ! = NULL) { slow = slow -> next ; fast = fast -> next -> next ;if (slow == fast) 
        return true ; 
} 
return false ; 
Copy the code

2. Find the entrance to the ring

From the above analysis, it is known that when FAST and Slow meet, slow has not completed the linked list, assuming that FAST has gone through n(1<= n) cycles within the ring. Assuming that SLOW takes S steps, then FAST takes 2s steps, and since the number of steps taken by Fast = S + N *r (s + n extra laps in the ring), then the following equation can be obtained:

2*s = s + n * r ; (1)

=> s = n*r (2)

If the length of the entire list is assumed to be L, the distance between the entry point and the encounter point is X (as shown in the figure above), and the distance from the starting point to the entry point is A (as shown in the figure above), then:

a + x = s = n * r; (3) From (2)

A + x = (n-1) * R + r = (n-1) * R + (L-a) (4) from the length of the ring = the total length of the list – the distance from the starting point to the entry point

a = (n – 1) * r + (L -a -x) (5)

As can be seen from the set formula (5) and the figure above, the distance a from the starting point of the linked list head to the entry point is the same as the distance from the meeting point of Slow and fast (as shown in the figure) to the entry point.

Therefore, we can use a pointer (ptr1, PRT2), starting from head and encounter point at the same time, each operation step, until ptr1 == ptr2, at this point is the entry point!

So far the second problem has been solved.

Case Final code

/*function ListNode(x){ this.val = x; this.next = null; } * /
function EntryNodeOfLoop(pHead)
{
    if(! pHead || ! pHead.next || ! pHead.next.next)return null;
    let slow = pHead.next;
    let fast = pHead.next.next;
    while(slow&&fast){
        if(slow ! == fast){ slow = slow.next; fast = fast.next.next; }else {
            break; }}// Check if there is a ring
    if(! slow || ! fast)return null;
    
    fast = pHead;
    while(fast ! == slow){ fast = fast.next; slow = slow.next; }return fast;
}
Copy the code

Delete duplicate nodes from the linked list

Topic describes

In a sorted linked list, there are duplicate nodes, please delete the duplicate nodes in the linked list, the duplicate nodes are not retained, return the linked list head pointer. For example, linked list 1->2->3->3->4->4->5 is 1->2->5

title

1. Because the linked list is one-way, if the first and second nodes are repeated, it is more troublesome to delete. Therefore, we can solve this problem by adding additional header nodes
2. Because the repeated nodes are not necessarily repeated two, may be repeated many, need to cycle processing.

* * * */*function ListNode(x){ this.val = x; this.next = null; } * /
function deleteDuplication(pHead)
{
    // write code here
    if(! pHead || ! pHead.next)return pHead;
    
    // Add a header
    const Head = new ListNode(null);
    Head.next = pHead;
    let pre = Head;
    let cur = pHead;
    
    while(cur){
        if(cur.next && cur.val === cur.next.val){
            // Multiple repetitions are possible
            while(cur.next && cur.val === cur.next.val){
                cur = cur.next;
            }
            // Pre lists do not contain duplicate nodes
            pre.next = cur.next;
            cur = cur.next;
        } else{ pre = pre.next; cur = cur.next; }}return Head.next;
}
Copy the code