- 博客(78)
- 收藏
- 关注
RSS订阅原创 两个栈实现队列
题目描述用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。思路stack1负责入队列，stack2负责出队列，当stack2为空时，将stack1中元素弹出压入stack2中。Java实现import java.util.Stack;public class Solution { Stack<Integer> stack1 = new Stack<Integer>(); Stack<Integer> stac
2021-01-23 12:37:27
118
原创 判断链表中是否有环
题意描述判断给定的链表中是否有环。如果有环则返回true，否则返回false。你能给出空间复杂度O(1)O(1)O(1)的解法么？思路快慢指针。fast每次走两步，slow每次走一步，如果有环，那么fast肯定能和slow相遇。注意循环时，要判断fast!=nullfast!=nullfast!=null和fast.next!=nullfast.next!=nullfast.next!=null，否则，当链表长度为1，为2时, fast指针会出现异常。Java实现/** * Definitio
2021-01-22 15:50:37
148
原创 反转链表
题目描述输入一个链表，反转链表后，输出新链表的表头。例如：输入：{1,2,3}返回：{3,2,1}思路双指针，用pre指针记录当前结点的前一个结点地址，用next记录当前结点的下一个结点地址，遍历链表，每次都令当前结点指向pre，并记录链表，防止断链，当前结点指向null时，返回pre即为新链表的表头。Java实现/*public class ListNode { int val; ListNode next = null; ListNode(int val
2021-01-22 15:25:23
109
原创 最大公约数
题目描述求出两个数的最大公约数，如果有一个自然数a能被自然数b整除，则称a为b的倍数，b为a的约数。几个自然数公有的约数，叫做这几个自然数的公约数。公约数中最大的一个公约数，称为这几个自然数的最大公约数。思路用辗转相除法（欧几里得）算法，gcd(a,b)=gcd(b,r)，其中r=a%b。Java实现import java.util.*;public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
2021-01-22 11:52:40
413
原创 判断回文串
题目描述给定一个字符串，请编写一个函数判断该字符串是否回文。如果回文请返回true，否则返回false。思路头尾指针遍历判断即可。Java实现import java.util.*;public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * @param str string字符串 待判断的字符串 * @return bool布尔型 */ publ
2021-01-22 01:12:46
389
原创 旋转数组
题目描述一个数组A中存有N（N>0N\gt0N>0）个整数，在不允许使用另外数组的前提下，将每个整数循环向右移M（M>=0）个位置，即将A中的数据由（A0 A1 ……AN-1 ）变换为（AN-M …… AN-1 A0 A1 ……AN-M-1 ）（最后M个数循环移至最前面的M个位置）。如果需要考虑程序移动数据的次数尽量少，要如何设计移动的方法？思路借助离散数学中的思路：（A逆B逆）的逆=BA，所以：反转前m-n-1位反转后m位反转整个数组得到结果注意有可能出现m>n的
2021-01-22 00:44:54
98
原创 寻找峰值
题目描述山峰元素是指其值大于或等于左右相邻值的元素。给定一个输入数组nums，任意两个相邻元素值不相等，数组可能包含多个山峰。找到索引最大的那个山峰元素并返回其索引。假设 nums[-1] = nums[n] = 负无穷。思路从数组尾端往前遍历，如果a[i]>a[i-1]，那么a[i]即为山峰，因为前一轮遍历已经说明了a[i]>a[i+1]。Java实现import java.util.*;public class Solution { /** * 寻找最后的
2021-01-22 00:02:44
102
原创 递归、迭代（动态规划）解决斐波那契数列
题目描述大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）n≤39n\leq39n≤39。解决思路递归，f(n)=f(n−1)+f(n−2)f(n)=f(n-1)+f(n-2)f(n)=f(n−1)+f(n−2)，自上而下求解并回溯到根节点，是一颗完全二叉树，所以时间复杂度O(2n2^n2n)；空间复杂度为递归栈的大小，所以是O(n)。迭代（动态规划）：自下而上求解，记录下中间值，dp[0]=0,dp[1]=1,dp[2]=dp[1]+
2021-01-21 23:24:35
198
原创 反转字符串
题目描述写出一个程序，接受一个字符串，然后输出该字符串反转后的字符串。（字符串长度不超过1000)。解题思路借助StringBuffer（线程安全）/ StringBuilder（线程不安全）的reverse方法，因为是单线程，所以用StringBuilder就可以。借助字符数组来交换或者直接赋值，先用toCharArray，最后使用toString转回字符串。Java实现解法一（使用StringBuilder）：import java.util.*;public class Sol
2021-01-21 18:43:36
166
1
原创 螺旋数组
题目描述给定一个m x n大小的矩阵（m行，n列），按螺旋的顺序（顺时针）返回矩阵中的所有元素。举例：输入[[1,2,3],[4,5,6],[7,8,9]]输出[1,2,3,6,9,8,7,4,5]解题思路数组模拟。顺时针打印，首先定义上下左右四个边界，每次遍历完一轮四个边界都要相应加1减1，每一轮遍历条件是上边界不超过下边界，左边界不超过右边界。要避免重复打印，在下、左遍历前要判断左右边界、上下边界。Java实现import java.util.*;public class So
2021-01-21 16:37:54
280
2
原创 合并两个有序数组
题目描述给出两个有序的整数数组A和 B，请将数组B合并到数组A中，变成一个有序的数组。例：A={1,3}， B={2,4}，合并后A={1,2,3,4}。注意：可以假设A数组有足够的空间存放B数组的元素，A和B中初始的元素数目分别为m和n。思路双指针遍历，从A和B的末尾开始遍历（也可以从头遍历，但是每次插入B中元素到A,需要移动元素位置），并设置合并后的数组下标m+n-1，谁大就把谁插入到合并后的A数组。如果B先遍历结束，说明合并结束；如果A先遍历结束，说明A中元素都比B大，直接把剩下B中元素复制
2021-01-20 21:03:00
354
原创 两数之和
题目描述给出一个整数数组，请在数组中找出两个加起来等于目标值的数，你给出的函数twoSum 需要返回这两个数字的下标（index1，index2），需要满足 index1 小于index2.。注意：下标是从1开始的，假设给出的数组中只存在唯一解。例如：给出的数组为 {20, 70, 110, 150},目标值为90输出 index1=1, index2=2思路解法一：暴力搜索，两层循环，对于每一个number，遍历整个数组，判断数组中是否存在numbers[i] + numbers[j] =
2021-01-20 15:12:37
93
原创 正向代理和反向代理
文章目录正向代理和反向代理正向代理参考资料：https://cloud.tencent.com/developer/article/1418457正向代理和反向代理正向代理客户端直接向目标服务器请求资源困难，索引向代理服务器发送请求，代理服务器转交客户端的请求给目标服务器，并且返回响应给客户端。实例场景：通过VPN访问外网。正向代理的特点：正向代理是为了解决客户端访问目标服务器困难的问题客户端知道代理服务器的存在正向代理，代理的是客户端提高访问速度，代理服务器可以缓存响应保护客户端安全
2021-01-19 16:47:09
72
原创 MySQL索引
文章目录MySQL索引MySQL索引类型B+Tree索引哈希索引全文索引空间数据索引（R-Tree）索引优化独立的列多列索引索引列的顺序前缀索引覆盖索引索引的优点索引的使用条件MySQL索引索引是在存储引擎层实现的，不是在服务器层实现的，不同存储引擎具有不同的索引类型和实现MySQL索引类型按索引实现的数据结构来分，为B+ tree索引，哈希索引，全文索引，R tree索引按逻辑来分，为主键索引，普通索引，唯一索引，组合索引；主键索引也被称为聚簇索引，其他非主键索引都称为二级索引B+Tr
2021-01-18 20:57:27
77
原创 数据库范式1NF,2NF,3NF,BCNF
数据库范式1NF，2NF，3NF和BCNF，实际开发中，常常需要满足1NF或者2NF第一范式（1NF）第一范式是属性的原子性，即属性不能再分解。属性1，属性2（属性2.1，属性2.2，属性2.3）…学号姓名出生年月日如果以上表格属性出生年月日，分为出生年、出生月、出生日，那就不符合第一范式。第二范式（2NF）第二范式是在第一范式基础上，保证记录的唯一性，每一条记录有唯一标识，非主属性不能对码存在部分函数依赖完全函数依赖和部分函数依赖：（完全）学号->
2021-01-18 15:48:21
366
1
原创 Java：反射
反射反射是在运行状态获取类的信息，包括构造方法，成员变量，成员方法等好处：低耦合，灵活坏处：效率低当使用 new 创造一个Student对象时，JVM会加载对应类的 .class（字节码）文件，然后会为这个 Student 对象创造一个 Class 对象（只创建一次），每个 Student 对象都共享这一个 Class 对象。反射就是通过调用这个 Class 对象的方法来获取、使用 Student类的构造方法、属性、成员方法等。1.获取 Class 对象获取 Class 对象有三种方法：s
2021-01-10 16:06:59
84
原创 SQL基础：连接
SQL: 连接连接用于连接多个表，使用 JOIN 关键字，并且条件语句使用 ON 而不是 WHERE。ON 是在生成临时表时使用的条件，而 WHERE 是临时表生成后再对表过滤。连接可以替代子查询，并且效率一般比子查询快。连接类型：内连接、自连接、自然连接、外连接。内连接等值连接使用 INNER JOIN 关键字，连接两个表符合条件 ON 的所有行，不删除重复的属性列e.g. 根据条件连接的两个表中的两列：SELECT A.value, B.valueFROM tablea AS
2021-01-06 21:30:39
140
原创 总结一下这一学期的密码学
Modern Cryptography开学刚看到课程名字就愣住了，一是不知道这个单词咋念，而是不确定这门课是不是就是学长学姐一直念叨的痛苦源泉（马上也是我们这届的）------密码学。。。密码学主要可以分为两大部分，一是对称加密（Symmetric Encryption），二是非对称加密，即公钥加密（Public Key Encryption），其余就是对以上两部分的一些理论补充，例如消息完整性（Integrity），哈希碰撞（Collsion），椭圆曲线（Ellptic Curve），双线性对（B
2021-01-04 00:26:12
453
原创 文件系统：逻辑结构
文件系统文件的逻辑结构(File Logical Structure)从用户观点出发所观察到的文件组织形式，是用户可以直接处理的数据及其结构，它独立于文件的物理特性，又称为文件组织(File Organization)有结构文件由一个记录以上构成的文件，又称为记录式文件定长记录每个记录的长度相同，即数据项的数目相同变长记录每个记录的长度不同，数据项数目不同组织记录的方式顺序文件：一系列记录按照一定顺序构成的文件，通常是定长记录，查找速度快索引文件：当记录长度可变，建立
2021-01-03 21:49:39
1021
1
原创 Java：Object类
Object类Object类的通用方法public native int hashCode()public boolean equals(Object obj)protected native Object clone() throws CloneNotSupportedExceptionpublic String toString()public final native Class<?> getClass()protected void finalize() thro
2021-01-03 21:48:02
69
原创 Java：String, StringBuilder, StringBuffer
StringString不可变。String 被声明为final，因此不可被继承，Integer等包装类也不能被继承。value[]也被声明为final，同时String内部没有改变value[]的方法，故String不可变。String内部实现JAVA8中，由char[]数组存储数据：public final class String implements java.io.Serializable, Comparable<String>, CharSequence {
2021-01-03 21:47:16
85
原创 Java：值传递
值传递Java中只有值传递，没有引用传递值传递，传递的是原值的副本，方法不能修改基本类型参数变量内容，典型错误：public static void main(String[] args) { int num1 = 10; int num2 = 20; swap(num1, num2); System.out.println("num1 = " + num1); System.out.println("num2 = " + num2);}pub
2021-01-03 21:41:18
82
原创 Java：Integer的缓存池
Integer 的缓存池JAVA8中，Integer的缓存池大小默认为 -128~127new Integer(value) 必定会创造新的对象，所以使用"=="判断两个Integer对象结果必然为false。Integer.valueOf(value)则会使用缓存池中（-128~127）的对象，多次调用会取得同一对象的引用，valueOf()方法实现如下：public static Integer valueOf(int i) { if (i >= IntegerCach
2021-01-03 21:40:47
580
原创 Java：抽象类和接口
抽象类和接口抽象类抽象类不能被实例化，只能被继承抽象类和抽象方法都使用abstract关键字进行声明。如果一个类中包含抽象方法，那么这个类必须声明为抽象类。public abstract class AbstractClassExample { protected int x; private int y; public abstract void func1(); public void func2() { System.out.print
2021-01-03 21:38:07
126
原创 Java：多线程
多线程启动 一个java程序 == 启动一个JVM进程，从而JVM的主线程调用main方法，同时main方法可以调用其他的线程创建线程的方法Thread t = new Thread();//创建一个新线程t.start();//启动线程创建一个类继承Thread类，并重写run方法（start方法内部调用了run方法）public class Main { public static void main(String[] args) { Thread t =
2021-01-03 21:32:14
72
原创 Java:final关键字
final关键字final 的使用修饰类、方法和变量（包括局部变量和成员变量）修饰类final修饰一个类，表示这个类不能被继承，且final类中所有的成员方法默认为final方法final修饰类用的较少，因为这和面向对象的理念有冲突修饰方法“使用final方法的原因有两个。第一个原因是把方法锁定，以防任何继承类修改它的含义；第二个原因是效率。在早期的Java实现版本中，会将final方法转为内嵌调用。但是如果方法过于庞大，可能看不到内嵌调用带来的任何性能提升。在最近的Java
2021-01-03 21:29:55
89
原创 Java中的“==“和equals()
==“”=="" 对于基本数据类型，比较的是值；对于引用数据类型，比较的是对象的地址例如：42 == 42.00 //tureString s1 = new String("a");String s2 = new String("a");s1 == s2;//falseString s3 = "b";//建立在常量池中String s4 = "b";//将常量池的变量赋值给s4s3 == s4;//trueequals()equals()是Object类的方法：
2021-01-03 21:23:29
88
原创 操作系统面试常常问到的问题
什么是操作系统？它的功能和特征？操作系统就是管理和控制计算机硬件和软件资源的程序，它的管理功能有：进程管理内存管理文件管理I/O管理操作系统是用户与硬件之间的接口，也是硬件和软件之间的接口。操作系统的四大特征：并发：两个或多个进程在同一时间间隔内发生，注意和并行的区别。共享：系统中的资源可供多个并发执行的进程使用。虚拟：把一个物理实体，变为若干个逻辑上的对应物，如虚拟...
2020-03-09 19:25:13
332
1
原创 Java实现：两个有序链表序列的合并
本题要求实现一个函数，将两个链表表示的递增整数序列合并为一个非递减的整数序列。函数接口定义List Merge( List L1, List L2 );其中List结构定义如下：typedef struct Node *PtrToNode;struct Node { ElementType Data; /* 存储结点数据 */ PtrToNode Next; /* ...
2020-03-07 11:21:03
1713
原创 pat-A1007-动态规划之最长子序列和问题
题目链接->link问题描述给定一个整数序列，其中有正有负，求其最长子序列的和，以及该子序列对应的首、尾元素，如果序列全为负数，那么则输出和为0，以及整个序列的首、尾元素。思路分析设置当前和thisSum和最大和maxSum，设置leftIndex，rightIndex记录最大子序列左、右下标，设置tempLeft记录临时左下标。循环输入序列元素，令thisSum=thisSum...
2020-03-04 17:42:32
181
原创 关于二分查找的思考
算法思想对一个顺序存储的线性表，设立head、rear、min三个指针，mid=（head+rear）/2，对于奇数个数的表，mid刚好在中间位置，对于偶数个数的表，mid在length/2-1的位置。因为有序的特性，假设为递增序列，那么当head<=rear的情况下（等号一定要取，否则可能出现目标元素在表头或者表尾但是循环就已经结束了）。当L[mid]>Target，说明目标...
2020-03-04 16:03:12
178
原创 学习笔记（二）：预测房价模型
问题描述现有47个房子的面积和价格，请建立一个模型对新的房价进行预测。分析输入数据为房子的面积，一维。目标数据为房子的房价，也是一维。那么显然这属于监督学习中的线性回归（Regression）问题，可以使用多项式函数和平方误差函数来建立模型。步骤获取与处理数据2104,3999001600,3299002400,3690001416,2320003000,539900...
2020-03-02 17:06:42
1845
1
原创 学习笔记（一）：机器学习绪论
什么是机器学习计算机使用输入给其的数据，利用我们赋予的算法得到某种模型，然后使用该模型来预测未知数据的信息或者结果。机器学习在统计理论下的本质：追求合理的假设空间（Hypothesis Space）和泛化能力（Generalization）。假设空间：模型在数学上的使用场合。泛化能力：模型在未知数据上的表现。机器学习常用术语数据集（Date Set）：即数据的集合。样本（Sim...
2020-03-02 12:20:03
177
原创 数组循环左移/右移问题
思路对于左移/右移思路都是一样的，拿循环左移p位来说:a0a1a2…ap-1ap…an-1操作后为ap…an-1a0a1a1a2，观察后可以得到这样的解法：先将前p个和后n-p个元素（对应下标为0-p-1，p-n-1）分别逆置。再将整个列表逆置，即可得到结果。同理：循环右移，则要把后p个元素后前n-p个元素分别逆置，在将整个列表逆置。代码逆置函数实现：void Revers...
2020-03-01 17:58:17
729
原创 pat-B1020-月饼
题目链接->link思路贪心的思路，只要选单价最高的月饼最多，那么总利润也是最高。对月饼按照单价从小到大排序，如果月饼库存小于需求，那么库存全选上，需求减少相应数量；直到库存大于需求，那么最多选择当前剩余需求乘上单价。坑点：如果库存和总价用int表示，然后计算单价时强制转为double，那么实际数会出错，因为double精度高于int。代码#include <cstdi...
2020-03-01 11:48:07
193
原创 pat-A1048-Find Coins
题目链接->link题意描述给定n个面值的硬币和总数m，求两硬币之和等于m，其中v1<=v2，如果有多种解，那么输出v1最小的情况。思路此题可以用散列或者two pointers来做。首先容易想到的做法是，现将硬币值从小到大排序，然后：for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ if(c...
2020-02-19 14:49:30
123
原创 pat-B1005-继续(3n+1)猜想
题目链接->link思路求关键字，故对每个数字进行(3n+1)猜想操作后，设置hashmap[n]=true，即被覆盖的数。对关键字序列从大到小排序输出，同时最后一个关键字后不能有空格，所以用count记录关键字个数做判断。由于(3n+1)猜想操作后数可能很大，所以hashmap[n]设置为100完全不够，会发生数组越界，即段错误，所以将其设为10000。代码#include...
2020-02-18 20:58:01
161
原创 pat-A1050-String Subtraction
题目链接->link题意描述输入两字符串s1,s2，输出s1-s2，即s2所有字符在s1不能出现。思路输入s2，遍历s2并记录bool型hashmap[]值为false；然后遍历s1，如果hashmap[s1[i]]的值为false则跳过。代码#include <stdio.h>#include <math.h>#include <strin...
2020-02-18 18:37:23
124
原创 pat-A1041-Be Unique
题目链接->link题意描述输入n个数字，数字范围1～104，要求输出第一个不重复出现的数字。思路int hashmap[10001]存储所有数字出现的次数，因为要输出第一个不重复出现的，所以用id[]作为hashmap[]的下标,遍历hashmap[id[i]]，出现第一个值为1的就输出。代码#include <stdio.h>#include <mat...
2020-02-18 18:08:48
129
原创 pat-B1047-编程团体赛
题目链接->link思路输入每行成绩，用int hashmap[]存储各队总成绩；用max记录冠军队下标输出即可。代码#include <stdio.h>#include <math.h>#include <string.h>#include <iostream>using namespace std;const int...
2020-02-18 17:04:41
139
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人