首页
壁纸
留言板
友链
更多
统计归档
Search
1
TensorBoard:训练日志及网络结构可视化工具
12,591 阅读
2
主板开机跳线接线图【F_PANEL接线图】
7,205 阅读
3
Linux使用V2Ray 原生客户端
6,331 阅读
4
移动光猫获取超级密码&开启公网ipv6
5,057 阅读
5
NVIDIA 显卡限制功率
3,162 阅读
好物分享
实用教程
linux使用
wincmd
学习笔记
mysql
java学习
nginx
综合面试题
大数据
网络知识
linux
放码过来
python
javascript
java
opencv
蓝桥杯
leetcode
深度学习
开源模型
相关知识
数据集和工具
模型轻量化
语音识别
计算机视觉
杂七杂八
硬件科普
主机安全
嵌入式设备
其它
bug处理
登录
/
注册
Search
标签搜索
好物分享
学习笔记
linux
MySQL
nvidia
typero
内网穿透
webdav
vps
java
cudann
gcc
cuda
树莓派
CNN
图像去雾
ssh安全
nps
暗通道先验
阿里云
jupiter
累计撰写
354
篇文章
累计收到
72
条评论
首页
栏目
好物分享
实用教程
linux使用
wincmd
学习笔记
mysql
java学习
nginx
综合面试题
大数据
网络知识
linux
放码过来
python
javascript
java
opencv
蓝桥杯
leetcode
深度学习
开源模型
相关知识
数据集和工具
模型轻量化
语音识别
计算机视觉
杂七杂八
硬件科普
主机安全
嵌入式设备
其它
bug处理
页面
壁纸
留言板
友链
统计归档
搜索到
17
篇与
的结果
2022-06-10
leetcode|中等:剑指 Offer 35. 复杂链表的复制
1.题目请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。示例 1:输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]示例 2:输入:head = [[1,1],[2,1]] 输出:[[1,1],[2,1]]示例 3:输入:head = [[3,null],[3,0],[3,null]] 输出:[[3,null],[3,0],[3,null]]示例 4:输入:head = [] 输出:[] 解释:给定的链表为空(空指针),因此返回 null。提示:-10000 <= Node.val <= 10000Node.random 为空(null)或指向链表中的节点。节点数目不超过 1000 。2. 题解2.1 思路分析思路1:哈希表法 利用哈希表的查询特点,考虑构建 原链表节点 和 新链表对应节点 的键值对映射关系,再遍历构建新链表各节点的 next 和 random 引用指向即可。2.2 代码实现思路1:哈希表法/* // Definition for a Node. class Node { int val; Node next; Node random; public Node(int val) { this.val = val; this.next = null; this.random = null; } } */ class Solution { public Node copyRandomList(Node head) { if(head == null) return null; Node cur = head; // 保存头节点,用于遍历链表 Map<Node,Node> map = new HashMap<Node,Node>();//用于保存新旧节点之间的关系 // 复制各节点,并建立 “原节点 -> 新节点” 的 Map 映射 while (cur!=null){ map.put(cur,new Node(cur.val)); cur = cur.next; } // 补全next和random的映射关系 cur = head; while (cur!=null){ map.get(cur).next = map.get(cur.next); map.get(cur).random = map.get(cur.random); cur = cur.next; } return map.get(head); } }2.3 提交结果提交结果执行用时内存消耗语言提交时间备注通过0 ms41 MBJava2022/06/10 15:18添加备注参考资料https://leetcode.cn/problems/fu-za-lian-biao-de-fu-zhi-lcof
2022年06月10日
660 阅读
0 评论
0 点赞
2022-06-10
leetcode|简单:剑指 Offer 24. 反转链表
1.题目定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。示例:输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL限制:0 <= 节点个数 <= 50002. 题解2.1 思路分析思路1: 本题比较简单直接上代码2.2 代码实现思路1/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseList(ListNode head) { if(head==null || head.next==null){ return head; } ListNode newHead = head.next; ListNode nextNewHead = newHead.next; head.next = null; while (nextNewHead!=null){ newHead.next = head; head = newHead; newHead = nextNewHead; nextNewHead = nextNewHead.next; } newHead.next = head; return newHead; } }思路1优化/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseList(ListNode head) { ListNode pre = null,cur=head; while (cur!=null){ ListNode tmp = cur.next; cur.next=pre; pre=cur; cur = tmp; } return pre; } }2.3 提交结果提交结果执行用时内存消耗语言提交时间备注通过0 ms41 MBJava2022/06/10 11:15添加备注提交结果执行用时内存消耗语言提交时间备注通过0 ms40.8 MBJava2022/06/10 11:32添加备注参考资料https://leetcode.cn/problems/fan-zhuan-lian-biao-lcof
2022年06月10日
598 阅读
0 评论
0 点赞
2022-06-10
leetcode|简单:剑指 Offer 06. 从尾到头打印链表
1.题目输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。示例 1:输入:head = [1,3,2] 输出:[2,3,1]限制:0 <= 链表长度 <= 100002. 题解2.1 思路分析统计链表长度申请数组并逐一填入链表元素反转数组2.2 代码实现/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public int[] reversePrint(ListNode head) { // 1.统计链表长度 int listLen = 0; ListNode tmp = head; while (tmp!=null){ listLen++; tmp = tmp.next; } // 2.申请数组并逐一填入链表元素 int[] res = new int[listLen]; tmp = head; int resIndex=0; while (tmp!=null){ res[resIndex++] = tmp.val; tmp = tmp.next; } // 3.反转数组 for (int i = 0; i < listLen/2; i++) { int tmpItem = res[i]; res[i] = res[listLen-1-i]; res[listLen-1-i] = tmpItem; } return res; } }2.3 提交结果提交结果执行用时内存消耗语言提交时间备注通过0 ms42.1 MBJava2022/06/10 10:30添加备注参考资料https://leetcode.cn/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof
2022年06月10日
494 阅读
0 评论
0 点赞
2022-06-10
leetcode|简单:剑指 Offer 09. 用两个栈实现队列
1.题目用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 )示例 1:输入: ["CQueue","appendTail","deleteHead","deleteHead"] [[],[3],[],[]] 输出:[null,null,3,-1]示例 2:输入: ["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"] [[],[],[5],[2],[],[]] 输出:[null,-1,null,null,5,2]提示:1 <= values <= 10000最多会对 appendTail、deleteHead 进行 10000 次调用2. 题解2.1 思路分析栈无法实现队列功能: 栈底元素(对应队首元素)无法直接删除,需要将上方所有元素出栈。双栈可实现列表倒序: 设有含三个元素的栈 A\=[1,2,3]和空栈 B\=[]。若循环执行 A元素出栈并添加入栈 B ,直到栈 A为空,则 A\=[], B\=[3,2,1],即 栈 B 元素实现栈 A 元素倒序 。利用栈 B 删除队首元素: 倒序后,B 执行出栈则相当于删除了 A 的栈底元素,即对应队首元素。可以设计栈 A 用于加入队尾操作,栈 B 用于将元素倒序,从而实现删除队首元素。加入队尾 appendTail()函数: 将数字 val 加入栈 A 即可。删除队首deleteHead()函数: 有以下三种情况。当栈 B 不为空: B中仍有已完成倒序的元素,因此直接返回 B 的栈顶元素。否则,当 A 为空: 即两个栈都为空,无元素,因此返回 −1。否则: 将栈 A 元素全部转移至栈 B 中,实现元素倒序,并返回栈 B 的栈顶元素。2.2 代码实现思路1:class CQueue { Stack<Integer> A,B; public CQueue() { A = new Stack<Integer>(); B = new Stack<Integer>(); } public void appendTail(int value) { A.push(value); } public int deleteHead() { if(!B.empty()){ return B.pop(); }else if(A.empty()){ return -1; }else { // 把栈B中的元素全部倒序移入栈A while (!A.empty()){ B.push(A.pop()); } return B.pop(); } } } /** * Your CQueue object will be instantiated and called as such: * CQueue obj = new CQueue(); * obj.appendTail(value); * int param_2 = obj.deleteHead(); */2.3 提交结果提交结果执行用时内存消耗语言提交时间备注通过72 ms47.8 MBJava2022/06/09 10:30添加备注参考资料https://leetcode.cn/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcofhttps://leetcode.cn/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/solution/mian-shi-ti-09-yong-liang-ge-zhan-shi-xian-dui-l-2/
2022年06月10日
538 阅读
0 评论
0 点赞
2022-06-09
leetcode|简单:剑指 Offer 30. 包含min函数的栈
1.题目定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min、push 及 pop 的时间复杂度都是 O(1)。示例: MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.min(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.min(); --> 返回 -2.提示:各函数的调用总次数不超过 20000 次2. 题解2.1 思路分析思路1: 使用辅助栈来维护最小值 只需要对现有的栈功能添加一个用于维护最小值的辅助栈minStack(普通栈) 每次push的时候都往minStack中push当前的最小值(由minStack.peek()和待push元素x得出) 每次pop的时候minStack也执行相应的pop 则每次调用min的时候只需要返回minStack.peek()即可2.2 代码实现思路1:使用辅助栈来维护最小值import java.util.Stack; class MinStack { Stack<Integer> stack; Stack<Integer> minStack; /** initialize your data structure here. */ public MinStack() { stack = new Stack<Integer>(); minStack = new Stack<Integer>(); } public void push(int x) { // push更新min if(minStack.empty()) { minStack.push(x); }else { int min = minStack.peek()<x?minStack.peek():x; minStack.push(min); } stack.push(x); } public void pop() { // pop更新min minStack.pop(); stack.pop(); } public int top() { return stack.peek(); } public int min() { return minStack.peek(); } } /** * Your MinStack object will be instantiated and called as such: * MinStack obj = new MinStack(); * obj.push(x); * obj.pop(); * int param_3 = obj.top(); * int param_4 = obj.min(); */2.3 提交结果提交结果执行用时内存消耗语言提交时间备注通过14 ms43.4 MBJava2022/06/09 10:54添加备注参考资料https://leetcode.cn/problems/bao-han-minhan-shu-de-zhan-lcof
2022年06月09日
622 阅读
0 评论
0 点赞
2022-06-08
leetcode|困难:4. 寻找两个正序数组的中位数
1.题目给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。算法的时间复杂度应该为 O(log (m+n)) 。示例 1:输入:nums1 = [1,3], nums2 = [2] 输出:2.00000 解释:合并数组 = [1,2,3] ,中位数 2示例 2:输入:nums1 = [1,2], nums2 = [3,4] 输出:2.50000 解释:合并数组 = [1,2,3,4] ,中位数 (2 + 3) / 2 = 2.5提示:nums1.length == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000$-10^6$ <= nums1[i], nums2[i] <= $10^6$2. 题解2.1 思路分析思路1: 确定中位数的组成部分midLeft和midRight,总数为奇数的midLeft=midRight 通过利用寻找第k小的数的算法来锁定midLeft和midRight寻找第k小的数算法由于数列是有序的,其实我们完全可以一半儿一半儿的排除。假设我们要找第 k 小数,我们可以每次循环排除掉 k/2 个数。看下边一个例子。假设我们要找第 7 小的数字。我们比较两个数组的第 k/2 个数字,如果 k 是奇数,向下取整。也就是比较第 3 个数字,上边数组中的 4 和下边数组中的 3,如果哪个小,就表明该数组的前 k/2 个数字都不是第 k 小数字,所以可以排除。也就是 1,2,3 这三个数字不可能是第 7 小的数字,我们可以把它排除掉。将 1349和 45678910 两个数组作为新的数组进行比较。更一般的情况 A[1] ,A[2] ,A[3],A[k/2] ... ,B[1],B[2],B[3],B[k/2] ... ,如果 A[k/2]<B[k/2] ,那么A[1],A[2],A[3],A[k/2]都不可能是第 k 小的数字。A 数组中比 A[k/2] 小的数有 k/2-1 个,B 数组中,B[k/2] 比 A[k/2] 小,假设 B[k/2] 前边的数字都比 A[k/2] 小,也只有 k/2-1 个,所以比 A[k/2] 小的数字最多有 k/1-1+k/2-1=k-2个,所以 A[k/2] 最多是第 k-1 小的数。而比 A[k/2] 小的数更不可能是第 k 小的数了,所以可以把它们排除。橙色的部分表示已经去掉的数字。由于我们已经排除掉了 3 个数字,就是这 3 个数字一定在最前边,所以在两个新数组中,我们只需要找第 7 - 3 = 4 小的数字就可以了,也就是 k = 4。此时两个数组,比较第 2 个数字,3 < 5,所以我们可以把小的那个数组中的 1 ,3 排除掉了。我们又排除掉 2 个数字,所以现在找第 4 - 2 = 2 小的数字就可以了。此时比较两个数组中的第 k / 2 = 1 个数,4 == 4,怎么办呢?由于两个数相等,所以我们无论去掉哪个数组中的都行,因为去掉 1 个总会保留 1 个的,所以没有影响。为了统一,我们就假设 4 > 4 吧,所以此时将下边的 4 去掉。由于又去掉 1 个数字,此时我们要找第 1 小的数字,所以只需判断两个数组中第一个数字哪个小就可以了,也就是 4。所以第 7 小的数字是 4。我们每次都是取 k/2 的数进行比较,有时候可能会遇到数组长度小于 k/2的时候。此时 k / 2 等于 3,而上边的数组长度是 2,我们此时将箭头指向它的末尾就可以了。这样的话,由于 2 < 3,所以就会导致上边的数组 1,2 都被排除。造成下边的情况。由于 2 个元素被排除,所以此时 k = 5,又由于上边的数组已经空了,我们只需要返回下边的数组的第 5 个数字就可以了。从上边可以看到,无论是找第奇数个还是第偶数个数字,对我们的算法并没有影响,而且在算法进行中,k 的值都有可能从奇数变为偶数,最终都会变为 1 或者由于一个数组空了,直接返回结果。所以我们采用递归的思路,为了防止数组长度小于 k/2,所以每次比较 min(k/2,len(数组) 对应的数字,把小的那个对应的数组的数字排除,将两个新数组进入递归,并且 k 要减去排除的数字的个数。递归出口就是当 k=1 或者其中一个数字长度是 0 了。2.2 代码实现思路1:利用第k小的数来寻找中位数class Solution { private int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) { int len1 = end1 - start1 + 1; // 计算数组1的剩余部分的长度 int len2 = end2 - start2 + 1; // 计算数组2的剩余部分的长度 // 递归出口 // 让 len1 的长度小于 len2,这样就能保证如果有数组空了,一定是 len1 if (len1 > len2) return getKth(nums2, start2, end2, nums1, start1, end1, k); // 当其中一个数组都消耗完 if (len1 == 0) return nums2[start2 + k - 1]; // k=1的边界情况 if (k == 1) return Math.min(nums1[start1], nums2[start2]); // 迁移探索k/2 int i = start1 + Math.min(len1, k / 2) - 1; int j = start2 + Math.min(len2, k / 2) - 1; // 缩小探索空间 if (nums1[i] > nums2[j]) { return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1)); } else { return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1)); } } public double findMedianSortedArrays(int[] nums1, int[] nums2) { int nums1Len = nums1.length; int nums2Len = nums2.length; // 计算中位数的位置 int midLeftIndex = (nums1Len + nums2Len -1) / 2; int midRightIndex = (nums1Len + nums2Len) / 2; // 用寻找第k小的数的算法来找到 中位数的midLeft 和 midRight int midLeft = getKth(nums1, 0, nums1Len - 1, nums2, 0, nums2Len - 1, midLeftIndex+1); int midRight = getKth(nums1, 0, nums1Len - 1, nums2, 0, nums2Len - 1, midRightIndex+1); // 计算中位数 double res = (midLeft+midRight) * 0.5; return res; } public static void main(String[] args) { Solution solution = new Solution(); int[] nums1 = {1,2}; int[] nums2 = {4}; Double res =solution.findMedianSortedArrays(nums1,nums2); System.out.println(res); } }2.3 提交结果提交结果执行用时内存消耗语言提交时间备注通过1 ms42.4 MBJava2022/06/08 21:12添加备注参考资料https://leetcode.cn/problems/median-of-two-sorted-arrayshttps://leetcode.cn/problems/median-of-two-sorted-arrays/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-2/
2022年06月08日
634 阅读
0 评论
0 点赞
2022-06-05
leetcode|中等:43. 字符串相乘
1.题目给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们的乘积也表示为字符串形式。示例 1:输入: num1 = "2", num2 = "3" 输出: "6"示例 2:输入: num1 = "123", num2 = "456" 输出: "56088"提示:1 <= num1.length, num2.length <= 200num1 和 num2 只能由数字组成。num1 和 num2 都不包含任何前导零,除了数字0本身。2. 题解2.1 思路分析思路1:题目比较简单 分析乘法运算过程并手动进行模拟即可2.2 代码实现思路1:手动模拟乘法计算过程import java.util.Arrays; class Solution { public String multiply(String num1, String num2) { if(num1.equals("0")||num2.equals("0")){ return "0"; } // 计算res的最大可能长度 int maxResLen = num1.length()*num2.length()+2; int[] res = new int[maxResLen]; for (int i = 0; i < maxResLen; i++) { res[i] = 0; } // String num1 --> num1BitList int[] num1BitList = new int[num1.length()]; for (int i = 0; i < num1.length(); i++) { num1BitList[num1.length()-1-i] = num1.charAt(num1.length()-1-i)-'0'; } // String num2 --> num2BitList int[] num2BitList = new int[num2.length()]; for (int i = 0; i < num2.length(); i++) { num2BitList[num2.length()-1-i] = num2.charAt(num2.length()-1-i)-'0'; } // cal num1 * num2 for (int i = 0; i < num1.length(); i++) { for (int j = 0; j < num2.length(); j++) { res[maxResLen-1-i-j] += num1BitList[num1.length()-1-i]*num2BitList[num2.length()-1-j]; } } // handle bit overflow for (int i = maxResLen-1; i >= 0; i--) { int tmp = res[i]; res[i] = 0; int offset = 0; while (tmp>0){ res[i-offset] += tmp%10; offset++; tmp/=10; } } // int[] res --> String StringBuilder sb = new StringBuilder(); boolean beginFlag = false; for (int i = 0; i < maxResLen; i++) { if(res[i]==0&&beginFlag==false){ continue; }else { beginFlag = true; } sb.append(res[i]); } return sb.toString(); } public static void main(String[] args) { Solution solution = new Solution(); String num1 = "123"; String num2 = "456"; String res =solution.multiply(num1,num2); System.out.println(res); } }2.3 提交结果提交结果执行用时内存消耗语言提交时间备注通过3 ms41.4 MBJava2022/06/05 21:01添加备注参考资料https://leetcode.cn/problems/multiply-strings/
2022年06月05日
471 阅读
0 评论
0 点赞
2022-04-27
leetcode|中等:36. 有效的数独
1.题目请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ,验证已经填入的数字是否有效即可。数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。(请参考示例图)注意:一个有效的数独(部分已被填充)不一定是可解的。只需要根据以上规则,验证已经填入的数字是否有效即可。空白格用 '.' 表示。示例 1:输入:board = [["5","3",".",".","7",".",".",".","."] ,["6",".",".","1","9","5",".",".","."] ,[".","9","8",".",".",".",".","6","."] ,["8",".",".",".","6",".",".",".","3"] ,["4",".",".","8",".","3",".",".","1"] ,["7",".",".",".","2",".",".",".","6"] ,[".","6",".",".",".",".","2","8","."] ,[".",".",".","4","1","9",".",".","5"] ,[".",".",".",".","8",".",".","7","9"]] 输出:true示例 2:输入:board = [["8","3",".",".","7",".",".",".","."] ,["6",".",".","1","9","5",".",".","."] ,[".","9","8",".",".",".",".","6","."] ,["8",".",".",".","6",".",".",".","3"] ,["4",".",".","8",".","3",".",".","1"] ,["7",".",".",".","2",".",".",".","6"] ,[".","6",".",".",".",".","2","8","."] ,[".",".",".","4","1","9",".",".","5"] ,[".",".",".",".","8",".",".","7","9"]] 输出:false 解释:除了第一行的第一个数字从 5 改为 8 以外,空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。提示:board.length == 9board[i].length == 9board[i][j] 是一位数字(1-9)或者 '.'2. 题解2.1 思路分析思路1:题目比较简单 暴力遍历即可2.2 代码实现思路1:class Solution { public boolean isValidSudoku(char[][] board) { // 0.计数数组 int[] counter = new int[9]; // 1.数字 1-9 在每一行只能出现一次。 for (int i = 0; i < 9; i++) { Arrays.fill(counter,0); for (int j = 0; j < 9; j++) { if(board[i][j]!='.'){ int index = board[i][j]-'1'; counter[index]++; if(counter[index]>1){ return false; } } } } // 2.数字 1-9 在每一列只能出现一次。 for (int i = 0; i < 9; i++) { Arrays.fill(counter,0); for (int j = 0; j < 9; j++) { if(board[j][i]!='.'){ int index = board[j][i]-'1'; counter[index]++; if(counter[index]>1){ return false; } } } } // 3.数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { Arrays.fill(counter,0); int x_offset = 3*i; int y_offset = 3*j; for (int k = 0; k < 3; k++) { for (int l = 0; l < 3; l++) { if(board[x_offset+k][y_offset+l]!='.'){ int index = board[x_offset+k][y_offset+l]-'1'; counter[index]++; if(counter[index]>1){ return false; } } } } } } return true; } }2.3 提交结果提交结果执行用时内存消耗语言提交时间备注通过1 ms40.8 MBJava2022/04/27 19:31添加备注参考资料https://leetcode-cn.com/problems/valid-sudoku/
2022年04月27日
678 阅读
0 评论
0 点赞
2022-04-27
leetcode|中等:31. 下一个排列
1.题目整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。例如,arr = [1,2,3] ,以下这些都可以视作 arr 的排列:[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地,如果数组的所有排列根据其字典顺序从小到大排列在一个容器中,那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列,那么这个数组必须重排为字典序最小的排列(即,其元素按升序排列)。例如,arr = [1,2,3] 的下一个排列是 [1,3,2] 。类似地,arr = [2,3,1] 的下一个排列是 [3,1,2] 。而 arr = [3,2,1] 的下一个排列是 [1,2,3] ,因为 [3,2,1] 不存在一个字典序更大的排列。给你一个整数数组 nums ,找出 nums 的下一个排列。必须 原地 修改,只允许使用额外常数空间。2. 题解2.1 思路分析思路1: 1.倒序遍历数组, 找到第一个前一个数比后一个数小的位置(即nums[i] < nums[i+1]); firstIndex = i 2.这个时候我们不能直接把后一个数nums[i+1] 跟前一个数nums[i]交换就完事了; 还应该从nums[i+1]-->数组末尾这一段的数据中 找出最优的那个值 如何最优? 即比nums[i]稍微大那么一丢丢的数, 也就是 nums[i+1]-->数组末尾中, 比nums[i]大的数中最小的那个值 下标记为secondeIndex 3.找到之后, 跟num[i]交换, 这还不算是下一个排列, num[i]后面的数值还不够小, 所以还应当对 nums[i+1]-->数组末尾 进升序排列 eg:nums = [1,2,7,4,3,1], 1.倒序遍历数组, 找出第一组 前一个数比后一个数小的两个数 即[2,7] 2.2所处的这个位置就是需要找出比它稍微大的数的位置; 3.我们从[7,4,3,1]中找出比2大的数中的最小值, 也就是3, 找到后跟2交换即可; 当然了, 如果没找到的话, 直接跳到第5步, 直接升序排列输出. 4.目前nums=[1,3,7,4,2,1], 明显可以看出来还不算下一个排列 5.对3后面的数, 升序排列, 即最终结果: nums = [1,3,1,2,4,7]2.2 代码实现思路1:import java.util.*; public class Solution { public void nextPermutation(int[] nums) { // 1.倒序遍历数组,找到第一个满足nums[i] < nums[i+1]的位置 for (int firstIndex = nums.length-2; firstIndex >=0; firstIndex--) { if(nums[firstIndex]<nums[firstIndex+1]){ int secondeIndex = firstIndex+1; // 2.在 nums[i+1]-->数组末尾 找比nums[i]大的数中最小的那个值 for (int i = secondeIndex+1; i < nums.length; i++) { if(nums[i]>nums[firstIndex]&&nums[i]<nums[secondeIndex]){ secondeIndex = i; } } // 3.交换nums[firstIndex]和nums[secondeIndex] int temp = nums[secondeIndex]; nums[secondeIndex] = nums[firstIndex]; nums[firstIndex] = temp; // 4.对nums[firstIndex+1]之后的数进行升序排列 Arrays.sort(nums,firstIndex+1,nums.length); return; } } // 5.如果没找到直接升序排列并返回 Arrays.sort(nums); return; } public static void main(String[] args) { Solution solution = new Solution(); int[] nums = new int[]{1,3,2}; solution.nextPermutation(nums); System.out.println(Arrays.toString(nums)); } } 2.3 提交结果提交结果执行用时内存消耗语言提交时间备注通过1 ms41.8 MBJava2022/04/27 18:36添加备注参考资料https://leetcode-cn.com/problems/next-permutation/
2022年04月27日
661 阅读
0 评论
0 点赞
2022-04-26
leetcode|困难:30. 串联所有单词的子串
leetcode|困难:30. 串联所有单词的子串1.题目给定一个字符串 s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。注意子串要与 words 中的单词完全匹配,中间不能有其他字符 ,但不需要考虑 words 中单词串联的顺序。示例 1:输入:s = "barfoothefoobarman", words = ["foo","bar"] 输出:[0,9] 解释: 从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。 输出的顺序不重要, [9,0] 也是有效答案。示例 2:输入:s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"] 输出:[]示例 3:输入:s = "barfoofoobarthefoobarman", words = ["bar","foo","the"] 输出:[6,9,12]提示:1 <= s.length <= 104s 由小写英文字母组成1 <= words.length <= 50001 <= words[i].length <= 30words[i] 由小写英文字母组成2. 题解2.1 思路分析思路1:滑动窗口+词频统计 对words进行词频统计 然后以words包含的所有字符数作为窗口大小进行滑动+窗口词频统计 判断词频是否相等并记录相对的位置 思路2:#TODO 借鉴KMP对思路1进行优化 避免进行一些冗余比较2.2 代码实现思路1:滑动窗口+词频统计class Solution { public List<Integer> findSubstring(String s, String[] words) { List<Integer> res = new ArrayList<>(); // 记录下来每个单词的长度和单词的总长度 int wordLen = words[0].length(); int allWordLen = words.length*wordLen; // 统计words的词频 Map<String,Integer> wordFrequnce = new HashMap<>(); for (int i = 0; i < words.length; i++) { if(!wordFrequnce.containsKey(words[i])) { wordFrequnce.put(words[i], 1); }else { wordFrequnce.replace(words[i], wordFrequnce.get(words[i])+1); } } // 采用滑动窗口进行遍历,每次滑动一个字符 for (int i = 0; i <= s.length()-allWordLen; i++) { // 统计滑动窗口内的词频 Map<String,Integer> winWordFrequnce = new HashMap<>(); for (int j = 0; j < allWordLen; j+=wordLen) { String tmpWord = s.substring(i+j,i+j+wordLen); if(!winWordFrequnce.containsKey(tmpWord)) { winWordFrequnce.put(tmpWord, 1); }else { winWordFrequnce.replace(tmpWord, winWordFrequnce.get(tmpWord)+1); } } // 判断二者的词频是否一致 boolean sameFlag = winWordFrequnce.equals(wordFrequnce); // 将开始所以加入到res if(sameFlag){ res.add(i); } } return res; } }2.3 提交结果提交结果执行用时内存消耗语言提交时间备注通过247 ms42.2 MBJava2022/04/26 13:56添加备注参考资料https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words
2022年04月26日
690 阅读
0 评论
0 点赞
2022-04-26
leetcode|中等:29. 两数相除
1.题目给定两个整数,被除数 dividend 和除数 divisor。将两数相除,要求不使用乘法、除法和 mod 运算符。返回被除数 dividend 除以除数 divisor 得到的商。整数除法的结果应当截去(truncate)其小数部分,例如:truncate(8.345) = 8 以及 truncate(-2.7335) = -2示例 1:输入: dividend = 10, divisor = 3 输出: 3 解释: 10/3 = truncate(3.33333..) = truncate(3) = 3示例 2:输入: dividend = 7, divisor = -3 输出: -2 解释: 7/-3 = truncate(-2.33333..) = -2提示:被除数和除数均为 32 位有符号整数。除数不为 0。假设我们的环境只能存储 32 位有符号整数,其数值范围是 $[−2^{31}, 2^{31} − 1]$。本题中,如果除法结果溢出,则返回 $2^{31} − 1$。2. 题解2.1 思路分析思路1:用减法来模拟乘法 O(n)会运行超时 思路2: 思路1优化:借鉴计算机网络的流量拥塞控制机制,对被除数进行快速倍增2.2 代码实现思路1:用减法来模拟乘法public class Solution { public int divide(int dividend, int divisor) { // 解决计算结果上溢的问题 if(dividend==Integer.MIN_VALUE&&divisor==-1){ return Integer.MAX_VALUE; } // 判断结果的正负并把负数取绝对值+类型提升int-->long System.out.println("dividend="+dividend+",divisor="+divisor); boolean positiveFlag = true; long dividendLong = dividend; long divisorLong = divisor; if(dividend<0){ positiveFlag = !positiveFlag; dividendLong = -(long)dividend; } if(divisor<0){ positiveFlag = !positiveFlag; divisorLong = -(long)divisor; } System.out.println("dividendLong="+dividendLong+",divisorLong="+divisorLong); // 用减法模拟乘法 long res = 0; while (dividendLong>=divisorLong){ dividendLong -= divisorLong; res++; } // 结果符号修正 res = positiveFlag?res:-res; return (int)res; } public static void main(String[] args) { Solution solution = new Solution(); int in = 3; System.out.println(solution.divide(Integer.MIN_VALUE,3)); } }思路2: 思路1优化:借鉴计算机网络的流量拥塞控制机制,对被除数进行快速倍增public class Solution { public int divide(int dividend, int divisor) { // 解决计算结果上溢的问题 if(dividend==Integer.MIN_VALUE&&divisor==-1){ return Integer.MAX_VALUE; } // 判断结果的正负并把负数取绝对值+类型提升int-->long boolean positiveFlag = true; long dividendLong = dividend; long divisorLong = divisor; if(dividend<0){ positiveFlag = !positiveFlag; dividendLong = -(long)dividend; } if(divisor<0){ positiveFlag = !positiveFlag; divisorLong = -(long)divisor; } // 用减法模拟乘法+快速倍乘 long res = 0; while (dividendLong>=divisorLong) { long base = divisorLong; while (dividendLong >= base) { dividendLong -= base; res += (base/divisorLong); base *= 2; } } // 结果符号修正 res = positiveFlag?res:-res; return (int)res; } public static void main(String[] args) { Solution solution = new Solution(); int in = 3; System.out.println(solution.divide(Integer.MIN_VALUE,2)); } }2.3 提交结果思路1提交结果执行用时内存消耗语言提交时间备注超出时间限制N/AN/AJava2022/04/26 10:10添加备注思路2提交结果执行用时内存消耗语言提交时间备注通过1 ms38.5 MBJava2022/04/26 10:29添加备注参考资料https://leetcode-cn.com/problems/divide-two-integers/
2022年04月26日
578 阅读
0 评论
0 点赞
2022-04-25
leetcode|中等:22. 括号生成
1.题目数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。示例 1:输入:n = 3 输出:["((()))","(()())","(())()","()(())","()()()"]示例 2:输入:n = 1 输出:["()"]提示:1 <= n <= 82. 题解2.1 思路分析思路1:DFS 比较简单 直接看代码2.2 代码实现import java.util.ArrayList; import java.util.HashMap; import java.util.List; public class Solution { public void dfs(char[] brackets,int lNum,int rNum,int n,List<String> res){ if(lNum==n && rNum==n) { res.add(new String(brackets)); return; } // 增加左括号 if(lNum<n){ brackets[lNum+rNum] = '('; dfs(brackets,lNum+1,rNum,n,res); } // 增加右括号 if(lNum>rNum&&rNum<n){ brackets[lNum+rNum] = ')'; dfs(brackets,lNum,rNum+1,n,res); } } public List<String> generateParenthesis(int n) { List<String> res = new ArrayList<>(); char[] brackets = new char[2*n]; dfs(brackets,0,0,n,res); return res; } public static void main(String[] args) { Solution solution = new Solution(); int in = 3; System.out.println(solution.generateParenthesis(in)); } }2.3 提交结果提交结果执行用时内存消耗语言提交时间备注通过0 ms41.3 MBJava2022/04/25 20:33添加备注参考资料https://leetcode-cn.com/problems/generate-parentheses/
2022年04月25日
536 阅读
0 评论
0 点赞
2022-04-25
leetcode|中等:17. 电话号码的字母组合
1.题目给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。示例 1:输入:digits = "23" 输出:["ad","ae","af","bd","be","bf","cd","ce","cf"]示例 2:输入:digits = "" 输出:[]示例 3:输入:digits = "2" 输出:["a","b","c"]提示:0 <= digits.length <= 4digits[i] 是范围 ['2', '9'] 的一个数字。2. 题解2.1 思路分析思路1:DFS 比较简单 直接看代码2.2 代码实现class Solution { public void dfs(char[] tel,int depth,HashMap<Character,String> digit2CharsMap,String digits,List<String> res){ // dfs出口 if(depth==tel.length) { res.add(new String(tel)); return; } char curDigit = digits.charAt(depth); char[] digit2Chars = digit2CharsMap.get(curDigit).toCharArray(); for(int i=0;i<digit2Chars.length;i++){ tel[depth]=digit2Chars[i]; dfs(tel,depth+1,digit2CharsMap,digits,res); } } public List<String> letterCombinations(String digits) { HashMap<Character,String> digit2CharsMap = new HashMap<>(); digit2CharsMap.put('2',"abc"); digit2CharsMap.put('3',"def"); digit2CharsMap.put('4',"ghi"); digit2CharsMap.put('5',"jkl"); digit2CharsMap.put('6',"mno"); digit2CharsMap.put('7',"pqrs"); digit2CharsMap.put('8',"tuv"); digit2CharsMap.put('9',"wxyz"); List<String> res = new ArrayList<>(); if(digits.length()==0){ return res; } char[] tel = new char[digits.length()]; dfs(tel,0,digit2CharsMap,digits,res); return res; } }2.3 提交结果提交结果执行用时内存消耗语言提交时间备注通过0 ms39.9 MBJava2022/04/25 20:18添加备注参考资料https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
2022年04月25日
513 阅读
0 评论
0 点赞
2022-03-24
leetcode|中等:15. 三数之和
1.题目给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。注意:答案中不可以包含重复的三元组。示例 1:输入:nums = [-1,0,1,2,-1,-4] 输出:[[-1,-1,2],[-1,0,1]]示例 2:输入:nums = [] 输出:[]示例 3:输入:nums = [0] 输出:[]提示:$0 <= nums.length <= 3000$$-10^5 <= nums[i] <= 10^5$2. 题解2.1 思路分析首先对数组进行排序,排序后固定一个数 nums[i] 如果 nums[i]大于 0,则三数之和必然无法等于 0,结束循环 否则使用左右指针指向nums[i]后面的两端,数字分别为 nums[L]和 nums[R]计算三个数的和 sum 判断是否满足等于0 等于0则添加进结果集 小于0则L++(L<R) 大于0则R--(L<R) 关于去重: 如果 nums[i]== nums[i-1],则说明该数字重复,会导致结果重复,所以应该跳过 当 sum == 0 时,nums[L] == nums[L+1]则会导致结果重复,应该跳过,L++ 当 sum == 0 时,nums[R] == nums[R-1] 则会导致结果重复,应该跳过,R--2.2 代码实现import java.util.*; public class Solution { public List<List<Integer>> threeSum(int[] nums) { // 数组排序 Arrays.sort(nums); List<List<Integer>> res = new ArrayList<>(); if(nums.length>=3) { for (int i = 0; i < nums.length; i++) { if (nums[i] > 0) break; if(i > 0 && nums[i] == nums[i-1]) continue; // 去重 int L = i + 1; // 左指针 int R = nums.length - 1; // 右指针 while (L < R) { while (L < R && nums[L] == nums[L + 1]) L++; // 去重 while (L < R && nums[R] == nums[R - 1]) R--; // 去重 int sum = nums[i] + nums[L] + nums[R]; if (sum == 0) { res.add(Arrays.asList(nums[i], nums[L], nums[R])); L++; R--; } else if (sum < 0) { L++; } else { R--; } } } } return res; } public static void main(String[] args) { Solution solution = new Solution(); System.out.println(solution.threeSum(new int[]{-1, 0, 1, 2, -1, -4})); } }2.3 提交结果提交结果执行用时内存消耗语言提交时间备注通过19 ms45.6 MBJava2022/03/24 20:29添加备注参考资料https://leetcode-cn.com/problems/3sum/https://leetcode-cn.com/problems/3sum/solution/hua-jie-suan-fa-15-san-shu-zhi-he-by-guanpengchn/
2022年03月24日
548 阅读
0 评论
0 点赞
2022-03-24
leetcode|中等:12. 整数转罗马数字
1.题目罗马数字包含以下七种字符: I, V, X, L,C,D 和 M。字符 数值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000例如, 罗马数字 2 写做 II ,即为两个并列的 1。12 写做 XII ,即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII,而是 IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况:I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。C 可以放在 D (500) 和 M (1000) 的左边,来表示 400 和 900。给你一个整数,将其转为罗马数字。示例 1:输入: num = 3 输出: "III"示例 2:输入: num = 4 输出: "IV"示例 3:输入: num = 9 输出: "IX"示例 4:输入: num = 58 输出: "LVIII" 解释: L = 50, V = 5, III = 3.示例 5:输入: num = 1994 输出: "MCMXCIV" 解释: M = 1000, CM = 900, XC = 90, IV = 4.提示:1 <= num <= 39992. 题解2.1 思路分析思路1:贪心 首先我们构造出所有可能会出现的元素 vals = {1,4,5,9,10,40,50,90,100,400,500,900,1000}; keys = {"I","IV","V","IX","X","XL","L","XC","C","CD","D","CM","M"}; 然后我们每次尽量使用最大的数来表示。 比如对于 1994 这个数,如果我们每次尽量用最大的数来表示,依次选 1000,900,90,4,会得到正确结果 MCMXCIV。2.2 代码实现public class Solution { public String intToRoman(int num) { int[] vals = {1,4,5,9,10,40,50,90,100,400,500,900,1000}; String[] keys = {"I","IV","V","IX","X","XL","L","XC","C","CD","D","CM","M"}; StringBuilder sb = new StringBuilder(); while (num>0){ // 先确定是要减哪一个 int targetIndex = vals.length-1; while (vals[targetIndex]>num){targetIndex--;}; sb.append(keys[targetIndex]); num -= vals[targetIndex]; } return sb.toString(); } public static void main(String[] args) { Solution solution = new Solution(); System.out.println(solution.intToRoman(1994)); } } 2.3 提交结果提交结果执行用时内存消耗语言提交时间备注通过3 ms40.7 MBJava2022/03/24 13:07添加备注参考资料https://leetcode-cn.com/problems/integer-to-roman/
2022年03月24日
553 阅读
0 评论
0 点赞
1
2