Daily question | fear dominated by reverse linked list

Some time ago, I saw that the Nuggets platform launched the daily algorithm punch in activity , It feels good , What a coincidence to open LeetCode My daily question is Reverse a linked list , This algorithm problem that failed in the interview at the beginning of last year , Take this opportunity to retrieve the memory of the previous algorithm .

Date: 2021-03-21 Week12

1、 Reverse a linked list II

• difficulty ：Medium

Title Description

Give you the head pointer of the single linked list head And two integers left and right , among left <= right . Please reverse from position left To the position right The linked list node of , return Inverted 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]

Problem solving ideas and Implementation

Linked list , Subconsciously, I don't want to use the pointer , Write and draw on paper for a long time , It may not be right yet .

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

The second iteration starts from the starting node , With the stack push All nodes that need to be reversed , Until you find the node on the right that doesn't need to be reversed , This node is recorded as the right boundary node .

The last iteration , Put all nodes in the stack in order pop Then connect first , Just go back .

By way of example 1 For example ,1 Is the left boundary node ,5 Is the right boundary node , Stack in turn [2,3,4], Then pop up one by one and connect , The output [1,4,3,2,5].

This problem is sorted back and forth 2 It took hours to write , The key points are 2：

• 1、 The boundary problem , How to right and left 2 Record the boundaries accurately ;
• 2、 Under normal circumstances ,head Should still be the first Node unchanged ; But if the left boundary is null, That is, the first element is the node to be reversed , So back head It should be on the right boundary Node.

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;

        // 1、 Find the first node to reverse , And point to  currNode
        while (curr < left) {
            curr++;
            leftNode = currNode;
            if (currNode == null)
                break;
            else
                currNode = currNode.next;
        }

        //  At this time  leftNode  Is the node of the left boundary , Keep still 

        ListNode rightNode = currNode.next;

        // 2、 Find the last node to reverse , And point to  currNode
        while (curr <= right) {
            curr++;
            stack.push(currNode);
            currNode = rightNode;
            if (rightNode == null)
                break;
            else
                rightNode = rightNode.next;
        }
        //  At this time  curr  Is the node of the right boundary 
        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;
    }
}

2、 Design the parking system

• difficulty ：Easy

Title Description

Please design a parking system for a parking lot . There are three different sizes of parking spaces in the parking lot ： Big , Zhonghe small , Each size has a fixed number of parking spaces .

Please realize ParkingSystem class ：

ParkingSystem(int big, int medium, int small) initialization ParkingSystem class , The three parameters correspond to the number of parking spaces of each type respectively . bool addCar(int carType) Check if there is carType The corresponding parking space . carType There are three types ： Big , in , Small , Separate numbers 1, 2 and 3 Express . A car can only park at carType In the parking space of the corresponding size . If there are no empty parking spaces , Please return false , Otherwise, park the car in the parking space and return to true .

Problem solving ideas and Implementation

The difficulty of this problem is not even enough to warm up , I even suspect that this is leetcode There is no one in the simplest algorithm problem ,2 Minutes out , 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;
    }
}

2.1、 Reverse a linked list

• difficulty ：Easy

Title Description

Invert a single chain table .

Example :
Input : 1->2->3->4->5->NULL
Output : 5->4->3->2->1->NULL

Problem solving ideas and Implementation

The classic problem of reversing the linked list , Do not touch for a long time , If you don't draw a picture for sorting, you still can't do it , There is only one idea to overcome this type of problem for the time being ： dedicated , I know you by hand .

public ListNode reverseList(ListNode head) {
    if (head == null) return head;

    //  Here we still use the familiar pointer to solve 
    ListNode curr = head;       //  The pointer  curr  Represents the position to be reversed 

    while (curr.next != null) {
        ListNode after = curr.next;  //  The pointer  after  It's a place holder , Used to temporarily store the next location 

        //  Invert the current node 
        curr.next = after.next;
        after.next = head;
        head = after;
    }
    return head;
}

