My way to shadow

This series records my algorithm problems

O ye
1. Spelling words
Spelling word original title link

I'll give you a vocabulary (string array) words and an alphabet (string) chars.

If you can spell a word (string) in words with "letters" (characters) in chars, then we think you have mastered the word.

Note: each letter in chars can only be used once per spelling.

Returns the sum of the lengths of all the words you know in the vocabulary words.

Example 1:

Input: words = ["cat", "bt", "hat", "tree"], chars = "atach"
Output: 6
The strings "cat" and "hat" can be formed, so the answer is 3 + 3 = 6.

Example 2:

Input: words = ["hello", "world", "leetcode"], chars = "weldonehoneyr"
Output: 10
The strings "hello" and "world" can be formed, so the answer is 5 + 5 = 10.


1 <= words.length <= 1000
1 <= words[i].length, chars.length <= 100
All strings contain only lowercase letters

Source: LeetCode
The meaning of this problem is to find the strings in a given array of characters

  public int countCharacters(String[] words, String chars) {
        int count = 0;
        int sum = 0;
         final String preChar = chars;
         //Traversing a string array
        for (int i = 0; i < words.length; i++) {
        //Traversing a string through characters
            for (int j = 0; j < words[i].length(); j++) {
            //If the given alphabet contains the j-th character of the i-th string
                if (chars.contains(String.valueOf(words[i].charAt(j)))) {
                //Reorganize the alphabet, because the title says that each letter of the alphabet can only be used once
                    chars = chars.substring(0, chars.indexOf(String.valueOf(words[i].charAt(j)))) + chars.substring(chars.indexOf(String.valueOf(words[i].charAt(j))) + 1);
                    //Add one to count each time you change the alphabet
                } else {
                //If not, skip the loop
                //If count is equal to the length of the ith string (the length of string into character array)
                if (count == words[i].length()) {
                //Sum plus count for final output
                    sum += count;
            //Reset count for next string operation
            count = 0;
            //The alphabet has been updated to remove used characters
            chars = preChar;
        return sum;

This is really the first algorithm problem I did. Although the definition of difficulty is simple, it is still difficult for me who has a weak foundation

2. Continuous array
Continuous array original question link

Given a binary array, find the longest continuous subarray with the same number of 0s and 1s.

Example 1:

Input: [0,1]
Output: 2
Description: [0, 1] is the longest continuous subarray with the same number of 0 and 1.

Example 2:

Input: [0,1,0]
Output: 2
Description: [0, 1] (or [1, 0]) is the longest continuous subarray with the same number of 0 and 1.

Note: the length of a given binary array will not exceed 50000.

Source: LeetCode
The meaning of this problem is to find out the length of a continuous subarray with the largest number of 0 and 1 in an array with only 0 and 1

 public int findMaxLength(int[] nums) {
     int max = 0;//Initialize maximum length
        int len = nums.length;
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        map.put(0, -1);//Used to identify 0 and 1
        //Store current maximum
        int sum = 0;
        //Traversal array nums
        for (int x = 0; x < len; x++) {
        //If the current number is 1
            if (nums[x] == 1) {
            } else {
        //If the current number is 0, - 1
            //If the sum key node of the map does not store value
            if (map.get(sum) == null) {
            //Add value
                map.put(sum, x);
            } else {
            //Otherwise, the maximum value of all traversals is the difference between the previous maximum value and the subscript of the current traversal and the value of sum as the key in the map
                max = Math.max(max, x - map.get(sum));
        return max; 

After the first contact with HashMap, I have been puzzled for several days. What's the use of HashMap? It can store data. Isn't both the list and the array OK? Today, I went to see the detailed explanation of the HashMap source code. I'm amazed that human beings are really smart and can combine the advantages of the array and the list, or even add the idea of tree. It's really amazing

3. Letter heterotopic word grouping
Letter heterotopic word group original topic link

Given an array of strings, you can combine words with different letters. Alphabetic words refer to strings with the same letters but arranged differently.


Input: ["eat", "tea", "tan", "ate", "nat", "bat"],


All inputs are lowercase.
Do not consider the order of the answer output.

Source: LeetCode
The meaning of this question is to put the same letter in a chain list of multiple words, and finally form a large chain list of multiple chain lists

public List<List<String>> groupAnagrams(String[] strs) {
//The map generics here use String as key and ArrayList < String > as value to facilitate the final return
           HashMap<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
           //Traversing the given string array
		for (String string : strs) {
		//To change a string into an array of char s
			char[] chars = string.toCharArray();
			//Sort it to filter out words with the same letters
			//Create a key for a string consisting of an array of characters
			String key = new String(chars);
			//If the key does not exist in the map
			if (!map.containsKey(key))
			//put, and create a new list
				map.put(key, new ArrayList<String>());
			//map gets the value of the current key, that is, a linked list, and calls add to put the currently traversed string into the linked list
		//The return value directly creates a linked list. The content is the set of map values. There is no generics here, but you can add or not
		return new ArrayList(map.values());

Using HashMap this time, I feel that it is very useful, efficient to traverse, unlimited key, value (can be changed at will when defining), self-contained efficient method, and call him

I began to feel the charm of the algorithm gradually. I tried to get through a new problem every day

We must protect our dreams, even at the expense of everything.

Published 13 original articles, won praise 8, visited 997
Private letter follow

Added by Hylian on Sat, 08 Feb 2020 16:33:04 +0200