Algorithm Basic(1)Algorithm in Java
1. Basic
Time O(1), O(n), O(n^2), O(n^3), O(2^n)
Storage
array is set, it is fast, but the length is set.
Collection
—List can have repeat objects
—ArrayList / LinkedList / Vector
—Set can not have repeat objects
—HashSet / TreeSet
Map
—HashMap
—HashTable
—TreeMap
List is interface, Implemented by ArrayList, Vector, LinkedList
ArrayList
good for list and search, bad for insert and delete.
length is not enough, then increase by 1.5 times and array copy happened,
int newCapacity = oldCapacity + (oldCapacity >> 1);
Arrays.copyOf(elementData, newCapacity)
Operator >> : System.out.println(10 >> 1); // 5
System.arraycopy
int[] ids1 = { 1, 2, 3, 4, 5 };
int[] ids2 = newint[6];
//copy ids1 begin from index 1, copy 3 elements to ids2 from index 0
System.arraycopy(ids1, 1, ids2, 0, 3);
System.out.println(Arrays.toString(ids2));
//[2, 3, 4, 0, 0, 0]
even we do add(int index, object), remove, we need to do array copy…..
LinkedList good for insert and delete
It is based on linked list.
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
Vector is slow than ArrayList
similar to ArrayList, and we have synchronized in the codes.
Bubblesort for Array
package com.sillycat.easyalgorithm.sort;
import java.util.List;
import java.util.Vector;
public class Bubblesort implements Sorter {
@Override
public void sort(List<Integer> list) {
if (list.isEmpty()) {
System.out.println("Vector can not be null!");
return;
}
Integer bak;
boolean flag = true;
while (flag) {
flag = false;
for (inti = 0; i < list.size() - 1; i++) {
System.out.println("counting ....");
bak = list.get(i);
if (bak > list.get(i + 1)) {
flag = true;
list.set(i, list.get(i + 1));
list.set(i + 1, bak);
}
}
}
}
public static void main(String[] args) {
Vector<Integer> v1 = new Vector<Integer>();
v1.add(1);
v1.add(9);
v1.add(3);
v1.add(11);
v1.add(6);
System.out.println(v1);
Bubblesort sort1 = new Bubblesort();
sort1.sort(v1);
System.out.println(v1);
}
}
At most, if we have an array N, we need N scan we have the array in right order. a = 2, f(n)=n^2, T(n) = O(n^2)
2. How to Check if Algorithm is good or bad
Time Complexity
Space Complexity
O(1) Complexity
Find the random number in an array, not the biggest, not the smallest, just pick first 3 numbers, sort it, pick up the middle number. O(3) + O(3) + O(1) = O(7)
O(log n) Complexity
10 to 3 functionality
package com.sillycat.easyalgorithm.basic;
public class BaseConversion {
public static int convert10to3(intsource){
String result = "";
while(source != 0){
result = source % 3 + result;
source = source / 3;
}
return result.isEmpty()? 0 : Integer.valueOf(result);
}
public static void main(String[] args) {
//convert 23(10) = 212(3)
System.out.println("23(10) = " + convert10to3(23) + "(3)");
//convert 0(10) = 0(3)
System.out.println("0(10) = " + convert10to3(0) + "(3)");
//convert 101(10) = 10202(3)
System.out.println("101(10) = " + convert10to3(101) + "(3)");
}
}
Adjust to convert to N
package com.sillycat.easyalgorithm.basic;
public class BaseConversion {
public static int convert10toRate(intsource, intrate) {
String result = "";
while (source != 0) {
result = source % rate + result;
source = source / rate;
}
return result.isEmpty() ? 0 : Integer.valueOf(result);
}
public static void main(String[] args) {
// convert 23(10) = 212(3)
System.out.println("23(10) = " + convert10toRate(23, 3) + "(3)");
// convert 0(10) = 0(3)
System.out.println("0(10) = " + convert10toRate(0, 3) + "(3)");
// convert 101(10) = 10202(3)
System.out.println("101(10) = " + convert10toRate(101, 3) + "(3)");
System.out.println("==============================");
// convert 2(10) = 10(2)
System.out.println("2(10) = " + convert10toRate(2, 2) + "(2)");
// convert 0(10) = 0(2)
System.out.println("0(10) = " + convert10toRate(0, 2) + "(2)");
// convert 101(10) = 1100101(2)
System.out.println("101(10) = " + convert10toRate(101, 2) + "(2)");
}
}
1 + |log3n| = O(log3n) = O(logn)
References:
http://daiziguizhong.qiniudn.com/article_20140305-18-32-10.html#rd
http://baike.baidu.com/view/7527.htm
http://javarevisited.blogspot.com/2013/03/top-15-data-structures-algorithm-interview-questions-answers-java-programming.html
http://www.cnblogs.com/wanlipeng/archive/2010/10/21/1857791.html
http://www.360doc.com/content/08/1027/15/61497_1833598.shtml
System.arraycopy(…)
http://blog.csdn.net/java2000_net/article/details/4059465
相关推荐
Algorithm-algorithm_basic_java.zip,这是一个储存库,总结了主要在编码采访中的算法问题。它是基于Java语言编写的。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
"Basic-algorithm-exercises" 是一个专为Java学习者设计的项目,旨在帮助初学者和进阶者通过实践来提升算法理解与应用能力。 这个项目的核心内容是"Basic-algorithm-exercises-master",它包含了多个子目录和文件,...
在“java-basic-algorithm”这个主题中,我们将深入探讨Java编程中的基本算法,这些算法是任何Java程序员都需要掌握的核心概念。 一、算法概述 算法是一组清晰定义的规则或步骤,用于解决特定问题或执行特定任务。...
"JavaData:Java_basic_sorting_algorithm简单"这个主题聚焦于Java中的基础排序算法,这些算法对于理解计算机科学的基本原理至关重要。下面将详细讨论几种常见的Java排序算法。 1. 冒泡排序(Bubble Sort): 冒泡...
Genetic Algorithms in Java Basics...Chapter 2: Implementation of a Basic Genetic Algorithm Chapter 3: Robotic Controllers Chapter 4: Traveling Salesman Chapter 5: Class Scheduling Chapter 6: Optimization
Chapter 1: Java Basics – you will learn the basic programming elements of the Java language, including how to set up your programming environment, using a text editor and how to write a program....
【描述】"java compiler code source for that are nice work wassim ahmed algorithm oj" 提到的是Java编译器源代码,这部分内容可能包括了用于解决算法问题的代码,可能是在在线判题平台(Online Judge, OJ)上...
Algorithms in Java, 3rd Ed, Part 1-4 - Robert Sedgewick Algorithms in Java, 3rd Ed, Part 5 Graph Algorithms - Robert Sedgewick C Algorithms For Real Time DsP - Paul Embree C and Data Structures - P.S....
**标题与描述:“Thinking in Patterns – Problem Solving Techniques using Java”** 本标题及描述主要聚焦于通过Java语言来实现“思维模式”(Thinking in Patterns)的概念。这里提到的“思维模式”,指的是软件...
C语言和Java中,通过二维数组可以方便地表示和操作矩阵,对于复杂的矩阵运算,可以利用库函数如OpenCV和BLAS(Basic Linear Algebra Subprograms)来提升性能。 接着是背包问题,这是运筹学中的一个经典问题,常...
以"bi"开头的文件(如`bi2015`、`biii2015`等)可能是"Basic"或"Basics"部分,它们可能涵盖Java的基础语法、类与对象、数据类型、流程控制(如if语句、for循环、while循环)、异常处理、数组和集合框架等核心概念。...
and then lays out the basic JavaScript foundations, such as primitive objects and types. Then, this book covers implementations and algorithms for fundamental data structures such as linked lists, ...
One result you must report is that when setting the teleport parameter to 0.85.In addition to the basic PageRank algorithm, you need to implement the Block-Stripe Update algorithm (see pages 52-61 in ...
MD5加密算法(Java版) 可以运行 原理 对MD5算法简要的叙述可以为:MD5以512位分组来处理输入的信息,且每一分组又被划分为16个32位子分组,经过了一系列的处理后,算法的输出由四个32位分组组成,将这四个32位...
Every programming language that can access a standard Win32 dll can use HIME: C, C++, C#, Visual Basic 5/6, VB.Net, Delphi, PowerBASIC, PureBASIC, Liberty Basic, Euphoria, Java, Macromedia Director ...
top.hengshare.interviewer.basic java基础 spring spring、spring组件源码分析 database 数据库 动态的切换数据源,你会怎么切?读写分离? struts 数据结构 thread 多线程、并发 有关多线程的一些小例子,在《Java...
org.geotools.geometry.iso.util.algorithm2D org.geotools.geometry.iso.util.algorithmND org.geotools.geometry.iso.util.elem2D org.geotools.geometry.iso.util.interpolation org.geotools.geometry.iso....
1. 寄存器分配的重要性: 在计算机程序执行过程中,寄存器比内存访问速度更快。通过有效地利用有限的寄存器资源,可以减少内存访问,从而显著提升程序性能。局部寄存器分配器便是为此目标服务的,它在编译阶段进行...