srm707 medium StepsConstruct
problem
There is a rectangular board that is divided into n rows by m columns of cells. Each cell is either empty or it contains an obstacle. You are given the description of the board in the board. Each character in board represents one cell. More precisely, the character board[i][j] represents the cell at coordinates (row i, column j). The character ‘#’ represents an obstacle, the character ‘.’ is an empty cell.
You would like to travel from the top left corner to the bottom right corner of the board in exactly k steps. More precisely, you want to perform the following sequence of actions:
Enter the board by stepping onto the cell at coordinates (0, 0): the top left corner. Make exactly k steps. In each step, you’ll move from your current cell to one of the cells that share a side with your current cell. In other words, in each step you’ll go one cell up, down, left, or right. After the k-th step, you must be in the bottom right corner: at coordinates (n-1, m-1). Note that you can only step onto empty cells. You have to move in each step, it is not allowed to stay in the same cell. You are allowed to visit each empty cell arbitrarily many times. You are not allowed to leave the board while making the k steps.
You are given the board and the k. Determine whether it is possible to reach the bottom right corner in the way described above. If there is no solution, return an empty . If there are some solutions, choose any one of them and return a containing its description.
If a solution exists, the returned should consist of k characters, each describing one step. Each character should be one of ‘U’ (up), ’D' (down), ‘L’ (left), and ‘R’ (right).
how to solve
I can solve this problem by using bfs search. There is some points to solve this problem. Firstly, the parity of step is same as the sum of the goal point’s x and y. So If I can find the goal route, and this step’s parity is same as the parity of k, I can get the way to reach the goal by k step.
code
srm707 easy Cross
problem
There is a rectangular board that is divided into n rows by m columns of cells. Each cell is either black or white. You are given the description of the board in the board. Each character in board represents one cell. More precisely, the character board[i][j] represents the cell at coordinates (row i, column j). The character ‘#’ represents a black cell, the character ‘.’ is a white cell. Formally, there is a cross centered at (x, y) if the following five cells are all black: (x, y), (x+1, y), (x-1, y), (x, y-1), and (x, y+1). Note that other cells adjacent to the cross may also be black, it is still a valid cross.
Return “Exists” if there is at least one cross on the given board. Otherwise, return “Does not exist”. Note that the return value is case-sensitive.
code
Delete Middle Node
problem
Implment an algorithm to delete a node in the middle of a singly linked list. But you can only access to that node.
note
The solution is simply to copy the data from the next node over to the current node.
code
RemoveDups
problem
Write code to remove duplicates from an unsorted linked list without using a temporary buffer.
how to solve
If I can use a temporary buffer, I recommend to use hash table. But in this case, I have to compare two elements to check that they are duplicated or not by using brute force search.
code
Insertion
problem
You are given two 32bit numbers n and m and two bit positions, i and j. Write a method to insert M into N such that M starts at bit j and ends at bit i.
how to solve
- Clear the bits j through i in N
- Shift M so that it lines up with bits j through i
- Merge M and N
code
AnimalShelter
Problem
An animal shelter, which holds only dogs and cats. Create the data structures to implement operations such as enqueue, dequeueAny, dequeueDog and dequeueCat.
How to solve
My approach is to simply use separate queues for dogs and cats. Then we store some sort of timestamp to mark when each animal was enqueued. When we called dequeueAny, we compare the front of the dog and cat queue and return the oldest.
Code
Rotate Matrix
problem
Given an image represented by an N*N matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?
how to solve
We swap on each layer, starting from the outermost layer and working our way inwards.
