- 博客(190)
- 收藏
- 关注
RSS订阅原创 剑指笔记-二叉树中和为某一值的路径
题目：输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。思路：先保存根节点，然后分别递归在左右子树中找目标值，若找到即到达叶子节点，打印路径中的值。二叉树的好像大部分都是用的递归的思想，这里比较重要的是找到递归结束的条件，特别注意。代码：public class Solution { ...
2019-09-09 17:10:23
154
原创 leetcode-415字符串相加
题目：给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。注意： num1 和num2 的长度都小于 5100. num1 和num2 都只包含数字 0-9. num1 和num2 都不包含任何前导零。 你不能使用任何內建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式。思路：这个是小米的二面里面的一道算法题，是...
2019-09-04 09:30:11
153
原创 字符串的调整与替换
题目：思路：这个是先找出左半边元素的总长度和空格的得数，然后计算出替换后的数组的总长度，接着从最后的位置开始进行替换。代码：public class zs2{ public static void main(String[]args){ Scanner sc=new Scanner(System.in); String a=sc.next...
2019-08-30 20:14:18
285
原创 在有序但还有空的数组中查找字符串
题目：思路：这个应该也可以用map的那种吧，不过需要遍历整个数组。复杂度是o(n);使用二分算法的话，时间复杂度是o(logn)。而且这个字符数组的话还是一个有序的字符数组。这个题我自己写的输入输出可能是有些问题，结果不正确。改用直接写数组是对的。代码：public static int method(String[]a1,String b){ if(a1==null||...
2019-08-27 17:04:00
147
原创 判断字符数组中是否所有的字符都只出现过一次
题目：思路：第一种是直接用一个数组组成 的map来统计出现的个数。第二种的思想是先对数组中的元素进行排序，这样相同的元素就会放在一起。重点是使用什么样的排序。对于时间复杂度是o(nlogn)的算法，归并排序需要额外的辅助数组，快速排序额外空间不能达到o(1);希尔排序的时间复杂度不固定，因此选择堆排序。但是一般堆排序是使用递归函数实现的，需要额外的栈空间，下面是左神书中使用的非递归...
2019-08-27 16:03:19
702
原创 剑指笔记—矩阵中的路径
题目：请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如 a b c e s f c s a d e e 矩阵中包含一条字符串"bccced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了...
2019-08-27 11:04:13
86
原创 字符串的统计字符串
题目：思路：这个题的整体思路就是遍历字符串，如果当前字符串和前一个字符串相等，计数就加1；如果不相等就先将之前相等的进行拼接。代码：import java.util.Scanner;/** * Created by Administrator on 2019/8/26. */public class zs2{ public static void main(...
2019-08-26 10:40:47
111
原创 替换字符串中连续出现的指定字符串
题目：思路：对str和from字符串一个一个进行匹配，找到from字符串后，将其替换成0，最后输出时，将不为0的字符串拼接起来。代码：import java.util.*;public class zs2 { public static void main(String []args){ Scanner sc=new Scanner(System.in);...
2019-08-26 09:53:16
252
原创 判断两个字符串是否为旋转词（KMP算法）
题目：思路：这个题首先需要判断两个字符串的长度，如果长度不相等的话直接返回false.接着创造一个新的字符串b1，是的b1=b+b。接着判断在新的字符串b1中是否包含有字符串a，这里使用的是KMP算法。这个算法我还不太懂。。。。先把左神的相关代码都写在下面。整个算法的时间复杂度是o(n),n是a,b字符串的长度。这个下午清醒了看。。。。。这个还是有点不理解。。。。代码：i...
2019-08-24 17:20:52
245
原创 将整数字符串转成整数值
题目：、思路：这个思路不复杂就是有点麻烦，直接看代码吧。。。代码：import java.util.*;public class zcy1 { public static void main(String[] args){ Scanner sc=new Scanner(System.in); String a=sc.next();//返回处理完的数...
2019-08-24 16:26:42
429
原创 去掉字符中连续出现的k个子串
题目：思路：这个题也是遍历一遍数组，当遇到特殊字符0时进行处理。需要注意的是以下几点：（1）我自己写输入输出的时候要注意，都是用next()。然后再进行转换（2）在取出字符0的时候，直接给相应位置的设置为数字0就可以了。在输出的时候判断以下不是0再输出就可以了代码：import java.io.*;import java.util.*;public class zcy...
2019-08-23 16:59:13
263
原创 字符串中数字子串的求和
题目：思路：这个题就是需要直接遍历整个字符串，然后对不同的字符进行处理，特别注意对负号的处理代码：import java.io.*;import java.util.*;public class zcy1 { public static void main(String[]args){ Scanner sc=new Scanner(System.i...
2019-08-23 16:18:54
481
原创 判断两个字符串是否为变形词
题目：思路：使用一个长度为256的数组作为map。在字符串1中出现的字符就加1；对于字符串2在相应的字符出减1.当整个数组中出现为负数的时候就代表这两个不是互行词。代码：mport java.io.*;import java.util.*;public class zcy1 { public static void main(String[]args){ ...
2019-08-23 15:07:28
251
原创 HW代码题-明明的随机数
题目描述：明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数（N≤1000），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作(同一个测试用例里可能会有多组数据，希望大家能正确处理)。输入：n...
2019-08-08 15:57:57
181
原创 HW代码题—全量字符集和已占用字符集
题目：有两个字符集，一个是全量字符集一个是已占用字符集，输出全量字符集中剩余的字符集。思路：代码是大神们写的，先放在这里。其实整体的思路是挺简单的，使用一个HashMap存储字符集中各个字符以及它们的个数，然后减去已占用字符集中存在的字符和个数。比较麻烦的是要自己处理输入输出，并且有很多字符串之间的转换。这两部分比较麻烦。首先要注意引入包，一般io,util包都是常用的，记住要写。使用Bu...
2019-08-08 15:47:12
2848
原创 HW代码题-字符串中的字符个数
题目描述写出一个程序，接受一个由字母和数字组成的字符串，和一个字符，然后输出输入字符串中含有该字符的个数。不区分大小写。输入描述:第一行输入一个有字母和数字以及空格组成的字符串，第二行输入一个字符。输出描述:输出输入字符串中含有该字符的个数。思路：感觉思路挺简单的，就是遍历整个字符串，找到相同的数量就加1，但是这个题是要区分大小写的，这个要注意。除了这个意外，我自己不熟的还有输入怎...
2019-08-07 16:38:34
196
原创 HW代码题-字符串最后一个单词的长度
题目描述计算字符串最后一个单词的长度，单词以空格隔开。输入描述: 一行字符串，非空，长度小于5000。输出描述: 整数N，最后一个单词的长度。思路：这个是我第一次碰见需要自己写输入输出的情况。代码来源：https://blog.csdn.net/weixin_42805929/article/details/82710420需要自己写主函数和引用包，同时还要使用输入输出的...
2019-08-07 15:56:35
132
原创 leetcode笔记—117填充每个节点的下一个右侧节点Ⅱ
题目：给定一个二叉树struct TreeLinkNode { TreeLinkNode *left; TreeLinkNode *right; TreeLinkNode *next;}填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。初始状态下，所有next 指针都被设置为 NULL。...
2019-07-09 09:44:16
150
原创 海量数据相关
以下基本来自左神的算法书相关题目：1.找到100亿url中最多出现的k个分析：这个只是知道一个大致的思路，先把思路写在这里。在大规模数据处理中，经常会遇到的一类问题：在海量数据中找出出现频率最高的前k个数，或者从海量数据中找出最大的前k个数，这类问题通常被称为top K问题。例如，在搜索引擎中，统计搜索最热门的10个查询词；在歌曲库中统计下载最高的前10首歌等。针对top...
2019-07-02 15:25:34
166
原创 布隆过滤器
题目：不安全网页的黑名单包含有100亿个黑名单网页，每一个网页的URL最多占用64B。现在想要设计一种网络过滤刺痛可以根据网页的URL判断URL是否在黑名单上，请设计该系统。要求：1.该系统允许有万分之一的判断失误率 2使用额外的空间不要超过30GB思路：以下来自左神的算法书。如果把全部的URL存储起来空间是不够的。如果以后遇到网页黑名单系统垃圾邮件过滤系...
2019-07-02 11:09:59
131
原创 最长公共子串问题
题目：给定两个字符串，返回两个字符串的最长公共子串思路：以下是来自左神的思路和代码。使用动态规划的思想。创建一个数组dp,dp[i][j]表示必须以str1[i]和str2[j]这两个字符结尾的最长公共子串的长度。对于第一行的元素即dp[0][j]若满足str2[i]==str1[0]则该值为1，否则该值为0；对以第一列也是如此。对于其他位置，如果str1[i]！=str2[j...
2019-07-02 10:16:56
512
原创 最长公共子序列——字节跳动
题目1：对于两个子序列 S1 和 S2，找出它们最长的公共子序列。思路1：以下内容来自大神CYC2008这是一个动态规划的问题定义一个二维数组 dp 用来存储最长公共子序列的长度，其中 dp[i][j] 表示 S1 的前 i 个字符与 S2 的前 j 个字符最长公共子序列的长度。考虑 S1i 与 S2j 值是否相等，分为两种情况：当 S1i==S2j 时，那么就能在 S1 的前 i...
2019-07-01 15:25:10
367
原创 leetcode笔记——646最长数对链
题目：给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。给定一个对数集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。示例 :输入: [[1,2], [2,3], [3...
2019-07-01 11:27:15
219
原创 leetcode笔记——300最长递增子序列
题目：给定一个无序的整数数组，找到其中最长上升子序列的长度。示例:输入: [10,9,2,5,3,7,101,18]输出: 4解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。说明: 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。 你算法的时间复杂度应该为 O(n2) 。进阶: 你能将算法的时间复杂度降低到 O(n log...
2019-07-01 10:25:58
962
原创 leetcode382-链表随机节点&蓄水池算法&多益笔试
题目：给定一个单链表，随机选择链表的一个节点，并返回相应的节点值。保证每个节点被选的概率一样。进阶:如果链表十分大且长度未知，如何解决这个问题？你能否使用常数级空间复杂度实现？示例:// 初始化一个单链表 [1,2,3].ListNode head = new ListNode(1);head.next = new ListNode(2);head.next.next = ...
2019-06-30 15:21:33
199
原创 leetcode-347前k个高频元素
题目：给定一个非空的整数数组，返回其中出现频率前 k 高的元素。示例 1:输入: nums = [1,1,1,2,2,3], k = 2输出: [1,2]示例 2:输入: nums = [1], k = 1输出: [1]说明： 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。 你的算法的时间复杂度必须优于 O(n log...
2019-06-29 15:38:10
195
原创 leetcode笔记——103二叉树的锯齿形层次遍历
题目：给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。例如：给定二叉树[3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7返回锯齿形层次遍历如下：[ [3], [20,9], [15,7]]思路：下面...
2019-06-25 17:16:00
98
原创 leetcode笔记——198打家劫舍
题目：你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。示例 1:输入: [1,2,3,1]输出: 4解释: 偷窃 1 号房屋 (金额 = 1) ，然后...
2019-06-18 10:19:06
106
原创 leetcode笔记——96不同的二叉搜索树
题目：给定一个整数 n，求以1 ...n为节点组成的二叉搜索树有多少种？示例:输入: 3输出: 5解释:给定 n = 3, 一共有 5 种不同结构的二叉搜索树: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 ...
2019-06-17 10:20:17
78
原创 LeetCode笔记——31下一个排列
题目：实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。必须原地修改，只允许使用额外常数空间。以下是一些例子，输入位于左侧列，其相应输出位于右侧列。1,2,3 → 1,3,23,2,1 → 1,2,31,1,5 → 1,5,1思路：先把leetcode中的解答和最快的解答放...
2019-06-16 16:43:57
95
原创 leetcode笔记——背包问题总结2
1.找零钱的最少硬币数322. Coin Change (Medium)题目：给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。示例 1:输入: coins = [1, 2, 5], amount = 11输出: 3解释: 11 = 5 + 5 + 1示例 ...
2019-06-16 16:38:44
1460
原创 leetcode笔记——背包问题总结1
这部分内容是参考大神CyC2018的代码和总结，将leetcode中和背包问题相关的放在这里。1.字符串按单词列表分割139. Word Break (Medium)这个问题也可以使用背包问题的思路，把这个代码放在问题139中了。2.划分数组为相等的两部分416. Partition Equal Subset Sum (Medium)题目：给定一个只包含正整数的非空数组。...
2019-06-16 10:28:18
439
原创 leetcode笔记——95不同的二叉搜索树Ⅱ
题目：给定一个整数 n，生成所有由 1 ...n 为节点所组成的二叉搜索树。示例:输入: 3输出:[ [1,null,3,2], [3,2,null,1], [3,1,null,null,2], [2,1,3], [1,null,2,null,3]]解释:以上的输出对应以下 5 种不同结构的二叉搜索树： 1 3 3 ...
2019-06-13 16:40:17
116
原创 求两个数组的交，并，补集
题目：给出两个数组，分别求出这两个数组的交集，并集和补集思路：主要还是利用了HashSet的去重功能，在set中不存在相同的元素代码：public class Substract { public static void substract(int[] arryA, int[] arryB) { HashSet<Integer> set = new...
2019-06-06 21:18:15
946
原创 leetcode笔记——92反转链表Ⅱ
题目：反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。说明:1 ≤m≤n≤ 链表长度。示例:输入: 1->2->3->4->5->NULL, m = 2, n = 4输出: 1->4->3->2->5->NULL思路：网上百度了大神的解法，原文链接：https://www.jianshu.com/...
2019-06-06 20:56:31
104
原创 背包问题总结
在笔试的时候碰到了这个背包问题，是第一次做，因此在这里把相关的问题都总结在这里。参考大神的代码，链接如下：https://blog.csdn.net/lanyu_01/article/details/79815801 https://blog.csdn.net/na_beginning/articl...
2019-06-06 11:08:00
469
原创 leetcode笔记——206反转链表
题目：反转一个单链表。示例:输入: 1->2->3->4->5->NULL输出: 5->4->3->2->1->NULL进阶:你可以迭代或递归地反转链表。你能否用两种方法解决这道题？思路：使用迭代和递归两种思路解决这个问题。代码：以下代码来自CyC2018递归代码：public ListNode ...
2019-06-03 10:16:57
129
原创 leetcode笔记——145 二叉树的后序遍历
题目：给定一个二叉树，返回它的 后序遍历思路：这个题之前总结二叉树的相关知识的时候写过，但是后序遍历比较难，所有在这里单独把后序遍历拿出来总结下。以下的代码来自leetcode评论中大神的代码，分别使用递归，迭代和另外一种方法进行后序遍历。代码：（1）递归写法class Solution { public List<Integer> res = new Arra...
2019-05-17 11:18:05
119
原创 剑指笔记——66.构建乘积数组
题目：给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]A[1]...A[i-1]A[i+1]...A[n-1]。其中A[i] = 1。不能使用除法思路：根据剑指中的思路，可以使用矩阵法求解，将矩阵分为上三角矩阵和下三角矩阵，分别求解乘积。代码：public int[] multiply(int[] A) {int l...
2019-05-11 15:42:04
103
原创 剑指笔记——65 不用加减乘除做加法
题目：写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号思路：根据剑指中的思路，我们可以 用位运算代替二进制的加法运算。第一步不用考虑进位对每一位相加。这一步的结果和两数异或的结果相同；第二步进位相当于是两个数进行与运算再向左移动一位；第三部将前两个步骤的结果相加，知道不产生进位为止。代码：public int Add(int num1,int num2) {w...
2019-05-11 10:06:51
83
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人