1、不使用额外空间,将 A,B两链表的元素交叉归并
复制代码
/**
*
* @author phinecos
* @since 2009-05-19
*
*/
public class LinkList
{
private static class Node
{//内部节点类
private int value;//节点值
Node next;//下一个节点
public Node(int value)
{
this.value = value;
this.next = null;
}
public Node(int value, Node next)
{
this.value = value;
this.next = next;
}
public int getValue()
{
return value;
}
public void setValue(int value)
{
this.value = value;
}
public Node getNext()
{
return next;
}
public void setNext(Node next)
{
this.next = next;
}
}
private Node head;//头节点
public LinkList()
{
this.head = null;
}
public LinkList(LinkList rhs)
{
Node current = rhs.head;
while (current!= null)
{
this.add(current.value);
current = current.next;
}
}
public boolean add(int num)
{//以递增方式增加节点到链表头部
Node newNode = new Node(num);
if (this.head == null)
{//第一个节点
this.head = newNode;
}
else
{
Node pre = null,current = this.head;
while (current != null && current.value < num)
{//找到合适的插入位置
pre = current;
current = current.next;
}
//插入新节点
pre.next = newNode;
newNode.next = current;
}
return true;
}
public boolean remove(Node node)
{//删除节点
Node pre = null,current = this.head;
if (node == this.head)
{//要删除的是头节点
this.head = this.head.next;
}
else
{
while (current != node)
{
pre = current;
current = current.next;
}
pre.next = current.next;
}
current = null;
return true;
}
public boolean merge(LinkList rhs)
{//和另一个链表合并(不使用额外空间)，以当前链表为基准
boolean result = false;
Node p1,p2,p2Pre;
p2Pre = null;
p1 = this.head;
p2 = rhs.head;
while ((p1 != null) && (p2 != null))
{
if (p1.value < p2.value)
{
p1 = p1.next;
}
else if(p1.value >= p2.value)
{
p2Pre = p2;
p2 = p2.next;
rhs.remove(p2Pre);
this.add(p2Pre.value);
}
}
while (p2 != null)
{
p2Pre = p2;
rhs.remove(p2Pre);
this.add(p2Pre.value);
p2 = p2.next;
}
return result;
}
@Override
public String toString()
{
StringBuilder sb = new StringBuilder();
Node current = this.head;
while (current != null)
{
sb.append(current.value);
current = current.next;
}
return sb.toString();
}
public static void main(String[] args)
{
LinkList list1 = new LinkList();
list1.add(1);
list1.add(7);
list1.add(5);
list1.add(4);
list1.add(3);
LinkList list2 = new LinkList();
list2.add(2);
list2.add(4);
list2.add(8);
list1.merge(list2);
System.out.println(list1);
System.out.println(list2);
}
}
复制代码
2，字节对齐
复制代码
#include <iostream>
using namespace std;
struct A
{
short a1;
short a2;
short a3;
};
struct B
{
long a1;
short a2;
};
struct C
{
int a1;
short a2;
char a3;
};
int main()
{
cout<<sizeof(A)<<endl;
cout<<sizeof(B)<<endl;
cout<<sizeof(C)<<endl;
return 0;
}
复制代码
输出：
6
8
8
结构体A中有3个short类型变量，各自以2字节对齐，结构体对齐参数按默认的8字节对齐，则a1,a2,a3都取2字节对齐，则sizeof(A)为6，其也是2的整数倍.
B中a1为4字节对齐，a2为2字节对齐，结构体默认对齐参数为8，则a1取4字节对齐，a2取2字节对齐，结构体大小6字节，6不为4的整数倍，补空字节，增到8时，符合所有条件，则sizeof(B)为8。
C中补空字节，结构体大小加到8时，是4的倍数，符合条件.
根据上述原理可做如下实验:
复制代码
struct C
{
int i;//4个字节
short s;//2个字节
char c;//1个字节
long a4;//4个字节
};
复制代码
此时sizeof(C)输出12，因为结构体大小填充字节到12时，是4的倍数，符合条件。
那如果想抛弃掉字节对齐呢，如何做呢？只需要加入下面语句即可
#pragma pack(1)
3,插入排序
复制代码
import java.util.*;
class InsertSort
{
List al = null;
public InsertSort(int num,int mod)
{
al = new ArrayList(num);
Random rand = new Random();
System.out.println("The ArrayList Sort Before:");
for (int i=0;i<num ;i++ )
{
al.add(new Integer(Math.abs(rand.nextInt()) % mod + 1));
System.out.println("al["+i+"]="+al.get(i));
}
}
public void sortList()
{
Integer tempInt;
int MaxSize=1;
for(int i=1;i<al.size();i++)
{
tempInt = (Integer)al.remove(i); //待插入的数据
if(tempInt.intValue()>=((Integer)al.get(MaxSize-1)).intValue())
{
al.add(MaxSize,tempInt); //插入
MaxSize++;
System.out.println(al.toString());
}
else
{ //比结尾数据小，找到插入位置
for (int j=0;j<MaxSize ;j++ )
{
if (((Integer)al.get(j)).intValue()>=tempInt.intValue())
{
al.add(j,tempInt);
MaxSize++;
System.out.println(al.toString());
break;
}
}
}
}
System.out.println("The ArrayList Sort After:");
for(int i=0;i<al.size();i++)
{
System.out.println("al["+i+"]="+al.get(i));
}
}
public static void main(String[] args)
{
InsertSort is = new InsertSort(10,100);
is.sortList();
}
}
复制代码
4，编写一个截取字符串的函数，输入为一个字符串和字节数，输出为按字节截取的字符串。但是要保证汉字不被截半个，如“我ABC”4，应该截为“我AB”，输入“我ABC汉DEF”，6，应该输出为“我ABC”而不是“我ABC+汉的半个”。
复制代码
import java.util.ArrayList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
/**
*
* @author phinecos
* @since 2009-05-19
*
*/
public class Test
{
public static boolean isChinense(String str)
{//是否中文
boolean result = false;
//U+4e00 ~ U+9FB0
Pattern p1 = Pattern.compile("[\u4E00-\u9FB0]") ;
Matcher m = p1.matcher(str);
if (m.matches())
{
result = true;
}
return result;
}
public static List<String> splitString(String strInfo, int n)
{
List<String> result = new ArrayList<String>();
String strTmp;
int count = 0;
StringBuilder sb = new StringBuilder();
for (int i=0; i < strInfo.length(); ++i)
{
strTmp = strInfo.substring(i,i+1);
if (count < n)
{
if (isChinense(strTmp))
{//是中文
count += 2;
sb.append(strTmp);
}
else
{
++count;
sb.append(strTmp);
}
}
else if(count >n)
{
sb.deleteCharAt(sb.length()-1);
i -= 2;
count = 0;
result.add(sb.toString());
sb.delete(0,sb.length());
}
else
{
count = 0;
result.add(sb.toString());
sb.delete(0, sb.length());
--i;
}
}
return result;
}
public static void main(String[] args)
{
String strInfo = "中国,我是phinecos爱好java";
List<String> result = splitString(strInfo,6);
for (String s : result)
{
System.out.println(s);
}
}
}
复制代码
5，
复制代码
#include <iostream>
using namespace std;
struct bit
{
int a:3;
int b:2;
int c:3;
};
int main(int argc, char* argv[])
{
bit s;
char *c = (char*)&s;
int a = 2;
a += 2;
*c = 0x99;
cout << s.a << endl << s.b << endl << s.c << endl;
return 0;
}
复制代码
输出：
1
-1
-4
解答：int a:3的意思是a占3个bit依次类推
c指向s,*c=0x99后，c指向的值变为0x99,即100 11 001故a=1 b= -1 c= -4
因为最高位为符号位
100(算术右移)
=>1111 1111 1111 1100 = -4
11(算术右移)
=>1111 1111 1111 1111 = -1
001(算术右移)
=>0000 0000 0000 0001 = 1
最高位是1，就向左补齐1，最高位是0，就补0，然后按补码看，
如100，最高位是1，按32位补齐成1111 1111 1111 1100 ，这是补码，还原成原码，减一取反为100，负的100，即－4
本文转自Phinecos(洞庭散人)博客园博客，原文链接：http://www.cnblogs.com/phinecos/archive/2009/05/19/1460488.html，如需转载请自行联系原作者
