Attention

At the end of autumn college entrance examination, I summarized the algorithm questions in the posts about written examination on Niuke and WanAndroid, and wrote this series of articles combined with previous examination questions. All articles were checked and tested with LeetCode. Welcome to eat

This article will cover “binary” + “bit operation” and Lru interview algorithm questions, I will give:

Interview Questions
The idea of how to solve this problem
Tips and considerations for specific problems
Examine the knowledge points and concepts
Detailed code andparsing

Before we begin, let’s take a look at some of the highlights:

For your convenience, I’m here`GitHub`A warehouse was set up

Warehouse address: Super dry goods! Carefully summarized video, classification, summary, you pass by the old iron support! For a Star!

Let’s get started now!

matrix

Spiral matrix

Given a matrix containing m x n elements, (m rows, n columns), return all elements in the matrix in spiral order.
Example:

Input: [[1, 2, 3, 4], [5, 6, 7, 8], [9,10,11,12]] output:,2,3,4,8,12,11,10,9,5,6,7 [1]Copy the code

Their thinking

We define the KTH layer of the matrix to be all vertices k away from the nearest boundary. For example, the outermost elements of the matrix below areLevel 1Both of the lower outer elementsLayer 2, and then theLayer 3.

[[1, 1, 1, 1, 1, 1].[1, 2, 2, 2, 2, 1].[1, 2, 3, 3, 3, 2, 1].[1, 2, 2, 2, 2, 1].[1, 1, 1, 1, 1, 1, 1]]
Copy the code

For each layer, we traverse all elements in clockwise order starting from the upper left, assuming that the upper-left coordinate of the current layer isThe lower right corner coordinates are.

First, iterate over all the elements above(r1, c)According to thec = c1,... ,c2The order.
And then iterate over all the elements on the right(r, c2)According to ther = r1+1,... ,r2The order.
If this layer has four sides (i.er1 < r2andc1 < c2), we iterate over the elements below and the elements to the left as shown below.

public List<Integer> spiralOrder(int[][] matrix) {
    ArrayList<Integer> rst = new ArrayList<Integer>();
    if(matrix == null || matrix.length == 0) {
        return rst;
    }
    
    int rows = matrix.length;
    int cols = matrix[0].length;
    int count = 0;
    while(count * 2 < rows && count * 2 < cols){
        for (int i = count; i < cols - count; i++) {
            rst.add(matrix[count][i]);
        }
        
        for (int i = count + 1; i < rows - count; i++) {
            rst.add(matrix[i][cols - count - 1]);
        }
        
        if (rows - 2 * count == 1 || cols - 2 * count == 1) { // If there is only 1 row or 1 column left
            break;
        }
            
        for (int i = cols - count - 2; i >= count; i--) {
            rst.add(matrix[rows - count - 1][i]);
        }
            
        for (int i = rows - count - 2; i >= count + 1; i--) {
            rst.add(matrix[i][count]);
        }
        
        count++;
    }
    return rst;
}
Copy the code

Determine whether sudoku is legal

Please determine if a sudoku is valid. The sudoku may only be partially filled with numbers, and the missing numbers are represented by.
Maintains a HashSet to remember if the same number exists in the same row, column, or grid

Example:

Input: [[" 8 ", "3", ""," ", "7", ""," ", ""," "], [" 6 ", ""," ", "1", "9", "5", ""," ", ""], [".", "9", "eight" and ". ", ""," ", ""," 6 ", ""]. [" 8 "and". ", ""," ", "6", ""," ", ""," 3 "], [" 4 ", ""," ", "eight" and ". ", "3", ""," ", "1"], [" 7 ", ""," ", ""," 2 ", ""," ", ""," 6 "]. [". ", "6", ""," ", ""," ", "2", "eight", ""], [".", ""," ", "4", "1", "9", ""," ", "5"]. [". ", ". ", ""," ", "eight" and ". ", ""," 7 ", "9"]] output: false interpretation: in addition to the first line of the first number changed from 5 to 8, the Spaces within the other Numbers are the same as the sample 1. But since there are two eights in the 3x3 in the upper left corner, this sudoku is invalid.Copy the code

Description:

