1. Majority elements

Topic describes

Given an array of size N, find most of the elements. Most elements are those that occur more than ⌊ n/2 ⌋ in the array. You can assume that the array is non-empty and that a given array always has most elements.Copy the code

The sample

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

The problem solving

from collections import Counter

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count_result = Counter(nums)
        return count_result.most_common(1)[0][0]
Copy the code

We use the Collections library Counter in Python, which is a Counter that we can use to easily count occurrences of elements such as strings, lists, Tuples, and so on.

The most_common(1) method, which checks the most common N elements, checks the most common 1 element. The return is a [(2,1)] corresponding to a tuple in the list, the first being the element and the second the number of occurrences of that element.

So, the final value returned is count_result.most_common(1)[0][0].

The longest public prefix

Topic describes

Write a function to find the longest public prefix in an array of strings. Returns the empty string "" if no public prefix exists.Copy the code

The sample

Example 1: Input: STRS = ["flower","flow","flight"] Output: "FL" Example 2: Input: STRS = ["dog","racecar","car"] Output: "" Description: The input does not have a public prefix.Copy the code

The problem solving

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        result = ""
        for i in zip(*strs):
            temp_set = set(i)
            if len(temp_set) == 1:
                result += i[0]
            else:
                break
        return result
Copy the code

The zip() function in Python solves this problem subtly.

For example, STRS = [“flower”, “flow”, “flight”], for loop zip(* STRS), and see the output:

strs = ["flower", "flow", "flight"]
new = zip(*strs)

for i in new:
    print(i)
Copy the code

The output

('f', 'f', 'f')
('l', 'l', 'l')
('o', 'o', 'i')
('w', 'w', 'g')
Copy the code

You can see that the tuple is packed as if you were unpacking every element in STRS, and the number of loops depends on the shortest element “flow”.

Here are the ideas for solving the problem:

  • Declare aresultVariable is an empty string followed by a character.
  • The for loop outzip(*strs)Each element I of phi.
  • I then converts the iterated element I to set(), de-duplicating.
  • If the value of set() is 1, then the characters in the iterated element I are the same, conforming to the common prefix.

    Added to theresultString.
  • If the length of set() is not equal to 1, there are different characters in it.breakLoop, return the resultresult.

3. Numbers that appear only once

Topic describes

Given an array of non-empty integers, each element appears twice except for one element. Find the element that appears only once.Copy the code

The sample

Example 1: input: [2, 2, 1] output: 1 example 2: input:,1,2,1,2 [4] output: 4Copy the code

The problem solving

from collections import Counter

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        result = None
        count_dict = dict(Counter(nums))
        for k, v in count_dict.items():
            if v == 1:
                result = k
                return result
Copy the code

Again, the Collections Counter is used.

For example, if the test input is nums=[4,1,2, 2], then Counter(nums) is Counter({1: 2, 2: 2, 4: 1}).

At this point, the solution is:

  • willCounterThe result converts to dict, which should be{4: 1, 1: 2, 2: 2}.
  • The dict is iterated to determine whenvalue==1The time,returnThe correspondingkey.

Integer inversion

Topic describes

You are given a 32-bit signed integer x that returns the result of reversing the numeric portion of x. If the inverted integer exceeds the range of 32-bit signed integers [−231, 231 − 1], 0 is returned. Assume that the environment does not allow storage of 64-bit integers (signed or unsigned).Copy the code

The sample

Example 1: Input: x = 123 Output: 321 Example 2: Input: x = -123 Output: -321 Example 3: Input: x = 120 Output: 21 Example 4: input: x = 0 Output: 0Copy the code

The problem solving

class Solution: def reverse(self, x: int) -> int: str_x = str(x) if str_x[0] ! = "-": str_x = str_x[::-1] x = int(str_x) else: str_x = str_x[:0:-1] x = int(str_x) x = -x if (-2**31) < x < (2**31-1): return x else: return 0Copy the code

The idea is to convert int to STR, and then slice backwards, but consider positive and negative cases, and (-2**31) < x < (2**31-1).

  • The input int is converted to STR,str_x = str(x).
  • If it’s a negative number,str_x[0] ! = "-".

    If it’s positive, slice it in reverse order[: : 1]And then turn backintType.

    If it’s negative, notice the minus signThe '-'It’s not, so slice it up[:0:-1]And then turn backintType.

    * Finally, judge the conditions given by the question,(-2**31) < x < (2**31-1), and returns only when satisfiedxOtherwise return0.

5. Maximum suborder sum

Topic describes

Given an integer array nums, find a contiguous subarray with the maximum sum (the subarray contains at least one element) and return the maximum sum.Copy the code

The sample

Example 1: input: nums = [-2,1,-3,4,-1,2,1,-5,4] output: 6 explanation: the maximum sum of consecutive subarrays [4,-1,2,1] is 6. Example 2: Input: nums = [1] Output: 1 Example 3: Input: nums = [0] Output: 0 Example 4: Input: nums = [-1] Output: -1 Example 5: Input: nums = [-100000] Output: -100000Copy the code

The problem solving

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        temp = nums[0]
        _max = temp
        for i in range(1, len(nums)):
            if temp > 0:                
                temp += nums[i]
                _max = max(_max, temp)
            else:
                temp = nums[i]
                _max = max(_max, temp)
        return _max
Copy the code

Violent solution, declare two variables, a current sum temp, a maximum sum _max. Compare the two by iterating through the array, assigning the larger one to _max.

Nums = [-5, -3, -2], temp = -8, -8 + (-2) < 0, nums = [-5, -3, -2], temp = -8, -8 + (-2) < 0. So the subsequence of the largest sum is definitely not going to start at minus 5, and then make temp equal to minus 2, and then go from there.