搜索到
17
篇与
的结果
-
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 -
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
-
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
-
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/
-
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
-
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/
-
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/
-
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/
-
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/
-
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
-
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/
-
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/
-
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/
-
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/
-
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/
