06 2021 03

This week’s 5 leetcodes are:

  • 221 Maximum square
  • 208 Implements the prefix tree
  • 720 The longest word in the dictionary
  • 207 the curriculum
  • 389 to find different

221 Maximum square

Topic describes

In a two-dimensional matrix of ‘0’ and ‘1’, find the largest square containing only ‘1’ and return its area.

  • Example 1

Input: matrix = [[" 1 ", "0", "1", "0" and "0"], [" 1 ", "0", "1", "1", "1"], [" 1 ", "1", "1", "1", "1"], [" 1 ", "0", "0", "1", "0"]] output: 4Copy the code

Source: LeetCode link: leetcode-cn.com/problems/ma… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Solution 1 dynamic programming

Use dp[I][j] to represent the maximum side length of the square that can be formed in the lower right corner of row I and column J.

So if matrix[I][j] is ‘0’, no square can be formed at this time, dp[I][j] = 0.

If matrix[I][j] is ‘1’, then the smallest square is itself with side length of 1. If the square is to be enlarged, then matrix[I][J-1],matrix[i-1][j],matrix[i-1][J-1],matrix[i-1][J-1] must be able to form a square. And the length that can be increased must be the minimum of the length that can be formed by each of the three positions (only by taking the minimum length of the side can we ensure that the vertical and horizontal sides are equal in length). So at this point, we have;


d p [ i ] [ j ] = 1 + m i n ( d p [ i – 1 ] [ j ] . d p [ i ] [ j – 1 ] . d p [ i – 1 ] [ j – 1 ] ) dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

In fact, we only need to operate on the ‘1’ position. Also pay attention to the boundary judgment, prevent the boundary, 0 row and 0 column, dp[I][j] does not exceed the maximum of 1.

