“Offer comes, ask friends to take it! I am participating in the 2022 Spring Recruit Punch card campaign. Click here for more details.”

📢 preface

🚀 Algorithm 🚀
  • 🌲 punch in an algorithm every day, which is not only a learning process, but also a sharing process 😜
  • 🌲 tip: the programming languages used in this column are C# and Java
  • 🌲 to maintain a state of learning every day, let us work together to become a god of algorithms 🧐!
  • 🌲 today is the 87th day 🎈!
🚀 Algorithm 🚀

🌲 Can the robot return to the origin

In two dimensions, I have a robot that starts at the origin (0, 0). Give the order of its movement and determine whether the robot ends at (0, 0) after it completes its movement.

The movement order is represented by a string. The character move[I] indicates its i-th move. The effective actions of the robot are R (right), L (left), U (up) and D (down). Returns true if the robot returns to the origin after completing all actions. Otherwise, return false.

Note: It doesn’t matter which way the robot is “facing”. “R” will always make the robot move to the right once, “L” will always move to the left, etc. Furthermore, assume that the robot moves by the same amount each time it moves.

Example 1:

Input:"UD"Output:trueExplanation: The robot moves up once, then down once. All actions have the same magnitude, so it eventually returns to where it started. So let's go backtrue.Copy the code

Example 2:

Input:"LL"Output:falseExplanation: The robot moves to the left twice. It ends up two "moves" to the left of the origin. We return tofalseBecause it doesn't return to the origin at the end of the movement.Copy the code

Tip:

  • Both lists are within the length range of [1, 1000].
  • The strings in both lists will be in the range of [1,30].
  • The subscript starts at 0 and goes to the length of the list minus 1.
  • There are no duplicate elements in either list.

🌻C# method: new space traversal

  • Define a dictionary to hold strings and subscripts, and store an array to the dictionary
  • Loop through another array and dictionary to see if the key has the same value, then check the index and

Code:

public class Solution {
    public string[] FindRestaurant(string[] list1, string[] list2) {
            int n = int.MaxValue;
            List<string> index = new List<string> (); Dictionary<string.int> dic = new Dictionary<string.int> ();for (int i = 0; i < list1.Length; i++)
            {
                dic.Add(list1[i],i);
            }
            for (int i = 0; i < list2.Length; i++)
            {
                if (dic.ContainsKey(list2[i]))
                {
                    if (i + dic[list2[i]]<n)
                    {
                        n=i + dic[list2[i]];
                        index.Clear();
                        index.Add(list2[i]);
                    }
                    else if(i + dic[list2[i]] == n) { index.Add(list2[i]); }}}returnindex.ToArray(); }}Copy the code

The execution result

By execution time:172Ms, in all C# beat 93.50% of users in submissionMemory consumption:62MB, in all CBeat 9.90% of users in # commit
Copy the code

🌻Java method: emulation

We only need to simulate the coordinates of robot movement according to the command. At the beginning, the coordinate of the robot is (0,0)(0,0)(0,0). After traversing all instructions and moving the robot, it can be determined whether the coordinate of the robot is (0,0)(0,0).

Specifically, we use two variables XXX and YYy to represent the robot’s current coordinates as (x,y)(x,y)(x,y). At the beginning, x=0x=0x=0,y =0y=0y=0. Next we iterate over the instructions and update the coordinates of the robot:

  • If the instruction is UUU, let y=y−1y=y-1y= Y −1
  • If the instruction is DDD, make y=y+1y=y+1y=y+1
  • If the instruction is LLL, make x=x−1x=x-1x=x−1
  • If the instruction is RRR, make x=x+1x=x+1x=x+1

(x,y)(x,y)(x,y) is (0,0)(0,0)(0,0).

Code:

class Solution {
    public boolean judgeCircle(String moves) {
        int x = 0, y = 0;
        int length = moves.length();
        for (int i = 0; i < length; i++) {
            char move = moves.charAt(i);
            if (move == 'U') {
                y--;
            } else if (move == 'D') {
                y++;
            } else if (move == 'L') {
                x--;
            } else if (move == 'R') { x++; }}return x == 0 && y == 0; }}Copy the code

The execution result

By execution time:6Ms, beat out all Java commits60.41% user memory consumption:38.4MB, beat out all Java commits57.40% of the userCopy the code

Complexity analysis

Time complexity: O(n) Space complexity: O(n)Copy the code

💬 summary

  • Today is the eighty-seventh day of buckle algorithm clocking!
  • The article USES theC# andJavaTwo programming languages to solve the problem
  • Some methods are also written by the god of reference force buckle, and they are also shared while learning, thanks again to the algorithm masters
  • That’s the end of today’s algorithm sharing, see you tomorrow!