This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.
One, foreword
1024 program section, I wish you a happy holiday!
Recently, a friend of mine had a heart-to-heart talk with me. He felt that it was too difficult to brush the algorithm, and he had no idea at all. He felt frustrated and wanted to give up. Think about yourself, have these ideas are really quite normal, in fact, we brush algorithm is to cultivate a thinking problem, problem solving thinking, this thinking is not overnight, but step by step.
So, this is the only way to grow, learn classics to experience even ninety-nine hundred and eleven difficult, but want to hold to it only, every day is a brand-new oneself, small white becomes the road of great god is destined not to be simple, but you are willing to do nothing all the time, still comfort oneself ordinary commendable?
Stick to it, you can peel cocoon into a butterfly! Please continue to learn with Xiaocheng, xiaocheng will do his best to make each algorithm from topic analysis to solution more popular understanding, and grow together with everyone. If you feel frustrated and want to give up when you brush the questions, welcome to find Xiaocheng to ridicule, xiaocheng will give you full of energy to start again!
The oldest string without repeating characters
Finished speaking, to see today’s Boss: “no repeated characters of the oldest string”.
Given a string s, find the length of the smallest string that does not contain repeating characters.
Example:
Example 1: Input: s = "abcabcbb" Output: 3 Explanation: Since the oldest string without repeating characters is "ABC", its length is 3. Example 2: Input: s = "BBBBB" Output: 1 Explanation: Since the oldest string without repeating characters is "b", its length is 1. Example 3: Input: s = "pwwkew" Output: 3 Explanation: Since the oldest string without repeating characters is "wKE", its length is 3. Note that your answer must be the length of the substring, "pwke" is a subsequence, not a substring. Example 4: Input: s = "" Output: 0Copy the codeBy hint:
-
0 <= s.length <= 5 *
-
S consists of letters, digits, symbols, and Spaces
Third, topic analysis
This topic looks relatively simple, but it is easy to be misled if you don’t understand the details of it well.
Detail 1: The difference between substrings and subsequences
Substring: A substring must be a contiguous segment of the string that can be found in the string. For example, ab and BC in the string ABC are substrings.
2. A sequence of characters in the original sequence that may be discontinuous, as in; In the string ABC, ac is a character sequence
Detail 2: The string consists of letters, numbers, symbols, and Spaces
The string does not contain Chinese so that we can use the fourth solution (guess what)
4. Customs clearance method 1: brute force cracking
Solution introduction: Brute force cracking, through a number of cycles to find out the answer. Simple and easy to think of solutions, including the two algorithm problems we brush before, can also be solved by brute force cracking. The disadvantage is that although simple, the efficiency is very low, and it is not the optimal solution.
Compare each character in the string as a loop with the combination of substrings to get the longest string length. For example, if the string ABC is used, character A is compared with substrings A, AB, and ABC in the first round, character B is compared with substrings B, BC in the second round, and so on. Finally, the length of the unique substring is obtained.
Solution code:
/** * Solution 1: Brute force crack **@param s
* @return* /
public static Integer lengthOfLongestSubstring(String s) {
int maxLength = 0;
// Each round is compared with one character and substring. If there are no repeated characters, the maximum length is obtained and the last character position is known
for (int i = 0; i < s.length(); i++) {
for (int j = i + 1; j <= s.length(); j++) {
if(! judgeCharacterExist(i, j, s)) { maxLength = Math.max(maxLength, j - i); }}}return maxLength;
}
/** * determine if there is a duplicate character ** in the substring@param start
* @param end
* @param param
* @return* /
private static Boolean judgeCharacterExist(int start, int end, String param) {
HashSet<Character> hashSet = new HashSet<>();
for (int i = start; i < end; i++) {
if (hashSet.contains(param.charAt(i))) {
return true;
}
hashSet.add(param.charAt(i));
}
return false;
}
Copy the code
Derivation of algorithm time complexity:
According to the code implemented above, as the scale of input problem increases (namely string length programming), the function between the logic to be judged is F (n) = N 3^33. According to the big O notation, it can be deduced that the time complexity of the brute force cracking algorithm is O(n 3^33), a function to the third power. You can imagine how inefficient it is when the input size gets bigger.
Result: There is no problem with executing the code in LeetCode, but there will be a timeout when submitting the code, because 987 cases need to be verified at the time of submitting. Some cases contain so many characters that the execution will timeout. Therefore, this solution is definitely not recommended!
5. Customs clearance method 2: Sliding window method
Sliding window: is an abstract concept in array and string, can be divided into sliding and window two concepts.
Window: represents a range, usually a set of elements in the middle of an index range, a string and an array, from start to end. For example, the string abcd, if the start index is 0 and the end index is 2, the window contains the character ABC.
Slide: This indicates that the window starts and ends and the index can be moved in a certain direction. In the example above, if the start index and the end index are 0 and 2 respectively, when the start index and end index are moved one bit to the right, their index values are 1 and 3 respectively. This window contains the character BCD.
Here’s a concrete image to help you visualize the “sliding window” :
After introducing the concept of “sliding Windows”, let’s look at how to solve the problem of the largest string without repeating characters in this way.
Use a HashSet to implement a sliding window that checks for repeated characters. Start index = 0; end index = 0; end index = 0; end index = 0;
The code is as follows:
/** * Solution 2: sliding window **@param s
* @return* /
public static Integer lengthOfLongestSubstring2(String s) {
int maxLength = 0;
/ / pointer to the left
int leftPoint = 0;
/ / right pointer
int rightPoint = 0;
// 用于判断重复的Set集合(窗口)
Set<Character> set = new HashSet<>();
while (leftPoint < s.length() && rightPoint < s.length()) {
if(! set.contains(s.charAt(rightPoint))) {// Store characters in set if there are no duplicate characters and move the right pointer back one bit
set.add(s.charAt(rightPoint++));
maxLength = Math.max(maxLength, rightPoint - leftPoint);
} else {
// If there are duplicate elements, move the left pointer one bit to the right (delete the same character as currently)set.remove(s.charAt(leftPoint++)); }}return maxLength;
}
Copy the code
Derivation of algorithm time complexity:
According to the code implemented above, as the scale of input problem increases (namely, string length programming), the function between the logic to be judged is F (n) = n. According to the big O notation, it can be deduced that the time complexity of the sliding window algorithm is O(n), which greatly improves its efficiency compared with brute force cracking.
Execution Result:
5. Customs Clearance Method 3: Optimization by sliding Window Method (I)
Although the sliding window time complexity is only O(n), if there are repeated characters, the index needs to be moved to start. Therefore, we can consider the idea of “space for time” mentioned by other algorithms before, and establish character and index mapping by using HashMap to avoid manual index moving.
The code is as follows:
/** * Sliding window optimization a **@param s
* @return* /
public static Integer lengthOfLongestSubstring(String s) {
char[] charArray = s.toCharArray();
// Use HashMap to create a mapping of characters and indexes
HashMap<Character, Integer> keyMapping = new HashMap<>();
Integer maxLength = 0;
// start indexing
Integer leftIndex = 0;
for (int i = 0; i < charArray.length; i++) {
if (keyMapping.containsKey(charArray[i])) {
// If there are duplicate data, get the largest index value
leftIndex = Math.max(leftIndex, keyMapping.get(charArray[i]));
}
// Duplicate values are overwritten
keyMapping.put(charArray[i], i + 1);
maxLength = Math.max(maxLength, i - leftIndex + 1);
}
return maxLength;
}
Copy the code
Derivation of algorithm time complexity:
According to the code implemented above, as the scale of input problem increases (namely string length programming), the function between the logic to be judged is F (n) = n. According to big O notation, it can be deduced that the time complexity of the optimization algorithm of the sliding window method is O(n), although the time complexity is the same as that of the previous scheme. However, there is still some improvement in efficiency (when thinking about problems, we should think about whether there are other high-quality solutions and cultivate divergent thinking).
Execution Result:
7. Customs clearance mode 4: Character and ASCII mapping
We should pay attention to the following information: These characters can be represented by ASCII (for example, the ASCII value of character A is 97), then we can suggest the mapping relationship between characters and ASCII, so as to realize the exclusion of duplicate characters.
The code is as follows:
public static Integer lengthOfLongestSubstring(String s) { int[] index = new int[128]; int len = 0; int length = s.length(); for (int i = 0, j = 0; j < length; J ++) {// If there are repeated characters, get the maximum subscript I = math.max (index[s.char (j)], I); Len = math.max (len, j-i + 1); len = math.max (len, j-i + 1); index[s.charAt(j)] = j + 1; } return len; }Copy the code
Derivation of algorithm time complexity:
According to the code implemented above, as the scale of input problem increases (i.e. string length programming), the function between the logic to be judged is F (n) = n. According to the big O notation, it can be deduced that the time complexity of the character-ASCII mapping algorithm is O(n).
Execution Result:
Eight: the use of algorithmic ideas in actual business
1. The sliding window algorithm is often used to solve some problems involving child elements in strings and arrays. Find the maximum length of a string without duplicates.
2. The sliding window algorithm can also be used to optimize the for loop, converting multiple loops into single layer loops to reduce time complexity and improve execution performance.
Nine: Write at the end
One problem, some time do not just tangle with one solution, you can think in many ways through divergent thinking, to find a solution. Divergent thinking is not at the beginning, it needs constant contact and accumulation. Therefore, every brush a question, need to learn to sum up, into their own things.
Time comes to him who waits! If the article if you are helpful, welcome to give me like, attention, favorites (one key three even).