[每天两道题]坚持找到工作为止

adbase

58. Length of Last Word
今天题目简单，所以我做了几道easy题。这道题太简单了，我就直接写在这里了。
这个题解法很多，若是想要展示水平，可以用有限状态机。
若是最优解法，就用双指针，写两个while，第一次先找到末尾非空白的字符位置，第二次找到这个字符的起点。最后两个指针之差就是答案。
若是展示语言运用能力，可以先trim，再split,然后直接返回最后一个string 的长度。推荐用这种方式，写起来就两行代码，比较漂亮

class Solution {
public int lengthOfLastWord(String s) {
String[] sc = s.trim().split(" ");
return sc[sc.length - 1].length();
}
}

复制代码

adbase

59. Spiral Matrix II
这道题和54. Spiral Matrix 是一摸一样的。上一道题是让你返回路径，这道题是填充矩阵。
思路还是完全一样，用dfs的，只是用一个参数控制方向，并且通过下一个节点的位置，判断是否需要更改方向。用一个一维数组记录走过的节点。最后无路可走，即返回递归。
dfs的过程中，自增地填充数字即可。
我的代码是：

class Solution {
int[][] m;
int[] seen;
public int[][] generateMatrix(int n) {
m = new int[n][n];
seen = new int[n * n];
int[] p = {0, 0};
helper(0, 1, p);
return m;
}
private void helper(int dir, int count, int[] p) {
if(!verify(p)) return;
seen[p[0] * m.length + p[1]] = 1;
m[p[0]][p[1]] = count;
int[] next = {p[0], p[1]};
update(next, dir);
if(!verify(next)) {
dir = dir == 3 ? 0 : dir + 1;
update(p, dir);
}else{
p[0] = next[0];
p[1] = next[1];
}
helper(dir, count + 1, p);
}
private boolean verify(int[] p) {
int r = p[0];
int c = p[1];
int idx = r * m.length + c;
if(r < 0 || r > m.length - 1 ||
c < 0 || c > m[0].length - 1 ||
seen[idx] == 1) {
return false;
}
return true;
}
private void update(int[] next, int dir) {
if(dir == 0) {
next[1]++;
}else if(dir == 1) {
next[0]++;
}else if(dir == 2) {
next[1]--;
}else next[0]--;
}
}

复制代码

adbase

60. Permutation Sequence
这道题是好题，我的做法是比较笨的方法，也是最直观的方法。也就是利用31. Next Permutation的方法。
假设n = 3 我们建立一个数组，初始化为[1, 2, 3]，也就是全排序的第一个数组。之后第k个，也就是运行k - 1次 next permutation。然后把数组元素组合成字符串返回即可。

next permutation的方法再复习一次，用双指针，第一个指针p1，从数组末尾倒数第二位 -- nums.length - 2 开始找，找第一个数字，使得nums[p1] < nums[p1 + 1]。
也就是从尾巴开始，看数字大小，找山顶或者走到头为止。
然后我们第二个指针p2, 再从尾巴开始，直到nums[p2] > nums[p1]为止。
然后，我们互换p1 , p2上的数字，再把[p1, nums.length - 1]区间内的数字反转，就是下一个全排序的组合。

当时我就认为这个方法一定要记牢，肯定有题目要求你对元素的全排序进行查找，本题就是如此。

当然，我的方法不是最优解。最优解，是数学方法，也就是这个题目的数字都是123456..这样的。这个数组的全排序是有规律的，总结一下每一个位的出现规律公式，就可以在o(1)时间内计算出数字。

不过我认为面试中，除非背题，否则不可能立刻发觉和总结出数学公式，还不如就按我的方法，写next permutation。这样等于一次做两个题，也更能让面试官满意。

所以我的代码就是

