今天的主要的目标是：
1， 学习一个算法：最长的回文的算法（最长的公共子序列和最长的公共子串）
2， 搞明白一个并发编程的类: 原子类
3， 外加一个知识点：原子类的用法
一个算法：最长的回文字符
/**
* 第一种方法：采用最长的子串
* 把要求的字符串s,颠倒一下变为s`,然后求取两个字符串的最长公共子串，LCS
* 这个是把未知的问题转化为已知的问题
* */
public String longestPalindrome1(String s) {
//构建辅助的s`
String ss = changeOver(s);
String lcs = longestCommomSubstring(s, ss);
return lcs;
}
/**
* 求取两个字符串的最长的公共子序列<br>
* 采用的是动态规划的算法，两个字符串s1，s2 怎么算出最长的公共子序列的？状态的转移的方程是什么样子的？<br>
* 假设 km 是字符转ai 和 bj 的最长的公共的子序列。k[0,1,2,......m] = lcs(a[0,1,2,3,......i],b[0,1,2,3,......j];<br>
* 那么如果字符a[i] == b[j] 那么km = a[i] ，k[0,1,2,......m-1] = lcs(a[0,1,2,3,......i-1],b[0,1,2,3,......j-1];<br>
* 那么如果字符a[i] != b[j] 并且km = a[i] ，k[0,1,2,......m-1] = lcs(a[0,1,2,3,......i-1],b[0,1,2,3,......j];<br>
* 那么如果字符a[i] != b[j] 并且km = b[j] ，k[0,1,2,......m-1] = lcs(a[0,1,2,3,......i],b[0,1,2,3,......j-1];<br>
* 最后的总结是：k[0,1,2,......m-1] = max{lcs(a[0,1,2,3,......i],b[0,1,2,3,......j-1],lcs(a[0,1,2,3,......i-1],b[0,1,2,3,......j]};<br>
*
* 然后我们就可以得到：需要一个中间变量来表示a[i]是否等于b[j],这个时候就能自然而然的想起二维数组来进行表示k[i][j],如果是使用k[i][j]等于1来表示<br>
* a[i] == b[j],那么我们根据k[i][j] 就能够找到最长的公共子序列，这个时候的状态转移方程，也会有相应的变化<br>
*
* 如果k[i][j] = 1 ，那么：k[0,1,2,......m] = 1+lcs(a[0,1,2,3,......i],b[0,1,2,3,......j];<br>
* 如果k[i][j] = 0 ，那么：k[0,1,2,......m] = max{lcs(a[0,1,2,3,......i],b[0,1,2,3,......j-1],lcs(a[0,1,2,3,......i-1],b[0,1,2,3,......j]};<br>
*
* @param first
* @param second
* @return
*/
// 最长公共子串（Longest Common Substring）指的是两个字符串中的最长公共子串，要求子串一定连续。
// 最长公共子序列（Longest Common Subsequence）指的是两个字符串中的最长公共子序列，不要求子序列连续。
public static String longestCommomSubsequence(String first, String second) {
if(first == null || first.length() <= 0 || second == null || second.length() <= 0){
return null;
}
char[] fir = first.toCharArray();
char[] sec = second.toCharArray();
int f = fir.length;
int s = sec.length;
// 首先是初始化
int[][] k = new int[f][s];
for (int i = 0; i < f; i++) {
for (int j = 0; j < s; j++) {
if(fir[i] == sec[j]){
if(i == 0||j== 0){
k[i][j]=1;
}else{
k[i][j]=k[i-1][j-1]+1;
}
}else{
if(i == 0||j== 0){
k[i][j]=0;
}else{
k[i][j]=Math.max(k[i-1][j],k[i][j-1]);
}
}
}
}
// 输出数组结果进行观察
for (int i = 0; i < f ; i++) {
for (int j = 0; j < s ; j++) {
System.out.print(k[i][j]+",");
}
System.out.println("");
}
int ff = fir.length-1;
int ss = sec.length-1;
int maxlength = k[ff][ss];
StringBuffer sb=new StringBuffer();
while(maxlength > 0 && ss >= 0 && ff>=0){
System.out.println(fir[ff]+"，"+sec[ss]);
if(fir[ff] == sec[ss]){
System.out.println(k[ff][ss]);
sb.append(fir[ff]);
ff = ff-1;
ss = ss-1;
maxlength--;
}else{
if (k[ff][ss-1]>k[ff-1][ss]) {
ss = ss-1;
}else {
ff =ff-1;
}
}
}
return sb.reverse().toString();
}
/**
* 得到最长的公共子串
* */
public static String longestCommomSubstring(String first, String second) {
if(first == null || first.length() <= 0 || second == null || second.length() <= 0){
return null;
}
char[] fir = first.toCharArray();
char[] sec = second.toCharArray();
int ff = fir.length;
int ss = sec.length;
int[][]k = new int[ff][ss];
int max = 0;int imax = 0,jmax=0;
for (int i = 0; i < ff; i++) {
for(int j = 0;j<ss;j++){
if(fir[i] == sec[j]){
if(i == 0||j==0){
k[i][j]=1;
}else{
if(k[i-1][j-1] > 0){
k[i][j]=k[i-1][j-1]+1;
}else{
k[i][j]=1;
}
}
}else{
k[i][j]=0;
}
if(k[i][j] > max){
imax=i;
jmax =j;
max= k[i][j];
}
}
}
StringBuilder res = new StringBuilder();
for (int i = imax,j = jmax; i >= 0 && j >= 0 && max>0 ; i--,j--) {
res.append(fir[i]);
max--;
}
return res.reverse().toString();
}
public static void main(String[] args){
String a = "csdn.ertieiteitoebteoteteutt";
String b = "csdn.bt";
System.out.println(longestCommomSubsequence(a, b));
}
一个具体的类：java.util.concurrent.atomic.AtomicInteger
声明的变量：private volatile int value;
/** 1.8的jdk
* Atomically increments by one the current value.
*
* @return the updated value
*/
public final int incrementAndGet() {
return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
}
// 1.5的
public final int incrementAndGet() {
for (;;) {
int current = get();
int next = current + 1;
if (compareAndSet(current, next))
return next;
}
}
java.util.concurrent.atomic.AtomicInteger 采用的是：java中CAS的实现
CAS就是Compare and Swap的意思，比较并操作。很多的cpu直接支持CAS指令。CAS是项乐观锁技术，当多个线程尝试使用CAS同时更新同一个变量时，只有其中一个线程能更新变量的值，而其它线程都失败，失败的线程并不会被挂起，而是被告知这次竞争中失败，并可以再次尝试。CAS有3个操作数，内存值V，旧的预期值A，要修改的新值B。当且仅当预期值A和内存值V相同时，将内存值V修改为B，否则什么都不做。
JDK1.5中引入了底层的支持，在int、long和对象的引用等类型上都公开了CAS的操作，并且JVM把它们编译为底层硬件提供的最有效的方法，在运行CAS的平台上，运行时把它们编译为相应的机器指令。在Java.util.concurrent.atomic包下面的所有的原子变量类型中，比如AtomicInteger，都使用了这些底层的JVM支持为数字类型的引用类型提供一种高效的CAS操作。
在CAS操作中，会出现ABA问题。就是如果V的值先由A变成B，再由B变成A，那么仍然认为是发生了变化，并需要重新执行算法中的步骤。有简单的解决方案：不是更新某个引用的值，而是更新两个值，包括一个引用和一个版本号，即使这个值由A变为B，然后为变为A，版本号也是不同的。AtomicStampedReference和AtomicMarkableReference支持在两个变量上执行原子的条件更新。AtomicStampedReference更新一个“对象-引用”二元组，通过在引用上加上“版本号”，从而避免ABA问题，AtomicMarkableReference将更新一个“对象引用-布尔值”的二元组。