- 博客(33)
- 收藏
- 关注
RSS订阅原创 计算机网络原理
一、计算机网络体系结构1. 五层协议应用层 ：为特定应用程序提供数据传输服务，例如 HTTP、DNS 等协议。数据单位为报文。传输层 ：为进程提供通用数据传输服务。由于应用层协议很多，定义通用的传输层协议就可以支持不断增多的应用层协议。运输层包括两种协议：传输控制协议 TCP，提供面向连接、可靠的数据传输服务，数据单位为报文段；用户数据报协议 UDP，提供无连接、尽最大努力的数据传输服...
2019-09-22 22:37:45
250
原创 数据库复习
一、事务概念事务指的是满足 ACID 特性的一组操作，可以通过 Commit 提交一个事务，也可以使用 Rollback 进行回滚。ACID1. 原子性（Atomicity）事务被视为不可分割的最小单元，事务的所有操作要么全部提交成功，要么全部失败回滚。回滚可以用回滚日志来实现，回滚日志记录着事务所执行的修改操作，在回滚时反向执行这些修改操作即可。2. 一致性（Consistenc...
2019-09-22 17:11:20
154
原创 小红书面试
小红书一面手撕三道1、反转单链表2、求两个链表的交点3、一个数组中有一个数出现了一半以上，找到这个数抽象类和接口的区别二面写测试用例（他随便说的一道 主要看你思维）http和https的区别线程安全手撕两道1、自己写一个栈2、找出栈中最小元素...
2019-09-17 21:42:05
1133
原创 字符串----判断两个字符串是否互为变形词
关键点：准备一个词频表map[a]= b:表示 字符 a 出现了 b 次代码：public static boolean isDeformation(String str1,String str2) { if(str1 == null || str2 == null || str1.length() != str2.length()) { return false; ...
2019-09-04 10:28:49
170
原创 字符串---前缀树、字典树、Trie树的实现
关键点：1、节点类的构建，通过一个数组记录下一个节点及路径2、注意path==0、end==0的含义//字典树、前缀树的实现/*是一种树形结构，优点是利用字符串的公共前缀来节约存储空间 * */ class TrieNode{ public int path;//表示有多少个单词共用这个节点 public int end;//表示有多少个单词以这个节点结尾 publi...
2019-08-22 11:14:47
244
原创 递归和动态规划----换钱的最少货币数
关键点：设 N = arr.length dp[N][aim+1] ：dp[ i ][ j ]表示在可以任意使用arr[ 0...i ]货币的情况下，组成 j 所需的最小张数第一行 ： dp[0][0..j..aim] 表示只使用arr[0]货币的情况下，换钱数为 j 的最小张数； 第一列 ： dp[0.. i .. N-1 ][0] 表示要换的钱数为 0 时需要的最小张数...
2019-07-17 10:56:55
265
原创 递归与动态规划----矩阵的最小路径和
关键点： dp[i][j]表示从（0，0）到（i,j）的最小路径和 代码：public static int minPathSum(int[][] m) { if(m == null || m.length == 0 || m[0] == null || m[0].length == 0) { return 0; } int row = m.length;...
2019-07-16 16:37:22
213
原创 链表----合并两个有序链表
关键点：先找到两个链表头节点中值较小的节点作为新链表的头节点 类似归并排序的merge过程将较小值串起来代码：public static ListNode merge(ListNode list1,ListNode list2) { if(list1 == null || list2 == null) { return list1 == null ? list2...
2019-07-16 10:45:28
77
原创 链表----向有序的环形单链表中插入新节点
关键点：如果链表为空，让newNode自己组成环形链表，然后返回newNode； 如果链表不为空，令pre = head，cur = head.next，然后pre和cur同步移动，如果遇到pre节点的值小于等于num并且cur的值大于等于num，将newNode插在pre和cur之间然后返回头节点； 如果pre和cur转了一圈，说明newNode应该插在头节点的前面，要么是num比链...
2019-07-15 18:20:18
375
原创 链表----一种怪异的节点删除方式
关键点：将要删除节点的下一个节点的value值赋给该节点 删除该节点的下一个节点 注意！！ 这种方法无法删除链表的最后一个节点public static void removeNode(Node node) { if(node == null) return; Node next = node.next; if(next == null) { throw ne...
2019-07-15 17:54:40
94
原创 链表----单链表的选择排序
关键点：链表在逻辑上分成排序部分和未排序部分。利用选择排序，从未排序的链表中找到最小值，删除后链接在排好序部分的尾部，逐渐将未排序的部分缩小，最后变成排好序的部分。 每次在未排序的链表中删除最小值节点的时候要保证未排序链表在结构上不断，故要找到删除节点的前一个节点代码：public static Node selectSort(Node head) { if(head =...
2019-07-15 17:23:26
831
原创 链表----将二叉搜索树转换成双向链表
关键点：一、使用队列 T = O(N) S = O(N)按照二叉树中序遍历的顺序，将每个节点放在队列中 从队列中依次弹出节点，并按照弹出的顺序依次连接节点代码：public static Node convert(Node root) { Queue<Node> q = new LinkedList<Node>(); InOrderT...
2019-07-15 10:32:08
92
原创 链表----将单链表的每K个节点之间逆序
关键点：一、使用栈从左到右遍历链表，如果栈的大小不等于K，就将节点不断压入栈； 当栈的大小第一次达到K时，说明凑齐了K个节点进行逆序，从栈中依次弹出这些节点，并根据弹出的顺序进行重连，同时记录新的头部，该组的最后一个节点连接下一个节点； 当栈的大小每次到达K时，说明又凑齐了一组，从栈中弹出并进行重连后，该组的最后一个节点连接下一个节点，更新pre，然后继续凑下一组，直到链表被遍历完...
2019-07-14 16:00:35
399
原创 链表----删除无序链表中值重复出现的节点
//一、利用哈希表 //T = O(N) S = O(N) public static Node removeRep1(Node head) { if(head == null) return head; HashSet<Integer> set = new HashSet<Integer>(); Node cur = head; Node pr...
2019-07-12 11:44:51
128
原创 链表----两个链表相加生成相加链表
关键点：1、将链表拆成左右两部分 2、合并左右两部分//1、将链表从中间断开，分成左右两部分 public static Node reCombination(Node head) { if(head == null || head.next == null || head.next.next == null) { return head; } //找中点从中间...
2019-07-11 22:41:24
210
原创 链表----两个单链表相交的一系列问题
关键点：1、判断链表是否有环利用快慢指针，若链表有环，快慢指针一定会相交 快慢指针第一次相遇后，快指针回到头节点，变为一次走一步，两指针再次在入环节点处相遇2、两个无环链表相交若相交，两链表是Y型结构3、两个有环链表相交：若相交，两个链表一定是共享一个环入环节点相同：先相交再共享环 入环节点不同，两个链表分别有一个入环节点代码//一、判断链表是否有环，无环返...
2019-07-11 20:17:50
177
原创 链表----将单链表按某值划分成左边小、中间相等、右边大的形式
关键点：1、利用快排的思想将链表放在数组中； 利用荷兰国旗思想将链表进行调整； 然后将数组中的链表串联起来 。2、仅用链表结构代码：将链表分成三个部分small、equal、big 将三个链表串联起来 特别注意三个链表都有可能为空//一、荷兰国旗改进快排 + LinkedList /Node[] /ArrayList实现 //T = O(N) S = O(N...
2019-07-11 15:59:55
141
原创 链表----复制含有随机指针的链表
关键点：方法1：利用hashmap 方法2：利用指针代码 public static Node copyList1(Node head) { if(head == null) return null; //1、准备一个HashMap <key,value> <节点,该节点的副本> HashMap<Node,Node> map =...
2019-07-09 22:20:03
107
原创 链表----判断一个链表是否为回文结构
关键点：方法1：利用栈 T= O(N) S = O(N) //将链表压入栈，利用栈的先进后出逆序出链表对比原链表各节点值 方法2：利用栈 T= O(N) S = O(N/2) //将链表后半段压入栈，逆序后半段 与前半段链表值比较 方法3：仅用指针 T= O(N) S = O(1) //将链表后半段反转，后半段 与前半段链表值比较，然后...
2019-07-09 21:22:25
165
原创 链表----反转部分单向链表
关键点：将链表分成三部分找到from前一个节点 和 to的后一个节点 反转from--to 将三部分连接起来代码：public static Node reversePart(Node head,int from,int to) { if(head == null) return head; //1、找到from前一个节点 和 to的后一个节点 ...
2019-07-09 11:51:46
118
原创 链表----反转链表
关键点：在于使用三个指针：pre、cur、next; 每次将pre和cur之间的链表指向反转代码public static Node reverseList(Node head) { if(head == null) return head; Node pre = null; Node cur = head; Node next = null; ...
2019-07-09 09:48:09
72
原创 链表----删除链表的中间节点和a/b处的节点
关键点：代码：删除一个节点，首先找到待删除节点的前一个节点 注意此题利用快慢指针找到中间节点的方法 删除a/b处节点，即 int k = (int)Math.ceil((double) (a*size)/((double)b));//向上取整 删除第k个节点public static Node removeMidNode(Node head) { if(head ...
2019-07-08 17:49:55
104
原创 链表----打印两个有序链表的公共部分
public static void printCommonPart(Node head1,Node head2) { if(head1 == null || head2 == null) return; while(head1 != null && head2 != null) { if(head1.value < head2.value) { ...
2019-07-08 16:34:54
79
原创 二叉树----层序遍历、从上到下打印、之字形打印
题目：层序遍历（宽度遍历） 从上到下按行打印 之字形打印二叉树关键点：二叉树的宽度遍历 层间换行代码实现： public static class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int value) ...
2019-07-08 16:22:50
203
原创 链表-----删除倒数第k个节点
注意点：删除头节点的处理 在双链表中删除最后一个节点指针悬空情况代码public static class Node{ public int value; public Node next; public Node(int value) { this.value = value; } } public static class DoubleNod...
2019-07-08 16:14:18
253
原创 字节跳动校招提前批面试
一面：1、java写一个单例模式 ？？？？2、fina、finally、finalize的区别3、手写代码单链表的反转 已知二叉树的前序和中序，输出后序4、TCP的四次挥手，为什么四次挥手5、浏览器访问百度的过程6、什么事哈希表 哈西冲突怎么办二面：1、java相关基础：解释Java的三个性质：封装、继承、多态 Java的基本数据类型有哪些 Int...
2019-07-03 15:35:26
943
1
转载 微信发红包的测试用例
最近发现测试用例真的还是很重要，所以先总结一下微信红包的测试要点，方便之后查看1、功能测试1）发给单个好友① 正确的金额+无留言+无表情② 错误的金额+无留言+无表情③ 正确的金额+有留言+无表情④ 错误的金额+有留言+无表情⑤ 正确的金额+无留言+有表情⑥ 错误的金额+无留言+有表情⑦ 正确的金额+有留言+有表情⑧ 错误的金额+有留言+有表情其中，金额（0.01-200）可以测...
2019-07-01 16:23:00
24546
原创 栈和队列-----用一个栈实现另一个栈的排序
关键点：将要排序的栈记为stack，申请的辅助栈记为help。在stack上执行pop操作，弹出的元素记为cur。如果cur小于或等于help的栈顶元素，则将cur直接压入help； 如果cur大于help的栈顶元素，则将help的元素逐一弹出，逐一压入stack，直到cur小于或等于help的栈顶元素，再将cur压入help。（即每次都把help中小于等于cur的元素全部弹出并...
2019-06-28 16:48:59
129
原创 栈和队列----猫狗队列
关键点：构造Pet_Count类：pet 为动物实例，count记录该动物实例进入队列的顺序号码 两个队列：dogQ，catQ 要求实现的CatDogQueue中存储的对象类型为Pet_Count类型代码：class Pet{ private String type; public Pet(String type) { this.type = type; }...
2019-06-28 11:49:16
157
原创 栈和队列----仅用递归函数和栈操作逆序一个栈
关键点：两个递归函数getAndRemoveLastElement(): 将栈底元素返回并移除 2.reverse(): 逆序栈代码：public int getAndRemoveLastElement(Stack<Integer> s) { int result = s.pop(); if(s.isEmpty()) { r...
2019-06-28 10:40:47
73
原创 栈和队列----栈实现队列
关键点：准备两个栈。stackPush//压入栈 stackPop//弹出栈 push操作：向stackPush栈中压入数据之前，先判断stackPop是否为空 * 若不为空，stackPush先依次压入stackPop栈中的全部元素，然后再压入新数据 pop操作 ：从stackPop栈中弹出数据之前，先判断stackPush栈是否为空 ...
2019-06-27 17:01:31
66
原创 栈和队列----设计一个有getMin功能的栈
关键点：准备两个栈。一个数据栈stackData，一个存储当前栈中最小元素的栈stackMin。 stackMin的栈顶元素永远是当前栈的最小元素代码：class MyStack1{ private Stack<Integer> stackData; private Stack<Integer> stackMin; public MySt...
2019-06-27 11:48:16
72
原创 稀疏数组
线性结构：数组、队列、栈、链表 非线性结构：树形结构、图结构、多维数组 链式存储 顺序存储 目录基本介绍：处理方法：举例编码实现：当一个数组中大部分元素为0或者为同一个值时，可以使用稀疏数组来保存该数组应用场景：五子棋程序中用二维数组记录棋盘，该二维数组的很多值是默认值0（空白位置），因此记录了很多无意义的数据处理方法：...
2019-06-26 15:34:59
57
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人