class Solution {
public String getPermutation(int n, int k) {
int[] nums = new int[n];
for(int i = 0; i < nums.length; i++) {
nums[i] = i + 1;
}
while(k > 1) {
next(nums);
//System.out.print(nums.toString());
k--;
}
StringBuilder rs = new StringBuilder();
for(int i = 0; i < nums.length; i++) {
rs.append(nums[i]);
}
return rs.toString();
}
private void next(int[] nums) {
int left = nums.length - 2;
while(left >= 0 && nums[left] >= nums[left + 1]) {
left--;
}
int right = nums.length - 1;
while(right >= 0 && nums[right] <= nums[left]) {
right--;
}
swap(nums, left, right);
reverse(nums, left + 1, nums.length - 1);
}
private void swap(int[] nums, int left, int right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
private void reverse(int[] nums, int a, int b) {
while(a < b) {
swap(nums, a, b);
a++;
b--;
}
}
}

复制代码

adbase

61. Rotate List
思路，看到linkedlist 要求你找到第k个节点，那么就用快慢指针。本题也是如此。
这个题难度在于两个，一个是k可能大于链表长度。所以我们就先走一次，找出链表长度。然后取模 k % len就可以得出循环到最后应该是第几个节点，

再用快慢指针，fast先走，走k % len步之后，slow再从head和fast一起走，直到fast走到终点。此时，slow就是新链表的尾巴，slow.next就是新链表的head。所以我们三个步骤，第一，先把头接上dumy.next = slow.next。第二、把尾巴断开slow.next = null。第三，把原来的尾巴接到原来的头 fast.next = head;
这样就做完了，所以代码就是

/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if(head == null) return head;
ListNode fast = head;
ListNode slow = head;
ListNode dummy = new ListNode();
dummy.next = head;
int len = 1;
while(fast.next != null) {
fast = fast.next;
len++;
}
int n = k % len;
//System.out.println(n + " " + len + " " + k);
fast = head;
while(n > 0) {
fast = fast.next;
n--;
}
while(fast.next != null) {
fast = fast.next;
slow = slow.next;
}
//System.out.println(fast.val + " " + slow.val);
dummy.next = slow.next == null ? head : slow.next;
fast.next = head;
slow.next = null;
return dummy.next;
}
}

复制代码

adbase

62. Unique Paths
这道题乍一看，可以用dfs做。先走到一次终点，然后退一步，换另一个方向试一试，同时要记录哪些节点已经走过了。但是想了想不太对。
当我们见到一个题，要求给出有多少种走法，那么一定是bfs。dfs的用途在于问题有没有解，而问题有多少解，bfs才是更好的方法。

那么bfs怎么做呢？我们自然会想到从起点开始，和起点相邻的格子，都只有1种走法，由于只能向右或者向下，所以第一行和第一列其实都只有一种走法，所以第一行和第一列的格子都填1。然后我们看bfs的第二层，马上很容易意识到，除了第一行和第一列，其他每一个格子的值，等它上面格子＋左面格子。

那么，我们就可以明白了，此时我们已经使用了dp。只要建立一个m x n二维数组，初始化第一行和第一列为1，然后按照上面的规律填写其他格子。最后返回右下角格子的值就是答案。

这题写到这里基本就可以了，当然你可以优化一个空间复杂度，因为我们填写格子的顺序，是从上倒下，从左到右。所以其实我们是一行一行填写的，就像你在作文纸上写作文一样。
那么我们不需要把整个作文纸的格子都画出来。我们只要定义一行就可以。这一行相当于上面的格子，然后我们用一个int pre记录上一个数字，也就是左边的格子。
所以dp[i] = dp[i] + pre. 然后 pre = i== 0 ? 1 : dp[i]。这样我们就可以节省一些空间复杂度。不过时间复杂度还是一样的。
最后代码就是

class Solution {
public int uniquePaths(int m, int n) {
// 0 1 1 1 1 1 1
// 1 2 3 4 5 6 7
// 1 3 6 10 15 21 28
int[] dp = new int[n];
Arrays.fill(dp,1);
int pre = 1;
for(int i = 0; i < m -1; i++) {
for(int j = 0; j < n; j++) {
if(j == 0) pre = 1;
else{
dp[j] = dp[j] + pre;
pre = dp[j];
}
}
//System.out.println(Arrays.toString(dp));
}
return dp[n - 1];
}
}

复制代码

adbase

63. Unique Paths II
这道题和61是一样的，只是多一个障碍。它们的做法也是一样，也就是bfs的思想，去填充dp矩阵。每一个格子依然是 dp[i][j] = dp[i][j - 1] + dp[i - 1][j]
但是多一种情况，就是若是obs[i][j] = 1。也就是本格子是个障碍，那么dp[i][j] = 0；
同样，初始化第一行和第一列的时候，若是有障碍，那么后面的格子都是0,也就是无法到达。原因也很简单，因为机器人只能向右走或者向下走，所以第一行和第一列是没法绕开障碍的。
所以代码就是