// Dynamic programming
public int maximalSquare(char[][] matrix) {
    int[][] dp = new int[matrix.length][matrix[0].length];
    // Maximum side length
    int maxSideLength = 0;
    for(int i = 0; i < matrix.length; ++i){
        for(int j = 0; j < matrix[0].length; ++j){
            if(matrix[i][j] == '1'){
                dp[i][j] = 1;
                // The length of the edge cannot be increased
                dp[i][j] += (i == 0 || j == 0)?0 : min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j]);
                // Update the maximum edge lengthmaxSideLength = Math.max(maxSideLength,dp[i][j]); }}}// return area
    return maxSideLength*maxSideLength;
}

// The minimum value of three numbers
public int min(int a, int b, int c){
    return Math.min(Math.min(a,b),c);
}
Copy the code


208 Implements the prefix tree

Topic describes

A Trie (pronounced like “try”) or prefix tree is a tree data structure for efficiently storing and retrieving keys in a string data set. This data structure has a number of applications, such as auto-completion and spell checking.

Please implement Trie class:

Trie() initializes the prefix tree object. Void insert(String word) Inserts the String word into the prefix tree. Boolean search(String word) Returns true if the String word is in the prefix tree (that is, inserted before retrieval); Otherwise, return false. Boolean startsWith(String prefix) Returns true if one of the prefixes of the previously inserted String word is prefix; Otherwise, return false.Copy the code
  • Example:
Input [" Trie ", "insert", "search", "search", "startsWith", "insert", "search"] [[], [" apple "], [" apple "], [] "app", ["app"], ["app"]] [NULL, null, true, false, true, null, true] trie.insert("apple"); trie.search("apple"); // Return True trie.search("app"); // Return False trie.startswith ("app"); // Return True trie.insert("app"); trie.search("app"); / / return TrueCopy the code

Source: LeetCode link: leetcode-cn.com/problems/im… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

implementation

A prefix tree node can contain the following attributes:

  • The set of characters stored by the current nodeHashMapOr an array
  • Whether the current node is the end node of a string: yesboolean isEndsaid
  • The value of the string terminating at the current node: usedvaluesaid

Prefix tree nodes are defined as follows:

// Prefix tree node
public class TrieNode {
    public HashMap<Character,TrieNode> children;
    public boolean isEnd;
    public String value;

    public TrieNode(a){
        this.children = new HashMap<>();
        this.isEnd = false;
        this.value = null; }}Copy the code

When inserting the string INSERT into the prefix tree, check to see if the character is included in the character set of the current node.

  • If it does, the current node points to the next node of the string
  • If not, the node is inserted into the character set of the current node, pointing to the next node

The same logic applies to search and startsWith.

// Prefix tree implementation
public class Trie {
    private TrieNode root;

    public Trie(a) {
        this.root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode cur = this.root;
        for(char c : word.toCharArray()){
            if(! cur.children.containsKey(c)) { cur.children.put(c,new TrieNode());
            }
            cur = cur.children.get(c);
        }
        cur.isEnd = true;
        cur.value = word;
    }

    public boolean search(String word) {
        TrieNode cur = this.root;
        for(char c : word.toCharArray()){
            if(! cur.children.containsKey(c)){return false;
            }
            cur = cur.children.get(c);
        }
        return cur.isEnd;
    }

    public boolean startsWith(String prefix) {
        TrieNode cur = this.root;
        for(char c : prefix.toCharArray()){
            if(! cur.children.containsKey(c)){return false;
            }
            cur = cur.children.get(c);
        }
        return true; }}Copy the code

Note that startsWith returns true directly, while search returns isEnd because the presence of a prefix for a string does not count as its presence in the prefix tree. The prefix is considered to exist in the prefix tree only after it is inserted using the INSERT method.


720 The longest word in the dictionary

Topic describes

Gives an English dictionary consisting of an array of strings words. Find the longest word that is made up of other words in the words dictionary by adding one letter step by step. If there are more than one possible answer, return the word with the smallest lexicographic order in the answer.

If there is no answer, an empty string is returned.

  • Example 1:
Input: words = [" w ", "send", "wor", "worl", "world"] output: "world" explanation: the words "world" by "w", "send", "wor", and "worl" add a letters.Copy the code
  • Example 2:
Input: words = [" A ", "banana", "app", "appl", "AP ", "apply", "apple"] Output: "apple" Explanation: both "apply" and "apple" can be composed of words from the dictionary. But "apple" has less lexicographical order than "apply".Copy the code

Source: LeetCode link: leetcode-cn.com/problems/lo… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Solution a dictionary tree (prefix tree)

First build a prefix tree from the given array of strings,

for(String word : words){
    this.insert(word);
}
Copy the code

We then iterate through the words array to determine whether the current word meets the requirement in the dictionary tree.

If a word (for example,apple) meets the criteria, then all prefixes (a, AP,app,appl,apple) must exist in the dictionary tree.

Initialize the result string result = “”, for a string, if it is likely to be the longest word, the dictionary tree is traversed, otherwise directly traversed the next word, determine whether possible conditions encapsulated as follows:

/ * * *@paramWord The string * currently traversed@paramResult Current result string */
private boolean potentialLongestWord(String word,String result){
    return word.length() > result.length() || word.length() == result.length() && word.compareTo(result) < 0;
}
Copy the code

If isEnd of the current character is false, the prefix ending with the character does not exist, and the next character string is traversed directly. If isEnd is true, a node is continued.

The complete code is as follows:

public class Trie{
    / /... Omit other methods
    
    // Find the longest word
    public String longestWord(String[] words){
        if(words == null || words.length == 0) {return null;
        }
        // Build the dictionary tree
        for(String word : words){
            this.insert(word);
        }
        String result = "";
        for(String word : words){
            TrieNode cur = this.root;
            // The longest word if possible
            if(potentialLongestWord(word,result)){
                boolean isWord = true;
                for(char ch : word.toCharArray()){
                    cur = cur.children.get(ch);
                    if(! cur.isEnd){ isWord =false;
                        break; }}if(isWord){ result = word; }}}return result;
    }

    private boolean potentialLongestWord(String word,String result){
        return word.length() > result.length() || word.length() == result.length() && word.compareTo(result) < 0; }}Copy the code


207 the curriculum

Topic describes

You must take numCourses this semester, marked 0 to numcourses-1.

Some prerequisite courses are required before you can take certain courses. Prerequisites Prerequisites Prerequisites for system system system 2005: System system for System System 2005: System system for System System 2005: System system for System System 2005: System system for System System 2005: System system for system System 2005

For example, advanced Placement for [0, 1] means: In order to take course 0, you need to complete Course 1.

Would you please judge whether it is possible to complete all the courses? If so, return true; Otherwise, return false.

  • Example 1:
Input: numCourses = 2, resident = [[1,0]] output: true Before you can study course 1, you need to complete course 0. It's possible.Copy the code
  • Example 2:
Input: numCourses = 2, prerequisites = [[1,0],[0,1]] You need to complete Course 0 before taking course 1; And you should also complete course 1 before taking course 0. It's impossible.Copy the code

Source: LeetCode link: leetcode-cn.com/problems/co… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Solution number one to determine if there is a ring

The given course and the preceding course are constructed into a graph, which is represented by an adjacency matrix. The number of nodes in the graph is the number of lessons to learn.

If there is a loop in the figure, it indicates that there is a cyclic dependence between courses, and all courses cannot be completed at this time.

We can use DFS depth-first search to determine if there are rings in a graph. Details are as follows:

Define an access array visited to represent the state of a node. 0 indicates that the node is not visited, 1 indicates that there is a ring from this node, and 2 indicates that there is no ring from this node.

For a node node, first set visited[node] to 1, indicating that the node is visited and assume that there is a ring, and then obtain its successor node. If there is no ring in the recursion process of successor nodes, it means that there is no ring in traversing from node.

The recursive function isLoopFrom is defined as follows:

// recursive function, starting from node node traversal, whether there is a loop
public boolean isLoopFrom(int node, int[] visited, List<List<Integer>> adjacency){
    if(visited[node] == 1) {return true;
    }
    if(visited[node] == 2) {return false;
    }
    visited[node] = 1; // Is accessed, and is assumed to have a ring
    for(int suc : adjacency.get(node)){
        // Recursively search each successor to see if there is a ring
        if(isLoopFrom(suc,visited,adjacency)){
            return true; }}// There is no successor or there is no ring in the successor
    visited[node] = 2;
    return false;
}
Copy the code

IsLoopFrom is called for each course, and if there is a loop in one course, all courses cannot be completed.

// DFS depth-first search
public boolean canFinish(int numCourses, int[][] prerequisites) {
    List<List<Integer>> adjacency = buildGraph(numCourses,prerequisites);
    int[] visited = new int[numCourses];
    for(int i = 0; i < numCourses; ++i){
        if(isLoopFrom(i,visited,adjacency)){
            return false; }}return true;
}

// Construct the adjacency matrix of the graph
public List<List<Integer>> buildGraph(int numCourses,int[][] prerequisites){
    List<List<Integer>> adjacency = new ArrayList<>();
    for(int i = 0; i < numCourses; ++i){
        adjacency.add(new ArrayList<>());
    }
    // initialize adjacency list
    for(int[] arr : prerequisites){
        adjacency.get(arr[1]).add(arr[0]);
    }
    return adjacency;
}
Copy the code

Solution two topological sort

The idea of topological sorting is to extract one node of zero degree of entry from the graph at a time until all nodes in the graph have been removed. If you have multiple nodes with zero degree of entry, their order doesn’t matter.

Define an inDegrees[I] array to represent the entry of node I. Use queues to store all nodes with a current entry of 0.

Traverse the queue, take out the node with the input degree of 0, and reduce the number of courses by 1. Decrement the input degree of its successor node by 1. If the successor node becomes 0 after decrement by 1, it joins the queue.

If there are rings in a graph, it means that the subgraph formed by this ring never has a node with an entry degree of 0. Therefore, when the final queue is empty, the number of courses is not 0, which means that the learning of courses cannot be completed. If the queue is empty, the number of courses is also 0, indicating that learning can be completed.

// Topological sort
public boolean canFinish(int numCourses, int[][] prerequisites) {
    List<List<Integer>> adjacency = new ArrayList<>();
    int[] inDegrees = new int[numCourses];
    Queue<Integer> queue = new LinkedList<>();
    for(int i = 0; i < numCourses; ++i){
        adjacency.add(new ArrayList<>());
    }
    for(int[] arr : prerequisites){
        inDegrees[arr[0]] + +; adjacency.get(arr[1]).add(arr[0]);
    }

    // Queue all nodes with an input degree of 0
    for(int i = 0; i < inDegrees.length; i++){
        if(inDegrees[i] == 0){ queue.offer(i); }}while(! queue.isEmpty()){// If the input degree is 0, the node exits the queue
        int zeroDegree = queue.poll();
        numCourses--;
        // The entry degree of the successor node decreases by 1. If it becomes 0, the successor node is enqueued
        for(int cur : adjacency.get(zeroDegree)){
            inDegrees[cur]--;
            if(inDegrees[cur] == 0){ queue.add(cur); }}}return numCourses == 0;
}
Copy the code


389 to find different

Topic describes

Given two strings s and t, they contain only lowercase letters.

The string t is randomly rearranged by the string S, and a letter is added at the random position.

Please find the letter added to t.

  • Example 1:
Input: s = "abcd", t = "abcde" Output: "e" Explanation: 'e' is the letter being added.Copy the code
  • Example 2:
Input: s = "", t = "y"Copy the code
  • Example 3:
Input: s = "a", t = "aa" output: "a"Copy the code
  • Example 4:
Input: s = "ae", t = "aea"Copy the code

Source: LeetCode link: leetcode-cn.com/problems/fi… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Solution a counting method

Since it contains only lowercase letters, you can have an array of length 26, with subscripts corresponding to characters and array values representing the number of occurrences of characters.

Traversing s, the number of occurrences of the character +1, traversing T, the number of occurrences of the character -1. There must be one and only one position in the array of degree -1, and that position represents the character we are looking for.

The character ch and index index correspond to index = ch – ‘a’.

// Solution - counting method
public char findTheDifference(String s, String t) {
    int[] table = new int[26];
    for(char ch : s.toCharArray()){
        table[ch - 'a'] + +; }for(char ch : t.toCharArray()){
        table[ch - 'a']--;
    }
    // O(1)
    for(int i = 0; i < 26; i++){
        if(table[i] < 0) {return (char) (i + 'a'); }}return 'a';
}
Copy the code

Note that the space consumption of this method is constant (no matter how s and t change, only the array space of length 26 is required) and the space complexity is O(1). Likewise, the third loop is O(1).

Solution two addition and subtraction

The idea is similar to the counting method, also use ch – ‘a’ to convert characters into integers, add and subtract, the characters in T are added first, and then the characters in S are subtracted, so that at the same time appear in S, the characters in T will cancel out, and the last integer is the corresponding to the required characters.

It’s important to note that adding the t traversal and subtracting the S traversal ensures that the final integer is positive. If you add s first and then subtract T, and the final integer is negative, you need to take the absolute value before converting it to a character.

// Add and subtract
public char findTheDifference(String s, String t) {
    int sum = 0;
    for(char ch : t.toCharArray()){
        sum += ch - 'a';
    }
    for(char ch : s.toCharArray()){
        sum -= ch - 'a';
    }
    return (char) ('a' + sum);
}
Copy the code