- 博客(141)
- 资源 (3)
- 收藏
- 关注
RSS订阅原创 服务器SSH问题
服务器突然不能访问了，总之就是各种connect refused，没有了SSH我是啥都干不了。然后就看到阿里云有一个救援连接。经过无数次的retry总算是搞好了。首先的话我就是先把SSH重新卸载，然后再安装。安装完了以后使用这个救援连接没有权限去启动SSH service，于是需要更改权限然后再启动。步骤基本上就是用了这两步，主要是哪个救援连接没有滚动，什么都改不了。后来自己随便输了个clear...
2020-05-03 00:12:07
287
原创 《剑指offer》：数组中只出现一次的数字
如果是只有一个数字，那么当然可以直接将全部元素进行异或，最后得出那个只出现一次的元素，原理就是一个元素和自己本身异或为0，且元素之间异或的顺序不影响最后的结果。那么如果有两个数字都出现了一次呢？可以使用HashMap来存储每个元素出现的次数，最后再进行寻找。但是我们还是要掌握一下如何使用异或来解决这个问题：首先我们还是先将所有元素进行异或，那么我们此时得到的结果是那两个元素异或的结果，加入结果...
2020-03-25 21:35:40
182
原创 leetcode_79:单词搜索
这个题目就是典型的回溯法，然后我只会用一种比较耗时的回溯法，主要耗时或者耗费内存的地方在于对于访问标志数组的创建，因为每次走都是要新建一个访问标志数组的： public boolean exist(char[][] board, String word) { //boolean[][] visit = new boolean[board.length][board[0].l...
2020-03-25 18:11:00
170
原创 《剑指offer》：机器人的运动范围
这个题目就是典型的深度优先遍历，或者说回溯法。就是在运动过程中记住访问过的状态，然后每到一个点如果点超出了边界直接return如果访问过这个点直接return如果点不满足我们的条件也return，最后如果满足则计数器加1，然后继续向上、下、左、右四个方向进行遍历。public class Solution { int count = 0; public int mov...
2020-03-25 17:40:16
124
原创 《剑指offer》：剪绳子
递归求解递归的方法就是我假设剪某一刀的时候，总是有n-1种选择动态规划动态规划的思路也很简答，就是每次剪绳子的时候，我们
2020-03-25 17:31:42
116
原创 《剑指offer》：数组中重复的数字
首先我们可以使用排序，然后再判断每两个相邻元素是否相等就行了。当然还可以使用一个HashSet来存储所有元素，当添加元素时判断Set中有没有，有则说明有重复的元素存在。简单解法因为题目规定的是数组长度为n，且数字都在0-n-1内，如果没有重复元素，则每个元素正好可以占据一个位置。那么我们可以让每个元素都待在自己应该在的位置上，如果一个位置上有两个元素需要占据，说明有重复的元素存在。我们先循...
2020-03-25 11:48:30
147
原创 《剑指offer》：二叉搜索树的后序遍历序列
这个题目刚开始不太会，虽然知道后序遍历的特点，也知道左子树都小于根节点、右子树都大于根节点，且根节点总是一个子树的最后一个节点，但还是无法下手的感觉。最后知道了怎么做，其实就是对于一个树，找到左右子树的分界点，然后分界点左边肯定是都比根节点小，因为我们就是利用左子树的特点去找分界点，那么真正要判断是否符合的就是右子树中的所有元素是不是都大于根节点即可。如果满足则递归判断左右子树，否则返回false...
2020-03-24 23:12:58
154
原创 阿里笔试2：求最长非递减字符长度
首先这个题目我自己是做错了的，最后AC是0.1，和没有一样（香菇…），但是思路上是对的，只是这应该是个动态规划问题，我做成了BFS的问题了。动态规划首先输入的均是小写字母，且每个字符串都已经满足了是非递减的，...
2020-03-20 17:23:57
547
原创 《剑指offer》：字符流中第一个不重复的字符
这个题目的话其实是可以想到利用一个128大小数组来保存字符出现的次数，只是如果我们要找第一个时，每次都需要从头开始遍历，直到找到一个次数为1的则立即返回。那么我们可不可以简化这个遍历的过程？当我们遇到一个字符时，如果是第一次出现我们就将它放到一个队列中，如果不是第一次就不放到队列中了。当取第一个出现次数为1的字符时，我们去队列里拿，当然随着字符流的进行，队列里的字符不都是只出现一次了，那么我们就从...
2020-03-16 22:07:45
97
原创 《剑指offer》：删除链表中重复的结点
这个题目就是考察的边界条件，方法上没什么特别的。我们仍然要注意的是，遇到链表题目时，最好几个伪头结点。 public ListNode deleteDuplication(ListNode pHead) { if(pHead == null || pHead.next == null) //为null或者只有一个节点，直接返回 return ...
2020-03-16 21:34:49
82
原创 《剑指offer》：和为S的连续正数序列
这个题目就是维持一个窗口内的和，然后动态的向前滑动，直到右边界到达了目标和S为止，因为此时窗口内的和肯定是大于S，不管窗口有多小。代码如下： public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) { ArrayList<ArrayList<Integer&...
2020-03-12 22:25:35
90
原创 《剑指offer》：平衡二叉树
这个题目按照我们一般的思路来说比较容易做，就是求出两个子树的长度，如果满足平衡的条件则递归的判断各自的子树，否则返回false，代码如下：public class Solution { public boolean IsBalanced_Solution(TreeNode root) { if (root == null) //为null，则返回true ...
2020-03-12 21:37:09
121
原创 《剑指offer》：连续子数组的最大和
这个题目就是典型的动态规划问题，也就是对于当前的元素num[i]，如果它前面相邻的连续和flag[i-1]>0，那么它的最大连续和就是num[i]+flag[i-1]；如果flag[i-1]<0，那么它的最大连续和就是本身num[i]。然后可以在更新完相应的flag[i]后，直接和result进行判断，取最大值。public class Solution { public i...
2020-03-12 00:24:39
80
原创 《剑指offer》：最小的K个数
这个题目的话，单纯看题目的名字就知道利用堆可以去解决。但是先讲一下另一种思路，就是将所有元素记录到自己的位置上，这样元素就会默认的从小到大进行排列，然后就可以找到了。代码如下： public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) { ArrayList<Intege...
2020-03-12 00:17:11
119
原创 《剑指offer》：数组中出现次数超过一半的数字
这个题目和leetcode169：多数元素类似。只是leetcode的题目保证数字总是存在的。我们知道这个题目可以使用哈希表来解决，只是在最坏的情况下时间复杂度可能是O(n)，即每个元素都只出现一次。所以我们可以变一下思路。我们首先记住当前数量较多的元素和它出现的次数，当再次遇到此元素时次数+1，当遇到不一样的次数时就-1，而当更改完次数后如果变为了0，说明这个元素很少，那么我们就要更新当前数量...
2020-03-10 12:39:06
109
原创 《剑指offer》：之字形打印二叉树
也不难的题目，就是判断每层是奇数层还是偶数层，然后偶数层的时候要将顺序进行翻转即可。代码如下：class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList&l...
2020-03-09 23:28:50
78
原创 《剑指offer》：栈的压入、弹出序列
这个题目的话，我们的思路就是先将元素入栈，直到遇到出栈序列中的元素，那么此时我们就将满足的元素不停的出栈，最后判断栈是否为空即可。public class Solution { public boolean IsPopOrder(int [] pushA,int [] popA) { Stack<Integer> stack = new Stack<&g...
2020-03-09 23:07:42
102
原创 《剑指offer》：树的子结构
这个题目很明显的是递归，就是当两个指针指向两个根节点时，先判断根节点的值是否相等，如果相等的话那就递归判断左子树和右子树；否则的话就将root1变为它的左子树，看root2是不是它左子树的子结构，同样将root1变为它的右子树，看root2是不是它右子树的子结构。左右子树只要有一个满足就证明可行，代码如下：链接：https://www.nowcoder.com/questionTerminal/...
2020-03-09 18:07:33
108
原创 《剑指offer》：调整数组顺序使奇数位于偶数前面
首先这个题目有一个点要注意，就是不能更换同类型数据之间的相对顺序。如果没有这个限制的话，我们的代码可以使用两个指针分别从最左和最右向中间靠拢，然后遇到不符合的相互交换即可，代码如下：public class Solution { public void reOrderArray(int [] array) { int left = 0, right = array.len...
2020-03-08 22:02:54
103
原创 leetcode_50:Pow(x,n)
这个题目说实话刚开始感觉棘手，后来如果用心想发现没那么难，当然暴力法在此我们就不多接赘述了。1. 递归法就是将问题分解成小问题，也叫快速幂法，代码如下。一定要注意的就是对于n<0时的处理情况，将其变为n>0的情况进行处理。class Solution { public double myPow(double x, int n) { if(n == 0) r...
2020-03-08 21:38:04
112
原创 leetcode_263:丑数（丑数II）
给了我们一个丑数的概念，真是为了考验我们什么手段都能使出来。首先说一下第一个题目，判断一个数是不是丑数，就是不断地去除5、除3、除2就行了，当然除之前看看余数是不是0，否则的话说明已经不能被这三个数整除了，直接结束： public boolean isUgly(int num) { boolean flag = true; while(num != 1 &a...
2020-03-04 19:25:16
124
原创 leetcode_198:打家劫舍
这个问题的话，我觉得应该是属于贪心算法，反正思路上很明确。假设我们有一个数组flag用来存储各个位置的最大值，且数组长度大于2，那么我们在求第i个最大值时只与两个值有关：第i-1个值和第i-2个值。且flag[i] = Math.max(flag[i-1], flag[i-2]+nums[i])，因为当前的最大值要不然就是前一个的最大值，要不然就是前两个的最大值加上当前的值，只能是这两种情况。所以...
2020-03-02 21:38:28
120
原创 leetcode_128:最长连续序列
1. 双向寻找我也不知道我这种解法具体叫什么，思路就是：先把所有数字放到一个HashSet里然后对里面的每个数据都去双向的扩展，然后在HashSet里面去找查找的过程记录下数量，同时从HashSet里删除避免重复查找最后其实我们对于所有的连续数列只查找了一遍，时间复杂度O(n)，空间复杂度O(n)代码如下： public int longestConsecutive(int...
2020-02-28 22:48:13
69
原创 leetcode_139:单词拆分
1. 递归+回溯这种思路比较容易想到，对于每个位置如果包含这个字符串，就去递归地判断后面的字符串。当最后的下标位置为字符串长度时，说明正好判断完，返回true。public class Solution { public boolean wordBreak(String s, List<String> wordDict) { return word_Brea...
2020-02-28 21:15:10
90
原创 leetcode_84:柱状图中的最大矩形
1. 暴力法这个暴力法基本上没什么难度，就是每到一个柱状就要扩展地向两边遍历，而且要保证两边的柱子都比它短才可以得到以这个柱子为中心的长方形，至于比它小的柱子我们在遍历小柱子的时候就已经考虑到了。所以核心就是要找两边都比它大的柱子。代码如下： public int largestRectangleArea(int[] heights) { int result = 0, ...
2020-02-26 18:35:53
118
原创 leetcode_100:相同的树
这个题目很容易想到使用递归的方法去解决，如果两个树它们的值相等，则去递归的判断它们的左子树和右子树，且要同时满足左子树和右子树都相等。当两个根节点都为null是返回true；如果只有一个为null，则返回false；如果两个根节点的值都不相等，直接返回false。代码如下： public boolean isSameTree(TreeNode p, TreeNode q) { ...
2020-02-26 16:14:39
67
原创 剑指offer：从上到下打印二叉树
普通的打印二叉树很简单，使用队列就可以解决。但是我做的这个题目是要将每一层的节点都存起来，而且不同层之间是分开存储的。其中有个问题就是我们如何去判断某一层是遍历完了，然后要到下一层了呢。我们可以这样解决，记住每层的个数，这样遍历上一层时我们知道上一层个数了就不会遍历下一层的节点；而遍历过程中也要把子节点加入到队列中，这个过程把下一层的节点数也要记住。看代码注释部分比较详细： public...
2020-02-25 17:43:28
75
原创 链表环的问题
1.判断一个链表有没有环这个题目很经典，剑指offer和leetcode141上都有原题，核心思想就是快慢指针，当两个指针相遇的时候说明是有环的。代码如下： public boolean hasCycle(ListNode head) { if (head == null || head.next == null) return false; ...
2020-02-24 22:12:00
144
原创 leetcode_146:LRU缓存机制
这个题目不用多说，就是手撕LRU。实现原理基本上就是哈希表+双向链表。但是这个结构刚开始其实挺难理解的，就是如何把他们连接在一起会感觉有点乱。其实不用想的那么复杂，这样想我们的既然是cache，那么首先有个HashMap（HashTable）来存储数据，key作为数据，value作为...
2020-02-23 08:44:57
92
原创 leetcode_206:反转链表
这个题目可以说是很经典了。当然思路也不难，主要分两种。递归法和迭代法，先说一下比较容易理解的迭代法。1.迭代法使用三个指针pre、cur、next，然后每次都是更新cur让其next指向pre，然后next则用来保存下一个cur的位置，更新规则如下：cur.next = pre; pre = cur; cur = next;而且每次循环的开始或者说更新前都要记住最新的next，即next =...
2020-02-20 08:03:41
74
原创 leetcode_238:除自身以外数组的乘积
1.左右乘积列表这个题目当然也是剑指offer里的题目，方法就是构造一个左乘积数组left，构造一个右乘积数组right，然后对于每一个i，它的结果就应该是left[i-1] * right[i+1]。思想比较好理解直接上代码： public int[] productExceptSelf(int[] nums) { if(nums.length < 2) ...
2020-02-19 23:32:45
78
原创 leetcode_236:二叉树的最近公共祖先
这个题目我不会，直接看的别人的解法，是递归。解释都很清晰，试着理解然后记住吧…。我看了一会，貌似理解了其中的核心：只要找到了p或者q就要返回。当然这是句废话，但也不是，因为很多句子都是为它服务的。譬如说代码（1）处，只要遇到p或者q那我这次递归就结束了，返回到上一层，上一层也就是代码（2）和（3）处然后我们看返回到（2）（3）后发生了什么，如果左和右都不为空，说明两个分支都找到了，那公共的...
2020-02-19 23:00:26
82
原创 leetcode_106:相交链表
1.计数法我们知道如果两个链表listA和listB，长度分别为lengthA和lengthB，则一个较长的节点只需要先走lengthA-lengthB步，就能保证他俩在某个地方相遇。代码如下： public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode pA = headA; ...
2020-02-19 22:06:01
90
原创 leetcode_155:最小栈
这个问题当然也是leetcode上的原题，无非就是使用一个额外的栈来存储最小值，每次入栈的时候进行判断就行了。但是如果要求空间复杂度为O(1)呢，即不使用额外的空间该怎么办。答案就是栈不存储元素，而是存储差值。总体来说就是：入栈的时候将元素x与当前最小值min的差值x-min入栈出栈的时候判断一下栈顶，如果栈顶大于等于0，那就是当前的最小值min加上栈顶。因为我们入栈的时候x-min大于0且...
2020-02-19 20:50:48
744
1
原创 leetcode_49:字母异位词分组
这个题目我是直接看的答案，其实考察的就是我们如何来表达两个词确实是异位词：首先要保证长度相等其次就要保证每个字符出现的次数一样所以我们主要还是从第二点出发。如下1. 将字符串中字符排序重组这个思路就是对于一个字符串里的所有字符进行排序然后重组，那异位词肯定是相同的。代码如下：class Solution { public List<List<String>...
2020-02-18 23:32:02
82
原创 leetcode_703:数据流中的第K大元素
这个题目反正我是只通过了九个测试用了，而且感觉自己的好像还挺对的。但是最后那个很长的就是通不过，说一说思路吧。这个题目一看就能看出来，使用小根堆。代码如下：class KthLargest { //维持一个大小为k的最小堆 int[] heap; public KthLargest(int k, int[] nums) { heap = new int[k...
2020-02-18 22:05:38
93
原创 leetcode_43:字符串相乘
一、无脑竖式法这种方法就是按照我们通常的思路，让一个数和另一个数的每一位相乘，然后把结果加起来。其中我用到了两个辅助函数：字符串相加。也就是两个字符串相加得到一个结果一个字符串和一个字符相乘，得到一个字符串但是我写的代码有问题，就是当一个数为0的情况时，会返回多个0。但看通过率的话我只有5个测试用例没有通过，也就不想改了。毕竟时间太紧张，没时间了。代码如下：class Solutio...
2020-02-09 20:01:25
241
原创 leetcode_143:重排链表
这个题目思路就是：先把链表分成两个长度相等（奇数的时候后半部分少一个）的子链表然后将后面的链表进行反转最后将两个链表合并，后面的链表总是插入到前面链表的后面public void reorderList(ListNode head) { if (head == null || head.next == null) //有0个或1个结点，直接返回 ...
2020-02-08 21:51:35
107
原创 leetcode_71:简化路径
此题主要考察的是栈,所以定义一个辅助栈;先把字符串以"/“为分隔符分割成数组,此时数组有 [“路径”]，[”"]，["."]，["…"]这四种情况;遍历数组,当s[i].equals("…")并且栈不空时pop,当!s[i].equals("") && !s[i].equals(".") &&!s[i].equals("…"),即s[i]是路径入栈;栈空,返...
2020-02-08 16:08:36
91
原创 leetcode_23:合并K个排序链表
一、暴力法暴力法不用做太多解释，代码也不写了，主要是两个暴力法：每次都合并两个链表到一个上面，再用这个新链表继续和另一个链表进行合并。这样需要合并n-1次。逐一比较的方法，就是每次从这K个链表的头结点中选一个最小的，然后加到新建的链表中，重复下去。二、优先级队列（小顶堆）其实就是上面暴力法2的一个变种，我们如何从K个链表的头结点中选一个最小的。方法就是建立一个小顶堆，然后每次从堆顶就...
2020-02-08 15:29:41
175
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人