✨今日算法三题
文章目录
1.二进制求和
题目描述
思路详解
有个较为简单的思路：
直接把两个数转换为十进制整数进行相加，再转换成二进制。
但是这里时间复杂度为O(m+n)，即两个字符串的位数，同时也存在位数精度问题。
这里采用模拟的方法。模拟就是让计算机模拟我们人进行解题的过程。
二进制计算呢，逢二进一，所以每一位的数值就等于对应位置(a+b+carry)%2，这里carry为上一位进上来的数值，那么本位的进位值为（a+b+carry）/ 2. 按照这样的计算过程遍历完a和b的每一位就可以得出结果了。
注意，刚开始我们计算的时候要把每一位对其哦，当然计算机也少不了对齐这个步骤，我们可以倒着计算来存储最后反转一下，也可以短位左补零使其长度一样，然后先从高位开始算。
代码与结果
class Solution { public String addBinary(String a, String b) { StringBuffer ans = new StringBuffer(); int n = Math.max(a.length(), b.length()), carry = 0; for (int i = 0; i < n; ++i) { carry += i < a.length() ? (a.charAt(a.length() - 1 - i) - '0') : 0; carry += i < b.length() ? (b.charAt(b.length() - 1 - i) - '0') : 0; ans.append((char) (carry % 2 + '0')); carry /= 2; } if (carry > 0) { ans.append('1'); } ans.reverse(); return ans.toString(); } }
2.螺旋矩阵
题目描述
思路详解
本题采用模拟迷宫寻路的方法实现。
首先定义四个方向，顺序为，右下左上。看到数据-100
注意，这里的换方向条件要么达到边界，要么下一步已经访问过。值得注意的是，我们首先要访问完一圈再访问一圈，所以我们的方向就不能随便改哦，只能一个方向走完再换。
代码与结果
class Solution { int INF = 101; public List<Integer> spiralOrder(int[][] mat) { List<Integer> ans = new ArrayList<>(); int m = mat.length, n = mat[0].length; // 定义四个方向 int[][] dirs = new int[][]{{0,1},{1,0},{0,-1},{-1,0}}; for (int x = 0, y = 0, d = 0, i = 0; i < m * n; i++) { ans.add(mat[x][y]); mat[x][y] = INF; // 下一步要到达的位置 int nx = x + dirs[d][0], ny = y + dirs[d][1]; // 如果下一步发生「溢出」或者已经访问过（说明四个方向已经走过一次） if (nx < 0 || nx >= m || ny < 0 || ny >= n || mat[nx][ny] == INF) { d = (d + 1) % 4; nx = x + dirs[d][0]; ny = y + dirs[d][1]; } x = nx; y = ny; } return ans; } }
3.模拟行走机器人
题目描述
思路详解
本题和上一题很相似，定义接收到的方向。也注意到限制了步数，那么去哦们就可以限制输入。同时这个障碍物的坐标，我们采用set集合存储，方便查询，同时提高效率。
代码与结果
class Solution { public int robotSim(int[] commands, int[][] obstacles) { int[] dx = new int[]{0, 1, 0, -1}; int[] dy = new int[]{1, 0, -1, 0}; int x = 0, y = 0, di = 0; // Encode obstacles (x, y) as (x+30000) * (2^16) + (y+30000) Set<Long> obstacleSet = new HashSet(); for (int[] obstacle: obstacles) { long ox = (long) obstacle[0] + 30000; long oy = (long) obstacle[1] + 30000; obstacleSet.add((ox << 16) + oy); } int ans = 0; for (int cmd: commands) { if (cmd == -2) //left di = (di + 3) % 4; else if (cmd == -1) //right di = (di + 1) % 4; else { for (int k = 0; k < cmd; ++k) { int nx = x + dx[di]; int ny = y + dy[di]; long code = (((long) nx + 30000) << 16) + ((long) ny + 30000); if (!obstacleSet.contains(code)) { x = nx; y = ny; ans = Math.max(ans, x*x + y*y); } } } } return ans; } }
✨总结
今天主要练习了模拟的思想，我们对人工操作或者一些时间进行模拟，从而得出结果，这也是计算机最初的目的。多多练习才能熟练使用哦！！！
