增强For循环

Posted on 2018-09-15 | In Java

今天读程序遇到有for循环里有冒号，去查了下，属于增强for循环

for(元素变量:元素集合)

{
	程序块；

}

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class ForeachTest
{
    public static void main(String[] args)
    {
        int[] arr = {1, 2, 3, 4, 5};
        
        System.out.println("----------旧方式遍历------------");
        //旧式方式        
        for(int i=0; i<arr.length; i++)
        {
            System.out.println(arr[i]);
        }
        
        System.out.println("---------新方式遍历-------------");
        
        //新式写法,增强的for循环
        for(int element:arr)
        {
            System.out.println(element);
        }
        
        System.out.println("---------遍历二维数组-------------");
        
        //遍历二维数组
        
        int[][] arr2 = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}} ;
        
        for(int[] row : arr2)
        {
            for(int element : row)
            {
                System.out.println(element);
            }
        }
        
        //以三种方式遍历集合List
        
        List<String> list = new ArrayList<String>();
        
        list.add("a");
        list.add("b");
        list.add("c");
        
        System.out.println("----------方式1-----------");
        //第一种方式，普通for循环
        for(int i = 0; i < list.size(); i++)
        {
            System.out.println(list.get(i));
            
        }
        
        System.out.println("----------方式2-----------");
        //第二种方式，使用迭代器
        for(Iterator<String> iter = list.iterator(); iter.hasNext();)
        {
            System.out.println(iter.next());
        }
        System.out.println("----------方式3-----------");
        //第三种方式，使用增强型的for循环
        for(String str: list)
        {
            System.out.println(str);
            
        }
    }

}

关于Java中String的传递问题

Posted on 2018-09-15 | In Java

今天在写java时想写一个方法public void Helper(TreeNode root,List<String> list, String path) 前面两者不必说，传递的是地址，叫 emm 叫值传递——java中只存在值传递，只存在值传递！！！（然而我们经常看到对于对象（数组，类，接口）的传递似乎有点像引用传递，可以改变对象中某个属性的值。但是不要被这个假象所蒙蔽，实际上这个传入函数的值是对象引用的拷贝，即传递的是引用的地址值，所以还是按值传递。）再来看一看String的问题，String是对象，但是表现出像基本数据类型一样的值传递表现，比较一下下面两者：

public class Test3 {
    public static void change(int []a){
        a[0]=50;
    }
    public static void main(String[] args) {
        int []a={10,20};
        System.out.println(a[0]);
        change(a);
        System.out.println(a[0]);
    }
}

输出10，50

public class Test {
    public static void change(String s){
        s="zhangsan";
    }
    
    public static void main(String[] args) {
        String s=new String("lisi");
        System.out.println(s);
        change(s);
        System.out.println(s);
    }
}

输出lisi lisi
照理说String是对象，应该输出lisi zhangsan才对啊，怎么change方法里没把String改掉呢？这是因为String具有不变性，看下图来源这里写图片描述
String具有不可变性，String被重新赋值为abcdel时，是在堆内重新开辟空间放入abcdel，并且String指向它，相当于新建了一个String对象，但是原先的String s=abcd仍然存在。
同理对于上面change方法里重新建立了一个String zhangsan对象，回到main里，zhangsan对象地址由于是值传递，在main里当然就消失了，此时的s仍然是lisi这个对象.
2. 再从根本上来看下为什么String具有这种不变性
翻开JDK源码，java.lang.String类起手前三行，是这样写的：

public final class String implements java.io.Serializable, Comparable<String>, CharSequence {
    /** String本质是个char数组. 而且用final关键字修饰.*/
    private final char value[];
	...
	...
}

首先String类是用final关键字修饰，这说明String不可继承。
再看下面，String类的主力成员字段value是个char[ ]数组，而且是用final修饰的。final修饰的字段创建以后就不可改变。

有的人以为故事就这样完了，其实没有。因为虽然value是不可变，也只是value这个引用地址不可变。挡不住Array数组是可变的事实。Array的数据结构看下图，

这里写图片描述

也就是说Array变量只是stack上的一个引用，数组的本体结构在heap堆。String类里的value用final修饰，只是说stack里的这个叫value的引用地址不可变。没有说堆里array本身数据不可变。看下面这个例子，

final int[] value={1,2,3}
int[] another={4,5,6};
value=another;    //编译器报错，final不可变
value用final修饰，编译器不允许我把value指向堆区另一个地址。但如果我直接对数组元素动手，分分钟搞定。

final int[] value={1,2,3};
value[2]=100;  //这时候数组里已经是{1,2,100}

所以String是不可变，关键是因为SUN公司的工程师，在后面所有String的方法里很小心的没有去动Array里的元素，没有暴露内部成员字段。private final char value[]这一句里，private的私有访问权限的作用都比final大。而且设计师还很小心地把整个String设成final禁止继承，避免被其他人继承后破坏。所以String是不可变的关键都在底层的实现，而不是一个final。考验的是工程师构造数据类型，封装数据的功力。

参考文献

[1] 胖胖. 如何理解 String 类型值的不可变[EB/OL]. https://www.zhihu.com/question/20618891.

ArrayList的初始化陷阱

Posted on 2018-09-15 | In Java

List<String> list = new ArrayList<>(2);
这个乍一看，还以为像数组一样，你初始化了个长度为2的数组，然后你就可以随意修改下标为0，1的内容。当然0，1是肯定不会下标越界的。
我当时也是这么想的。然而不是的。
源码里面的构造函数的注释说明：这个真的是在底层新建了个长度为2的数组Object[]，但是他又不是我们经常看到的一般数组。这个是空的。
当前list集合仍然是一个带有初始容量的empty list。
list.size()
我上来也是想当然的以为，这个size()不就是上面的那个2吗！但是我错了。
源码中ArrayList的size属性对应的注释是：The size of the ArrayList (the number of elements it contains).
这个size是表示这个集合包含的元素的个数，而不是底层数组的大小。

如何求中间位置的数——快慢指针

Posted on 2018-09-15 | In Data Structures and Algorithms

一个数组是有序数组，则mid=(start+end)/2即是中间位置。
倘若是一个有序链表呢？
转换为数组？——数组size怎么确定。暂时设大点吧
第一次遍历记录size，第二次再到size/2位置

也许方法很多，但是今天可以通过快慢指针来完成：

概念

快慢指针中的快慢指的是移动的步长，即每次向前移动速度的快慢。例如可以让快指针每次沿链表向前移动2，慢指针每次向前移动1次。

寻找中间位置的数

该方法在不借助计数器变量实现寻找中位数的功能。原理是：快指针的移动速度是慢指针移动速度的2倍，因此当快指针到达链表尾时，慢指针到达中点。程序还要考虑链表结点个数的奇偶数因素，当快指针移动x次后到达表尾（1+2x），说明链表有奇数个结点，直接返回慢指针指向的数据即可。如果快指针是倒数第二个结点，说明链表结点个数是偶数，这时可以根据“规则”返回上中位数或下中位数或（上中位数+下中位数）的一半。

while (fast&&slow)
{
　　if (fast->next==NULL)
　　    return slow ->data;
　　else if (fast->next!= NULL && fast->next->next== NULL)
　　    return (slow ->data + slow ->next->data)/2;
　　else
　　{
　　    fast= fast->next;
　    　fast= fast->next;
　　    slow = slow ->next;
　　}
　}

具体地，可以拿leetcode 109题练手。

其他用途

判断单链表是否为循环链表
如果链表为存在环，如果找到环的入口点？

具体可以参考下关于快慢指针的若干应用详解.

天洋行空

戒骄戒躁

GitHub E-Mail