Question brushing record day01

1. Palindrome number

Title Description

Give you an integer x , If x Is a palindrome integer , return true ; otherwise , return false .

Palindrome number refers to positive order （ From left to right ） Reverse order （ From right to left ） Read all the same integers .

for example ,121 It's palindrome. , and 123 No .

The main point of solving the problem

All negative numbers are not palindromes

Turn into string Will be easier to detect , How to translate into string？std：：to_string() function

Code

#include <string>

class Solution {
public:
    bool isPalindrome(int x) {
        // Check if it is negative 
        if(x<0)
            return false;
        // Convert numbers to strings 
        std::string arr=std::to_string(x);
        int end=arr.size()-1;
        int begin=0;
        while(begin<end&&arr[begin]==arr[end])
        {
            begin++;
            end--;
        }
        if(begin<end)
            return false;
        else
            return true;
    }
};

2.* Merge 2 An ascending list

Title Description

Merge two ascending linked lists into a new   Ascending   Link list and return . The new linked list is made up of all the nodes of the given two linked lists .

Answer key

A pointer pi, Point to the smaller address

Code

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode newHead(0);
        ListNode *pi = &newHead;
        while(l1 && l2) {
            if(l1->val > l2->val) swap(l1, l2);
            pi->next = l1;
            l1 = l1->next;
            pi = pi->next;
        }
        pi->next = l1 ? l1 : l2;// Fill in the rest 
        return newHead.next;
    }
};

3. Merge N An ascending list

Title Description

Here's an array of linked lists , Each list has been listed in ascending order .

Please merge all the linked lists into one ascending list , Return the merged linked list .

Answer key

Ideas 1：

It's about the same as above , It's just that you have to find the smallest one among the many pointers pi Back

Code 1： Not written

Ideas 2： Divide and conquer method , Similar to the merging algorithm

First, two by two , And then continue to combine them in pairs

If the number of linked lists is greater than 2, Just separate from the middle , Call the merge algorithm respectively

The number of linked lists is equal to 2, Use the merge algorithm and return the header node

The number of linked lists is equal to 1, Directly back to the head node

The number of linked lists is equal to 0, return NULL

Code 2

class Solution {

    public ListNode mergeKLists(ListNode[] lists){
        if(lists.length == 0)
            return null;
        if(lists.length == 1)
            return lists[0];
        if(lists.length == 2){
           return mergeTwoLists(lists[0],lists[1]);
        }

        int mid = lists.length/2;
        ListNode[] l1 = new ListNode[mid];
        for(int i = 0; i < mid; i++){
            l1[i] = lists[i];
        }

        ListNode[] l2 = new ListNode[lists.length-mid];
        for(int i = mid,j=0; i < lists.length; i++,j++){
            l2[j] = lists[i];
        }

        return mergeTwoLists(mergeKLists(l1),mergeKLists(l2));

    }
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;

        ListNode head = null;
        if (l1.val <= l2.val){
            head = l1;
            head.next = mergeTwoLists(l1.next, l2);
        } else {
            head = l2;
            head.next = mergeTwoLists(l1, l2.next);
        }
        return head;
    }
}

4.* The number of repeats in the array

Title Description

At a length of n Array of nums All the numbers in 0～n-1 Within the scope of . Some numbers in the array are repeated , But I don't know how many numbers are repeated , I don't know how many times each number has been repeated . Please find any duplicate number in the array .

Their thinking

You can't use the simplest double loop , Will timeout

This requires the properties of the hash table

Code

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        unordered_map<int, bool> map;
        for(int num : nums) {
            if(map[num]) return num;
            map[num] = true;
        }
        return -1;
    }
};

5. The longest common prefix

Title Description

Write a function to find the longest common prefix in the string array .

If no common prefix exists , Returns an empty string  "".

 Input ：strs = ["flower","flow","flight"]
 Output ："fl"

The main point of solving the problem

One doesn't need to know string Too many function usage ideas ：

Find the length of the shortest string length, Record the total number of strings n

from 0 Start , Compare in turn n A string i Characters , Until the comparison length

use count The public records are the first few

One needs to be familiar with string Ideas on usage , But it's simpler ：

Iterate over whether all strings are s start , No. , will s Decrease one bit to continue the comparison

The end condition is ,s No characters or both s start

Code

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs.length==0)return "";
        // The common prefix is shorter than all strings , Choose any one first 
        String s=strs[0];
        for (String string : strs) {
            while(!string.startsWith(s)){
                if(s.length()==0)return "";
                // Public prefix mismatch makes it shorter ！
                s=s.substring(0,s.length()-1);
            }
        }
        return s;
    }
}