Date: 2019--8-12

1. Converting strings to integers (Examining knowledge points: strings and programmatic conversions)

Topic Description

Converting a string to an integer (realizing the function of Integer.valueOf(string), but returning 0 when string does not meet the number requirement) requires that the library function of string conversion to an integer cannot be used. If the value is 0 or the string is not a valid value, it returns 0.

Input Description:

Enter a string, including numeric alphabetic symbols, that can be null

Output description:

If it is a valid numerical expression, it returns the number, otherwise it returns 0.

Example 1

input

copy

+2147483647
    1a33

output

copy

2147483647
    0

Analysis: At first, the idea of direct int is to use a try grammar for this problem, but it is not this point that should be examined. We need to consider the way of string writing, so we can judge one character by one character.

First of all, it is still necessary to make a non-null judgment on the input characters.

Then the first character is inspected separately:

i) If the first character is a symbol or a non-numeric character, the result a can be directly set to 0 without directly returning 0.

ii) When the first digit is a number, it can express the highest digit directly by the first digit * (10**(len(s)-1).

Then traverse and inspect the characters on the back bits. If they are between 0 and 9, the corresponding * will be accumulated later. Otherwise, when they are not between 0 and 9, they will return 0 directly.

Finally, we consider the case that the first bit is the symbol bit, +time output a, -time output-a.

Finally, we need to output a bit at the outermost layer, considering that if the first bit is not a symbol bit, and satisfy the output when each bit is between 0 and 9.

# -*- coding:utf-8 -*-
class Solution:
    def StrToInt(self, s):
        # write code here
        if not s:
            return 0
        else:
            if s[0] >'9'or s[0] <'0':  # Here is the connection is or, because in else, yes and condition
                a = 0  # You can't return 0 directly because the first possible bit is the symbol bit.
            else:
                a = int(s[0])*(10**(len(s)-1))  # If the first character is between 0 and 9, it is converted to the highest number.
            if len(s)>1:
                for i in range(1, len(s)):
                    if s[i] <= '9' and s[i] >='0':  # First, determine whether the character in the first place is between 0 and 9. If so, add up
                        a += int(s[i])*(10**(len(s)-1-i))
                    else:  # Otherwise, if the character in the first place is a character, it does not conform to the rule and returns 0.
                        return 0
        if s[0] == '+':     # Output with + sign
            return a
        elif s[0] == '-':   # Output with - sign
            return -a 
        return a     # General output without prefix symbols

# -*- coding:utf-8 - * - Another clever way of thinking, using try statements, is also passed, and the time complexity is smaller!
class Solution:
    def StrToInt(self, s):
        # write code here
        try:
            return int(s)
        except Exception as e:
            return 0

In addition, it can initialize a list of numbers 0~9 and a symbol dictionary {'+': 1,'-': -1} first, then discuss two ways according to the situation of the first character, and then traverse the following characters to discuss the processing of the character situation (continuous accumulation).

# -*- coding:utf-8 -*-  # Introducing digital list and symbol dictionary, the time complexity is similar to the first method, and the space complexity is a little bit larger.
class Solution: 
    def StrToInt(self, s):
        if not s:
            return 0
        str2num={'1':1,'2':2,'3':3,'4':4,'5':5,'6':6,'7':7,'8':8,'9':9,'0':0}
        flag2num={'-':-1,'+':1}
        first=s[0]
        if first in ['+','-']:
            flag=flag2num[first]
            x=0
            for i in s[1:]:
                if i not in str2num:
                    return 0
                x=x*10+str2num[i]
            return flag*x
        else:
            x=0
            for i in s:
                if i not in str2num:
                    return 0
                x=x*10+str2num[i]
            return x

2. Repeated numbers in arrays (checking knowledge points: arrays)

Topic Description

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

Analysis: At first I didn't understand the meaning of this question, then I thought about the topic: I need to find any duplication number, first assign it to duplication[0], then return true, the system background will automatically give the corresponding correct output.

Idea: I think the first way is to borrow a full-zero array B with len(numbers) length, and then traverse every number in the number, accumulating its occurrence number at the corresponding position in the B array. If the first occurrence number equals 2, then assign the value directly and return it. Otherwise, false is returned at the outermost level. (The title here shows that numbers are all numbers in an array of length N in the range of 0 to n-1, so it can be assumed that the array of B arrays also defaults from 0 to n-1.)

# -*- coding:utf-8 -*-
class Solution:
    # Special attention should be paid here to finding an arbitrarily repeated value and assigning it to duplication[0]
    # Function returns True/False
    def duplicate(self, numbers, duplication):
        # write code here
        if not numbers:
            return False
        B = [0]* len(numbers)  # Initialize the all-zero array B for calculating the frequency of numbers in numbers
        for i in range(len(numbers)):  # ergodic
            B[numbers[i]] += 1   # According to the number [i], the corresponding position in B is calculated accumulatively.
            if B[numbers[i]] == 2:  # If 2 occurs for the first time, the assignment can be made and the return can be made.
                duplication[0] = numbers[i]
                return True
        return False

The second clever method is to use Counter() Library in collections module to calculate the frequency of each number in numbers, but I don't think the original intention of the test is here (this is a high-level algorithm), but it is still possible to solve the problem.

# -*- coding:utf-8 -*-
import collections
class Solution:
    # Special attention should be paid here to finding an arbitrarily repeated value and assigning it to duplication[0]
    # Function returns True/False
    def duplicate(self, numbers, duplication):
        # write code here
        if not numbers:
            return False
        c_dicts = collections.Counter(numbers)  # According to this function, we can get the frequency statistics of each number, which is a dictionary.
        for k,v in c_dicts.items():
            if v >1:   # If the corresponding K frequency is greater than 1, assign and return
                duplication[0] = k
                return True
        return False

3. Construct product array (check knowledge points: array). (Subscript selection is a bit difficult to understand, see more!)

Topic Description

Given an array A[0,1,...,n-1], construct an array B[0,1,...,n-1], where the element B [i] = A [0] * A [1] * * A [i-1] * * A [i+1] * A [n-1]. Division cannot be used.

Analysis: Idea 1: Super high time complexity, not considered, but write down the idea: for each element B[i] calculation directly using the cumulative A [0] * A [1] * * A [i-1] * A [i + 1] * * A [n-1]. But apparently from the factor analysis, we find that it can be regarded as the product of the front and back parts, and then as the product of the two parts.

Idea 2: From the above intuitive ideas, we can find that we can use the idea of "sacrificing space for time" to construct two lists to store forward recursive product and backward recursive product; head[i] = A[0]*A[1] *... * A[i-1] tail[i] = A[-1]*A[-2]*... * A[-i], note that the first element of both lists is 1, and tail uses a backward traversal (negative index) method when it fetches them.

# -*- coding:utf-8 -*-
class Solution:
    def multiply(self, A):
        # write code here
        if not A:
            return False
        head = [1]  # Initial value is to find the first element, the value of the first element should be given 1, but use A[1]... * A[n-1]
        tail = [1]  # Initial value is to find the last element, the last element should be given a value of 1, but the use of A[-2]... *A[-n]
        for i in range(len(A)-1):
            head.append(head[i]*A[i])  # The result of forward multiplication, the final length equal to len(A)
            tail.append(tail[i]*A[-i-1])  # The result of reverse multiplication, the final length equal to len(A)
        return [head[j]*tail[-j-1] for j in range(len(head))]  # Note that head is forward fetching and tail is backward index fetching!

Attached are the intuitive explanations given by others on the cattle passenger.

Idea: Calculate the product of the two parts of each row divided by one according to the figure above, so that two lists can be calculated by cumulative multiplication from the beginning to the end, and then the two lists can be multiplied by the beginning and the end to be elements of B.

4. Regular expression matching (investigating knowledge: strings, regular expressions) has many details to discuss, which is more complex!!! Look more

Topic Description

Implement a function to match regular expressions including'. 'and'*'. The character'. 'in the pattern represents any character, and'*' indicates that the character before it can appear any number of times (including 0 times). In this topic, matching means that all characters of a string match the entire pattern. For example, the string "a a a" matches the pattern "a.a" and "ab*ac*a", but does not match "aa.a" and "ab*a".

Analytical thinking: (Write down the overall thinking first) It is divided into four parts, and then some parts need to be discussed below.

1) Both strings are empty and the direct matching is successful