A valid Sudoku (partially filled)Not necessarilyIt’s solvable.
You only need to verify that the number has been filled in according to the above rulesCan be effective.
Give a sudoku sequence that contains only numbers1-9And character'. ' 。
Give sudoku forever9x9In the form of. `

Their thinking

An iteration
First, let’s discuss the following two questions:
How to enumerate subsudoku? You can use box_index = (row / 3) * 3 + columns / 3, where/is integer division.

How do I make sure there are no duplicates in row/column/sudoku? You can use a value -> count hash map to keep track of all values that have been encountered.
We have now completed all the preparations for this algorithm:

Go through sudoku.
Check to see if each cell value has already appeared in the current row/column/sudoku:
If a duplicate occurs, returnfalse.
If not, the value is retained for further tracing.
returntrue.

public boolean isValidSudoku(char[][] board) {
    Set seen = new HashSet();
    for (int i=0; i<9; ++i) {
        for (int j=0; j<9; ++j) {
            char number = board[i][j];
            if(number ! ='. ')
                if(! seen.add(number +" in row "+ i) || ! seen.add(number +" in column "+ j) || ! seen.add(number +" in block " + i / 3 + "-" + j / 3))
                    return false; }}return true;
}
Copy the code

Rotate the image

Given an N by N two-dimensional matrix representing the image, rotate the image 90 degrees clockwise.
Example:

Input:,1,0,0 [[1].,0,0,1 [1].,1,1,1 [0].,0,1,0 [1]] output:,1,0,0 [[1].,1,1,0 [0].,0,0,1 [0].,0,1,0 [1][解释: first flip each line:[[0,0,1,1].,0,0,1 [1].,1,1,0 [1].,1,0,1 [0]]; Then reverse the image:,1,0,0 [[1].,1,1,0 [0].,0,0,1 [0].,0,1,0 [1]]
Copy the code

Description:

1 <= A.length = A[0].length <= 20
0 <= A[i][j] <= 1
Copy the code

Their thinking

Let’s start by looking at how each element moves as it rotates:

This gives us an idea of dividing a given matrix into four rectangles and subsuming the original problem into twoRotate these rectanglesThe problem.

Now the solution is straightforward — you can move elements in the first rectangle and in a temporary list of four elements in lengthmobileAll of them.

public void rotate(int[][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return;
    }

    int length = matrix.length;

    for (int i = 0; i < length / 2; i++) {
        for (int j = 0; j < (length + 1) / 2; j++){
            int tmp = matrix[i][j];
            matrix[i][j] = matrix[length - j - 1][i];
            matrix[length -j - 1][i] = matrix[length - i - 1][length - j - 1];
            matrix[length - i - 1][length - j - 1] = matrix[j][length - i - 1];
            matrix[j][length - i - 1] = tmp; }}}Copy the code

Binary/bit operation

Advantages: under certain circumstances, the calculation is convenient, fast, is widely supported if the arithmetic method is used, the speed is slow, the logic complex bit operation is not limited to a language, it is the basic operation method of the computerCopy the code

Knowledge preheating

A number that appears only once

given2 * n + 1Each number except one appears twice. Find that number.

Xor operation has very good properties. The same number becomes 0 after xOR operation, and has the commutative law and associative law. Therefore, after xOR operation of all numbers, the number that only appears once can be obtained.

Example:

Input:,1,2,1,2 [4]Output: 4Copy the code

Their thinking

If we do XOR on 0 and binary, we still get this binary
If we do an XOR operation on the same binary bit, we return 0
XOR satisfies commutative and associative laws
So we just XOR all the numbers to get that unique number.

public int singleNumber(int[] A) {
    if(A == null || A.length == 0) {
        return -1;
    }
    int rst = 0;
    for (int i = 0; i < A.length; i++) {
        rst ^= A[i];
    }
    return rst;
}
Copy the code

Complexity analysis

Time complexity:O(n). We just need to putThe element is iterated over, so the time is zeroNumber of elements in.
Space complexity:O(1) 。

Gray coding

Gray code is a binary number system in which two consecutive values differ by only one binary. Given aNon-negative integer n, represents the total number of all binaries in the code, find its Gray encoding order. A Gray code order must be0Start and cover all of them2nAn integer. Example — input:2; Output: [0, 1, 3, 2]; Explanation:00 0 -.1-01.3-11.2-10

Their thinking

Grey code generation formula:G(i) = i ^ (i >> 2)

public ArrayList<Integer> grayCode(int n) {
    ArrayList<Integer> result = new ArrayList<Integer>();
    for (int i = 0; i < (1 << n); i++) {
        result.add(i ^ (i >> 1));
    }
    return result;
}
Copy the code

other

Integer inversion

Inverts the number of an integer, and returns 0 (marked as a 32-bit integer) when the inverted integer overflows.
Example:

Input:- 123.Output:- 321.
Copy the code

Their thinking

usingIn addition to more than 10 takeThe method will be lowest and highestReverse outputCan be

public int reverseInteger(int n) {
    int reversed_n = 0;
    
    while(n ! =0) {
        int temp = reversed_n * 10 + n % 10;
        n = n / 10;
        if (temp / 10! = reversed_n) { reversed_n =0;
            break;
        }
        reversed_n = temp;
    }
    return reversed_n;
}
Copy the code

LRU cache policy

Using your knowledge of data structures, design and implement an LRU (least recently used) caching mechanism. It should support the following operations: get for data and PUT for writing data.
Get (key) – Gets the value of the key if it exists in the cache (always positive), otherwise -1 is returned.
Write data PUT (key, value) – Writes the data value of the key if it does not exist. When the cache reaches its maximum capacity, it should remove the least-recently used data values before writing new data to make room for new data values.

Example:

LRUCache cache = new LRUCache(2 /* Cache capacity */); cache.put(1, 1); cache.put(2, 2); cache.get(1); // return 1 cache. Put (3, 3); Cache.get (2); // This operation invalidates key 2. // return -1 (not found) cache.put(4, 4); Cache.get (1); // This operation invalidates key 1. // return -1 (not found) cache.get(3); // return 3 cache.get(4); / / return 4Copy the code

Their thinking

Solution a:

Custom data structure:

Implement a linked list to keep track of the cache and handle the frequency of call usage
To define aHashMapUsed to record cache contents

public class LRUCache {
    private class Node{
        Node prev;
        Node next;
        int key;
        int value;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
            this.prev = null;
            this.next = null; }}private int capacity;
    private HashMap<Integer, Node> hs = new HashMap<Integer, Node>();
    private Node head = new Node(-1, -1);/ / head
    private Node tail = new Node(-1, -1);/ / the end

    public LRUCache(int capacity) {
        this.capacity = capacity;
        tail.prev = head;
        head.next = tail;
    }

    public int get(int key) {
        if( !hs.containsKey(key)) {    		/ / can't find the key
            return -1;
        }

        // remove current
        Node current = hs.get(key);
        current.prev.next = current.next;
        current.next.prev = current.prev;

        // move current to tail
        move_to_tail(current);			// Each get, the number of uses +1, the most recently used, put in the tail

        return hs.get(key).value;
    }

    public void set(int key, int value) {			// Put the data into the cache
        // The get method moves the key to the end, so there is no need to call move_to_tail
        if(get(key) ! = -1) {
            hs.get(key).value = value;
            return;
        }

        if (hs.size() == capacity) {		// The cache limit is exceeded
            hs.remove(head.next.key);		// Delete header data
            head.next = head.next.next;
            head.next.prev = head;
        }

        Node insert = new Node(key, value);		// Create a node
        hs.put(key, insert);
        move_to_tail(insert);					// put it in the tail
    }

    private void move_to_tail(Node current) {    // Move the data to the tailcurrent.prev = tail.prev; tail.prev = current; current.prev.next = current; current.next = tail; }}Copy the code

Method 2:

So the question is:LRUThe caching mechanism needs to be inO(1)Complete the following operations within the time:

Get the key/check if the key exists
Set the key
Deletes the key inserted first
The first two operations can be performed using a standard hash tableO(1)Finish in time.

There is a data structure called an ordered dictionary, a combination of hash and linked lists, called LinkedHashMap in Java.
This is implemented using this data structure.

class LRUCache extends LinkedHashMap<Integer.Integer>{
    private int capacity;
    
    public LRUCache(int capacity) {
        super(capacity, 0.75 F.true);
        this.capacity = capacity;
    }

    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        super.put(key, value);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        returnsize() > capacity; }}Copy the code

Complexity analysis

Time complexity: Yes for put and GET operationsBecause all operations in an ordered dictionary:
Get/set/in/move_to_end popitem (get/either containsKey/put/remove)It can all be done in constant time. Space complexity:Because space is only used for ordered dictionaries to store up to capacity + 1 elements.

Attention

In order to improve the quality of the article, prevent tedious

Next part of the algorithm

The longer the article is summed up. I’ve always felt that an overly long article, like an overly long meeting/class, is a bad experience, so I’m going to write another article
In the follow-up article, I will continue to list stack queue heap dynamic planning matrix bit operations and other nearly 100 kinds, interview high-frequency algorithm questions, and its text and text analysis + teaching video + example code, in-depth analysis can continue to pay attention to _yuanhao programming world
Not fast, just high quality, each article will be updated in 2-3 days cycle, and strive to maintain high quality output

🔥 interview essential: high-frequency algorithm summary “text and text analysis + teaching video + example code” string processing + dynamic planning collection! 🔥
🔥 interview essential: high-frequency algorithm summary “text and text analysis + teaching video + example code” binary search tree + dual Pointers + greedy summary 🔥
Interview algorithm dichotomy + Hash table + heap/priority queue summary
🔥 interview necessary: high-frequency algorithm summary “text and text analysis + teaching video + example code” linked list + stack + queue part! 🔥
🔥 interview essential: high-frequency algorithm summary “text and text analysis + teaching video + example code” sort + binary tree part 🔥
This article is enough to effectively solve the problem of “SQLite” database access security
Everyone has to learn picture compression to effectively solve the Android app OOM
Android gives your Room a free ride on the RxJava bandwagon from repetitive code
The founder of the ViewModel and ViewModelProvider. Factory: the ViewModel
Singleton pattern – globally available Context objects, enough for this article

Welcome to attention_yuanhaoThe nuggets!

I set up a warehouse on GitHub for you to follow up your study

Warehouse address: Super dry goods! Carefully summarized video, classification, summary, you pass by the old iron support! For a Star!

Thumb up, please! Because your encouragement is the biggest power that I write!

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

7 matrix + bit operation + LRU interview algorithm questions, you know? “Suggested collection”

Attention

Before we begin, let’s take a look at some of the highlights:

For your convenience, I’m here`GitHub`A warehouse was set up

matrix

Spiral matrix

Their thinking

Determine whether sudoku is legal

Their thinking

Rotate the image

Their thinking

Binary/bit operation

Knowledge preheating

A number that appears only once

Their thinking

Complexity analysis

Gray coding

Their thinking

other

Integer inversion

Their thinking

LRU cache policy

Their thinking

Complexity analysis

Attention

Next part of the algorithm

Related articles

Welcome to attention_yuanhaoThe nuggets!

I set up a warehouse on GitHub for you to follow up your study

Thumb up, please! Because your encouragement is the biggest power that I write!

7 matrix + bit operation + LRU interview algorithm questions, you know? “Suggested collection”

Attention

Before we begin, let’s take a look at some of the highlights:

For your convenience, I’m hereGitHubA warehouse was set up

matrix

Spiral matrix

Their thinking

Determine whether sudoku is legal

Their thinking

Rotate the image

Their thinking

Binary/bit operation

Knowledge preheating

A number that appears only once

Their thinking

Complexity analysis

Gray coding

Their thinking

other

Integer inversion

Their thinking

LRU cache policy

Their thinking

Complexity analysis

Attention

Next part of the algorithm

Related articles

Welcome to attention_yuanhaoThe nuggets!

I set up a warehouse on GitHub for you to follow up your study

Thumb up, please! Because your encouragement is the biggest power that I write!

Related Posts

Android componentization foundation

Android source code parsing init.rc script

Module decoupling Framework RxFluxArchitecture1- Introduction to the framework

For your convenience, I’m here`GitHub`A warehouse was set up