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

2021-08-25 06:44:04 nezha

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;
}

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.

【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