首页 文章 精选 留言 我的

精选列表

搜索[leetcode]，共439篇文章
优秀的个人博客,低调大师

leetcode算法题解(Java版)-11-贪心大法

一、全排列变式（递归） 题目描述 Given a collection of numbers that might contain duplicates, return all possible unique permutations. For example,[1,1,2]have the following unique permutations:[1,1,2],[1,2,1], and[2,1,1]. 思路 多了一个条件，就是有重复数字出现。那可以考虑先排序，然后递归选择在相应位置放置数字的时候，可以添加判断是否被用过，也就是和前面那个比较一下：如果前面那个数和它一样值，而且目前的used 显示false那说明这个数已经在这个位置被用过了，而且已经计入了结果res中。 代码 import java.util.ArrayList; import java.util.Arrays; public class Solution { public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) { ArrayList<ArrayList<Integer>> res=new ArrayList<>(); int len=num.length; if(num==null||len==0){ return res; } boolean [] used=new boolean[len]; ArrayList<Integer> list=new ArrayList<>(); Arrays.sort(num); dfs(list,num,used,res); return res; } public void dfs(ArrayList<Integer> list,int [] num,boolean [] used,ArrayList<ArrayList<Integer>> res){ if(list.size()==num.length){ res.add(new ArrayList<Integer>(list)); return ; } for(int i=0;i<num.length;i++){ if(i>0&&num[i]==num[i-1]&&!used[i-1]){//如果它前一个和它一样的数现在没有被用过，那就跳过， //说明之前那个数已经形成过结果list之一了，目前这个分支处于回溯阶段。。。有点绕，希望能明白 continue; } if(!used[i]){ used[i]=true; list.add(num[i]); dfs(list,num,used,res); list.remove(list.size()-1); used[i]=false; } } } } 二、贪心 题目描述 Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index. For example:A =[2,3,1,1,4], returntrue. A =[3,2,1,0,4], returnfalse 思路 贪心的题，每走一步，跟新一下从当前这个位置所能到达的最大距离。这就是这题的贪心，贪心一般证明很难，但是可以逻辑简单想一下，肯定是能走的距离越大越好，越有可能到达终点，再说，如果最大距离都不能到终点，那其他情况更加不可能了。 代码 public class Solution { public boolean canJump(int[] A) { int maxlen=A[0]; for(int i=1;i<A.length;i++){ if(maxlen==0){ return false; } maxlen-=1; maxlen=Math.max(maxlen,A[i]); //if(maxlen+i==A.length-1){//剪枝 // return true; // } } return true; } } 三、动态规划or贪心 题目描述 Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Your goal is to reach the last index in the minimum number of jumps. For example:Given array A =[2,3,1,1,4] The minimum number of jumps to reach the last index is2. (Jump1step from index 0 to 1, then3steps to the last index 思路 dp解法： 题目想考察的是贪心，想了一下，思绪有点乱。先看一下动态规划的解法。 首先，满足dp的条件：1.子问题的最优解也是全局的最优解，有最优子结构；2.当前状态只依赖于它上一个状态，与怎么到达它上一个状态的路径无关。 代码 public class Solution { public int jump(int[] A) { int [] dp=new int[A.length];//存放起点到各点的最小步数 for(int i=0;i<A.length;i++){ int maxpos=Math.min(i+A[i],A.length-1); for(int j=i+1;j<=maxpos;j++){ if(dp[j]==0){ dp[j]=dp[i]+1; } } if(dp[A.length-1]!=0){ break; } } return dp[A.length-1]; } } 思路二 贪心解法： 贪心大法好，但真的难想明白。。首先，要设置三个值：当前位置（是一个区域：从i~furthest_pre中，区域中的点中能到达的最大位置）所能到达的最大位置（furthest_cur)，当前位置的上一个位置(也是区域）所能到达的最大位置（furthest_pre），还有就是所走的步数。 有一点可能有点会懵，furthest_cur是还没有step++的时候，具体结合代码，也就是是一个预判能走到的但还没走的状态。 感觉讲的还是有点乱，现在抛开代码，想象我们站在题目给的数组的开头位置：从开始位置到开始位置能走到的最大距离（furthest_pre）之间构成了一块区域，然后我们开始一格一格走，每走一下刷新一下当前这块区域能到的最大位置(furthest_cur)，如果走到从开始位置走到了furthest_pre那我们也刷新出了最大的furthest_cur,如果furthest_cur比终点大，那恭喜！再跳一不就到终点了！可以开始跳一步咯！然后重复上述的动作，直到到达终点。 如果能一步到最大位置furthest_pre，那肯定能到一步到它前面那块区域的某一位置，实行下一步跳，跳到furthest_cur。 给一个测试用例，可以在纸上画画： 4 1 6 9 7 4 5 0 6 8 1 2 3 5 8 0 2 1 2 代码 public class Solution { public int jump(int[] A) { int len=A.length; if(len==0||A==null){ return 0; } int furthest_cur=0; int furthest_pre=0; int steps=0; for(int i=0;i<len;i++){ if(furthest_pre>=len){ return steps; } if(i>furthest_pre){ furthest_pre=furthest_cur; steps++; } furthest_cur=Math.max(furthest_cur,A[i]+i); } return steps; } }
2018-05-05
优秀的个人博客,低调大师

leetcode算法题解(Java版)-7-循环链表

一、循环链表 题目描述 Given a linked list, determine if it has a cycle in it. Follow up:Can you solve it without using extra space? 思路 不能用多余空间，刚开始没有考虑多个指针什么，一下子想到个歪点子：循环就是重复走，那我可以标记一下每次走过的路，如果遇到标记过的路，那说明就是有回路了。 代码一 /** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public boolean hasCycle(ListNode head) { if(head==null){ return false; } ListNode p=new ListNode(0); p=head; int u=-987123; while(p.val!=u&&p.next!=null){ p.val=u; p=p.next; } if(p.val==u){ return true; } else{ return false; } } } 思路二 当然标准的是应该用两个指针来“追赶”，前提是这两个指针走的速度不一样，一前一后如果相遇了则说明有回路。 代码二 /** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public boolean hasCycle(ListNode head) { if(head==null){ return false; } ListNode p=head; ListNode q=head.next; while(p!=q&&q!=null&&p!=null){ q=q.next; if(q!=null){ q=q.next; } p=p.next; } if(p==q&&p!=null){ return true; } else{ return false; } } } 优化过的代码： /** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public boolean hasCycle(ListNode head) { if(head==null){ return false; } ListNode fastNode=head; ListNode lowNode=head; while(fastNode!=null&&fastNode.next!=null){ fastNode=fastNode.next.next; lowNode=lowNode.next; if(fastNode==lowNode){ return true; } } return false; } } 今天有场考试，到七点半才结束，就刷这么多了。
2018-05-02
优秀的个人博客,低调大师

LeetCode 225：用队列实现栈 Implement Stack using Queues

题目： 使用队列实现栈的下列操作： push(x) -- 元素 x 入栈 pop() -- 移除栈顶元素 top() -- 获取栈顶元素 empty() -- 返回栈是否为空 Implement the following operations of a stack using queues. push(x) -- Push element x onto stack. pop() -- Removes the element on top of the stack. top() -- Get the top element. empty() -- Return whether the stack is empty. 示例: MyStack stack = new MyStack(); stack.push(1); stack.push(2); stack.top(); // 返回 2 stack.pop(); // 返回 2 stack.empty(); // 返回 false 注意: 你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。 你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。 你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作） Notes: You must use only standard operations of a queue -- which means only push to back, peek/pop from front, size, and is empty operations are valid. Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue. You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack). 解题思路： 方法一（两个队列）： ​ 队列先进后出，栈后进先出。用队列实现栈，可以用两个队列完成题解： ​ 出入栈： ​ 入栈时用 queue1 来存入节点；出栈时queue1 内节点顺序出队列并入队列到 queue2，直到queue1剩最后一个元素时即为栈顶元素，弹出即可； ​ 取栈顶元素： ​ 用一个 top 指针一直指向栈顶元素，top() 方法查询栈顶元素时直接返回 top 指针即可。 方法二（一个队列）： ​ 只用一个队列，只需要在入栈时反转队列即可： 入栈存入到队列queue 节点1入栈：queue：1 反转队列0次：queue：1 节点2入栈queue：1->2 反转队列1次： queue：1->2 --> queue：2->1 节点2入栈queue：2->1->3 反转队列2次： queue：2->1->3 ---> queue：1->3->2 ---> queue：3->2->1 ...... 这样不管什么时候出队顺序都是按照出栈的顺序。 Java： 方法一 class MyStack { Queue<Integer> queue1; Queue<Integer> queue2; private int top;//指向栈顶元素 public MyStack() { queue1 = new LinkedList<>(); queue2 = new LinkedList<>(); } public void push(int x) { queue1.offer(x); top = x;//新加入元素为栈顶元素 } public int pop() { while (queue1.size() > 1) {//条件为队列1的元素个数大于一 top = queue1.poll();//用top暂存元素，当循环结束时，top刚好是栈顶元素 queue2.add(top); } //队列1与队列2交换 Queue<Integer> tmp = queue2; queue2 = queue1; queue1 = tmp; return queue2.poll();//返回队列2的队列头元素，队列2也只有一个元素 } public int top() { return top; } public boolean empty() { return queue1.isEmpty();//队列1决定了栈是否为空 } } 方法二： 每次入队时反转队列即可，只有入栈需要特殊操作，出栈、取栈顶元素、是否空都按照队列正常出队列、取队列头元素、是否空方法操作。下面是入栈时代码： Queue<Integer> queue = new LinkedList<>(); public void push(int x) { queue.add(x); int sz = queue.size();//获得队列长度 while (sz > 1) {//反转次数为队列长度减一 queue.add(queue.remove());//反转 sz--; } } Python： Python语言没有栈和队列数据结构，只能用数组 List 或双端队列 deque 实现。 这类编程语言就压根不需要 用队列实现栈或用栈实现队列这种问题，因为栈和队列本身就必须借助List、deque实现。 所以这道题在这种语言中这就非常简单了，可以说是作弊。 class MyStack: def __init__(self): self.stack = [] def push(self, x: int) -> None: self.stack.append(x) def pop(self) -> int: return self.stack.pop(-1) def top(self) -> int: return self.stack[-1] def empty(self) -> bool: return not self.stack 欢迎关注微.信公.众号：爱写Bug
2019-08-11
优秀的个人博客,低调大师

LeetCode 232：用栈实现队列 Implement Queue using Stacks

题目： 使用栈实现队列的下列操作： push(x) -- 将一个元素放入队列的尾部。 pop() -- 从队列首部移除元素。 peek() -- 返回队列首部的元素。 empty() -- 返回队列是否为空。 Implement the following operations of a queue using stacks. push(x) -- Push element x to the back of queue. pop() -- Removes the element from in front of queue. peek() -- Get the front element. empty() -- Return whether the queue is empty. 示例: MyQueue queue = new MyQueue(); queue.push(1); queue.push(2); queue.peek(); // 返回 1 queue.pop(); // 返回 1 queue.empty(); // 返回 false 说明: 你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。 Notes: You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid. Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack. You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue). 解题思路： 队列先进后出，栈后进先出。用栈实现队列，可以用两个栈完成题解。入队列时用 stack1 存入节点，出队列时 stack1 内节点顺序出栈压入 stack2 中。 例如 1, 2, 3 元素顺序入队列 即存入栈stack1：[1, 2, 3] 出队列时顺序应为：1->2->3 但是栈先进先出，出栈顺序为：3->2->1 与出队列顺序不相符 借助另一个栈stack2 stack1内的元素顺序出栈并压入stack2 stack1：[1, 2, 3] ---> stack2：[3, 2, 1] 此时stack2出栈顺序：1->2->3 与出队列顺序相符 注意：在出队列时无需着急将 stack1 中的节点顺序压入 stack2。因为要实现的队列是先进后出，可以将 stack2 中的节点全部弹出之后 再将 stack1 内节点顺序压入stack2，这样可以将出栈的时间复杂度摊还到 O(1)。 Java： class MyQueue { private Stack<Integer> stack1; private Stack<Integer> stack2; public MyQueue() { stack1 = new Stack<>(); stack2 = new Stack<>(); } public void push(int x) { stack1.push(x); } public int pop() { if (stack2.isEmpty()) { while (!stack1.isEmpty()) { stack2.push(stack1.pop()); } } return stack2.pop(); } public int peek() { //stack1节点顺序弹出并压入stack2 if (stack2.isEmpty()) {//条件是: stack2为空,而不是stack1非空, 这样摊还复杂度O(1) while (!stack1.isEmpty()) { stack2.push(stack1.pop());//stack1弹出节点并压入stack2 } } return stack2.peek(); } public boolean empty() { return stack1.isEmpty() && stack2.isEmpty(); } } Python： Python语言没有栈和队列数据结构，只能用数组 List 或双端队列 deque 实现。 这类编程语言就压根不需要 用队列实现栈或用栈实现队列这种问题，因为栈和队列本身就必须借助List、deque实现。 所以这道题在这种语言中这就非常简单了，可以说是作弊。 class MyQueue: def __init__(self): self.queue = [] def push(self, x: int) -> None: self.queue.append(x) def pop(self) -> int: #弹出第一个元素 return self.queue.pop(0) def peek(self) -> int: #返回第一个元素 return self.queue[0] def empty(self) -> bool: return not self.queue 欢迎关注微.信公.众号：爱写Bug
2019-08-09
优秀的个人博客,低调大师

Leetcode打卡 | No.24 两两交换链表中的节点

No.24 两两交换链表中的节 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。 示例: 给定 1->2->3->4, 你应该返回 2->1->4->3. 说明: ●你的算法只能使用常数的额外空间。 ● 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。 分析：这一题通过画图才能够比较直观的看出来思路，我们之前有提过链表的删除节点、交换节点位置等操作比列表简单方便，这里就是属于这交换类的啦。 首先初始状态是这样的，（图片来源于网络，手绘的太丑就不放出来了） 通过改变节点指针的指向确定新的连接方式 。 得到的结果如下： 之后依次后移循环上述操作，直到循环终止。 上述实现代码如下： 原文发布时间为：2018-08-29本文作者：我爱小詹本文来自云栖社区合作伙伴“ 小詹学Python”，了解相关信息可以关注“ 小詹学Python”。
2018-08-29
优秀的个人博客,低调大师

Java 代码----------------LeetCode------------ 53. 最大子序和

这道题本来是能做出来的，但是还是遗憾收场，我分析了之所以这样，是因为我做题时又乱了阵脚，没有秉承先思考这道题的思路，再往具体的算法上靠近的规则，这是一道动态规划类的题，它求的最大子序列，也是一步一步的推出来的，它的下一步是由上一步推出来的。对于这类题，你要看的我感觉就不必太多，你要着眼的就是最初的那数组的前几个，分析它们是否满足最大子序列然后就可以类推到一个更长的数组。 public int maxSubArray(int[] nums) { int[] dp = new int[nums.length]; dp[0] = nums[0]; int max = dp[0]; for (int i = 1, length = nums.length; i <length ; i++) { // 加入数组只有两个元素，那么它们要比的就是两个元素的和的大小和第一个元素和第二个元素的大小比较，首先你要明白，如果第一/二个元素是负数，那么加上它就是累赘，就不是最大长度了，所以你要判断它的第一/二个元素是否为负。 dp[i] = Math.max(dp[i-1]+nums[i],nums[i]); max = Math.max(max,dp[i]); } return max; } 所以你只需要用清楚当元素个数为2个时，你就可以推出更多的元素个数
2018-08-04
优秀的个人博客,低调大师

leetcode算法题解(Java版)-13-经典反转链表

一、简单二分搜索 题目描述 Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array. Here are few examples.[1,3,5,6], 5 → 2[1,3,5,6], 2 → 1[1,3,5,6], 7 → 4[1,3,5,6], 0 → 0 思路 题目很简单，二分就能通过 代码 public class Solution { public int searchInsert(int[] A, int target) { //二分查找 int left = 0; int right = A.length-1; while(left<=right){ int mid = (left+right)/2; if(A[mid]==target){ return mid; } else if(A[mid]<target){ left = mid+1; } else{ right = mid-1; } } return left; } } 二、反转链表 题目描述 Reverse a linked list from position m to n. Do it in-place and in one-pass. For example:Given1->2->3->4->5->NULL, m = 2 and n = 4, return1->4->3->2->5->NULL. Note: Given m, n satisfy the following condition:1 ≤ m ≤ n ≤ length of list. 思路 经典的题目，值得反复推敲。设置两个指针，一个指向m的位置，一个指向m之前的那个位置，不断刷新这两个指针的next，达到反转的效果。 注意，这两个指针本身不变化，变化的是他们的next. 这样做，满足了题意中的：do it in-place and in one-place 代码 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode reverseBetween(ListNode head, int m, int n) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode start = head; ListNode prestart = dummy; for(int i=1;i<m;i++){ prestart = start; start = start.next; } ListNode tem; for(int i=0;i<n-m;i++){ tem = start.next; start.next = tem.next; tem.next = prestart.next; prestart.next = tem; } return dummy.next; } } 三、深搜 题目描述 Given a collection of integers that might contain duplicates, S, return all possible subsets. Note: Elements in a subset must be in non-descending order. The solution set must not contain duplicate subsets. For example,If S =[1,2,2], a solution is: [ [2], [1], [1,2,2], [2,2], [1,2], [] ] 思路 题目要列出所有不重复的，用所给数组中数字组成的非递减数列。 深搜解决问题：注意到不能有重复的数字，之前好像做过类似的题目，今天又碰到了，也就是要让拿的数字不能和已经拿过的一样。if(start>i&&num[i]==num[i-1] 代码 import java.util.ArrayList; import java.util.Arrays; public class Solution { ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>(); public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) { if(num==null||num.length==0){ return res; } Arrays.sort(num); findAll(num,0,new ArrayList<>()); return res; } public void findAll(int [] num,int start,ArrayList<Integer> list){ res.add(new ArrayList<Integer>(list)); for(int i=start;i<num.length;i++){ if(i>start&&num[i]==num[i-1]){ continue; } list.add(num[i]); findAll(num,i+1,list); list.remove(list.size()-1); } } }
2018-05-18
优秀的个人博客,低调大师

leetcode算法题解(Java版)-12-中序遍历

日子又恢复正常了，浪了半个月。。。还是学习的时候感觉好~~ 一、动态规划 题目描述 Given n, how many structurally unique BST's (binary search trees) that store values 1...n? For example,Given n = 3, there are a total of 5 unique BST's. 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3 思路 题目看上去像是二叉搜索树的题，实际上是动态规划。给到1~n的数，要找出多少种二叉查找树，对于取值为k的数来说，在它左边的又1~k-1，右边的有k+1~n.所以可以把左子树排列的种数乘右子树的种数得到以这个为根的二叉查找树的个数。 用一个状态数组记录下值。 代码 public class Solution { public int numTrees(int n) { if(n==0){ return 0; } int [] f = new int[n+1]; f[0]=1; for(int i=1;i<=n;i++){//外循环，刷新1，2，3，4.。。n的结果 for(int j=1;j<=i;j++){//小循环，计算各个的值 f[i]+=f[j-1]*f[i-j]; } } return f[n]; } } 二、中序遍历 题目描述 Given a binary tree, return the inorder traversal of its nodes' values. For example:Given binary tree{1,#,2,3}, 1 \ 2 / 3 return[1,3,2]. 思路 二叉树的中序遍历，就是所谓的左-中-右。 递归和非递归方法，直接看代码！ 代码 //递归 /** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ import java.util.ArrayList; public class Solution { public ArrayList<Integer> inorderTraversal(TreeNode root) { ArrayList<Integer> res=new ArrayList<Integer>(); if(root==null)return res; inorder(root,res); return res; } public static void inorder(TreeNode root, ArrayList<Integer> list){ if(root != null){ inorder(root.left,list); list.add(root.val); inorder(root.right,list); } } } //非递归 /** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ import java.util.ArrayList; import java.util.Stack; public class Solution { public ArrayList<Integer> inorderTraversal(TreeNode root) { ArrayList<Integer> res = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); TreeNode node = root; if(root==null){ return res; } while(!stack.isEmpty()||node!=null){ while(node!=null){ stack.add(node); node = node.left; } node = stack.pop(); res.add(node.val); node = node.right; } return res; } } 三、深搜 题目描述 Given a string containing only digits, restore it by returning all possible valid IP address combinations. For example:Given"25525511135", return["255.255.11.135", "255.255.111.35"]. (Order does not matter) 思路 深度搜索+回溯的时候剪枝 代码 import java.util.ArrayList; public class Solution { public ArrayList<String> restoreIpAddresses(String s) { ArrayList<String> res =new ArrayList<String>(); ArrayList<String> ip =new ArrayList<String>(); int start = 0 ; dfs(s,res,ip,start); return res; } public void dfs(String s,ArrayList<String> res,ArrayList<String> ip,int start){ if(ip.size()==4&&start==s.length()){ res.add(ip.get(0)+'.'+ip.get(1)+'.'+ip.get(2)+'.'+ip.get(3)); } if(s.length()-start > 3*(4-ip.size())){//剪枝 return ; } if(s.length()-start+1 < 4-ip.size()){//剪枝 return ; } int num = 0 ; for(int i=start;i<start+3&&i<s.length();i++){ num = num*10+(s.charAt(i)-'0'); if(num<0||num>255){ return ; } ip.add(s.substring(start,i+1)); dfs(s,res,ip,i+1); ip.remove(ip.size()-1); if(num==0){//可以添加0，但不允许有前缀为0的 break; } } } }
2018-05-17
优秀的个人博客,低调大师

leetcode算法题解(Java版)-10-全排列(递归)

一、二维数据 题目描述 You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees (clockwise). Follow up:Could you do this in-place? 思路 最简单的方法就是在开一个新二维数组tem,然后实行“旋转操作” 这样，不符合题意！要在同一个数组中进行！ 代码 public class Solution { public void rotate(int[][] matrix) { int [][] tem=new int [matrix.length][matrix.length]; for(int i=0;i<tem.length;i++){ for(int j=0;j<tem.length;j++){ tem[j][tem.length-1-i]=matrix[i][j]; } } for(int i=0;i<tem.length;i++){ for(int j=0;j<tem.length;j++){ matrix[i][j]=tem[i][j]; } } } } 思路二 画一条从左上角到右下角的对角线，这时候矩阵被分成了两份，然后将左下角那部分和右上角那部分的处于对称位置的对调。 然后将列水平对称位置对调，即为所求！ 听着有点懵的话，不妨在纸上试试。 代码 public class Solution { public void rotate(int[][] matrix) { int len=matrix.length; int tem; for(int i=0;i<len;i++){ for(int j=0;j<i;j++){ tem=matrix[i][j]; matrix[i][j]=matrix[j][i]; matrix[j][i]=tem; } } for(int i=0;i<len;i++){ for(int j=0;j<len/2;j++){ tem=matrix[i][j]; matrix[i][j]=matrix[i][len-1-j]; matrix[i][len-1-j]=tem; } } } } 二、全排列（深搜） 题目描述 Given a collection of numbers, return all possible permutations. For example,[1,2,3]have the following permutations:[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], and[3,2,1]. 思路 找全排列，典型的深搜题。 语法点：res.add(new ArrayList<Integer>(list));不要忘了加new ArrayList<Integer>不加就通过不了，虽然不明白为什么要加上。 代码 import java.util.ArrayList; public class Solution { public ArrayList<ArrayList<Integer>> permute(int[] num) { ArrayList<ArrayList<Integer>> res=new ArrayList<>(); int len=num.length; if(num==null||len==0){ return res; } boolean [] visit=new boolean [len]; ArrayList<Integer> list=new ArrayList<>(); dfs(num,list,visit,res); return res; } public void dfs(int [] num,ArrayList<Integer> list,boolean [] visit,ArrayList<ArrayList<Integer>> res){ if(list.size()==num.length){ res.add(new ArrayList<Integer>(list)); return ; } for(int i=0;i<num.length;i++){ if(!visit[i]){ visit[i]=true; list.add(num[i]); dfs(num,list,visit,res); list.remove(list.size()-1); visit[i]=false; } } } } 这道全排列的题，还有扩展，明天接着搞~~
2018-05-05
优秀的个人博客,低调大师

leetcode算法题解(Java版)-9-N皇后问题

一、贪心 题目描述 Find the contiguous subarray within an array (containing at least one number) which has the largest sum. For example, given the array[−2,1,−3,4,−1,2,1,−5,4],the contiguous subarray[4,−1,2,1]has the largest sum =6. click to show more practice.More practice: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle. 思路 贪心的基本思想就是局部找最优解，然后通过局部的最优解得出来的结果，就是全局的最优解，往往很难证明，但不妨先试一试。 就像这道题，因为要求的是最大的子串和，那显然负数是起到反作用的，所以如果当前和是负的，那就果断舍去，这也是贪心的思路。 这样的解法时间复杂度是O(n）题目中说明了，可以使用分治进一步优化，请看代码二。 代码一 public class Solution { public int maxSubArray(int[] A) { int len=A.length; if(len==0){ return 0; } int sum=A[0]; int max=A[0]; for(int i=1;i<len;i++){ if(sum<0){ sum=0; } sum+=A[i]; if(sum>max){ max=sum; } } return max; } } 代码二 public class Solution { public int div(int [] A,int left,int right){ int mid=(left+right)/2; if(left==right){ return A[left]; } int max1=div(A,left,mid); int max2=div(A,mid+1,right); int max3=-999999;//这里不严谨，但不能用Integer.MIN_VALUE。 //否则max3+max4如果是负数和Integer.MIN_VALUE相加会溢出 int max4=-999999; int tem=0; for(int i=mid;i>=left;i--){ tem+=A[i]; max3=Math.max(max3,tem); } tem=0; for(int i=mid+1;i<=right;i++){ tem+=A[i]; max4=Math.max(max4,tem); } return Math.max(Math.max(max1,max2),max3+max4); } public int maxSubArray(int[] A) { int len=A.length; if(len==0){ return 0; } return div(A,0,len-1); } } 二、N皇后问题 题目描述 Follow up for N-Queens problem. Now, instead outputting board configurations, return the total number of distinct solutions. 思路 经典的老题目了，存储当然是用一个数组map解决：下标表示行号，每个map[i]中存放的数字表示列号。 然后就是写一个判断函数：1.判断行是否重复：这个不需要判定，因为数组下标即使行。2.判断列是否重复，即map[t]!=map[i]。3.判断对角线是否重复：即map[t]-map[i]!=t-i。 代码 public class Solution { public int [] map=new int[30]; public int count=0;//注意！！不能写成public static int count=0; //否则全局静态变量的话，内存地址是一个， //也就是当前测试用例会受到上一个测试用例中count的影响 public int totalNQueens(int n) { backtrack(1,n); return count; } public void backtrack(int t,int n){ if(t>n){ count++; } else{ for(int i=1;i<=n;i++){ map[t]=i; if(valid(t)){ backtrack(t+1,n); } } } } public boolean valid(int t){ for(int i=1;i<t;i++){ if(Math.abs(t-i)==Math.abs(map[t]-map[i])||map[i]==map[t]){ return false; } } return true; } } 三、N皇后问题再度升级 题目描述 The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other. Given an integer n, return all distinct solutions to the n-queens puzzle. Each solution contains a distinct board configuration of the n-queens' placement, where'Q'and'.'both indicate a queen and an empty space respectively. For example,There exist two distinct solutions to the 4-queens puzzle: [ [".Q..", // Solution 1 "...Q", "Q...", "..Q."], ["..Q.", // Solution 2 "Q...", "...Q", ".Q.."] ] 思路 和上一道只需要输出个数，这道题也需要把所有的图输出来。只需要改动一个地方就OK。具体的看代码，写的很清楚。 代码 import java.util.ArrayList; public class Solution { public int [] mark=new int [30]; public int count=0; public ArrayList<String[]> resList=new ArrayList<>(); public ArrayList<String[]> solveNQueens(int n) { backtrack(1,n); return resList; } public StringBuilder drawOneLine(int n){ StringBuilder sb=new StringBuilder(); for(int i=0;i<n;i++){ sb.append('.'); } return sb; } public boolean valid(int t){ for(int i=1;i<t;i++){ if(Math.abs(mark[i]-mark[t])==Math.abs(i-t)||mark[i]==mark[t]){ return false; } } return true; } public void backtrack(int t,int n){ if(t>n){ String [] tem=new String[n]; for(int i=0;i<n;i++){ StringBuilder line=drawOneLine(n); line.setCharAt(mark[i+1]-1,'Q');//因为String从0开始而我的mark是从1开始记的 //这里下标有点乱：mark数组是从1开始的，而tem是从0开始的。 tem[i]=line.toString(); } resList.add(tem); } else{ for(int i=1;i<=n;i++){ mark[t]=i; if(valid(t)){ backtrack(t+1,n); } } } } }
2018-05-04
优秀的个人博客,低调大师

leetcode算法题解(Java版)-3-广搜+HashMap

一、运算符——异或"^" 题目描述 Given an array of integers, every element appears twice except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? 思路 题目很简单，考到了一个知识点——异或：比较两个操作数的二进制的各个位置，相同则为0不同则为1。所以，1.与0异或是本身2.与和自己一样的异或是0. 代码 public class Solution { public int singleNumber(int[] A) { int res=0; for(int i=0;i<A.length;i++){ res^=A[i]; } return res; } } 二、动态规划 题目描述 There are N children standing in a line. Each child is assigned a rating value. You are giving candies to these children subjected to the following requirements: Each child must have at least one candy. Children with a higher rating get more candies than their neighbors. What is the minimum candies you must give? 思路： 一开始看错题了，孩子们本来站好队了，我按权重从大到小排了一下。。。看了别人的代码，思路并不难：先给每人一个糖果，两个循环解决问题，一，从前往后扫一遍，如果下一个比上一个权重大就在上一个基础上加一；再从后往前扫一遍，如果前面的比后面的权重大且糖果比他少就再后面的基础上加一刷新原有的值。 语法点：Arrays.fill(array,val);Arrays.sort(array); 代码 import java.util.Arrays; public class Solution { public int candy(int[] ratings) { if(ratings==null||ratings.length==0){ return 0; } int len=ratings.length; int [] cnt=new int [len]; Arrays.fill(cnt,1); for(int i=1;i<len;i++){ if(ratings[i]>ratings[i-1]){ cnt[i]=cnt[i-1]+1; } } int sum=0; for(int i=len-1;i>0;i--){ if(ratings[i-1]>ratings[i]&&cnt[i-1]<=cnt[i]){ cnt[i-1]=cnt[i]+1; } sum+=cnt[i]; } return sum+cnt[0]; } } 三、模拟题（环状） 题目描述 There are N gas stations along a circular route, where the amount of gas at station i isgas[i]. You have a car with an unlimited gas tank and it costscost[i]of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations. Return the starting gas station's index if you can travel around the circuit once, otherwise return -1. Note: The solution is guaranteed to be unique. 思路 设置start和end，分别放在首尾。如果能继续走就让end++,不能则让start退一个。结束while循环有两种可能结果，一个是sum>=0，则最后相会的点就是出发点，另一个则不可能。 代码 public class Solution { public int canCompleteCircuit(int[] gas, int[] cost) { int len=gas.length; int start=len-1; int end=0; int sum=0; sum=gas[start]-cost[start]; while(end<start){ if(sum>=0){ sum+=gas[end]-cost[end]; end++; } else{ start--; sum+=gas[start]-cost[start]; } } return sum>=0?start:-1; } } 四、BFS+HashMap 题目描述 Clone an undirected graph. Each node in the graph contains alabeland a list of itsneighbors. 思路 广搜，然后用map存储原来的和克隆的一一映射 HashMap中通过get()来获取value，通过put()来插入value，containsKey()则用来检验对象是否已经存在 Stack：st.push(node);st.pop();st.empty(); 代码 /** * Definition for undirected graph. * class UndirectedGraphNode { * int label; * ArrayList<UndirectedGraphNode> neighbors; * UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); } * }; */ import java.util.Stack; import java.util.HashMap; public class Solution { public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { if(node==null){ return null; } HashMap<UndirectedGraphNode,UndirectedGraphNode> map=new HashMap<>(); Stack<UndirectedGraphNode> stackNode=new Stack<>(); stackNode.push(node); while(!stackNode.empty()){ UndirectedGraphNode tempNode=stackNode.pop(); if(map.containsKey(tempNode)){ continue; } UndirectedGraphNode copyNode=new UndirectedGraphNode(tempNode.label); for(UndirectedGraphNode uNode:tempNode.neighbors){ copyNode.neighbors.add(uNode); if(map.containsKey(uNode)){ continue; } stackNode.push(uNode); } map.put(tempNode,copyNode); } return map.get(node); } }
2018-04-28
优秀的个人博客,低调大师

LeetCode 1365. 有多少小于当前数字的数字

题目 给你一个数组nums，对于其中每个元素nums[i]，请你统计数组中比它小的所有数字的数目。 换而言之，对于每个nums[i]你必须计算出有效的j的数量，其中 j 满足j != i 且 nums[j] < nums[i]。 以数组形式返回答案。 示例 1： 输入：nums = [8,1,2,2,3] 输出：[4,0,1,1,3] 解释： 对于 nums[0]=8 存在四个比它小的数字：（1，2，2 和 3）。 对于 nums[1]=1 不存在比它小的数字。 对于 nums[2]=2 存在一个比它小的数字：（1）。 对于 nums[3]=2 存在一个比它小的数字：（1）。 对于 nums[4]=3 存在三个比它小的数字：（1，2 和 2）。 示例 2： 输入：nums = [6,5,4,8] 输出：[2,1,0,3] 示例 3： 输入：nums = [7,7,7,7] 输出：[0,0,0,0] 提示： 2 <= nums.length <= 5000 <= nums[i] <= 100 解题思路 排序，然后根据index处理 class Solution: def smallerNumbersThanCurrent(self, nums: [int]) -> [int]: tempList = nums.copy() tempList.sort() ret = [tempList.index(i) for i in nums] return ret
2020-06-09
优秀的个人博客,低调大师

LeetCode 347: 前 K 个高频元素 Top K Frequent Elements

题目: 给定一个非空的整数数组，返回其中出现频率前 K 高的元素。 Given a non-empty array of integers, return the K most frequent elements. 示例 1: 输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2] 示例 2: 输入: nums = [1], k = 1 输出: [1] 说明： 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。 Note: You may assume k is always valid, 1 ≤ k ≤ number of unique elements. Your algorithm's time complexity must be better than O(n log n), where n is the array's size. 解题思路: ​ 这道题大致解题步骤是: 频率统计 --> 按频率排序 --> 返回频率最高的前 K 个元素 注意点: 题目要求时间复杂度优于 O(n log n) 首先频率统计最优雅的方法应该是借助哈希映射, key 为元素, value 为频率. 其时间复杂度为 O(n) 重点是返回前 K 个频率最高的元素, 所以另一种更简单的方法是直接借助 堆(优先队列) 这种数据结构 维护一个 大小为 K 的堆来动态存储前 K 个频率最高的元素, 其时间复杂度为 O(n) 代码: Java: class Solution { public List<Integer> topKFrequent(int[] nums, int k) { // 建立哈希映射 HashMap<Integer, Integer> count = new HashMap(); // 频率统计 for (int n : nums) count.put(n, count.getOrDefault(n, 0) + 1); // 建立优先队列, 借助 Lambda 表达式 PriorityQueue<Integer> heap = new PriorityQueue<Integer>((a, b) -> count.get(a) - count.get(b)); // 也可以借助 compare 比较函数 // PriorityQueue<Integer> heap = new PriorityQueue<>(new Comparator<Integer>() { // @Override // public int compare(Integer a, Integer b) { // return map.get(a) - map.get(b); // } // }); // 维护一个大小为 k 的已排序的优先队列 for (int n : count.keySet()) { heap.add(n); if (heap.size() > k) heap.poll(); } // 返回结果 List<Integer> top_k = new LinkedList(); while (!heap.isEmpty()) top_k.add(heap.poll()); return top_k; } } Python: Python 基础库里的 heapq 堆数据结构, 有两个函数: nlargest nsmallest 例如 heapq.nsmallest(n, nums) 表示取迭代器 nums 前 n 个最大元素, 该函数还能接受一个 key 关键字,以应对复杂的数据结构 结合 collections.Counter() 频率统计函数, 两行代码即可解决 class Solution: def topKFrequent(self, nums, k): """ :type nums: List[int] :type k: int :rtype: List[int] """ count = collections.Counter(nums) return heapq.nlargest(k, count.keys(), key=count.get) 注意体会关键字参数的作用: key=count.get 欢迎关注微.信公.众号: 爱写Bug
2020-02-22
优秀的个人博客,低调大师

LeetCode 136：只出现一次的数字 Single Number

题目： 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。 Given a non-empty array of integers, every element appears twice except for one. Find that single one. 说明： 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？ Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? 示例 1: 输入: [2,2,1] 输出: 1 示例 2: 输入: [4,1,2,1,2] 输出: 4 解题思路： 排序数组，如果某个数与前后两个数均不相等则该数只出现一次。 哈希映射，key 为每个数的值，value 为每个数出现的频率。最后找到 value = 1 的数返回。 异或运算，直接进行异或操作求值。不使用额外空间。 异或运算（XOR）解题是最优雅的解法，且不使用额外空间，其概念为： 如果我们对 0 和二进制位做 XOR 运算，得到的仍然是这个二进制位 a XOR 0 = a 如果我们对相同的二进制位做 XOR 运算，返回的结果是 0 a XOR a = 0 XOR 满足交换律和结合律 代码： 借助哈希表： Java: 哈希映射频率（可用于字符串出现频率的计算） class Solution { public int singleNumber(int[] nums) { Map<Integer, Integer> map = new HashMap<>(); for (int num : nums) { Integer count = map.get(num); //get() 方法获取元素不存在时返回null count = count == null ? 1 : ++count; //count为null 时证明元素不存在，则频率改为1，否则count频率+1 map.put(num, count); //加入映射表 } for (Integer num : map.keySet()) if (map.get(num) == 1) return num; //返回频率为1的数 return 0; } } Python： 1、借助 try...except...，只适用于该题中重复元素重复出现次数为偶数次。 class Solution(object): def singleNumber(self, nums): hash_map = {} for i in nums: try: hash_map.pop(i) # 尝试移除该数 except: hash_map[i] = 1 # 移除失败证明字典内没有该值，则添加到字典 return hash_map.popitem()[0] #最后字典中只剩下一个键值对，返回其键值 2、字典映射频率（可用于字符串出现频率的计算） class Solution: def singleNumber(self, nums: List[int]) -> int: hash_map = {} for num in nums: hash_map.setdefault(num, 0) hash_map[num] += 1 # 每次出现频率加一 for k, v in hash_map.items(): #二次遍历返回频率为1的数 if v == 1: return k return 0 亦或运算(XOR)： 其处理逻辑可以简单理解为： 输入: [2 , 3 , 2 , 4 , 3] , 初始化 result = 0 result = 0 XOR 2 = 2 result = 2 XOR 3 = [2 , 3] result = [2 , 3] XOR 2 = 3 result = 3 XOR 4 = [3 , 4] result = [3 , 4] XOR 3 = 4 返回 result = 4 异或运算是位操作中最基本运算之一，以上是为方便理解异或运算而简化抽象的逻辑，如果想进一步了解位操作可以参考Wiki百科。 高级程序设计语言异或运算表示符号一般是 ^。 Java: class Solution { public int singleNumber(int[] nums) { int result = 0; for (int num : nums) result = result ^ num; return result; } } Python: class Solution: def singleNumber(self, nums: List[int]) -> int: result = 0 for num in nums: result = result ^ num return result
2019-10-10
优秀的个人博客,低调大师

LeetCode 118：杨辉三角 II Pascal's Triangle II

公众号：爱写bug（ID：icodebugs）作者：爱写bug 给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。 Given a non-negative index k where k ≤ 33, return the kth index row of the Pascal's triangle. Note that the row index starts from 0. 在杨辉三角中，每个数是它左上方和右上方的数的和。 In Pascal's triangle, each number is the sum of the two numbers directly above it. 示例: 输入: 3 输出: [1,3,3,1] 进阶： 你可以优化你的算法到 O(k) 空间复杂度吗？ 解题思路： 和之前写的那篇118号杨辉三角基本类似。这道题只是不用考虑每行输出，只输出最后一行。这样只在一个数组上修改即可：该数 的值 = 该数的值+该数左边的值之和（该数不包括第一个和最后一个数）。 这道题只是不用考虑每一行输出，只输出最后一行。这样只在一个数组上修改即可：该数 的值 = 该数的值+该数左边的值之和（该数不包括第一个和最后一个数）。 用两个嵌套循环，外循环是要计算的每行数组，内循环在上一次计算的数组基础上更改数值得出该行数组。 需要注意的是：内循环 j 指针应该从每行的最后一个数开始更改。 如果 j 指针从左开始更改索引的值： [1] [1,1] [1,2,1] 索引1 的值是索引 0 和 1的和，没问题 [1,3,4,1] 索引2 的值是索引 2 和索引 1的和 为4，而不是预期的3 因为我们是在同一个数组里更改每个数值的，所以如果做左边开始求值，索引 1 的值会从2变为3，此时计算索引2的值，由于该索引左边的值已经改变为3，该索引将不再是预期值。 起先我用的是 ArrayList<Integer>() ： class Solution { public List<Integer> getRow(int rowIndex) { List<Integer> nums = new ArrayList<Integer>(); nums.add(1); for (int i = 1; i <= rowIndex; i++) { for (int j = i - 1; j > 0; j--) { nums.set(j, nums.get(j) + nums.get(j - 1)); } nums.add(1); System.out.println(nums); } return nums; } } 提交时虽然能通过但是每次调用 set()、add() 导致性能很差很差。 Java： class Solution { public List<Integer> getRow(int rowIndex) { Integer[] nums = new Integer[rowIndex+1];//所有值被默认置为0 Arrays.fill(nums, 0); nums[0] = 1; for (int i = 1; i <= rowIndex; i++) { for (int j = i; j >0; j--) { nums[j] = nums[j] + nums[j-1];//当j为1时，nums[j]为0，不影响最后一个值，不用单独给每行末尾赋值1 } } return Arrays.asList(nums);//转为List<Integer>型并返回 } } Python3： class Solution: def getRow(self, rowIndex: int) -> List[int]: nums = [1] for i in range(1, rowIndex+1): for j in range(i-1, 0, -1): nums[j] +=nums[j-1] nums.append(1) # 需要给末尾索引赋值1 return nums
2019-07-06

资源下载

更多资源
Mario

Mario

马里奥是站在游戏界顶峰的超人气多面角色。马里奥靠吃蘑菇成长，特征是大鼻子、头戴帽子、身穿背带裤，还留着胡子。与他的双胞胎兄弟路易基一起，长年担任任天堂的招牌角色。

时间: 2026-10-18 大小: 211.28KB 下载: 56次
腾讯云软件源

腾讯云软件源

为解决软件依赖安装时官方源访问速度慢的问题，腾讯云为一些软件搭建了缓存服务。您可以通过使用腾讯云软件源站来提升依赖包的安装速度。为了方便用户自由搭建服务架构，目前腾讯云软件源站支持公网访问和内网访问。

时间: 2026-08-21 大小: 1MB 下载: 10次
Nacos

Nacos

Nacos /nɑ:kəʊs/ 是 Dynamic Naming and Configuration Service 的首字母简称，一个易于构建 AI Agent 应用的动态服务发现、配置管理和AI智能体管理平台。Nacos 致力于帮助您发现、配置和管理微服务及AI智能体应用。Nacos 提供了一组简单易用的特性集，帮助您快速实现动态服务发现、服务配置、服务元数据、流量管理。Nacos 帮助您更敏捷和容易地构建、交付和管理微服务平台。

时间: 2026-09-24 大小: 189MB 下载: 9次
Sublime Text

Sublime Text

Sublime Text具有漂亮的用户界面和强大的功能，例如代码缩略图，Python的插件，代码段等。还可自定义键绑定，菜单和工具栏。Sublime Text 的主要功能包括：拼写检查，书签，完整的 Python API ， Goto 功能，即时项目切换，多选择，多窗口等等。Sublime Text 是一个跨平台的编辑器，同时支持Windows、Linux、Mac OS X等操作系统。

时间: 2026-08-21 大小: 9.84MB 下载: 40次
热门标签
DeepSeek Jdk25 OpenAi HarmonyOS6 Nacos3 SpringBoot4 SpringCloud Docker Kubernetes Service Mesh Redis Gemini3 Rocky

欢迎您来访！

登录后，您将获得更多功能！
热门文章
联系我们

有任何问题或合作意向欢迎联系我们

Email: 99873273@qq.com

QQ: 99873273

用户登录
用户注册