多拿好offer_gx

分类

题解(24)

/ 注册

全部文章（共24篇）

题解 | #把字符串转换成整数(atoi)#

首先去除掉首位空格，此时第一个字符有三种情况首先是-或者+，此时往前进一位，当后面没有字符或者后面字符不是数字时，返回0。将后面的数字字符累加起来。累加过程中需要与Integer.MAX_VALUE或者Integer.MIN_VALUE比较；后面字符是数字，将后面字符累加起来。累加过程中与In...

Java 字符串

2021-12-21

2 668

题解 | #买卖股票的最好时机(二)#

贪心：每当下一天股票价格相对于今天是下降的，那么就将股票卖出，并在明天买入。需要注意：在最后一天一定需要将股票卖出，因为没有下一天了。 import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿...

Java 贪心双指针

2021-12-17

0 368

题解 | #判断一个链表是否为回文结构#

快慢指针+反转链表使得空间复杂度降到O(1)：需要注意链表长度是奇数还是偶数的情况。 import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * } */ publi...

Java 双指针链表

2021-12-16

0 322

题解 | #通配符匹配#

这题是p串匹配s串。其中p串含有'?'（能匹配任一个字符），'*'能匹配任意字符串包括空串。使用动态规划：f[i][j]表示s串前i个字符匹配p串前j个字符的结果。分为三种情况： p串第j个字符串既不是'?'，也不是'*'，那么当s串第i个字符与p串第j个字符相同时，f[i][j]取决于f[i-...

Java

2021-12-14

0 268

题解 | #数组中的逆序对#

归并排序中有一步是比较两个有序子数组中两个数的大小，当属于后半部分的那个数小于前半部分的那个数时，由于是有序子数组，那么前半部分那个数后面的数也大于后半部分的那个数，所以这些数都能组成逆序对。所以每次将这些逆序对个数累加即可。 public class Solution { int cnt ...

Java 归并排序

2021-12-13

0 293

题解 | #矩阵元素查找#

利用该数组的单调性特性，从右上角开始查找，如果当前数==目标值则返回该位置。如果当前数大于目标数的话，那么根据单调性，数据必然在矩阵的左半边，即j--。如果当前数小于目标数的话，那么同样根据单调性，数据必然在矩阵的下半边，即i++。 import java.util.*; public class...

Java 数组

2021-12-13

0 307

题解 | #数组中的最长连续子序列#

思路：首先对数组进行排序操作，当相邻的两个数差值为1时，说明连续，连续子序列长度＋1。但是数组中存在重复数字，可以先用HashSet进行去重操作，但是空间复杂度较大。所以可以使用双指针算法，找出重复数字的最后一个索引。 import java.util.*; public class Solut...

Java 双指针

2021-12-13

0 355

题解 | #岛屿数量#

Flood fill算法：遍历每个位置，当该位置为岛屿时，将该位置相邻的岛屿全部标记。标记的方式又DFS和BFS。 import java.util.*; public class Solution { /** * 判断岛屿数量 * @param grid char字...

Java 广度优先搜索深度优先搜索

2021-12-13

0 284

题解 | #验证IP地址#

import java.util.*; public class Solution { /** * 验证IP地址 * @param IP string字符串一个IP地址字符串 * @return string字符串 */ public S...

Java 字符串

2021-12-09

0 400

题解 | #矩阵的最小路径和#

动态规划：f[i][j]表示从(0,0)走到(i,j)的最小路径和。状态转移：情况1从上方来到，即f[i-1][j]，情况2从左边来到，即f[i][j-1]，两者取最小值。原地操作来节省内存，这样需要记录matrix[i][j]的值。 import java.util.*; public cla...

Java 动态规划数组

2021-12-09

0 335