Daily question brushing record (13)

The first question is : The finger of the sword Offer II 015. All modifiers in the string

LeetCode: The finger of the sword Offer II 015. All modifiers in the string
describe :
Given two strings s and p, find s All in p Of A modifier The string of , Returns the starting index of these substrings . Regardless of the order of the answer output .

A modifier Means the same letters , But arrange different strings .

Their thinking :

1. Here create a size of p.length() Sliding window of
2. Use an array pArr Record p In a string , The number of occurrences of each character . sArr Record the number of occurrences of each character in the string in the current window .
3. Traversal string s Always keep the size of the sliding window , If the current sArr and pArr The contents are consistent . It returns the subscript currently traversed ( Left window subscript ).
   

Code implementation :

class Solution {
    
    public List<Integer> findAnagrams(String s, String p) {
    
        List<Integer> res = new ArrayList<>();
        int pLen = p.length();
        int sLen = s.length();
        if(pLen > sLen) return res;
        int[] pArr = new int[26];
        int[] sArr = new int[26];
        for(int i = 0; i < pLen; i++) {
    
            pArr[p.charAt(i)-'a']++;
            sArr[s.charAt(i)-'a']++;
        }
        if(Arrays.equals(pArr,sArr)) {
    
            res.add(0);
        }
        for(int i = 0; i < sLen-pLen; i++) {
    
            sArr[s.charAt(i)-'a']--;
            sArr[s.charAt(i+pLen)-'a']++;
            if(Arrays.equals(pArr,sArr)) {
    
                res.add(i+1);
            }
        }
        return res;
    }
}

The second question is : The finger of the sword Offer II 025. The two numbers in the linked list are added

LeetCode: The finger of the sword Offer II 025. The two numbers in the linked list are added

describe :
Given two Non empty linked list l1 and l2 To represent two nonnegative integers . The highest digit is at the beginning of the list . They store only one digit per node . Adding these two numbers will return a new linked list .

It can be assumed that in addition to numbers 0 outside , Neither of these numbers starts with zero .

Their thinking :

1. Two stacks are used here , Put the elements of the two linked lists on the stack
2. Take two stack elements out of the stack , Add up , See if you need to carry , Or whether you need to carry last time
3. Note that when the stack is finished , You also need to decide whether to carry .
   

Code implementation :

class Solution {
    
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    
        Stack<Integer> A = new Stack<>();
        Stack<Integer> B = new Stack<>();
        while(l1 != null) {
    
            A.push(l1.val);
            l1=l1.next;
        }
        while(l2 != null) {
    
            B.push(l2.val);
            l2=l2.next;
        }
        ListNode tmp = null;
        int ret = 0;
        while(!A.isEmpty() || !B.isEmpty() || ret != 0) {
    
            int a = A.isEmpty() ? 0 : A.pop();
            int b = B.isEmpty() ? 0 : B.pop();
            int sum = a + b + ret;
            ret = (a + b + ret) / 10;
            sum %= 10;
            ListNode node = new ListNode(sum);
            node.next = tmp;
            tmp = node;
        }
        return tmp;
    }
}

Third question : The finger of the sword Offer II 026. Rearrange the list

LeetCode: The finger of the sword Offer II 026. Rearrange the list

describe :
Given a single chain table L The head node of head , Single chain list L Expressed as ：
L0 → L1 → … → Ln-1 → Ln
Please rearrange them to ：
L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
You can't just change the value inside the node , It needs to actually exchange nodes .

Their thinking :

1. Here we first find the intermediate node .
   • The intermediate node can be found by the way of fast and slow pointer
2. Reverse the middle node to the tail node .
   • Three reference traversal .
3. Then on the first half and The second half is organized
   

Code implementation :

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */
class Solution {
    
    public void reorderList(ListNode head) {
    
        if(head == null) return;
        ListNode mid = getMid(head);
        ListNode midNext = mid.next;
        mid.next = null;
        ListNode ret = head;
        ListNode tmp = reverse(midNext);
        while(ret != null && tmp != null) {
    
            ListNode retNext = ret.next;
            ListNode tmpNext = tmp.next;
            ret.next = tmp;
            tmp.next = retNext;

            ret = retNext;
            tmp = tmpNext;
        }
    }
    public ListNode getMid(ListNode head) {
    
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next != null && fast.next.next != null) {
    
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    public ListNode reverse(ListNode head) {
    
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null) {
    
            ListNode curNext = cur.next;
            cur.next = pre;
            pre = cur;
            cur = curNext;
        }
        return pre;
    }
}

