免费企业一键建站网站,哪些网站教做生物实验,网店营销推广实训平台,镇江网站关键字优化如何目录
第一题
题目来源
题目内容
解决方法
方法一#xff1a;动态规划
第二题
题目来源
题目内容
解决方法
方法一#xff1a;模拟
方法二#xff1a;数学规律
方法三#xff1a;分组
第三题
题目来源
题目内容
解决方法
方法一#xff1a;数学方法
方法…目录
第一题
题目来源
题目内容
解决方法
方法一动态规划
第二题
题目来源
题目内容
解决方法
方法一模拟
方法二数学规律
方法三分组
第三题
题目来源
题目内容
解决方法
方法一数学方法
方法二转换字符串 第一题
题目来源
213. 打家劫舍 II - 力扣LeetCode
题目内容 解决方法
方法一动态规划
这道题可以使用动态规划的方法求解。首先我们观察到第一个房屋和最后一个房屋是相邻的因此它们不能同时被偷窃。所以我们可以将问题分成两种情况来考虑 偷窃第一个房屋但不偷窃最后一个房屋在这种情况下我们只需要计算从第一个房屋到倒数第二个房屋能够偷窃到的最高金额。 不偷窃第一个房屋但偷窃最后一个房屋在这种情况下我们只需要计算从第二个房屋到最后一个房屋能够偷窃到的最高金额。
对于每一种情况我们可以使用动态规划来求解。定义一个长度为n的数组dp其中dp[i]表示从第一个房屋到第i个房屋能够偷窃到的最高金额。那么我们有以下状态转移方程 对于第一种情况dp[i] max(dp[i-2] nums[i], dp[i-1])其中dp[i-2] nums[i]表示偷窃第i个房屋得到的金额dp[i-1]表示不偷窃第i个房屋得到的金额。 对于第二种情况dp[i] max(dp[i-1], dp[i-2] nums[i])其中dp[i-1]表示不偷窃第i个房屋得到的金额dp[i-2] nums[i]表示偷窃第i个房屋得到的金额。
最后我们可以将第一种情况和第二种情况的结果取较大值作为最终的结果即max(dp[n-2], dp[n-1])其中n是数组nums的长度。
class Solution {public int rob(int[] nums) {int n nums.length;if (n 1) {return nums[0];}return Math.max(robHouse(nums, 0, n - 2), robHouse(nums, 1, n - 1));}private int robHouse(int[] nums, int start, int end) {int pre2 0, pre1 0;for (int i start; i end; i) {int cur Math.max(pre2 nums[i], pre1);pre2 pre1;pre1 cur;}return pre1;}
}
在上述解法中我们使用了动态规划的思想来解决问题。接下来我们来分析一下该解法的时间复杂度和空间复杂度。
时间复杂度分析
在计算偷窃第一种情况的最高金额时我们需要遍历从第一个房屋到倒数第二个房屋因此时间复杂度为O(n)。在计算偷窃第二种情况的最高金额时我们需要遍历从第二个房屋到最后一个房屋同样时间复杂度为O(n)。最后取两种情况的较大值作为最终结果时间复杂度为O(1)。 综上所述该解法的时间复杂度为O(n)。
空间复杂度分析
我们使用了一个长度为n的dp数组来保存每个房屋能够偷窃到的最高金额因此空间复杂度为O(n)。另外我们还使用了常量级的额外空间来保存前两个房屋的偷窃金额所以空间复杂度为O(1)。 综上所述该解法的空间复杂度为O(n)。
总结 该解法的时间复杂度为O(n)空间复杂度为O(n)。在给定限制条件下这是一个较优的解法。
LeetCode运行结果 第二题
题目来源
6. N 字形变换 - 力扣LeetCode
题目内容 解决方法
方法一模拟
这个问题可以使用模拟的方法来解决。我们可以创建一个长度为numRows的字符串数组表示Z字形排列后每一行的字符串。然后遍历原始字符串s将每个字符按照Z字形的规律放入对应的行中。
具体步骤如下
若numRows为1或s的长度小于等于numRows则直接返回s作为结果。创建一个长度为numRows的字符串数组rows用于保存每一行的字符串。创建一个变量rowIndex初始值为0表示当前所在的行。创建一个变量goingDown初始值为true表示当前的方向是向下。遍历字符串s的每个字符 将当前字符加入rows[rowIndex]中。如果当前的方向是向下且当前行不是最后一行则向下移动到下一行rowIndex。如果当前的方向是向上且当前行不是第一行则向上移动到上一行rowIndex--。如果当前行是第一行或最后一行则改变方向goingDown !goingDown。将数组rows中的每个字符串按顺序连接起来即为结果。
class Solution {public String convert(String s, int numRows) {if (numRows 1 || s.length() numRows) {return s;}String[] rows new String[numRows];for (int i 0; i numRows; i) {rows[i] ;}int rowIndex 0;boolean goingDown true;for (char c : s.toCharArray()) {rows[rowIndex] c;if (goingDown rowIndex numRows - 1) {rowIndex;} else if (!goingDown rowIndex 0) {rowIndex--;}if (rowIndex 0 || rowIndex numRows - 1) {goingDown !goingDown;}}StringBuilder result new StringBuilder();for (String row : rows) {result.append(row);}return result.toString();}
}
复杂度分析如下
时间复杂度
String转换为char数组的时间复杂度是O(n)其中n为字符串s的长度。遍历字符数组并按规则放入对应行的时间复杂度是O(n)。将数组中的每个字符串连接起来的时间复杂度是O(numRows)。因此总体时间复杂度为O(n)。
空间复杂度
创建了一个长度为numRows的字符串数组rows所以额外的空间复杂度是O(numRows)。除此之外没有使用其他额外的空间。因此总体空间复杂度也是O(numRows)。
综上所述该解法的时间复杂度和空间复杂度都是O(n)其中n为字符串s的长度。
LeetCode运行结果 方法二数学规律
除了模拟方法外还可以使用数学规律来解决这个问题。
观察Z字形变换的规律可以发现以下几个关键点
第一行和最后一行中的字符之间的距离为周期性的即间隔为2 * numRows - 2。中间行的字符之间的距离有两个部分组成一个是上方的字符与下方的字符之间的距离为周期性的间隔同样为2 * numRows - 2。另一个是斜对角方向的字符与当前字符之间的距离为固定值为2 * numRows - 2 - 2 * i其中i为当前行的索引。对于原始字符串中每个字符的位置可以通过行索引和列索引来确定。
基于以上观察可以直接计算每个字符在变换后字符串中的位置然后将其按顺序放入结果字符串中。
class Solution {public String convert(String s, int numRows) {if (numRows 1 || s.length() numRows) {return s;}StringBuilder result new StringBuilder();int cycleLen 2 * numRows - 2;int n s.length();for (int i 0; i numRows; i) {for (int j 0; j i n; j cycleLen) {result.append(s.charAt(j i));if (i ! 0 i ! numRows - 1 j cycleLen - i n) {result.append(s.charAt(j cycleLen - i));}}}return result.toString();}
}
复杂度分析如下
时间复杂度
遍历每个字符并确定其位置的时间复杂度是O(n)其中n为字符串s的长度。在遍历过程中对于每个字符最多进行两次append操作。因此总体时间复杂度仍然为O(n)。
空间复杂度
只使用了常数级别的额外空间即StringBuilder中的空间。因此空间复杂度是O(1)。
综上所述使用数学规律的方法的时间复杂度和空间复杂度分别为O(n)和O(1)其中n为字符串s的长度。相比于模拟方法这种方法在空间复杂度上有优势因为不需要额外的数组来存储每一行的字符串。
LeetCode运行结果 方法三分组
除了前面介绍的方法还可以使用分组方法来完成Z字形变换。
具体步骤如下
创建一个长度为numRows的字符串数组rows用来存储每一行的字符。遍历原始字符串s按照特定的分组规则将每个字符放入对应的分组中。 第一组的长度为2 * numRows - 2。后续的每一组的长度也是2 * numRows - 2但是每个字符在分组中的位置会有所不同。 对于中间的行行索引1到numRows-2每个分组包含两个字符分别位于当前行和其对称行中。对于首尾两行行索引0和numRows-1每个分组只包含一个字符位于对应行中。遍历完成后将每一行的字符串按顺序拼接成最终的结果字符串。
class Solution {public String convert(String s, int numRows) {if (numRows 1 || s.length() numRows) {return s;}String[] rows new String[numRows];Arrays.fill(rows, );int groupSize 2 * numRows - 2;for (int i 0; i s.length(); i) {int remain i % groupSize;int row remain numRows ? remain : groupSize - remain;rows[row] s.charAt(i);}StringBuilder result new StringBuilder();for (String row : rows) {result.append(row);}return result.toString();}}
复杂度分析如下 时间复杂度 遍历整个字符串s的时间复杂度为O(n)。将每个字符放入对应分组的时间复杂度为O(1)。因此总的时间复杂度为O(n)。 空间复杂度 创建了一个大小为numRows的字符串数组rows因此空间复杂度为O(numRows) O(n)。这里假设numRows远小于n可以忽略。
LeetCode运行结果 第三题
题目来源
7. 整数反转 - 力扣LeetCode
题目内容 解决方法
方法一数学方法
要反转一个整数可以使用数学方法。
具体步骤如下 需要注意的是该代码假设输入的整数为32位有符号整数。如果输入的整数超过了范围或者溢出反转后的整数范围将返回0。
初始化一个变量 res 用于存储反转后的整数。进入循环当原始整数不为0时执行以下操作 通过取余运算获取原始整数的最后一位数字保存在 digit 中。检查反转后的整数是否有可能溢出如果溢出则返回0。具体的判断条件如下 如果 res 大于 Integer.MAX_VALUE / 10或者当 res 等于 Integer.MAX_VALUE / 10 且 digit 大于7则表示溢出返回0。如果 res 小于 Integer.MIN_VALUE / 10或者当 res 等于 Integer.MIN_VALUE / 10 且 digit 小于-8则表示溢出返回0。更新 res 的值将 res 乘以10并加上 digit。将原始整数除以10以便获取下一位数字。循环结束后返回 res即为反转后的整数。
class Solution {public int reverse(int x) {int res 0;while (x ! 0) {int digit x % 10;if (res Integer.MAX_VALUE / 10 || (res Integer.MAX_VALUE / 10 digit 7)) {return 0;}if (res Integer.MIN_VALUE / 10 || (res Integer.MIN_VALUE / 10 digit -8)) {return 0;}res res * 10 digit;x / 10;}return res;}
} 复杂度分析如下
这段代码的时间复杂度是 O(log|x|)其中 x 是输入的整数。在循环中每次都会将原始整数除以10因此循环的次数与输入的整数的位数相关。由于一个整数的位数大约为 log|x|以10为底所以循环的次数也大约为 log|x|。另外在循环内部执行的操作包括取余运算、比较和乘法操作这些操作的时间复杂度都可以忽略不计。因此整体的时间复杂度可以近似地看作 O(log|x|)。空间复杂度为 O(1)因为只使用了常数个变量来存储结果和临时值没有使用额外的数据结构。
LeetCode运行结果 方法二转换字符串
要实现整数反转的功能可以按照以下步骤进行
将输入的整数转换为字符串。判断整数是否为负数如果是负数则将符号标记下来并将整数转换为正数处理。将字符串逆序排列。将逆序后的字符串转换回整数。如果原整数为负数则将结果乘以-1。
class Solution {public int reverse(int x) {// 转换为字符串String str Integer.toString(x);// 判断是否为负数boolean isNegative false;if (str.charAt(0) -) {isNegative true;str str.substring(1); // 移除负号}// 逆序排列字符串StringBuilder sb new StringBuilder(str);sb.reverse();String reversedStr sb.toString();// 转换回整数long result Long.parseLong(reversedStr);// 处理溢出情况if (result Integer.MAX_VALUE || result Integer.MIN_VALUE) {return 0;}// 处理负数if (isNegative) {result * -1;}return (int)result;}
}
复杂度分析
时间复杂度分析
转换为字符串这个步骤的时间复杂度是O(log|x|)其中|x|是输入整数的绝对值。判断是否为负数这个步骤的时间复杂度是O(1)。逆序排列字符串使用StringBuilder的reverse方法时间复杂度为O(log|x|)。将逆序后的字符串转换为长整型使用Long.parseLong方法时间复杂度同样为O(log|x|)。处理溢出情况、处理负数这两个步骤的时间复杂度都是O(1)。返回结果同样也是O(1)的时间复杂度。
综上所述整体的时间复杂度可以视为O(log|x|)。
空间复杂度分析
字符串转换和逆序排列过程中会使用StringBuilder对象来构建字符串所以它的空间复杂度为O(log|x|)。其他变量的空间复杂度是常数级的不随输入规模变化。
因此整体的空间复杂度可以视为O(log|x|)。
需要注意的是这里的|x|是指输入整数的绝对值的位数。由于整数的位数在实际问题中通常是固定的因此我们可以将该算法的时间复杂度和空间复杂度视为O(1)。
LeetCode运行结果