2) If the string is empty, but the pattern is not empty, the matching may be unsuccessful and successful (when the length of the pattern is greater than 1 and the second bit is * the recursive invocation of the pattern is backward by two; otherwise the direct matching is unsuccessful)

3) The string is not empty, but the pattern is empty, so the matching is obviously unsuccessful.

4) When the string and pattern are not empty, we need to discuss whether the second bit in the pattern is * or not.

4.1) If the length of the mode is greater than 1 and the second position of the mode is *, it needs to be judged whether the first position is equal or not.

4.1.1) If the first place is unequal and the first place of the mode is not. the string remains unchanged and the mode is moved back by two (equivalent to treating the first two of the mode as empty)

4.1.2) Otherwise, it can be divided into the following three cases, and any one of them can be called recursively:

(i) Make the first two of P empty: move two after p, and make recursive calls with s unchanged

ii) Match the first two of p with the first two of s: move two after p and one after s (equivalent to 0 repetitions of generations).

iii) try to match the first two bits of p with the first two bits of s: p unchanged, and move one bit after s (try to match multiple characters)

4.2) If the second character is not equal to *, when the first bit of the string and pattern is equal or the first bit of the pattern is. the match is successful, then the match is made by recursive calls later; otherwise the match is unsuccessful!

# This is the longest comment I have ever written on any offer. Because it is difficult to understand, there are many details to consider, we must see more and see more!!!
# -*- coding:utf-8 -*-
class Solution:
    # s, pattern are strings
    def match(self, s, pattern):
        # write code here
        # If both are empty, the match is successful
        if len(s) == 0 and len(pattern) == 0:
            return True
        # If the string is empty, the mode is not empty. If the length of the pattern is greater than 1 and the second bit is *, the matching is recursive and the pattern is moved back by two. Otherwise, if the length is 1 or the second bit is not *, the matching is unsuccessful.
        elif len(s) == 0 and len(pattern) != 0:
            if len(pattern)>1 and pattern[1] == '*':
                return self.match(s,pattern[2:])  # This is equivalent to using * in pattern 0 times.
            # Otherwise, if the length is 1 or the second position is not *, the matching is unsuccessful.
            else:
                return False  
        # If the string is not empty, but the pattern is empty, obviously the match will not succeed.
        elif len(s) != 0 and len(pattern) == 0:
            return False
        # Neither is empty and needs to be discussed with the help of the second model:
        else:
            # The second model is*
            if len(pattern)>1 and pattern[1] == '*':
                # If the first one is unequal and not, then the pattern is moved back by two, which is equivalent to treating the first two of the pattern as empty.
                if  s[0] != pattern[0] and pattern[0] != '.':
                    return self.match(s, pattern[2:])
                else:
                    # The second bit of the pattern is *, and the first bit of the pattern is equal to the first bit of the string. There are three cases, any one of which can be established:
                    #1. Take the first two places of p as empty: p moves back two places and s remains unchanged.
                    #The first two of 2p are to match the first one: two of P are moved back and one of s is moved back.
                    #The first two digits of 3p are to match the first two digits of s: P is unchanged, s is moved backward one digit (the first two digits of P at this time try to match the first multiple characters of s)
                    return self.match(s,pattern[2:]) or self.match(s[1:],pattern[2:]) or self.match(s[1:],pattern)
            else:
                # If the second position of the pattern is not *, first judge if the first position is equal or if the first position of the pattern is * then their first match is successful and they all move one bit backwards.
                if s[0] == pattern[0] or pattern[0] == '.':
                    return self.match(s[1:],pattern[1:])
                # Otherwise, the second position of the pattern is not *, and the first position is unequal and the first position of the pattern is not. Then the matching is unsuccessful.
                else:
                    return False

