Some time ago, I saw that the Nuggets platform launched a daily algorithm clocking activity, which felt quite good. It happened that the daily problem opened by LeetCode happened to be reverse linked list, which was the algorithm problem that bytedance failed in the interview at the beginning of last year, so I took this opportunity to retrieve the memory of the previous algorithm.

Date: 2021-03-21 Week12

1. Reverse linked list II

  • Difficulty:Medium

Topic describes

Give you the head pointer to the singly linked list head and two integers left and right, where left <= right. Reverse the list node from position left to position right to return the reversed list.

Example 1 Input: head = [1,2,3,4,5], left = 2, right = 4 Output: [1,4,3,2,5]

Example 2 Input: head = [5], left = 1, right = 1 Output: [5]

Solution and implementation

Linked list of this kind of problem, is subconsciously do not want to use Pointers, writing on paper and drawing for a long time, may not be able to write correctly.

The simplest way is to use the stack. The idea is very simple. In the first iteration, the next node on the left to be reversed is found, and this node is recorded as the left boundary node.

The second iteration starts from the starting node and pushes all nodes that need to be reversed by the stack until the node on the right that does not need to be reversed is found and recorded as the right boundary node.

For the last iteration, pop all the nodes in the stack and join them first, then return.

Take example 1, where 1 is the left boundary node and 5 is the right boundary node. [2,3,4] are stored in the stack in turn, and then are popped up and connected in turn, that is, output [1,4,3,2,5].

It took 2 hours to write this question back and forth. The key points are 2:

  • 1. Boundary problem, how to accurately record the left and right boundaries;
  • 2. Under normal circumstances,headI think it’s the first oneNodeThe same; But if the left boundary is zeronull, that is, the first element is the node to be reversedheadIt should be on the rightNode.
class Solution { public ListNode reverseBetween(ListNode head, int left, int right) { Stack<ListNode> stack = new Stack<>(); int curr = 1; ListNode leftNode = null; ListNode currNode = head; While (curr < left) {curr++; leftNode = currNode; if (currNode == null) break; else currNode = currNode.next; } // The leftNode is the left edge of the node, leave the ListNode rightNode = currNode.next; While (curr <= right) {curr++; stack.push(currNode); currNode = rightNode; if (rightNode == null) break; else rightNode = rightNode.next; } ListNode start = leftNode == null? null : head; while (! stack.isEmpty()) { ListNode node = stack.pop(); if (leftNode == null) { leftNode = node; start = leftNode; } else { leftNode.next = node; leftNode = leftNode.next; } } leftNode.next = currNode; return start; }}Copy the code

2. Design the parking system

  • Difficulty:Easy

Topic describes

Please design a parking system for a parking lot. There are three different sizes of parking Spaces: large, small and medium, with a fixed number of Spaces for each size.

Implement the ParkingSystem class:

ParkingSystem(int big, int medium, int small) initializes the ParkingSystem class with three parameters corresponding to the number of each parking space. Bool addCar(int carType) Checks whether there is a parking space corresponding to carType. Cartypes come in three types: large, medium, and small, denoted by the numbers 1, 2, and 3, respectively. A car can only park in the parking space corresponding to the carType. Return false if there is no empty parking space, otherwise park the car in the parking space and return true.

Solution and implementation

The difficulty of this problem is not enough to warm up, I even doubt that this is one of leetcode’s simplest algorithm problems. It will be completed in 2 minutes, and by the way, review the reverse linked list.

class ParkingSystem {

    private int[] arr;

    public ParkingSystem(int big, int medium, int small) {
        this.arr = new int[]{big, medium,small};
    }

    public boolean addCar(int carType) {
        if (this.arr[carType - 1] > 0) {
            this.arr[carType - 1] = this.arr[carType -1] -1;
            return true;
        }
        return false;
    }
}
Copy the code

2.1 reverse linked lists

