Leetcode每日一题 —— 657. 机器人能否返回原点

2026-04-11 12:002阅读0评论SEO教程
  • 内容介绍
  • 文章标签
  • 相关推荐
问题描述：
力扣 LeetCode

657. 机器人能否返回原点 - 力扣（LeetCode）

657. 机器人能否返回原点 - 在二维平面上，有一个机器人从原点 (0, 0) 开始。给出它的移动顺序，判断这个机器人在完成移动后是否在(0, 0) 处结束。 移动顺序由字符串moves表示。字符 move[i] 表示其第 i 次移动。机器人的有效动作有R（右），L（左），U（上）和 D（下）。 如果机器人在完成所有动作后返回原点，则返回 true。否则，返回 false。 注意：机器人“面朝”的方向无关紧要。 “R” 将始终使机器人向右移动一次，“L”...

依旧机器人 (¬`‸´¬)

思路

其实就是简单的模拟题，根据操作模拟左右上下移动、更新坐标，最终判断是否回到原点即可。

代码

class Solution { public: bool judgeCircle(string moves) { // 模拟题 int xPos=0,yPos=0; for(char c:moves){ switch(c){ case 'R': xPos++; break; case 'L': xPos--; break; case 'U': yPos++; break; case 'D': yPos--; break; } } return xPos==0 && yPos==0; } };

然后就是继续复习 Hot100

20. 有效的括号 - 力扣（LeetCode）

  • 注意最后栈需要是非空的。

class Solution { public: bool isValid(string s) { // 用栈即可 stack<char> stk; for(char c:s){ switch(c){ case ')': if(stk.empty()||stk.top()!='('){ return false; } stk.pop(); break; case '}': if(stk.empty()||stk.top()!='{'){ return false; } stk.pop(); break; case ']': if(stk.empty()||stk.top()!='['){ return false; } stk.pop(); break; default: stk.emplace(c); } } // 注意最后栈不能为空 return stk.empty(); } };

155. 最小栈 - 力扣（LeetCode）

  • 思路很值得回顾的一题，每次入栈时同时存储当时的最小值状态，弹栈时就相当于恢复上一个状态了。

class MinStack { private: vector<pair<int,int>> stk; public: MinStack() { // 这题难点就是常数时间拿到最小元素 // 一个很巧的思路就是，每个入栈的元素都记录当前最小的元素 } void push(int val) { int currMin=val; if(!stk.empty()){ // 如果有栈顶，就和上一个最小值状态进行比较看谁更小 currMin=stk.back().second; } currMin=min(currMin,val); stk.emplace_back(make_pair(val,currMin)); } void pop() { stk.pop_back(); } int top() { return stk.back().first; } int getMin() { return stk.back().second; } }; /** * Your MinStack object will be instantiated and called as such: * MinStack* obj = new MinStack(); * obj->push(val); * obj->pop(); * int param_3 = obj->top(); * int param_4 = obj->getMin(); */

33. 搜索旋转排序数组 - 力扣（LeetCode）

  • 又是一道容易写错的二分题，思路值得回顾。

这题每次剪枝时要考虑两点：

  1. 有序序列在哪里？
  2. target 在不在这个有序序列中？

可以发现，二分得到 mid 下标后，这个下标必然属于一个有序序列。数组可能因为旋转变成两个有序序列，那么 mid 就肯定在其中一个序列中。

这个时候就可以利用首个元素 nums[0]，如果大于 nums[0]，说明 [0, mid] 范围的序列是升序，否则是 [mid, n-1]。

找到升序序列后，判断 target 在不在这个序列中，如果在，则看是左边的有序序列还是右边的有序序列，如果是左边的，那为了逼近 target，就应该左移右边界；反之就是右移左边界。

这样不停更新边界来逼近这个 target，注意外层是在和数组首个元素比较，不同于以往是在和 target 比。

class Solution { public: int search(vector<int>& nums, int target) { // 旋转后数组可能被截成两段升序序列 // 此时首个元素和最后一个元素就有特殊的意义了 // 小于首个元素，说明在数组右侧 // 大于首个元素则在左侧 int l=0,r=nums.size()-1; while(l<=r){ int mid=(l+r)>>1; if(nums[mid]==target){ return mid; }else if(nums[mid]>=nums[0]){ // 如果比首个元素大，说明 [0, mid] 是有序序列 if(nums[0]<=target&&target<=nums[mid]){ // 如果 target 在这个有序序列中，就收缩右边界 // 已知 target 不会是 nums[mid] r=mid-1; }else{ // 否则 target 在另一侧 l=mid+1; } }else if(nums[mid]<nums[0]){ // 如果比首个元素小，则 [mid, n-1] 是有序序列 if(nums[mid]<=target&&target<=nums[nums.size()-1]){ // target 在这个有序序列中，收缩左边界 // 已知 target 不会是 nums[mid] l=mid+1; }else{ // 否则 target 在另一侧 r=mid-1; } } } return -1; } };

56. 合并区间 - 力扣（LeetCode）

  • 按区间开始位置进行排序，然后再扫描一遍按规则执行合并即可。

class Solution { public: vector<vector<int>> merge(vector<vector<int>>& intervals) { // 按 start 对 intervals 进行排序后合并即可 sort(intervals.begin(),intervals.end(),[](const auto& a, const auto& b){ return a[0]<b[0]; }); vector<vector<int>> res; // 存储上一个区间的结束位置 int lastEnd=-1; for(vector<int>& itv:intervals){ if(lastEnd>=itv[1]){ // 当前区间被上一个区间包含进去了 continue; } if(lastEnd>=itv[0]){ // 上一个区间的结束位置 >= 当前区间的开始位置，合并 lastEnd=itv[1]; res[res.size()-1][1]=lastEnd; }else{ // 否则独立成为一个新区间 lastEnd=itv[1]; res.emplace_back(itv); } } return res; } };

网友解答：
--【壹】--：

简单题。

class Solution { public: bool judgeCircle(string moves) { return !(std::count(moves.begin(),moves.end(),'L') - std::count(moves.begin(),moves.end(),'R')) & !(std::count(moves.begin(),moves.end(),'U') - std::count(moves.begin(),moves.end(),'D')); } };