Fourth question : The finger of the sword Offer II 030. Insert 、 Deletion and random access are O(1) The container of

LeetCode: The finger of the sword Offer II 030. Insert 、 Deletion and random access are O(1) The container of

describe :
Design a support in average Time complexity O(1) Next , Data structure to do the following ：

• insert(val)： When element val Return... When not present true , And insert the item into the collection , Otherwise return to false .
• remove(val)： When element val Return when there is true , And remove the item from the collection , Otherwise return to false .
• getRandom： Random return of an item in an existing collection . Every element should have Same probability Returned .

Their thinking :

1. Here we use a Hash table to record , key For the currently inserted value , value Insert the corresponding List The subscript
2. I'm going to use a list Insert .
3. At the time of insertion , Determine whether there is this in the hash table val 了 , If there is a direct return false, If not, it will val Insert list in , And will val And corresponding list Subscript insertion in map in . return true;
4. When deleting , Determine whether there is this in the hash table val, If there is no direct return false, If there is , Get this val The subscript , take list The last element in is exchanged with the current subscript , Then delete list The last element , Delete the corresponding... In the hash table key value , return true;
5. Random access , Create a random, The size is current list The size of a random number , Get a number in this range at random , And back to .

Code implementation :

class RandomizedSet {
    
    private Map<Integer,Integer> map;
    private List<Integer> list;
    private Random random;
    /** Initialize your data structure here. */
    public RandomizedSet() {
    
        map = new HashMap();
        list = new ArrayList<>();
        random = new Random();
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
    
        if(map.containsKey(val)){
    
            return false;
        }
        list.add(val);
        map.put(val,list.size()-1);
        return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
    
        if(!map.containsKey(val)){
    
            return false;
        }
        int index = map.get(val);
        int last = list.get(list.size()-1);
        list.set(index,last);
        map.put(last,index);
        list.remove(list.size()-1);
        map.remove(val);
        return true;
    }
    
    /** Get a random element from the set. */
    public int getRandom() {
    
        return list.get(random.nextInt(list.size()));
    }
}

Fifth question : The finger of the sword Offer II 032. Effective morphemes

LeetCode: The finger of the sword Offer II 032. Effective morphemes

describe :
Given two strings s and t , Write a function to determine whether they are a group of modifiers （ Letter heterotopic word ）.

Be careful ： if s and t The number of occurrences of each character is the same and the character order is not exactly the same , said s and t Each other is a modifier （ Letter heterotopic word ）.

Their thinking :

1. First of all, character string s and character string t Compare , See if it's the same , If the same direct return false;
2. Use an array to record s The number of times characters appear in , As long as it appears , Just ++
3. And then traverse the string t , If the character appears , Just --
4. Traversing the current array , Is there any element that is not 0, Not for 0 It means that you are not satisfied with the meaning of the question , return false
5. End of traversal return true

Code implementation :

class Solution {
    
    public boolean isAnagram(String s, String t) {
    
        if(s.equals(t)) return false;
        int[] arr = new int[26];
        for(char ch : s.toCharArray()) {
    
            arr[ch-'a']++;
        }
        for(char ch : t.toCharArray()) {
    
            arr[ch-'a']--;
        }
        for(int val : arr) {
    
            if(val != 0) return false;
        }
        return true;
    }
}

Sixth question : The finger of the sword Offer II 033. Morpheme phrase

LeetCode: The finger of the sword Offer II 033. Morpheme phrase

describe :
Given an array of strings strs , take A modifier Put together . You can return a list of results in any order .

Be careful : If each character in two strings appears the same number of times , They are called mutuals .

Their thinking :

1. Traverse strs, Turn every element into char Array to sort
2. And then char The array becomes a string , Using a hash table , Determine whether the current string exists in the hash table
   • If it doesn't exist , Just create one list, take str Put it in , Then deposit map in
   • If there is , Directly get the corresponding list, And then str Put it in .
3. End of traversal , take map become ArrayList return .

Code implementation :

class Solution {
    
    public List<List<String>> groupAnagrams(String[] strs) {
    
        Map<String,List<String>> map = new HashMap<>();
        for(String str : strs) {
    
            char[] ch = str.toCharArray();
            Arrays.sort(ch);
            String s = new String(ch);            
            if(!map.containsKey(s)) {
    
                List<String> ret = new ArrayList<>();
                ret.add(str);
                map.put(s,ret);
            }else{
    
                map.get(s).add(str);
            }
        }
        return new ArrayList(map.values());
    }
}