- 博客(136)
- 收藏
- 关注
RSS订阅原创 LeetCode1025. 除数博弈
解法一：dp，仔细想易知dp[i]的结果是由dp[1]到dp[i-1]的结果来决定的，即如果dp[i]为true，那么dp[j]（0<j<i-1）必然为false，并且i和j满足i%(i-j)==0。代码：class Solution {public: int dp[1005]; bool divisorGame(int N) { for(int i=2;i<=N;i++){ for(int j=i-1;j>0;j--.
2020-08-19 10:55:29
222
原创 Leetcode K 个一组翻转链表
思路：先找出这k个结点组成的链表，然后利用常规的单链表翻转方法进行翻转。需要一个指针lastEnd记录已经翻转后形成的链表的尾结点，还需要一个指针nextHead记录下一个待翻转的链表的链头，然后需要start和end记录当前需要翻转的k个结点组成的链表的表头和表尾，需要注意的是在调用reverse（）进行子链表翻转之前需要把end的next赋值为NULL，然后翻转后新的链表的表头为end，表尾是next。代码：class Solution {public: ListNode* rever.
2020-05-23 12:06:05
281
原创 LeetCode 两数相加（链表）
思路：因为链表的表示是逆序的，所以思路就是模拟两个数从个位相加的操作。考虑上进位。解法1： 首先我的想法是尽量利用现有的结点，通过改变结点值和指点的指向，因为题目里说了都是非空链表，所以我选择将l1链表作为最后返回的链表。然后分为了三种情况进行考虑，具体解释在代码注释里。代码：class Solution {public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* head=l1; /.
2020-05-22 17:07:09
424
原创 golang make的使用
make函数用于初始化slice、chan和map如果只用var声明，不用make初始化，变量对应的值为nil。1.make初始化slice共有三个参数：类型，长度和容量，其中类型和长度必须指定。关于长度和容量，指定长度len，即为slice赋指定长度的默认值，比如int赋值0，string赋值""，bool赋值false等。并且0到len-1都是合法的下标访问范围。容量表示sli...
2019-11-03 20:40:00
8599
4
原创 2019年南京大学计算机开放日（外地学校）
机试：南大机试共三道题，每题100分，每题10个样例，按样例点给分。南大优秀营员主要取决于机试成绩（因为面试成绩差不了很多）。机试题目及题解见这位同学的博客：https://blog.csdn.net/Tina_princess/article/details/98669399鄙人当时没做好，可能还是不够熟练吧，第一题80分，没有考虑前缀0的问题，当时一直没调出来。第二题60分，写的是个d...
2019-11-02 13:45:18
940
原创 2019年北京理工大学夏令营面试与机试
机试（两个小时两道题）：1.给一个字符串，其中包括(、)、和*三种类型的字符,其中星号可以当成小括号，也可以当成大括号。问这个字符串是否是满足正常的括号匹配，若满足，输出true，不满足，输出false。做法：我用的dfs来做，当时觉得用栈来做比较麻烦。2.给一个整数数组，输出最大连续子数组之和。例如：3，-5,1,4,-1,2,-6，5输出：6（1+4-1+2）做法：动态规划，记录以...
2019-11-02 13:35:28
1960
转载 golang关于向channel里读写数据
goroutine，信道(channel)，死锁的一些重点总结信道(channel)是goroutine之间互相通讯的东西，就是在做goroutine之间的内存共享，默认的信道的存消息和取消息都是阻塞的，这就叫做无缓冲的信道，也就是说，无缓冲的信道在取消息和存消息的时候都会挂起当前的goroutine，除非另一端已经准备好。var ch chan int = make(chan int)fu...
2019-10-09 11:29:55
2447
原创 LeetCode 946. 验证栈序列
数组里的元素是不重复的。思路是模拟入栈和出栈的操作，代码如下：class Solution {public: bool validateStackSequences(vector<int>& pushed, vector<int>& popped) { stack<int>s; int j=0; //...
2019-08-20 16:01:26
93
原创 二叉树的镜像、判断二叉树是否为对称二叉树
操作给定的二叉树，将其变换为源二叉树的镜像。思路：后续递归，访问的结点的时候将node的left和right结点指向交换一下即可。class Solution {public: void Mirror(TreeNode *pRoot) { if(!pRoot) return; TreeNode *tmp=pRoo...
2019-08-20 14:59:30
314
原创 利用递归实现栈的逆序
代码：利用递归暂时保存栈顶元素。其他见注释//利用递归得到栈底元素，并将栈底元素弹出int getbottom(stack<int> &s) { int top = s.top(); s.pop(); if (s.empty()) return top; int next = getbottom(s); //不是栈底元素的时候要把当前元素入栈 s.push...
2019-08-20 13:13:54
200
原创 LeetCode 48. 旋转图像
方法1：先进行矩阵转置，再将矩阵每一行逆序。class Solution {public: void rotate(vector<vector<int>>& matrix) { int n=matrix.size(); if(n==0) return; for(int i=0;i...
2019-08-18 10:49:57
91
原创 最优编辑（牛客网，动态规划）
对于两个字符串A和B，我们需要进行插入、删除和修改操作将A串变为B串，定义c0，c1，c2分别为三种操作的代价，请设计一个高效算法，求出将A串变为B串所需要的最少代价。给定两个字符串A和B，及它们的长度和三种操作代价，请返回将A串变为B串所需要的最小代价。保证两串长度均小于等于300，且三种代价值均小于等于100。测试样例：“abc”,3,“adc”,3,5,3,100返回：8思路：d...
2019-08-17 16:05:18
306
原创 字符串交错组成(牛客网，动态规划)
对于三个字符串A，B，C。我们称C由A和B交错组成当且仅当C包含且仅包含A，B中所有字符，且对应的顺序不改变。请编写一个高效算法，判断C串是否由A和B交错组成。给定三个字符串A,B和C，及他们的长度。请返回一个bool值，代表C是否由A和B交错组成。保证三个串的长度均小于等于100。测试样例：“ABC”,3,“12C”,3,“A12BCC”,6返回： true思路： 设dp[i][j]为...
2019-08-17 15:42:22
622
原创 反转链表
方法一：三指针法每次记录当前遍历指针cur，前一个指针pre，和下一个指针nextclass Solution {public: ListNode* reverseList(ListNode* head) { ListNode* pre=NULL; ListNode* cur=head; while(cur){ ...
2019-08-17 13:36:41
83
原创 LeetCode 234. 回文链表
请判断一个链表是否为回文链表。class Solution {public: bool isPalindrome(ListNode* head) { if(!head) return true; //利用快慢指针找出链表的中点 ListNode* fast=head; ListNode* slow...
2019-08-17 12:51:25
95
原创 LeetCode 141.链表判环， LeetCode 142.并找出环的入口
判环利用快慢指针，若快指针遍历完链表之前快慢指针没有相遇的话，则说明链表中有环。代码：/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * };...
2019-08-17 00:24:04
331
原创 手写堆排序
若从小到大排序，把原有数组维护成一个大顶堆即可，注意从非叶子结点中的最后一个结点倒序遍历。若二叉树结点下标从0开始，某个节点下标为k，则它的左右子节点的下标分别为2k+1，2k+2。 获得某个节点的父节点下标的方法为(idx+1)/2-1若二叉树结点下标从1开始，某个节点下标为k，则它的左右子节点的下标分别为2k，2k+1，获得某个节点的父节点下标的方法为idx/2。代码如下：#incl...
2019-08-16 23:34:26
513
原创 LeetCode.83 删除排序链表中的重复元素（保留一个数字）
借助一个虚拟头结点，每次保存重复结点的最后一个结点。/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solutio...
2019-08-16 18:52:22
85
原创 剑指offer：删除链表中的重复结点（重复的结点不保留）
题目描述在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5思路：因为这题要把结点重复的都删除，所以要考虑当第一二个结点就重复的情况。所以设立一个虚拟头结点，pre初始指向这个虚拟头结点。这里要用一个flag记录当前节点是否是连...
2019-08-16 18:21:11
60
原创 LeetCode 86 分隔链表
思路就是为小于k的结点链表设置一个表头，并用pcur记录新链的最后一个结点，当遍历到小于k的结点时，将pcur指向当前节点，更新pcur。用pre记录上一个大于等于k的结点（注意pre的next要设为空），当遍历到大于等于k的结点时，将pre指向当前节点，更新pre。最后将pcur指向fnode（fnode记录的是第一个大于等于k的结点）。代码：/** * Definition for s...
2019-08-16 09:58:46
82
原创 如何寻找单链表的中间节点（快慢指针）
设置两个指针，一个快指针，每次走两步，一个慢指针，每次走一步，直到快指针走到链尾。public class searchMid { public Node method(Node head) { Node p=head; Node q=head; while(q!=null&&q.next!=null&&q.next.next!=null) {...
2019-08-15 14:55:54
336
原创 最小的k个数（堆排序实现）
先用数组前k个元素维护一个大小为k的大顶堆（每次将元素插在最后，然后自底向上调整），从第k+1个数组元素开始，当数组元素小于堆顶时，取出堆顶，然后将这个元素放在堆顶，自顶向下调整。最后取出k个数的时候，先取出堆顶，然后将最后一个元素放在堆顶，自顶向下调整。class Solution {public: static const int maxn=1000000; int f=...
2019-08-15 14:27:46
484
原创 二叉树最大叶子结点到最小叶子结点的最短距离
有一棵二叉树，树上每个点标有权值，权值各不相同，请设计一个算法算出权值最大的叶节点到权值最小的叶节点的距离。二叉树每条边的距离为1，一个节点经过多少条边到达另一个节点为这两个节点之间的距离。给定二叉树的根节点root，请返回所求距离。解法：先利用getMaxandMin函数找到叶子结点中最大值和最小值对应的结点，然后利用tree函数，递归返回一个pair<int,int>，第一个...
2019-08-15 12:27:06
850
原创 对两个变量的值进行互换的三种方式
1.最常见的一种，利用第三个变量tmptmp=a,a=b,b=tmp2.在进行加法的时候可能会造成溢出x=x+yy=x-yx=x-y3.利用异或x=x^yy=x^yx=x^y
2019-08-15 09:57:43
376
转载 整数的因式分解（c语言实现）
#include<stdio.h>int main(){ int n,i; printf("Plz input int:"); scanf("%d",&n); printf("%d=",n); for(i=2;i<=n;i++) { whil...
2019-08-15 09:16:55
4976
原创 剑指offer：二叉搜索树和双向链表
题目： 输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）解答： 利用二叉树的中序遍历，找到第一个访问的结点（利用标志位first），用head记录头结点，p记录上一个访问的结点。cur记录当前中序遍历访问的结点。代码：/*st...
2019-08-11 11:29:13
70
原创 剑指Offer--二叉搜索树后序遍历
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。**解答：**将当前树看成二叉搜索树，那么最后一个数字就是当前树的根，而0到right-1可以划分为两段区间，第一段区间中所有的数都小于根（当然这一段区间可能为空），第二段区间中所有的数都大于根（当然这一段区间可能为空），然后对这两段区间再进行递归判断。cl...
2019-08-10 01:37:11
107
原创 面试智力题合集
1.用一个六升和五升的容器怎么得到三升的水答：先用5升的容器灌满水，倒入6升容器里，再用5升容器灌满水，用这个水把6升容器灌满，5升容器里只有4升水，把6生容器里的水倒掉，把5升容器里的水倒入6升容器，这样6升容器里有4升水。把5升容器灌满水，用这个水再把6升容器灌满，5升容器里就只有3升水了。2.已知一圈蚊香能烧1个小时，用2圈蚊香如何判断烧了15分钟？第一圈蚊香两头同时点燃，第二圈蚊香也...
2019-08-08 15:33:31
756
原创 华为校招2019.8.7笔试第三题（栈+表达式求值）
输入一个表达式的字符串，只包含0、1、|、&、!、(、)七种字符，然后输出表达式的结果，保证输入合法。!优先级大于&大于|。这题有个需要注意的点就是：！是一元运算符，这里考虑两种情况，如果！后面是数字，就直接进行运算，并将运算结果入栈。如果！后面是(，就将！压进符号栈，在(出栈时判断当前栈顶是否为！，若为！，将数字栈中的栈顶元素弹出进行！运算。代码：#include<i...
2019-08-08 10:39:56
707
4
原创 【剑指offer】树的子结构
题目描述输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）class Solution {public: bool judge(TreeNode* a,TreeNode* b){ if(b==NULL) return true; if(a!=NULL&&b!=NU...
2019-07-31 00:15:57
81
原创 918. 环形子数组的最大和
解法1：可以将这个数组复制一段接在原数组的后面，然后分别从1到n开始，进行普通子数组最大和的解法。但是这样时间复杂度为n^2。这题的数据量是30000，显然不行，所以应该考虑nlogn或者n的解法。解法2：分成两种情况，一是没有首尾相连，就用正常求最大子数组和的方法。二是有首尾相连的情况，那么这种情况的解法就是将数组求和减去其中一段最小子数组和，但是这种需要考虑一种特殊情况，就是加入数组都小...
2019-07-28 00:02:32
213
转载 c语言中rand()函数的用法笔记
一、rand()rand()函数用来产生随机数，但是，rand()的内部实现是用线性同余法实现的，是伪随机数，由于周期较长，因此在一定范围内可以看成是随机的。rand()会返回一个范围在0到RAND_MAX（至少是32767）之间的伪随机数（整数）。在调用rand()函数之前，可以使用srand()函数设置随机数种子，如果没有设置随机数种子，rand()函数在调用时，自动设计随机数种子为1。...
2019-07-27 19:04:54
975
原创 产生一个长度为100的数组，为数组中的每一项随机填充1-100之间的数并且保证不重复
思路：先产生一个1到100的顺序数组a和一个目标数组b，然后记录一个变量range（a中剩下的元素个数），然后一个for循环（i从1到100），每次产生一个1到range的随机数index，然后把a[index]赋值给b[i]，然后把a[range]赋值给a[index]，令range–。c语言代码：#include<iostream>#include<stdlib.h&g...
2019-07-27 19:02:12
2504
原创 哈深夏令营笔试编程第二题
求最小的一个十进制数,所有位上数字之和为n,且能被m整除的数。枚举m的整数倍。代码：#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<queue>#include<vector>#include<...
2019-07-18 00:20:44
479
原创 哈深夏令营机试题1：n个色子的点数之和为m的概率计算
实际就是求n个色字点数之和为m的组合数。动态规划:转移方程：dp[i][j]=dp[i-1][j-6] + dp[i-1][j-5] +dp[i-1][j-4]+dp[i - 1][j - 3] +dp[i-1][j-2] +dp[i-1][j-1]边界条件是:dp[0][0]=1;代码：#include<iostream>#include<cstdio>...
2019-07-18 00:11:23
970
1
转载 LeetCode 236. 二叉树的最近公共祖先
解法：代码：/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * };...
2019-07-17 20:16:22
62
原创 递归和非递归方法求斐波那契数
递归方法求斐波那契数int fun(int n){ int num = 0; if (n <= 2) { num = 1; return num; } else return fun(n - 1) + fun(n -2); }int main(){ int n = 30; for (int i = 1; i <=n; i++) { pri...
2019-07-15 13:45:41
168
原创 POJ 1018
某公司要建立一套通信系统，该通信系统需要n种设备，而每种设备分别可以有m1、m2、m3、…、mn个厂家提供生产，而每个厂家生产的同种设备都会存在两个方面的差别：带宽bandwidths 和 价格prices。现在每种设备都各需要1个，考虑到性价比问题，要求所挑选出来的n件设备，要使得B/P最大。其中B为这n件设备的带宽的最小值，P为这n件设备的总价。方法1：枚举法枚举存在的带宽值，作为当前...
2019-07-12 00:19:17
120
转载 C语言中将二维数组作为参数传递给函数的方法
/*********************************方法1: 第一维的长度可以不指定 *但必须指定第二维的长度 **********************************/void print_a(int a[][5], int n, int m)*方法2: 指向一个有5个元素一维数组的指针 ********************************...
2019-07-07 01:00:36
460
原创 LeetCode 417. 太平洋大西洋水流问题
设置两个数组，记录当前节点是否能够能流向太平洋和大西洋，从边界开始扩展， 能够扩展到的结点表示该节点能够流向太平洋或者大西洋，最后两个数组标志都1的坐标结点即为正确答案。class Solution {public: int tp[155][155]; int dx[155][155]; int dir[4][2]={{1,0},{-1,0},{0,1},{0,...
2019-07-07 00:57:56
209
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人