This is the 27th day of my participation in the August Genwen Challenge.More challenges in August

Brush questions, please go to LeetCode to brush questions together when you have time. By brushing questions, you can consolidate the data structure and algorithm foundation. The accumulated improvement is really great, especially now all the better factories will test the algorithm

Today’s content is leetCode reference offer(version 2) 39 and 50, hash table class

It is recommended to brush the same type at a time, for example, do not brush a binary tree and a dynamic planning at a time, brush a type of learning effect is better

Let’s get started

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

The title goes like this:

Find a number that occurs more than half the length of the array.

You can assume that the array is non-empty and that a given array always has most elements.

Example:

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

Limitations:

1 <= Array length <= 50000Copy the code

For example, in our development, we encountered a need to count the number of voters, which is somewhat similar to this problem

Idea 1: Hash tables

Iterate over the number group, use hash table mapping to store the frequency of occurrence of each element, take advantage of the feature that the key in the hash table will not repeat, store each element as key, and take the frequency of occurrence of each element as value

function majorityElement(nums){
    let hash = {}
    for(let i = 0, len = nums.length; i < len; i++){
        if(hash[nums[i]]) hash[nums[i]]+=1
        else hash[nums[i]] = 1
    }
    let max = 0, key
    // Run the hash table to find the key corresponding to the maximum value
    Object.keys(hash).map(k= > {
        if(max < hash[k]){
            max = hash[k]
            key = k
        }
    })
    return key
}
Copy the code

Idea 2: The voting algorithm

The idea is that the number of occurrences of each value cancels out one by one, and if all cancel out to zero, then the maximum value is the next value, because the condition is that there must be one value that occurs more than half of the array, so there is no total cancellation

If the current value is the same as num, the number of occurrences of num will be incremented. If the number of occurrences of num is different, the number of occurrences of num will be decreased by 1. If count is 0, the number of occurrences of num will be reassigned

function majorityElement(nums){
    let num = 0, count = 0
    for(let i = 0, len = nums.length; i < len; i++){
        if(count){
            count += nums[i] == num ? 1 : -1
        }else{
            num = nums[i]
            count++
        }
    }
    return num
}
Copy the code

The first character that occurs only once

The title goes like this:

Find the first character in the string s that occurs only once. If not, a single space is returned. The s contains only lowercase letters.

Example:

S = "abaccdeff" return "b" s = "return ""Copy the code

Limitations:

0 <= the length of s <= 50000Copy the code

Idea 1: Hash tables

And on the thinking of a problem is essentially the same, the code about the same, the difference is traversing the hash table for the first time meet value is 1, which is the first occurrences of one character is returned directly, without the need to traverse

function firstUniqChar(s) {
    let hash = {}
    for(let i of s){
        if(hash[i]) hash[i] += 1
        else hash[i] = 1
    }
    // Run through the hash table to find the first value to appear
    Object.keys(hash).map(k= > {
        if(hash[k] === 1) {return k
        }
    })
    return ""
}
Copy the code

Idea 2: Location comparison

Determine whether the first occurrence of the string and the last occurrence of the string point to the same value, if so, that is the value we need to find

function firstUniqChar(s) {
    for(let i of s){
        if(s.indexOf(i) === s.lastIndexOf(i)) return i
    }
    return ""
}
Copy the code

Today’s brush questions here, if you also want to brush questions, you can encourage each other to exchange

conclusion

Praise and support, hand left lingering fragrance, and have honor yan

Thank you for being here!