class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
// 1 1 1
// 1 0 1
// 1 1 2
if(obstacleGrid[0][0] == 1) return 0;
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[][] dp = new int[m][n];
for(int i = 0; i < n; i++) {
if(obstacleGrid[0][i] == 0) dp[0][i] = 1;
else break;
}
for(int i = 0; i < m; i++) {
if(obstacleGrid[i][0] == 0) dp[i][0] = 1;
else break;
}
for(int i = 1; i < m; i++) {
for(int j = 1; j < n; j++) {
if(obstacleGrid[i][j] == 1){
dp[i][j] = 0;
}else{
if(obstacleGrid[i][j] != 1) dp[i][j] = dp[i-1][j]+ dp[i][j - 1];
}
}
}
return dp[m - 1][n - 1];
}
}

复制代码

adbase

64. Minimum Path Sum
这道题和63也一样，是62的变种。给我们每个格子一个权重，要求返回权重最小的路径。
那么其实就是每一个格子dp[i][j] = grid[i][j] + min(dp[i][j-1], dp[i - 1][j])。
也就是贪心法的意思，每次我们都选上面和左边格子更小的那一个。然后填充整个dp矩阵，那么终点的值就是最小值。所以代码就是

class Solution {
public int minPathSum(int[][] grid) {
// 1 4 5
// 2 7 6
// 6 8 7
int r = grid.length;
int c = grid[0].length;
int[][] m = new int[r][c];
m[0][0] = grid[0][0];
int pre = m[0][0];
for(int i = 1; i < r; i++) {
m[i][0] = grid[i][0] + pre;
pre = m[i][0];
}
pre = m[0][0];
for(int i = 1; i < c; i++) {
m[0][i] = grid[0][i] + pre;
pre = m[0][i];
}
//System.out.println(Arrays.toString(m[0]));
for(int i = 1; i < r; i++) {
for(int j = 1; j < c; j++) {
m[i][j] = Math.min(m[i - 1][j], m[i][j - 1]) + grid[i][j];
}
//System.out.println(Arrays.toString(m[i]));
}
return m[r - 1][c - 1];
}
}

复制代码

匿名用户-UIWRI *2022-5-2 15:29:51* · 2022-5-2 15:29:51

楼主加油！！

雅言904

有这样的坚持，一定会早日上岸

adbase

65. Valid Number
这道题是通过率最少的几个题之一，非常不好，很难写对，但是算法技巧几乎全无。
这种判定字符串是否match某种规则的题，万能方法就是状态机。本题也是如此，用状态机比较好讨论，代码也相对精简。

我们的输入有四种情况：点，数字，e符号，正负号。其他字符立刻返回false。
然后有10种状态（这就是本题的难度）
0- 初始状态
1 －输入了一个正负号
2 －输入了一个整数位数字之后
3－输入了一些整数位数字，又输入了一个小数点
4-  输入了一个正负号，又立刻输入了一个小数点
5- 输入了一个小数位的数字
6-  输入了一个e
7-  输入了一个e之后的正负号
8- 输入了一个e之后的数字
9- 其他（false)
定义好状态转移矩阵之后，题目就很简单了，每次输入，就更新状态，注意的是，最后判断的时候，也要看一下状态是不是合法的状态，也就是只有结束的时候，状态是2 358才是数字，否则就不是。

代码就是

// init sign intnumber dot dotnumber exp expsign expnum nointdot false
// 0 1 2 3 4 5 6 7 8 9
// sign 1 9 9 9 9 6 9 9 9 9
// num 2 2 2 4 4 7 7 7 4 9
// dot 8 8 3 9 9 9 9 9 9 9
// exp 9 9 5 5 5 9 9 9 9 9
int[][] m = {
{1, 9, 9, 9, 9, 6, 9, 9, 9, 9},//sign
{2, 2, 2, 4, 4, 7, 7, 7, 4, 9},//num
{8, 8, 3, 9, 9, 9, 9, 9, 9, 9},//dot
{9, 9, 5, 5, 5, 9, 9, 9, 9, 9} //exp
};
int status = 0;
char[] sc = s.toCharArray();
for(int i = 0; i < sc.length; i++) {
//System.out.println("pre status = " + status);
char c = sc[i];
if(c == '+' || c == '-') {
status = m[0][status];
}else if(c >= '0' && c <= '9') {
status = m[1][status];
}else if(c == 'e' || c == 'E') {
status = m[3][status];
}else if(c == '.') {
status = m[2][status];
}else return false;
//System.out.println("c = " + c + " status is " + status);
//System.out.println("------------------");
if(status == 9){
return false;
}
}
//System.out.println(status);
return status == 2 || status == 3 || status == 4 || status == 7;
}
}

复制代码