[introduction to 100 day algorithm - three questions a day - Day7] verify palindrome strings, numbers that appear only once, and most elements

Hello everyone , I'm Nezha , A person who loves coding Java The engineer , In line with “ More haste, less speed. , If you want to reach, you need to be quick ” The attitude of learning , Growing up on the road of no return , Growth , Just take time to polish your eyes , When I was young, I valued , When you are old, you look like a feather , When I was young, I despised , When you are old, you look like Mount Tai , The road to growth , Is also gradually put down obsession , The journey of inner peace .

Maybe , We never know where we can go , Meet who , What kind of person will you become in the end , But remember , Someone who can climb high , Never someone else's shoulder , It's the one who stays up all night , The road of life has just started , When you are tired, don't be confused , Look back , You are no longer that young and frivolous boy .

Dalian Xinghai Park

---

  Algorithms are the foundation of advanced architects , The foundation is not solid , The earth trembled and the mountains swayed ,2021-8-14 Start to brush questions , The goal is 100 God ,300 Avenue LeetCode Algorithm problem , Sharing is the best way to learn , come on. , Hi up .

1、LeetCode 125. Verify the palindrome string

subject

Given a string , Verify that it is a palindrome string , Consider only alphabetic and numeric characters , The case of letters can be ignored .

explain ： In this question , We define an empty string as a valid palindrome string .

Xiaobian vegetable solution

public static boolean isPalindrome(String s) {
    //  Get only numeric and alphabetic parts through regular expressions 
    s=s.replaceAll("[^a-zA-Z0-9]","").toLowerCase();
    //  Palindromes are strings that are separated in the middle , Front and back revert equally 
    int length = s.length();
    String left = "";
    String right = "";
    if (length%2 != 0){
        left = s.substring(0,length/2);
        right = s.substring(length/2+1,length);
        right = new StringBuilder(right).reverse().toString();
    }else{
        int mid = length/2;
        left = s.substring(0,mid);
        right = s.substring(mid,length);
        right = new StringBuilder(right).reverse().toString();
    }
    return left.equals(right);
}

Although the implementation passed , But the efficiency is worrying .

Ideas and algorithms

“ Palindrome string ” It's a string that is read both forward and backward , such as “level” perhaps “noon” And so on are palindrome strings .

So why do you want to separate it in the middle , Direct reversal , Compare the reversed and initial , No, it's over ？ Food .

Improved version of side dishes

public static boolean isPalindrome3(String s) {
    //  Get only numeric and alphabetic parts through regular expressions 
    s=s.replaceAll("[^a-zA-Z0-9]","").toLowerCase();
    return s.equals(new StringBuilder(s).reverse().toString());
}

Efficiency is still very low , For the sake of regularity .

The boss points out the country

public static boolean isPalindrome(String s) {
    StringBuilder builder = new StringBuilder();
    for (int i = 0;i<s.length();i++){
        char c = s.charAt(i);
        if (Character.isLetterOrDigit(c)){
            builder.append(Character.toLowerCase(c));
        }
    }
    return builder.toString().equals(builder.reverse().toString());
}

The gap is still very obvious , Don't use regular expressions if you can .  

2、LeetCode 136. A number that appears only once

subject

Given an array of non-empty integers , Except that an element only appears once , Each of the other elements occurs twice . Find the element that only appears once .

explain ： Your algorithm should have linear time complexity . Can you do this without using extra space ？

Xiaobian vegetable solution

/**
 *  The brute force algorithm , Compare the current element with other elements , If there are equal , It means more than once , Unequal , It means only 
 */
public static int singleNumber(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        boolean flag = true;
        for (int j = 0; j < nums.length; j++) {
            if (i != j){
                if (nums[i] == nums[j]){
                    flag = false;
                    break;
                }
            }
        }
        if (flag){
            return nums[i];
        }
    }
    return 0;
}

The boss points out the country

Two values involved in the operation , If two correspond bit Same bit , The result is 0, Otherwise 1.

public static int singleNumber(int[] nums) {
    int single = 0;
    for (int num : nums) {
        single ^= num;
    }
    return single;
}

3、LeetCode 169. Most elements

subject

Given a size of n Array of , Find most of them . Most elements refer to the number of occurrences in an array Greater than  ⌊ n/2 ⌋  The elements of .

You can assume that the array is not empty , And there are always many elements in a given array .

Xiaobian vegetable solution

public static int majorityElement(int[] nums) {
    if (nums.length == 1){
        return nums[0];
    }

    for (int i = 0; i < nums.length; i++) {
        int sum = 1;
        for (int j = 0; j < nums.length; j++) {
            if (i != j){
                if (nums[i] == nums[j]){
                    sum++;
                }
            }
        }

        if (sum > nums.length/2){
            return nums[i];
        }
    }
    return 0;
}

Small cooking solution improved version

public static int majorityElement(int[] nums) {
    Map<Integer,Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        if (!map.containsKey(nums[i])){
            map.put(nums[i],1);
        }else{
            map.put(nums[i],map.get(nums[i]) + 1);
        }
    }
    for (Map.Entry<Integer,Integer> entry : map.entrySet()){
        if(entry.getValue() > nums.length/2){
            return entry.getKey();
        }
    }
    return 0;
}

The execution time is less than a little , Progress is remarkable , come on. .

The boss points out the country

public static int majorityElement(int[] nums) {
    Arrays.sort(nums);
    int mid = nums.length/2;
    return nums[mid];
}

what ？ You can play like this ？ Think about , It's true , Because to get the mode , The mode must be greater than half , If after sorting , The middle of this array must belong to mode , frigging awesome plus.

Recommended reading

【100 Introduction to sky algorithm - Three questions a day - Day1】 Middle order traversal of binary trees 、 Sum of two numbers 、 Integer inversion

【100 Introduction to sky algorithm - Three questions a day - Day2】 Two points search 、 First wrong version 、 Search insert location

【100 Introduction to sky algorithm - Three questions a day - Day3】 Palindrome number 、 Roman numerals to numbers 、 Maximum common prefix

【100 Introduction to sky algorithm - Three questions a day - Day4】 Valid parenthesis 、 Remove duplicate items from an ordered array 、 Realization strStr

【100 Introduction to sky algorithm - Three questions a day - Day5】 Length of last word 、 Same tree 、 The best time to buy and sell stocks

【100 Introduction to sky algorithm - Three questions a day - Day6】 Symmetric binary tree 、 The maximum depth of a binary tree 、 Convert an ordered array to a binary search tree