前言
本文属于特定的六道题目题解和调试代码。
正所谓磨刀不误砍柴功。下面我做这几篇文档对于涉及的题型或者数据结构的分析都很有帮助，贴出来仅供参考。
1 ✔ [69]x 的平方根 Easy 2022-12-28 101
2 ✔ [22]括号生成 Medium 2023-03-27 100
3 ✔ [93]复原IP地址 Medium 2023-03-12 98
4 ✔ [8]字符串转换整数 (atoi) Medium 2023-01-01 98
5 ✔ [41]缺失的第一个正数 Hard 2023-03-27 93
6 ✔ [239]滑动窗口最大值 Hard 2022-11-14 93
如何调试递归程序，有何技巧？
按照树形结构直观地打印出一棵二叉树、快速创建leetcode中树的结构(Java)
1 ✔ [69]x 的平方根 Easy 2022-12-28 101
//给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
//
// 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
//
// 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
//
//
//
// 示例 1：
//
//
//输入：x = 4
//输出：2
//
//
// 示例 2：
//
//
//输入：x = 8
//输出：2
//解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
//
//
//
//
// 提示：
//
//
// 0 <= x <= 2³¹ - 1
//
//
// Related Topics 数学 二分查找 👍 1297 👎 0
/*疑惑点：平方应该是从数字的0到1/2内的数字，然后通过双指针缩小范围，
感觉思路没有问题，不清楚为什么没有找到结果*/
解决疑惑点： midmid是一个很大的数字，超过了int的返回变成了负数导致。如果使用Long.valueOf(midmid) 也是不可以的，因为mid*mid之后已经是负数，然后再转化成Long类型也是没有效果的。
自测代码
public class P69_Sqrtx{
public static void main(String[] args) {
//测试代码
Solution solution = new P69_Sqrtx().new Solution();
System.out.println(solution.mySqrt(2147395599));
/*疑惑点：平方应该是从数字的0到1/2内的数字，然后通过双指针缩小范围，
感觉思路没有问题，不清楚为什么没有找到结果*/
}
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public int mySqrt(int x) {
if (x == 1) {
return 1;
}
int end = x/2;
int l = 0;
int r = x;
int res = -1;
while (l <= r){
int mid = l + (r - l) / 2;
Long i = (long)mid * mid;
if (i > x){
r = mid-1;
}else {
res = mid;
l = mid+1;
}
}
return res;
}
}
//leetcode submit region end(Prohibit modification and deletion)
}
提交代码
class Solution {
public int mySqrt(int x) {
if (x == 1) {
return 1;
}
int end = x/2;
int l = 0;
int r = x;
int res = -1;
while (l <= r){
int mid = l + (r - l) / 2;
Long i = (long)mid * mid;
if (i > x){
r = mid-1;
}else {
res = mid;
l = mid+1;
}
}
return res;
}
}
2 ✔ [22]括号生成 Medium 2023-03-27 100
//数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
//
//
//
// 示例 1：
//
//
//输入：n = 3
//输出：["((()))","(()())","(())()","()(())","()()()"]
//
//
// 示例 2：
//
//
//输入：n = 1
//输出：["()"]
//
//
//
//
// 提示：
//
//
// 1 <= n <= 8
//
//
// Related Topics 字符串 动态规划 回溯 👍 3168 👎 0
自测代码
public class P22_GenerateParentheses{
public static void main(String[] args) {
//测试代码
Solution solution = new P22_GenerateParentheses().new Solution();
System.out.println(solution.generateParenthesis(3));
/**/
}
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public List<String> generateParenthesis(int n) {
ArrayList<String> res = new ArrayList<>();
String data = new String();
generateStr(res,n,n,data);
return res;
}
public void generateStr(List<String> res,int l, int r,String data){
if (l == r && l == 0) {
res.add(data.toString());
return;
}
if (r == 0){
return;
}
if (l == 0) {
data = data+")";
generateStr(res,l,r-1,data);
data = data.substring(0, data.length() - 1);
}else {
data = data+"(";
generateStr(res,l-1,r,data);
data = data.substring(0, data.length() - 1);
if (l < r) {
data = data+")";
generateStr(res,l,r-1,data);
data = data.substring(0, data.length() - 1);
}
}
}
}
//leetcode submit region end(Prohibit modification and deletion)
}
提交代码
class Solution {
public List<String> generateParenthesis(int n) {
ArrayList<String> res = new ArrayList<>();
String data = new String();
generateStr(res,n,n,data);
return res;
}
public void generateStr(List<String> res,int l, int r,String data){
if (l == r && l == 0) {
res.add(data.toString());
return;
}
if (r == 0){
return;
}
if (l == 0) {
data = data+")";
generateStr(res,l,r-1,data);
data = data.substring(0, data.length() - 1);
}else {
data = data+"(";
generateStr(res,l-1,r,data);
data = data.substring(0, data.length() - 1);
if (l < r) {
data = data+")";
generateStr(res,l,r-1,data);
data = data.substring(0, data.length() - 1);
}
}
}
}
3 ✔ [93]复原IP地址 Medium 2023-03-12 98
//有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
//
//
// 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312"
//和 "192.168@1.1" 是 无效 IP 地址。
//
//
// 给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新
//排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
//
//
//
// 示例 1：
//
//
//输入：s = "25525511135"
//输出：["255.255.11.135","255.255.111.35"]
//
//
// 示例 2：
//
//
//输入：s = "0000"
//输出：["0.0.0.0"]
//
//
// 示例 3：
//
//
//输入：s = "101023"
//输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
//
//
//
//
// 提示：
//
//
// 1 <= s.length <= 20
// s 仅由数字组成
//
//
// Related Topics 字符串 回溯 👍 1183 👎 0
自测代码
public class P93_RestoreIpAddresses{
public static void main(String[] args) {
//测试代码
Solution solution = new P93_RestoreIpAddresses().new Solution();
List<String> strings = solution.restoreIpAddresses("0279245587303");
System.out.println(ArrayUtil.arrayListToString(strings));
// String data = "25525511135";
//
// String substring = data.substring(0,1);
// String substring1 = data.substring(1);
// System.out.println(substring1);
// System.out.println(substring);
}
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public List<String> restoreIpAddresses(String s) {
int len = s.length();
ArrayList<String> res = new ArrayList<>();
if (len < 4 || len > 12) {
return res;
}
subStr(s,3,"",res);
return res;
}
//输入：s = "25525511135"
//输出：["255.255.11.135","255.255.111.35"]
public void subStr(String data,int sum,String resTemp,ArrayList<String> res){
if (sum == 0){
if (restore(data)) {
resTemp += data;
res.add(resTemp);
}
return;
}
for (int i = 1 ; i <= 3 && i <= data.length() ; i++){
String substring = data.substring(0,i);
String substring1 = data.substring(i);
Boolean restore = restore(substring);
if (!restore) {
continue;
}else {
subStr(substring1,sum-1,resTemp+substring+".",res);
}
}
}
public Boolean restore(String data){
if (data.equals("")) {
return false;
}
int dataInt = Integer.parseInt(data);
if (!String.valueOf(dataInt).equals(data)) {
return false;
}
if (dataInt > 255) {
return false;
}
return true;
}
}
//leetcode submit region end(Prohibit modification and deletion)
}
提交代码
class Solution {
public List<String> restoreIpAddresses(String s) {
int len = s.length();
ArrayList<String> res = new ArrayList<>();
if (len < 4 || len > 12) {
return res;
}
subStr(s,3,"",res);
return res;
}
//输入：s = "25525511135"
//输出：["255.255.11.135","255.255.111.35"]
public void subStr(String data,int sum,String resTemp,ArrayList<String> res){
if (sum == 0){
if (restore(data)) {
resTemp += data;
res.add(resTemp);
}
return;
}
for (int i = 1 ; i <= 3 && i <= data.length() ; i++){
String substring = data.substring(0,i);
String substring1 = data.substring(i);
Boolean restore = restore(substring);
if (!restore) {
continue;
}else {
subStr(substring1,sum-1,resTemp+substring+".",res);
}
}
}
public Boolean restore(String data){
if (data.equals("")) {
return false;
}
int dataInt = Integer.parseInt(data);
if (!String.valueOf(dataInt).equals(data)) {
return false;
}
if (dataInt > 255) {
return false;
}
return true;
}
}
4 ✔ [8]字符串转换整数 (atoi) Medium 2023-01-01 98
//请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。
//
// 函数 myAtoi(string s) 的算法如下：
//
//
// 读入字符串并丢弃无用的前导空格
// 检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
// 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
// 将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤
//2 开始）。
// 如果整数数超过 32 位有符号整数范围 [−2³¹, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −2³¹ 的整数应该被固
//定为 −2³¹ ，大于 231 − 1 的整数应该被固定为 231 − 1 。
// 返回整数作为最终结果。
//
//
// 注意：
//
//
// 本题中的空白字符只包括空格字符 ' ' 。
// 除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。
//
//
//
//
// 示例 1：
//
//
//输入：s = "42"
//输出：42
//解释：加粗的字符串为已经读入的字符，插入符号是当前读取的字符。
//第 1 步："42"（当前没有读入字符，因为没有前导空格）
// ^
//第 2 步："42"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
// ^
//第 3 步："42"（读入 "42"）
// ^
//解析得到整数 42 。
//由于 "42" 在范围 [-2³¹, 2³¹ - 1] 内，最终结果为 42 。
//
// 示例 2：
//
//
//输入：s = " -42"
//输出：-42
//解释：
//第 1 步：" -42"（读入前导空格，但忽视掉）
// ^
//第 2 步：" -42"（读入 '-' 字符，所以结果应该是负数）
// ^
//第 3 步：" -42"（读入 "42"）
// ^
//解析得到整数 -42 。
//由于 "-42" 在范围 [-2³¹, 2³¹ - 1] 内，最终结果为 -42 。
//
//
// 示例 3：
//
//
//输入：s = "4193 with words"
//输出：4193
//解释：
//第 1 步："4193 with words"（当前没有读入字符，因为没有前导空格）
// ^
//第 2 步："4193 with words"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
// ^
//第 3 步："4193 with words"（读入 "4193"；由于下一个字符不是一个数字，所以读入停止）
// ^
//解析得到整数 4193 。
//由于 "4193" 在范围 [-2³¹, 2³¹ - 1] 内，最终结果为 4193 。
//
//
//
//
// 提示：
//
//
// 0 <= s.length <= 200
// s 由英文字母（大写和小写）、数字（0-9）、' '、'+'、'-' 和 '.' 组成
//
//
// Related Topics 字符串 👍 1645 👎 0
自测代码
public class P8_StringToIntegerAtoi{
public static void main(String[] args) {
//测试代码
Solution solution = new P8_StringToIntegerAtoi().new Solution();
System.out.println(Integer.MIN_VALUE);
System.out.println(solution.myAtoi("42"));
}
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public int myAtoi(String s) {
if (s == null || s.equals("")) {
return 0;
}
s = s.trim();
boolean one = false;
int sgin = 1;
StringBuffer stringBuffer = new StringBuffer();
for (int i = 0; i < s.length(); i++){
char c = s.charAt(i);
if (c == '-') {
sgin = -1;
}
while (i < s.length() && s.charAt(i) <= '9' && s.charAt(i) >= '0' ) {
stringBuffer.append(s.charAt(i));
i++;
}
if (c != '-' && c != '+') {
break;
}else {
if (one) {
break;
}
one = true;
}
}
int res = 0;
String str = stringBuffer.toString();
if (str.length() == 0) {
return 0;
}
try{
res = Integer.parseInt(str) * sgin;
}catch (Exception e){
if (sgin == 1) {
return Integer.MAX_VALUE;
}else {
return Integer.MIN_VALUE;
}
}
return res;
}
}
//leetcode submit region end(Prohibit modification and deletion)
}
提交代码
class Solution {
public int myAtoi(String s) {
if (s == null || s.equals("")) {
return 0;
}
s = s.trim();
boolean one = false;
int sgin = 1;
StringBuffer stringBuffer = new StringBuffer();
for (int i = 0; i < s.length(); i++){
char c = s.charAt(i);
if (c == '-') {
sgin = -1;
}
while (i < s.length() && s.charAt(i) <= '9' && s.charAt(i) >= '0' ) {
stringBuffer.append(s.charAt(i));
i++;
}
if (c != '-' && c != '+') {
break;
}else {
if (one) {
break;
}
one = true;
}
}
int res = 0;
String str = stringBuffer.toString();
if (str.length() == 0) {
return 0;
}
try{
res = Integer.parseInt(str) * sgin;
}catch (Exception e){
if (sgin == 1) {
return Integer.MAX_VALUE;
}else {
return Integer.MIN_VALUE;
}
}
return res;
}
}
5 ✔ [41]缺失的第一个正数 Hard 2023-03-27 93
//给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为
//O(n) 并且只使用常数级别额外空间的解决方案。
//
//
//
// 示例 1：
//
//
//输入：nums = [1,2,0]
//输出：3
//
//
// 示例 2：
//
//
//输入：nums = [3,4,-1,1]
//输出：2
//
//
// 示例 3：
//
//
//输入：nums = [7,8,9,11,12]
//输出：1
//
//
//
//
// 提示：
//
//
// 1 <= nums.length <= 5 * 10⁵
// -2³¹ <= nums[i] <= 2³¹ - 1
//
//
// Related Topics 数组 哈希表 👍 1785 👎 0
自测代码
public class P41_FirstMissingPositive{
public static void main(String[] args) {
//测试代码
Solution solution = new P41_FirstMissingPositive().new Solution();
System.out.println(solution.firstMissingPositive(ArrayUtil.StrToIntArray("[11,1,6,11,5,5,-6,9,-3,9,5,4,2,-8,16,-6,-4,2,3]")));
}
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public int firstMissingPositive(int[] nums) {
int len = nums.length;
if (len == 0) {
return 0;
}
int res = 0;
for (int i = 0; i < len; i++) {
int data = nums[i];
if (data < 1 || data >len){
nums[i] = 0;
}else if(data <= i){
int temp = data;
if (nums[i] == nums[nums[i]-1] && nums[i] -1 != i) {
nums[i] = 0;
}else {
nums[i] = nums[temp-1];
nums[temp-1] = temp;
i--;
}
}
while ( res <=i && nums[res] == res+1 ){
res++;
}
}
return res+1;
}
}
//leetcode submit region end(Prohibit modification and deletion)
}
提交代码
class Solution {
public int firstMissingPositive(int[] nums) {
int len = nums.length;
if (len == 0) {
return 0;
}
int res = 0;
for (int i = 0; i < len; i++) {
int data = nums[i];
if (data < 1 || data >len){
nums[i] = 0;
}else if(data <= i){
int temp = data;
if (nums[i] == nums[nums[i]-1] && nums[i] -1 != i) {
nums[i] = 0;
}else {
nums[i] = nums[temp-1];
nums[temp-1] = temp;
i--;
}
}
while ( res <=i && nums[res] == res+1 ){
res++;
}
}
return res+1;
}
}
6 ✔ [239]滑动窗口最大值 Hard 2022-11-14 93
//给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位
//。
//
// 返回 滑动窗口中的最大值 。
//
//
//
// 示例 1：
//
//
//输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
//输出：[3,3,5,5,6,7]
//解释：
//滑动窗口的位置 最大值
//--------------- -----
//[1 3 -1] -3 5 3 6 7 3
// 1 [3 -1 -3] 5 3 6 7 3
// 1 3 [-1 -3 5] 3 6 7 5
// 1 3 -1 [-3 5 3] 6 7 5
// 1 3 -1 -3 [5 3 6] 7 6
// 1 3 -1 -3 5 [3 6 7] 7
//
//
// 示例 2：
//
//
//输入：nums = [1], k = 1
//输出：[1]
//
//
//
//
// 提示：
//
//
// 1 <= nums.length <= 10⁵
// -10⁴ <= nums[i] <= 10⁴
// 1 <= k <= nums.length
//
//
// Related Topics 队列 数组 滑动窗口 单调队列 堆（优先队列） 👍 2228 👎 0
自测代码
public class P239_SlidingWindowMaximum{
public static void main(String[] args) {
//测试代码
Solution solution = new P239_SlidingWindowMaximum().new Solution();
solution.maxSlidingWindow(ArrayUtil.StrToIntArray("[1,3,-1,-3,5,3,6,7]"),3);
}
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
ArrayList<Integer> res = new ArrayList<>();
LinkedList<Integer> window = new LinkedList<>();
int len = nums.length;
for (int i = 0; i < len; i++) {
while (!window.isEmpty() && nums[window.getLast()] < nums[i]){
window.pollLast();
}
while(!window.isEmpty() && window.getFirst() <= i - k ){
window.pollFirst();
}
window.addLast(i);
if (i+1 >= k ) {
res.add(nums[window.getFirst()]);
}
}
int[] ress = new int[res.size()];
for (int i = 0; i < res.size(); i++) {
ress[i] = res.get(i);
}
return ress;
}
}
//leetcode submit region end(Prohibit modification and deletion)
}
提交代码
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
ArrayList<Integer> res = new ArrayList<>();
LinkedList<Integer> window = new LinkedList<>();
int len = nums.length;
for (int i = 0; i < len; i++) {
while (!window.isEmpty() && nums[window.getLast()] < nums[i]){
window.pollLast();
}
while(!window.isEmpty() && window.getFirst() <= i - k ){
window.pollFirst();
}
window.addLast(i);
if (i+1 >= k ) {
res.add(nums[window.getFirst()]);
}
}
int[] ress = new int[res.size()];
for (int i = 0; i < res.size(); i++) {
ress[i] = res.get(i);
}
return ress;
}
}
发表于 2023-4-6 09:55
|
发表于 2023-4-8 09:52
