Yaphat-CSDN博客

原创二叉树最大路径和

题目描述给出一棵二叉树，寻找一条路径使其路径和最大，路径可以在任一节点中开始和结束（路径和为两个节点之间所在路径上的节点权值之和）思路首先我们分析一下对于指定某个节点为根时，最大的路径和有可能是哪些情况。第一种是左子树的路径加上当前节点，第二种是右子树的路径加上当前节点，第三种是左右子树的路径加上当前节点（相当于一条横跨当前节点的路径），第四种是只有自己的路径。乍一看似乎以此为条件进行自下而上递归就

2017-09-04 13:32:58 1656

原创二叉树中和为某值的路径

题目描述输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。思路这道题有好几个需要注意的细节。public class Solution { ArrayList<ArrayList<Integer>> listall=new ArrayList<ArrayList<Integer>>(); Arr

2017-09-03 17:06:35 614

原创二叉树序列化和反序列化

题目描述请实现两个函数，分别用来序列化和反序列化二叉树实现public class Solution { String Serialize(TreeNode root) { StringBuffer sb=new StringBuffer(); if(root==null){ sb.append("#,"); r

2017-09-01 18:32:36 599

原创二叉搜索树转为双向链表

题目描述输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。实现中序遍历二叉搜索树就可以，需要记录节点的前一个指针。同时需要标记下是否是双向链表的头节点public TreeNode Convert(TreeNode root) { Stack<TreeNode> stack=new Stack<TreeNode>();

2017-09-01 17:26:20 522

原创二叉树

二叉树的常见操作import java.util.LinkedList;import java.util.Queue;import java.util.Stack;import javax.swing.LayoutStyle;import java.util.ArrayList;class TreeNode { int val; TreeNode left; Tre

2017-09-01 16:02:48 490

原创螺旋矩阵顺时针打印

问题描述输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.解法需要注意四个边界。import java.util.ArrayList;public class Solution {

2017-09-01 15:49:21 978

原创最大下标距离

题目描述给定一个整形数组，找出最大下标距离j−i, 当且A[i]解法public static int maxindexdistance(int A[]) { boolean[] isDes = new boolean[A.length]; int min = A[0]; isDes[0] = true; for (int i = 0;

2017-09-01 15:34:12 566

原创两数之和

题目描述给定一个整型数组，找出其中的两个数使其和为某个指定的数，并返回两个数的下标。思路这里其实要考虑数组可能出现相同值的情况。public int[] twoSum(int[] nums, int target) { int[] result=new int[2]; Map<Integer,Integer> map=new HashMap<Integer,Integ

2017-09-01 11:03:19 378

原创数组奇偶划分

题目描述输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分。情况一不需要保证奇数和偶数之间相对位置不变。这里可以用快排的思想。时间复杂度为O（n）public static int[] reOrderArray(int[] array) { int left = 0; int right =

2017-08-28 15:06:42 2586

原创数组中出现次数超过一半的数字

问题描述数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。思路一最容易想到的思路就是对数据排序，那么中间的数字就是要求的数字。时间复杂度就是排序的复杂度思路二下面说一下复杂度是O(n)的解法如果有符合条件的数字，则它出现的次数比其他所有数

2017-08-28 14:36:58 406

原创重建二叉树

问题描述输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。思路这道题还是有点绕的，尤其是索引值的确定，多想想吧。递归思想，每次将左右两颗子树当成新的子树进行处理，中序的左右子树索引很好找，前序的开始结束索引通过计

2017-08-25 15:03:17 369

原创搜索排序数组

问题描述假设有一个排序的按未知的旋转轴旋转的数组(比如，0 1 2 4 5 6 7 可能成为4 5 6 7 0 1 2)。给定一个目标值进行搜索，如果在数组中找到目标值返回数组中的索引位置，否则返回-1。解决对于这种部分有序的数组都可以使用二分法 public int search(int[] A, int target) { int low=0; int hi

2017-08-24 17:17:30 596

原创翻转链表

翻转链表的两种情况翻转单链表很简单public ListNode reverseList(ListNode head) { ListNode tmp=null; ListNode dummy=new ListNode(0); dummy.next=null; while(head!=null){ tmp=head

2017-08-23 18:45:12 439

原创最大公共子串&&最大公共子序列

问题描述最大公共子序列给出两个字符串，找到最长公共子序列(LCS)，返回LCS的长度。状态转移方程为：如果A[i]=A[j],则dp[i][j]=dp[i-1][j-1]+1，如果不等，则dp[i][j]=Math.max(dp[i][j-1],dp[i-1][j])public class Solution { /** * @param A, B: Two strings.

2017-08-18 16:32:13 450

原创最长上升子序列

问题描述给定一个整数序列，找到最长上升子序列（LIS），返回LIS的长度。public class Solution { /** * @param nums: The integer array * @return: The length of LIS (longest increasing subsequence) */ public int long

2017-08-18 16:24:38 395

原创寻找旋转排序数组中的最小值

问题描述假设一个旋转排序的数组其起始位置是未知的（比如0 1 2 4 5 6 7 可能变成是4 5 6 7 0 1 2）。你需要找到其中最小的元素。没有重复值public class Solution { /** * @param nums: a rotated sorted array * @return: the minimum number in the arr

2017-08-18 15:53:44 460

原创推荐算法的优缺点

基于领域的协同过滤基于矩阵分解矩阵分解方法将高维User-Item评分矩阵映射为两个低维用户和物品矩阵，解决了数据稀疏性问题。优点：预测精度较高缺点： 1、模型训练比较费时。 2、不具有很好的可解释性。分解出来的用户和物品矩阵的每个维度无法和现实生活中的概念来解释，无法用现实概念给每个维度命名，只能理解为潜在语义空间待填

2017-06-08 16:41:39 12533

原创链表去重

题目在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。例如，链表1->2->3->3->4->4->5 处理后为 1->2->5思路1、链表头可能被删除，在前面再加一个head节点， 2、如果当前元素没有重复的，则加入列表中 3、如何判断当前元素有没有重复，使用一个指针记录当前元素第一次出现的节点，然后第二个指针遍历具有相同元素的节点，便利完之后，

2017-04-25 13:59:02 1487

原创特征冗余

刻画特征之间相似性的几种方法： 1、对称不确定性（SU）：取值在（0，1）之间，值越大，X，Y之间相关性越大，当取值为0，表示X,Y之间相互独立，反之，代表之间具有强依赖性，意味着当知道其中一个变量就可以推测出另一个变量。∑i=0ni2=(n2+n)(2n+1)6\sum_{i=0}^n i^2 = \frac{(n^2+n)(2n+1)}{6}可以分为C-相关和F-相关，任何一个特征f和类别C之

2017-04-24 20:33:17 10948 1

原创 Top K

问题描述：在一维数组中找到第K大的数。比如说: 数组[3,2,1,5,6,4] k = 2, 返回 5.解法一：最容易想到的就是排序整个数组。可以用快速排序的方法。public int findKthLargest(int[] nums, int k) { final int N = nums.length; Arrays.sort(nums);

2017-04-24 11:06:03 726

原创最近公共父节点

1、二叉树最低公共父节点题目描述：构建一棵二叉树（不一定是二叉查找树），求出该二叉树中某两个结点的最低公共父结点。public class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(root==null || root==p ||

2017-04-18 15:35:19 789

原创远程访问jupyter notebook

1、登录服务器,生成配置文件$jupyter notebook --generate-config此时会在~/.jupyter目录下生成一个jupyter_notebook_config.py文件2、打开ipython，生成一个密文密码from notebook.auth import passwdpasswd()Enter password: Verify password: Out[2]

2017-04-16 10:28:05 629

原创从上到下打印二叉树

题目描述从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。解题思路类似之子形打印，但这里是顺序打印，所以可以用两个队列。java实现代码：import java.util.ArrayList;import java.util.Queue;import java.util.LinkedList;/*public class TreeNode { int val = 0;

2017-04-10 17:02:07 371

原创按之字形打印二叉树

题目描述请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。解题思路以题目中的二叉树为例，一步步分析。1、当二叉树的根结点（结点1）打印之后，它的左子结点（结点2）和右子结点（结点3）先后保存到一个容器中。值得注意的是，在打印第二层的结点时，先打印结点3，后打印结点2。由此可见结点在这个容器中是后进先出的，

2017-04-10 16:56:49 650

原创对称的二叉树

题目描述：请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。解题思路左子树的左子树和右子树的右子树相同，左子树的右子树和右子树的左子树相同，则为对称。/*public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null;

2017-04-10 15:39:05 394

原创二叉查找树中搜索区间

题目描述：给定两个值 k1 和 k2（k1 < k2）和一个二叉查找树的根节点。找到树中所有值在 k1 到 k2 范围内的节点。即打印所有x (k1 <= x <= k2) 其中 x 是二叉查找树的中的节点值。返回所有升序的节点值。样例如果有 k1 = 10 和 k2 = 22, 你的程序应该返回 [12, 20, 22].20 / \ 8 22 / \ 4 12解

2017-04-09 21:11:11 655

原创 Credit Card Fraud Detection（信用卡诈欺侦测）Spark建模

数据格式这个数据来自2013年9月欧洲信用卡交易数据，总共包括两天的交易数据。在284,807次交易中发现了492例诈骗。数据集极其不平衡，诈骗频率只占了交易频次的0.172%。这个数据因为涉及敏感信息，用PCA处理过了，V1,V2,…V28是主成分，‘Time’和‘Amount’是没有经过PCA处理的。‘Time’是每次交易与第一次交易之间距离的时间，以秒计。‘Amount’代表消费金额，‘C

2017-04-02 16:14:43 8318 5

原创 German Credit Risk(德国信用卡违约分析)

数据信息先看下数据格式：总共有20个属性，1个类别特征。信息如下：Attribute 1: (qualitative) Status of existing checking account A11 : … < 0 DM A12 : 0 <= … < 200 DM A13 : … >= 200 DM / salary assignments for at least 1 year

2017-03-29 22:44:46 10659 4

原创 Spark MLlib Python Notebook配置

在Spark上使用pySpark shell很麻烦，只能在命令行中输入。除了可以用spark submit提交应用外，也可以用jupter notebook。运行ipython打开notebook$ jupyter notebook初始化 pysparkimport osexecfile(os.path.join(os.environ["SPARK_HOME"], 'python/pyspark/

2017-03-29 14:48:27 1369

原创 Java常见面试题

1、Hashtable和HashMap的区别 Hashtable是线程安全的，HashMap不是线程安全的。即Hashtable的方法是Synchronize的，而HashMap不是。由于非线程安全，HashMap效率上比Hashtable高一点。 HashMap允许null健值，而HashMap不允许。 2、待填

2017-03-17 21:34:26 400

原创海量数据常见面试题

待填

2017-03-17 21:28:37 704

原创递归

对递归程序一直是一知半解，对于简单的递归程序，我大致能弄懂整个流程，但是复杂点的递归程序（比如说树的各种递归）就一头雾水。今天在看知乎时，看到一个非常不错的建议。大致如下。写递归函数要处理好递归的3个主要点： a) 出口条件，即递归通常什么时候结束，这个通常在递归函数的开始就写好； b) 如何由”情况 n” 变化到”情况 n+1”, 也就是非出口情况，也就是一般情况——”正在”递归中的情况；

2017-03-10 16:31:46 699

原创 SMOTE相关论文

Borderline-SMOTE：Borderline-SMOTE: A New Over-Sampling Method in Imbalanced Data Sets Learningmotivation：有些样本远离边界，所以对分类没有多大帮助，可以强化边界点。思路：将少数类样本根据距离多数类样本的距离分为noise,safe,danger三类样本集，只对danger中的样本集合使用smot

2017-03-04 21:11:54 9009 29

原创 equals()和hashcode()

Java对象的eqauls方法和hashCode方法是这样规定的：1、相等（相同）的对象必须具有相等的哈希码（或者散列码）。为什么？想象一下，假如两个Java对象A和B，A和B相等（eqauls结果为true），但A和B的哈希码不同，则A和B存入HashMap时的哈希码计算得到的HashMap内部数组位置索引可能不同，那么A和B很有可能允许同时存入HashMap，显然相等/相同的元素是不允许同时存入

2017-03-04 20:30:35 461

原创 MapReduce实现KMeans

具体方法：k-means的每一次迭代都可以分为以下3个步骤。第一步：Map：对于每一个点，将其对应的最近的聚类中心第二步：Combine：刚完成map的机器在本机上都分别完成同一个聚类的点的求和，减少reduce操作的通信量和计算量。第三步：reduce：将同一聚类中心的中间数据再进行求和，得到新的聚类中心 k-means 聚类算法进行 MapReduce 的基本思路:对串行算法中

2017-02-23 22:34:12 2705

原创排序算法和java实现

一、冒泡排序1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。 2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。 3、针对所有的元素重复以上的步骤，除了最后一个。 4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。public static void bubblesort(int[] array){

2017-02-10 14:52:27 486

原创图片的数据增强（Data Augmentation）方法

在深度学习中，为了避免出现过拟合（Overfitting），通常我们需要输入充足的数据量．若数据量比较小，可以对原有的图像数据进行几何变换，改变图像像素的位置并保证特征不变。旋转 | 反射变换(Rotation/reflection): 随机旋转图像一定角度; 改变图像内容的朝向;翻转变换(flip): 沿着水平或者垂直方向翻转图像;缩放变换(zoom): 按照一定的比例放大或者缩小图像;平

2017-01-05 22:20:10 12584

原创 CentOS安装显卡驱动

从 ELRepo 源中安装驱动1、添加 ELRepo 源rpm --import https://www.elrepo.org/RPM-GPG-KEY-elrepo.oryum install http://www.elrepo.org/elrepo-release-7.0-2.el7.elrepo.noarch.rpm2、需要卸载以下软件包及其依赖yum remove xorg-x11-glam

2016-12-15 11:15:18 2360 1

原创安装CUDA和cuDNN

下面是CentOS系统安装过程1、CUDA安装官方下载：https://developer.nvidia.com/cuda-downloadssudo rpm -i cuda-repo-rhel7-8.0.44-1.x86_64.rpmsudo yum clean allsudo yum install cuda设置环境变量# CUDA Toolkitexport CUDA_HOME=/u

2016-12-14 22:57:48 4468

原创 TensorFlow实现CNN

用TensorFlow实现CNN来做MNIST分类，做了很明确的标注。# encoding:utf-8import tensorflow as tffrom tensorflow.examples.tutorials.mnist import input_datamnist = input_data.read_data_sets("MNIST_data/data", one_hot=True)

2016-12-08 17:17:29 1795

空空如也

空空如也