199. Right view of binary trees

Given a binary tree, imagine yourself standing on the right side of it and return the values of the nodes visible from the right side, in order from top to bottom.

Example:

Input: [5, 1, 2, 3, null, null, 4]

Output: [1, 3, 4]

Explanation:

1 <-- / \ 2 3 <-- \ 5 4 <--Copy the code

Method 1: Depth-first search

We do a depth-first search of the tree, and during the search we always visit the right subtree first. So for each layer, the first node that we see at this layer must be the rightmost node. Complexity analysis

class Solution { public List<Integer> rightSideView(TreeNode root) { Map<Integer, Integer> rightmostValueAtDepth = new HashMap<Integer, Integer>(); int max_depth = -1; Stack<TreeNode> nodeStack = new Stack<TreeNode>(); Stack<Integer> depthStack = new Stack<Integer>(); nodeStack.push(root); depthStack.push(0); while (! nodeStack.isEmpty()) { TreeNode node = nodeStack.pop(); int depth = depthStack.pop(); if (node ! = null) {// Maintain the maximum depth of the binary tree max_depth = math. Max (max_depth, depth); // Insert if (! rightmostValueAtDepth.containsKey(depth)) { rightmostValueAtDepth.put(depth, node.val); } nodeStack.push(node.left); nodeStack.push(node.right); depthStack.push(depth + 1); depthStack.push(depth + 1); } } List<Integer> rightView = new ArrayList<Integer>(); for (int depth = 0; depth <= max_depth; depth++) { rightView.add(rightmostValueAtDepth.get(depth)); } return rightView; }}Copy the code

Time complexity: O(n). Depth-first search visits each node at most once, so it is linear.

Space complexity: O(n). In the worst case, the stack contains nodes close to the height of the tree, occupying O(n) space.

Method two: breadth-first search

Train of thought

We can do hierarchical traversal of the binary tree, so for each level, the rightmost node must be the last one to be traversed. The hierarchical traversal of binary trees can be implemented by breadth-first search.

algorithm

A breadth-first search is performed, with the left node being placed before the right, so that we access each layer from left to right. Therefore, by keeping only the last node visited at each depth, we can get the right-most node at each depth after traversing the entire tree. Other than changing the stack to a queue and removing the check before rightMOST_value_at_depth, no other changes were made to the algorithm.

class Solution { public List<Integer> rightSideView(TreeNode root) { Map<Integer, Integer> rightmostValueAtDepth = new HashMap<Integer, Integer>(); int max_depth = -1; Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>(); Queue<Integer> depthQueue = new LinkedList<Integer>(); nodeQueue.add(root); depthQueue.add(0); while (! nodeQueue.isEmpty()) { TreeNode node = nodeQueue.remove(); int depth = depthQueue.remove(); if (node ! = null) {// Maintain the maximum depth of the binary tree max_depth = math. Max (max_depth, depth); / / since the last visit to each layer of the node is the answer, so constantly update corresponding depth information rightmostValueAtDepth. Put (the depth, the node. Val); nodeQueue.add(node.left); nodeQueue.add(node.right); depthQueue.add(depth + 1); depthQueue.add(depth + 1); } } List<Integer> rightView = new ArrayList<Integer>(); for (int depth = 0; depth <= max_depth; depth++) { rightView.add(rightmostValueAtDepth.get(depth)); } return rightView; }}Copy the code

Time complexity: O(n). Each node can enter and exit the queue at most once, so the complexity of breadth-first search is linear.

Space complexity: O(n). Each node is queued at most once, so the queue length is no more than NN, so the space cost here is O(n).

300. Longest increasing subsequence

Given an integer array nums, find the length of the longest strictly increasing subsequence.

A subsequence is a sequence derived from an array that deletes (or does not delete) the elements of the array without changing the order of the rest of the elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

Example 1: input: nums = [10,9,2,5,3,7,101,18] output: 4 explanation: the longest increasing subsequence is [2,3,7,101], so length is 4. Example 2: Input: nums = [0,1,0,3, 3] Output: 4 Example 3: Input: nums = [7,7,7,7,7] Output: 1Copy the code

Method 1: dynamic programming

Ideas and Algorithms

Dp [I]\textit{dp}[I]dp[I] is defined as the length of the longest ascending subsequence ending in the ith digit, considering the first I elements, noting that nums[I]\textit{nums}[I]nums[I] must be selected.

Before calculating dp[I]\textit{dp}[I]dp[I], we have calculated dp[0… I −1]\textit{dp}[0 \ldots i-1]dp[0… I −1]. Then the state transition equation is:

$= \ \ textit {dp} [I] Max (\ textit {dp} [j]) + 1, \ text {of} \, 0 \ leq j < I \ and \ text, {and} \ \ textit {num} [j] < \ textit {num} [I]$

Consider adding a nums[I]\textit{dp}[0 \ldots i-1]dp[0… I −1] to the longest ascending subsequence. As dp[j]\textit{dp}[j]dp[j] dp[j] stands for nums[0… j]\textit{nums}[0 \ldots j]nums[0… j]\textit{nums}[j]nums[j] Therefore, if the state dp[j]\textit{dp}[j]dp[j] dp[j] dp[j] dp[j] dp[j] dp[j] dp[j] dp[j] dp[j] dp[j] dp[j] dp[j] dp[j] Nums [I]\textit{nums}[I]nums[I] can be placed after nums[j]\ Textit {nums}[j]nums[j].

Finally, the longest ascending subsequence of the entire array is the maximum of all dp[I]\textit{dp}[I]dp[I].

$\ text {LIS} _ {\ textit {length}} = \ Max (\ textit {dp} [I]), and \ text {of} \, 0 \ leq I < n$

class Solution{ public int lengthOfLIS(int[] nums){ if(nums.length == 0){ return 0; } int[] dp = new int[nums.length]; dp[0] = 1; int maxans = 1; for(int i = 1; i < nums.length; i++){ dp[i] = 1; for(int j = 0; j <i; j++){ if(nums[i] > nums[j]){ dp[i] = Math.max(dp[i],dp[j]+1); } } maxans = Math.max(maxans,dp[i]); } return maxans; }}Copy the code

Time complexity: O(n2)O(n^2)O(n2), where n is the length of array nums\textit{nums}nums. When calculating state DP [I]dp[I]dp[I], it takes O(n) time to traverse all states of dp[0… I −1]dp[0 \ldots i-1] DP [0… I −1], so the total time complexity is O(n2)O(n^2)O(n2).

Space complexity: O(n), additional DP array of length N is required.

Method two: greedy + binary search

Ideas and Algorithms

Consider a simple greed, if we want the ascending subsequence to be as long as possible, we want the sequence to rise as slowly as possible, so we want the number added to the end of each ascending subsequence to be as small as possible.

Based on the greedy idea above, we maintain an array D [I], which represents the minimum value of the last element of the longest ascending subsequence of length I. We record the length of the longest ascending subsequence by len, starting with len 1 and d[1]=nums[0].

And notice that d[I] is monotonically increasing with respect to I. Because if d[j]≥d[I] and j < I, we consider deleting I − J elements from the end of the longest ascending subsequence of length I, then the length of the sequence becomes J, and the JTH element x (the last element) must be less than d[I], thus less than d[j]. Then we find a longest ascending subsequence of length j, and the final element is smaller than d[j], resulting in a contradiction. So the monotonicity of array D is proved.

We iterate over each element in the nums array and update the values of the arrays D and len. Len = len + 1 if nums[I]>d[len] Otherwise in d [… len] 1 d (1 \ ldots len] find meet the d d [1… len] [I – 1] < nums [j] [I] d < d < \ [I – 1] textit {nums} [j] [I] < d d [I – 1] < nums [j] < d [I] the subscript I, [I] = d and update the nums [j] [I] = d \ textit {nums} [j] [I] = d nums [j].

Based on the monotonicity of the D array, we can use binary search to find the subscript I and optimize the time complexity.

Finally, the whole algorithm flow is as follows:

Let the length of the longest ascending subsequence currently calculated be Len (11 at the beginning), iterate over nums from front to back, and when traversing to NUMS [I] :

If nums[I]>d[len], add to end of dd array and update len=len+1;

Otherwise, binary search in the D array finds the first number d[k] less than nums[I] and updates d[k+1]=nums[I].

Take the input sequence [0,8,4,12,2] as an example:

Insert 0 in the first step, d = [0];

Step 2 insert 8, d = [0, 8];

Step 3 insert 4, d = [0, 4];

Step 4 insert 12, d = [0, 4, 12];

Step 5 insert 2, d = [0, 2, 12]

Finally, the maximum increasing subsequence length is 3.

class Solution{ public int lengthOfLIS(int[] nums){ int len = 1, n = nums.length; if(n == 0){ return 0; } int[] d = new int[n+1]; for(int i = 1; i < n; ++i){ if(nums[i] > d[len]){ d[++len] = nums[i]; }else{ int l = 1, r = len, pos = 0; while(l<=r){ int mid = (l+r)>>1; if(d[mid]<nums[i]){ pos = mid; l = mid + 1; }else{ r = mid - 1; } } d[pos+1] = nums[i]; } } return len; }}Copy the code

Time complexity: O(nlogn). The length of array nums is N. We update array D with the elements in the array in turn, and binary search O(logn) is needed to update array D, so the total time complexity is O(nlogn).

Space complexity: O(n), requires an additional D array of length N.

The two together

You are given two non-empty linked lists representing two non-negative integers. Each digit is stored in reverse order, and only one digit can be stored per node.

You add the two numbers and return a linked list representing the sum in the same form.

You can assume that neither of these numbers will start with 0, except for the number 0.

var addTwoNumbers = function(l1,l2){ let head = null,tail = null; let carry = 0; while(l1||l2){ const n1 = l1? l1.val:0; const n2 = l2? l2.val:0; const sum = n1+n2+carry; if(! head){ head = tail = new ListNode(sum%10); }else{ tail.next = new ListNode(sum%10); tail = tail.next; } carry = Math.floor(sum/10); if(l1){ l1 = l1.next; } if(l2){ l2 = l2.next; } } if(carry > 0){ tail.next = new ListNode(carry); } return head; };Copy the code

Complexity analysis

Time complexity: O(Max (m,n)), where M and n are the lengths of two linked lists respectively. We’re going through all the positions on both lists, and it only takes O(1) time to process each position.

Space complexity: O(1). Note that the returned value does not count space complexity.

151. Flip the words in the string

Given a string s, flip all the words in the string one by one.

A word is a string of non-space characters. Use at least one space in s to separate the words in the string.

Return a string that reverses the order of the words in s and concatenates them with a single space.

Description:

The input string s can contain extra Spaces before, after, or between words. Flipped words should be separated by a single space. The flipped string should not contain additional Spaces.

Example 1: Input: s = "The sky is blue" Output:" Blue is sky the" Example 2: Input: s = "Hello world" Output: "World hello" Explanation: The input string can contain extra Spaces before or after it, but the inverted character cannot. Example 3: Input: s = "a good example" Output: "example good a" Explanation: If there is extra space between two words, reduce the space between the flipped words to only one. Example 4: Input: S = "Bob Loves Alice" Output: "Alice Loves Bob" Example 5: Input: s = "Alice does not even like Bob" Output: "bob like even not does Alice"Copy the code

Method 1: Use language features

Ideas and Algorithms

Many languages provide split, reverse, and join methods for strings, so we can simply call the built-in API to do this:

Use split to split strings into string arrays by Spaces; Reverse reverses an array of strings using reverse; Use the join method to group the number of strings into a single string.

var reverseWords = function(s) {
    return s.trim().split(/\s+/).reverse().join(' ');
};

Copy the code

Complexity analysis

Time complexity: O(N), where N is the length of the input string.

Space complexity: O(N), used to store the result of string splitting.

Method two: write the corresponding function

Ideas and Algorithms

We can also write our own functions without using the API in the language. These functions are implemented differently in different languages. The main difference is that some languages have immutable strings (such as Java and Python) and some languages have mutable strings (such as C++).

For languages where strings are immutable, you first need to convert the string to other mutable data structures, and whitespace must be removed in the conversion process.

public StringBuilder trimSpaces(String s){ int left = 0,right = s.length()-1; While (left <= right && s.charat (left)== "){++left; While (left <= right &&s.charat (right)==' '){--right; } StringBuilder sb = new StringBuilder(); while(left <= right){ char c = s.charAt(left); if(c ! =' '){ sb.append(c); }else if (sb.charAt(sb.length()-1)! =' '){ sb.append(c); } ++left; } return sb; } public void reverse(StringBuilder sb,int left,int right){ while(left < right){ char tmp = sb.charAt(left); sb.setCharAt(left++; sb.charAt(end)! = "); sb.setCharAt(right--,tmp); } } public void reverseEachWord(StringBuilder sb){ int n = sb.length(); int start = 0,end = 0; While (start<n){// To the end of the word while(end <n &&sb.charat (end)! =' '){ ++end; } // reverse(sb,start, end-1); start = end+1; ++end; }}}Copy the code

Complexity analysis

Time complexity: O(N), where N is the length of the input string.

Spatial complexity: the Java and Python methods require O(N) space to store strings, while the C++ methods require only O(1) extra space to store several variables.

Method 3: double-endian queue

Ideas and Algorithms

Since the dual-ended queue supports insertion from the head of the queue, we can process words one by one along the string, then press the words into the head of the queue and turn the queue into a string.

class Solution{ public String reverseWords(String s){ int left = 0,right = s.length()-1; while(left<=right&&s.charAt(left)==' '){ ++left; } while(left <= right&&s.charAt(right==' ')){ --right; } Deque<String> d = new ArrayDeque<String>(); StringBuilder word = new StringBuilder(); while(left <= right){ char c = s.charAt(left); if((word.length()! =0)&&(c==' ')){ d.offerFirst(word.toString()); word.setLength(0); }else if (c! =' '){ word.append(c); } ++left; } d.offerFirst(word.toString()); return String.join(" ",d); }}Copy the code

Complexity analysis

Time complexity: O(N), where N is the length of the input string.

Space complexity: O(N), O(N) space is required to store words in a double-ended queue

8. String conversion to integer (AToi)

According to the description of the problem we judge and describe the corresponding solution method. For this problem, it’s obviously a string conversion problem. It is necessary to define the transformation rules and write corresponding sub-functions according to the transformation rules.

We’re going to do pattern recognition here, and when it comes to integer operations, we need to be careful about overflows. In this case, the step that may cause overflow is push. The multiply by 10 operation and the sum operation may both cause overflow. The handling of an overflow can usually be converted to the inverse of INT_MAX. For example, to determine if a number multiplied by 10 overflows, compare that number with INT_MAX divided by 10.

Method one: automata

Train of thought

String manipulation topics often involve complex processes and conditional situations, and if you go directly to a handwritten program, you can end up with extremely bloated code.

Therefore, in order to methodically analyze the processing of each input character, we can use the concept of automata:

Our program has a state S at each moment, enters a character C from the sequence at a time, and moves to the next state S ‘according to character C. So, all we need to do is create a table that maps from S and C to S prime for all the cases and we can solve the problem in the problem.

class Solution{ public int myAuto(String str){ Automaton automaton = new Automaton(); int length = str.length(); for(int i = 0; i<length; ++i){ automaton.get(str.charAt(i)); } return (int)(automaton.sign*automaton.ans); } } class Automaton{ public int sign = 1; public long ans = 0; private String state = "start": private Map<String,String[]>table = new HashMap<String,String[]>(){{ put("start", new String[]{"start", "signed", "in_number", "end"}); put("signed", new String[]{"end", "end", "in_number", "end"}); put("in_number", new String[]{"end", "end", "in_number", "end"}); put("end", new String[]{"end", "end", "end", "end"}); }}; public void get(char c){ state = table.get(state)[get_col(c)]; if("in_number".equals(State)){ ans = ans*10+c-'0'; ans = sign == 1? Math.min(ans, (long)Integer.MAX_VALUE):Math.min(ans,-(long)Integer.MIN_VALUE); }else if ("signed".equals(state)){ sign = c =='+'? 1:1; } } private int get_col(char c){ if(c == ' '){ return 0; } if(c=='+'||c=='-'){ return 1; } if(Character.isDigit(c)){ return 2; } return 3; }}Copy the code

Complexity analysis

Time complexity: O(n), where nn is the length of the string. We just need to process all the characters in turn, each character taking O(1) time to process.

Space complexity: O(1), the state of the automaton requires only constant space storage.