5. Strings representing numeric values (checking knowledge points: strings + regular expressions + mathematical rules)

Topic Description

Implement a function to determine whether a string represents a value (including integers and decimals). For example, strings "+100","5e2","-123","3.1416" and "-1E-16" all represent values. But "12e", "1a3.14", "1.2.3", "+5" and "12e+4.3" are not.

Analysis: This question and the first question have the similar method of passing by coincidence, but it is not the intention of the title (strongly do not recommend that you operate in this way, what kind of strange person I am!!)

First, stick out the clever passing code:

# -*- coding:utf-8 -*-
class Solution:
    # s String
    def isNumeric(self, s):
        # write code here
        try:
            return float(s)
        except Exception as e:
            return False

The second method: matching using re Library Based on the idea of regular expression

# -*- coding:utf-8 -*-
import re
class Solution:
    # s String
    def isNumeric(self, s):
        # write code here
        return re.match(r"^[\+\-]?[0-9]*(\.[0-9]*)?([eE][\+\-]?[0-9]+)?$",s)

Third kind: Mathematical rule method, suggest to see more!

Idea Analysis: Initialize three tags to mark symbol bits, decimal points and e respectively.

1) In the case of e, two e cannot occur at the same time, and e cannot be in the last place (because e is followed by a number).

2) In the case of symbol bits, if the symbol bits have appeared before, the symbol should appear after e, otherwise the error will occur.

If the symbol bit appears for the first time, if I > 1, the former must be e, otherwise false

3) For the case of decimal point, it can not occur twice, and after the occurrence of e, it can not occur again.

If the decimal point appears for the first time, but it has already appeared e before, it will not work.

4) Otherwise, if it is not an e decimal point, it should be a number between 0 and 9, otherwise false

Because the whole inside is to judge the inconsistency, so if the inside is not satisfied, jump to the outermost layer to give True's results!