3、 Evaluate the inverse Polish expression

• difficulty ：Medium

Title Description

According to the reverse Polish notation , Find the value of the expression .

Valid operators include +、-、*、/ . Each operand can be an integer , It can also be another inverse Polish expression .

explain ： Integer division keeps only the integer part . Given an inverse Polish expression is always valid . let me put it another way , The expression always yields a valid number and does not have a divisor of 0 The situation of .

Example 1：

Input ：tokens = [“2”,“1”,"+",“3”,"*"]
Output ：9
explain ： This formula is transformed into a common infix arithmetic expression as ：((2 + 1) * 3) = 9

Example 2：

Input ：tokens = [“4”,“13”,“5”,"/","+"]
Output ：6
explain ： This formula is transformed into a common infix arithmetic expression as ：(4 + (13 / 5)) = 6

Reverse Polish notation ：

The inverse Polish expression is a suffix expression , The so-called suffix means that the operator is written after .

The usual formula is a infix expression , Such as ( 1 + 2 ) * ( 3 + 4 ) . The inverse Polish expression of the formula is written as ( ( 1 2 + ) ( 3 4 + ) * ) . The inverse Polish expression has two main advantages ：

There is no ambiguity in the expression after removing the brackets , Even if the above formula is written as 1 2 + 3 4 + * You can also calculate the correct result according to the order . It is suitable for stack operation ： When it comes to numbers, it's on the stack ; When you encounter an operator, you take out two numbers at the top of the stack to calculate , And push the results into the stack .

Problem solving ideas and Implementation

I haven't finished reading the title yet , Just one sentence in the title It is suitable for stack operation I was shocked , Good guy is like giving the answer directly , I feel that the difficulty of the problem instantly decreases to a 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 {
                //  Numbers , Direct stack 
                stack.push(Integer.valueOf(elem));
            }
        }
        return stack.pop();
    }
}

4、 Matrix zeroing

• difficulty ：Medium

Title Description

Given a m x n Matrix , If an element is 0 , Set all elements of the row and column to 0 . Please use in-place algorithm .

Advanced ：

An intuitive solution is to use O(mn) Extra space , But it's not a good solution .
A simple improvement is to use O(m + n) Extra space , But it's still not the best solution .
Can you come up with a solution that only uses constant space ？

Problem solving ideas and Implementation

in-place algorithm Is to directly update the array of input parameters , Then return , This is in Android It's also common in （ For example. Rect class ）.

Ideas 1, Directly copy an array in place for recording , The complexity of time and space is O(mn).

Ideas 2, We can use two tag arrays to record whether there are zeros in each row and column .

In particular , We first traverse the array once , If an element is 0, Then set the position of the tag array corresponding to the row and column where the element is located to true. Finally, we iterate over the array again , Update 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;
                }
            }
        }
    }
}

The official solution below gives the space complexity of O(1) The plan , I looked at , And ideas 2 almost , But for recording 2 individual 1 Is an array , By using the matrix[0][] and matrix[][0] To record , Finally, restore , But the readability of the code is not good , Generally, there is no need to be so stingy in the actual combat application of the client , Just ignore , Interested readers can study .

Reference resources & thank

Most of the content of the article is excerpted from LeetCode, Example ：

• https://leetcode-cn.com/problems/reverse-linked-list-ii/
• https://leetcode-cn.com/problems/design-parking-system/
• https://leetcode-cn.com/problems/reverse-linked-list/
• https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/
• https://leetcode-cn.com/problems/set-matrix-zeroes/solution/ju-zhen-zhi-ling-by-leetcode-solution-9ll7/

About me

Hello, I am a But smell the plum , If you think the article is valuable to you , welcome ️, You are welcome to pay attention to my Blog perhaps GitHub.

If you think the article is not good enough , Please also go through Focus on Urge me to write better articles —— In case I improve one day ？

• my Android The learning system
• About article correction
• About knowledge payment
• About 《 reflection 》 series