  • Difficulty:Easy

Topic describes

Reverse a single linked list.

Example: input: 1 – > 2 – > 3 – > 4 – > 5 – > NULL output: 5 – > 4 – > 3 – > 1 – > 2 – > NULL

Solution and implementation

Reverse the classic list problem, do not contact for a long time, do not draw a picture to sort out still can not do, to overcome this kind of problem type of thinking for the time being only one: no other, but hand familiar.

public ListNode reverseList(ListNode head) { if (head == null) return head; ListNode curr = head; ListNode curr = head; // the pointer curr represents the position to be reversed. = null) { ListNode after = curr.next; Curr. Next = after. Next; curr. after.next = head; head = after; } return head; }Copy the code

3, inverse Polish expression evaluation

  • Difficulty:Medium

Topic describes

Evaluate the expression according to the inverse Polish notation.

Valid operators include +, -, *, and /. Each operand can be an integer or another inverse Polish expression.

Note: Integer division retains only integer parts. Given the inverse Polish expression is always valid. In other words, the expression always yields a valid value and never has a divisor of 0.

Example 1:

Input: tokens = [” 2 “, “1”, “+”, “3”, “*”] output: 9: the formula into common infix arithmetic expression is: ((2 + 1) * 3) = 9

Example 2:

Input: tokens = “4”, “13”, “5”, “/”, “+”] output: 6: this formula into common infix arithmetic expression is: (4 +) = 6 (13/5)

Inverse Polish expression:

An inverse Polish expression is an expression with a suffix, which means the operator is written after it.

The usual formula is an infix expression, such as (1 + 2) * (3 + 4). The inverse Polish expression of the formula is (1 2 +) (3 4 +) *). The inverse Polish expression has two main advantages:

After removing the parentheses, the expression has no ambiguity. Even if the above formula is written as 1, 2 + 3, 4 + *, the correct result can be calculated according to the order. Suitable for stack operation: the number is pushed into the stack; When encountering an operator, the top two numbers on the stack are calculated and the result is pushed onto the stack.

Solution and implementation

Before I finished reading the topic, I was shocked by the sentence suitable for stack operation operation in the topic stem. Good guy equals to directly give the answer, and I feel that the difficulty of the topic suddenly dropped to simple difficulty.

class Solution { public int evalRPN(String[] tokens) { Stack<Integer> stack = new Stack<>(); for (int index = 0; index < tokens.length; index++) { String elem = tokens[index]; if (elem.equals("+")) { int num1 = stack.pop(); int num2 = stack.pop(); stack.push(num2 + num1); } else if (elem.equals("-")) { int num1 = stack.pop(); int num2 = stack.pop(); stack.push(num2 - num1); } else if (elem.equals("*")) { int num1 = stack.pop(); int num2 = stack.pop(); stack.push(num2 * num1); } else if (elem.equals("/")) { int num1 = stack.pop(); int num2 = stack.pop(); stack.push( num2 / num1); } else {// number directly to stack.push(integer.valueof (elem)); } } return stack.pop(); }}Copy the code

4. Set the matrix to zero

  • Difficulty:Medium

Topic describes

Given an m x n matrix, if one element is 0, set all elements in its row and column to 0. Please use the in place algorithm.

Advanced:

An intuitive solution would be to use O(MN) extra space, but this is not a good solution. A simple improvement would be to use O(m + N) extra space, but this is still not the best solution. Can you come up with a solution that only uses constant space?

Solution and implementation

The in-place algorithm, which simply updates the input array and returns it, is also common in Android (such as the Rect class).

Idea 1: Directly copy an array in place for recording, time and space complexity is O(MN).

Idea 2: We can use two tag arrays to record whether zeros are present in each row and column, respectively.

Specifically, we first iterate through the array once, and if an element is 0, set the position of the tag array corresponding to that element’s row and column to true. Finally, we iterate through the array again, updating the original array with the tag array.

class Solution {
    public void setZeroes(int[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;

        boolean[] rowArray = new boolean[row];
        boolean[] colArray = new boolean[col];

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] == 0) {
                    rowArray[i] = true;
                    colArray[j] = true;
                }
            }
        }

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (rowArray[i] || colArray[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}
Copy the code

The space complexity of O(1) is similar to that of idea 2, but the two ones used for recording are arrays. Matrix [0][] and matrix[][0] in the input parameter are used to record, and finally restored. However, the code readability is not good, and generally there is no need to be so mean in the actual application of the client. I’m going to ignore it for those of you who are interested.

Reference & Thanks

Most of the text is excerpted from LeetCode.

  • Leetcode-cn.com/problems/re…
  • Leetcode-cn.com/problems/de…
  • Leetcode-cn.com/problems/re…
  • Leetcode-cn.com/problems/ev…
  • Leetcode-cn.com/problems/se…

About me

If you think this article is valuable to you, welcome to ❤️, and also welcome to follow my blog or GitHub.

If you feel that the article is not enough, please also urge me to write a better article by paying attention to it — in case I make progress one day?

  • My Android learning system
  • About the article error correction
  • About paying for knowledge
  • About the Reflections series