# -*- coding:utf-8 -*-
class Solution:
    # s String
    def isNumeric(self, s):
        # write code here
        if len(s) <= 0:
            return False
        # Whether there have been positive and negative sign, decimal point and e markers respectively, because these need special consideration
        has_sign = False
        has_point = False
        has_e = False
        for i in range(len(s)):
            # 1 For e
            if s[i] == 'E' or s[i] == 'e':
                # There are two different e
                if has_e:
                    return False
                # E can't appear at the end, because e is followed by a number
                else:
                    has_e = True
                    if i == len(s)-1:
                        return False
             # 2 For the case of sign bits
            elif s[i] == '+' or s[i] == '-':
                # If the symbol bit has already appeared before, then the symbol bit must be followed by e.
                if has_sign:
                    if s[i-1] != 'e' or s[i-1] != 'E':
                        return False
                 # If this is the first occurrence of a symbol bit and the occurrence is not the first occurrence of a string, then it can only occur after e.
                else:
                    has_sign = True
                    if i > 0 and s[i-1] != 'e' and s[i-1] != 'E':
                        return False
             # 3 For decimal points
            elif s[i] == '.':
                # The decimal point can't appear twice; and if it has already appeared e, then it can't appear again, because it can only be an integer after E.
                if has_point or has_e:
                    return False
                # If the decimal point appears for the first time, if e has appeared before, then the decimal point can not appear.
                else:
                    has_point = True
                    if i > 0 and has_e:
                        return False
            else:
                # 4 Other characters must be between'0'and'9'.
                if s[i] < '0' or s[i] > '9':
                    return False
            return True

6. The first non-repetitive character in the character stream (checking knowledge points: strings)

Topic Description

Implement a function to find the first character in the character stream that appears only once. For example, when only the first two characters "go" are read out from the character stream, the first character that appears only once is "g". When the first six characters "google" are read from the stream, the first character that appears only once is "l".

Output description:

If there is no character that appears once in the current character stream, return the # character.

Analysis: At the beginning of this topic, I did not understand why there are two functions and an insert function. Do we need to constantly add strings? Later, I see that their discussion is really like this. So we use _init_ function to build a global member function: self.s. And then continue to add char to this s.

The formal output of non-repetitive characters is from the FirstAppearingOne function. Then the count s function is used to calculate the frequency of the characters in S. The characters whose frequency is equal to 1 will be put into res in turn, and then the first one will be returned.

# -*- coding:utf-8 -*-
class Solution:
    # Return the corresponding char
    def __init__(self,):
        self.s = ''
    def FirstAppearingOnce(self):
        # write code here
        res = list(filter(lambda c: self.s.count(c)==1,self.s))
        return res[0] if res else '#'
    def Insert(self, char):
        # write code here
            self.s += char

But I don't think the above idea is the original intention of this topic. After all, I don't have an offer book now. I don't know what the implication is.

The second method:

"""
Solution: An int array is used to represent 256 characters, and the initial value of the array is set to -1.    
For each character read out, the position of the character is stored in the subscript of the corresponding array of characters.    
If the value is - 1 to mark the first reading, not - 1 and > 0 to indicate that it is not the first reading, change the value to - 2.    
Then the minimum value of > 0 is found in the array, and the character corresponding to the subscript of the array is required.    
In python, ord(char) is the ASCII code corresponding to char; chr(idx) is the character to get the ASCII bit idx.    
"""
class Solution:
    def __init__(self):
            self.char_list = [-1 for i in range(256)]
            self.index = 0 # records the number of current characters, which can be understood as subscripts in the input string
    def FirstAppearingOnce(self):
        # write code here
        min_value = 500
        min_idx = -1
        for i in range(256):
            if self.char_list[i] > -1:
                if self.char_list[i] < min_value:
                    min_value = self.char_list[i]
                    min_idx = i
        if min_idx > -1:
            return chr(min_idx)
        else:
            return '#'
    def Insert(self, char):
        # If the first occurrence occurs, the value of the corresponding element is changed to the following
        if self.char_list[ord(char)] == -1:
            self.char_list[ord(char)] = self.index
        # If it has already happened twice, do not modify it.
        elif self.char_list[ord(char)] == -2:
            pass
        # If it occurs once, it is modified to -2.
        else:
            self.char_list[ord(char)] = -2
        self.index += 1

The third method: Although the solution has passed, I think there is a problem.

class Solution:
    def __init__(self):
        self.s = ''
        self.queue = []     #Save all characters that appear only once in sequence
        self.second = []    #Save all characters in sequence
    def FirstAppearingOnce(self):
        if self.queue:
            return self.queue[0]
        return '#'     
    def Insert(self, char):
        self.s += char
        if char in self.queue:
            self.queue.pop(self.queue.index(char))  # If a character appears three times, the first two cancel out?
        elif char not in self.second:
            self.queue.append(char)  # Will you put in the characters that appear odd numbers?
            self.second.append(char)