Depp Wang's Blog

这是副标题

  • 首页
  • 归档
  • 推荐
  • 分类
  • 标签
  • 搜索

有序数组转换成二叉查找树 (Java 实现)

发表于 2017-09-14 | 分类于 Algorithms | | 阅读次数

[二叉查找树](https://zh.wikipedia.org/wiki/% E4% BA%8C% E5%85%83% E6%90%9C% E5% B0%8B% E6% A8% B9) 也称为排序二叉树或有序二叉树。将二叉查找树中序遍历就能得到一个有序数组。所以,有序数组转换成二叉查找树是中序遍历的逆操作。将数组中下标为中数的元素作为根节点,利用递归实现转换。以下是实现代码:

阅读全文 »

用数组实现 Stack

发表于 2017-09-13 | 分类于 Algorithms | | 阅读次数

在一些面试题中,常常出现用数组实现 Stack,主要实现它的 push()/push()/pop() 方法。也可以用容器(List)和链表实现,可以看 这篇博文。以下是使用数组实现 Stack:

阅读全文 »

逐行分析 HashMap 的 put() 方法源码

发表于 2017-08-15 | 分类于 Java | | 阅读次数

Image result for hashmap works internally in java

HashMap 是底层结构是数组 + 链表,数组是存放 Node(Entry)的数组 Entry[],链表是 Node 组成的链表,充分利用了 Node 的特性。链表的头结点存放在数组中。

put 方法的大致思路

  1. 调用 hash(key) 方法,根据 key 对象的 hashCode 计算出 kay 的 hash,根据 hash 计算出其在 tab 数组中的 index,将键和值放入 Node(Entry) 中;
  2. 如果 index 位置的 Node 为空,称为没碰撞,直接 Node 放入数组中;
  3. 如果碰撞(index 位置存在 Node),先跟头结点比较,key 不相等时,循环链表比较,如果 key 已经存在,替换 old value,否则将 Node 链接到链表最后。
  4. 如果碰撞导致链表的长度大于等于 7,将链表的结构转换为红黑树。
  5. 如果 bucket 存放的 current capacity(当前容量)超过容量的 load factor(0.75),就 resize,容量扩大为两倍。
阅读全文 »

Java 的参数传递

发表于 2017-07-26 | 分类于 Java | | 阅读次数

一、传值和传址(引用)

Java 的参数传递分为传递基本数据类型(传值)和传递引用数据类型(传址)

阅读全文 »

String 的两种实例化方式

发表于 2017-07-24 | 分类于 Java | | 阅读次数

String 的两种实例化方式

隐式实例化:直接赋值

public class Demo {
public static void main(String[] args) {
String s = "hello";
String s2 = "hello";
System.out.println(s == s2);
}
}
true
阅读全文 »

Object 的常用方法

发表于 2017-07-21 | 分类于 Java | | 阅读次数

所有的类都默认继承 Object 这个基类。

基本数据类型不是类,所以不继承,但它们的封装类继承,使用基本数据类型时会自动封箱为其封装类。equals()、hashCode()、getClass() 和 toString() 是 Object 常用的方法。

equals(Object obj) 方法

API,源码:

public boolean equals(Object obj) {
return (this == obj);
}

== 用于比较两个数值是否相等。

== 比较基本数据类型时,用来判断两个基本数据类型数值是否相等;引用变量存放的是对象在堆中的地址,== 比较两个引用时,比较两个地址的数值是否相等,即判断两个引用是否指向同一个对象。

int a = 1;
int a1 = 2;
a == a1; // false

Dog d = new Dog();
Cat c = new Cat();
Cat c2 = new Cat();
Dog d2 = d;
d == c; // false; 因为两个实例对象不同
c == c2; // false; 因为引用 c 和 c2 指向不同实例
d == d2; // true; 因为引用 d 和 d2 指向同一实例

所以 equals 方法用于判断两个对象是否在意义上相等,即这两个对象是否是同一个对象。

d.equals(c); // false
c.equals(c2); // false
d.equals(d2); // true

String 重写了 equals 方法,比较两个 String(匿名)对象是否带有相同的字节组合:

public boolean equals(Object anObject) {
// 比较两个引用是否指向字符串常量池中同一个字符串常量(匿名对象)
if (this == anObject) {
return true;
}
// 比较两个 String 对象是否带有相同的字节组合
if (anObject instanceof String) {
String anotherString = (String)anObject;
int n = value.length;
if (n == anotherString.value.length) {
char v1[] = value;
char v2[] = anotherString.value;
int i = 0;
while (n-- != 0) {
if (v1[i] != v2[i]) // 比较每一个字符是否相同
return false;
i++;
}
return true;
}
}
return false;
}
阅读全文 »

算法:数据结构之反转字符串

发表于 2017-07-18 | 分类于 Algorithms | | 阅读次数

反转字符串

题目描述:将字符串 "##We###Are###Family!###" 反转为 "###!ylimaF###erA###eW##"。

分析与解答:这题我们的解答方法有很多,常见的方法是使用数组,下面来介绍用数据结构中的 Stack(栈)来完成反转。

Stack 的特点是 FILO(First In,Last Out)— 先进后出。此特点用于将字符串反转非常合适,以下是代码实现:

import java.util.Stack;

public class Demo {
public static void main(String[] args) {
System.out.println(ReverseAllStringWithStack("##We###Are###Family!###"));
}

public static String ReverseAllStringWithStack(String string) {
// 如果 string 等于 null 或等于 "" 时,返回 string。
if (string == null || string.length() == 0)
return string;
// 新建一个 Stack,用于存放 Character 类型。为什么存放 Character 而不是 char,
// 因为泛型只能指定是类或接口类型,而不能是 primitive 主(基本)数据类型。
Stack<Character> stringStack = new Stack<>();

char[] array = string.toCharArray();//toCharArray() 将字符串转换成 char 类型数组
// 使用 for-each 将数组中的元素 push(推)进 Stack
for (Character c : array) {
stringStack.push(c);
}
int length = string.length();// 数组的长度 length; 字符串的长度 length(); 集合的长度 size()
// 利用 for 循环将元素从栈顶开始,依次弹出
for (int i = 0; i < length; i++) {
array[i] = stringStack.pop();
}

return new String(array);//String 的重载构造方法将 char[] 数组转换,返回一个实例化 String 对象
}
}
阅读全文 »

从字节码(ByteCode)角度理解 String 的连接

发表于 2017-07-15 | 分类于 Java | | 阅读次数

首先来看一道题。

题目描述

问下面两种赋值方式有何区别?

public class Demo {
public static void main(String[] args) {

String s = "1" + "2" + "3";

String s1 = "1";
String s2 = s1 + "2";
String s3 = s2 + "3";

System.out.println(s);
System.out.println(s3);
}
}

分析与解答

从表面其实看不出什么,我们可以通过 Class 文件反编译成的字节码(Byte Code)来分析。

如果你在使用 IDEA,请先在 IDEA 中安装 ASMified Bytecode Outline 插件,点击 安装详细教程,如果是其他集成环境,请自行 Google 安装插件教程。

阅读全文 »

Java 虚拟机运行时数据区域

发表于 2017-07-13 | 分类于 JVM | | 阅读次数

JVM 对于是每个 Java 程序员掌握一定 Java 基础后,都需要学习的。因为很多代码问题,只能了解了 JVM 底层原理后才能解决。大多数 Java 后端开发者都知道堆(Heap)和栈(Stack)的概念,却没有真正理解其原理。推荐 《深入理解 Java 虚拟机(第二版)》— 周志明著 学习 JVM。

进程和线程

学习 JVM 前要了解进程和线程的概念。

以下是一个类比,来自 阮一峰 — 进程与线程的一个简单解释。

  1. 计算机的 CPU 是像一座工厂,时刻在运行。
  2. 因工厂电力有限,一次只能供给一个车间使用。也就是说,一个车间开工的时候,其他车间都必须停工。背后的含义就是,单个 CPU 一次只能运行一个任务。
  3. 进程就好比工厂的车间,它代表 CPU 所能处理的单个任务。任一时刻,CPU 总是运行一个进程,其他进程处于非运行状态。
  4. 一个车间里,可以有很多工人。他们协同完成一个任务。
  5. 线程就好比车间里的工人。一个进程可以包括多个线程。
阅读全文 »

我奶奶人很胖,但心很美

发表于 2017-07-09 | 分类于 Live | | 阅读次数

我奶奶生在一个重男轻女的家庭中,她小时候被她的亲生母亲虐待,让她的右脚落下了隐疾。但奶奶不以此为芥蒂,始终性格开朗,特别爱笑。

起雾了

奶奶人很胖,饭量大,脚大,笑起来声音也大。我听我爷爷说,他娶奶奶的时候是 27 岁,奶奶是 20 岁。爷爷那时候是铁匠,给远近乡邻铸造各种生活、农耕工具。奶奶料理家务,兼顾农田,两人虽然日子清苦,但尚能温饱。

阅读全文 »
1…678
Depp Wang

Depp Wang

每个人都需要有自己的哈姆雷特

80 日志
25 分类
95 标签
RSS
GitHub Twitter
Links
  • 廖雪峰的官方网站
  • 阮一峰的网络日志
  • CoolShell
  • 1byte
© 2021 Depp Wang
由 Hexo 强力驱动
主题 - NexT.Mist
本站总共被访问 次    你是第 位小伙伴