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
Interpretation:
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
Interpretation:
The strings "hello" and "world" can be formed, so the answer is 5 + 5 = 10.
Tips:
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 count++; } else { //If not, skip the loop break; } //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; break; } } //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) { //sum+1 sum++; } else { //If the current number is 0, - 1 sum--; } //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.
Example:
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
Explain:
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 Arrays.sort(chars); //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 map.get(key).add(string); } //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.
-NANA
