算法练习day19——190410（数组中重复的数字、替换空格、从尾到头打印链表） -ag凯发k8国际

在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的，也不知道每个数字重复几次。请找出数组中任意一个重复的数字。

要求复杂度为 o(n) o(1)【时间复杂度 o(n)，空间复杂度 o(1)】

1.1 分析

这种数组元素在 [0, n-1] 范围内的问题，可以将值为 i 的元素调整到第 i 个位置上。

1.2 代码实现

public class duplicatenum {public static void main(string[] args) {int[] arr= {2,3,1,0,2,5};int n=arr.length;system.out.println(duplicate(arr,n));}public static int duplicate(int[] nums,int len) {if(nums==null||len<=0)return -1;int res=-1;for(int i=0;i2.替换空格

将一个字符串中的空格替换成 " "。

2.1 分析

在字符串尾部填充任意字符，使得字符串的长度等于替换之后的长度。

因为一个空格要替换成三个字符（ ） ，因此当遍历到一个空格时，需要在尾部填充两个任意字符。

令 p1 指向字符串原来的末尾位置，p2 指向字符串现在的末尾位置。

p1 和 p2从后向前遍历，当 p1 遍历到一个空格时，就需要令 p2 指向的位置依次填充 02%（注意是逆序的） ，否则就填充上 p1 指向字符的值。

从后向前遍是为了在改变 p2 所指向的内容时，不会影响到 p1 遍历原来字符串的内容。

p1==p2时，结束。

2.1 代码实现

public class replacespace {public static void main(string[] args) {string string="a b c";system.out.println(replacespace(string));}public static string replacespace(string str) {stringbuffer sb=new stringbuffer(str);//便于使用append()int p1=str.length()-1;for(int i=0;i=0&&p2>p1) {char c=sb.charat(p1--);if(c==' ') {sb.setcharat(p2--, '0');sb.setcharat(p2--, '2');sb.setcharat(p2--, '%');}elsesb.setcharat(p2--, c); }return sb.tostring();} }

输入链表的第一个节点，从尾到头反过来打印出每个结点的值。

3.1 分析1——使用栈

使用栈存储遍历过的节点值。

3.2 代码实现1

package qian10;import java.util.arraylist; import java.util.stack;public class printlistreverse {static class node{node next;int value;public node(int value) {this.value=value;}}public static void main(string[] args) {node head=new node(1);head.next=new node(2);head.next.next=new node(3);head.next.next.next=new node(4);arraylist result=printlistfromtailtohead1(head);for(int i=0;i printlistfromtailtohead1(node head) {stack stack=new stack<>();node cur=head;arraylist res=new arraylist();while(cur!=null) {stack.push(cur.value);cur=cur.next;}while(!stack.isempty()) {res.add(stack.pop());}return res;} }

3.3 分析2——使用递归

使用递归实现

当前节点不为空，继续向后；为空，则将当前节点加入结果集，返回结果集。

使用addall方法将返回的arraylist中的所有数据全部加入到当前arraylist中。

3.4 代码实现2

public static arraylist printlistfromtailtohead2(node listnode) {arraylist ret = new arraylist<>();if (listnode != null) {ret.addall(printlistfromtailtohead(listnode.next));ret.add(listnode.value);} return ret; }

注：原博

arraylist是一个实现可变长数组，继承abstractlist类，实现所有的list接口，还实现了randomaccess、cloneable、serializable接口。

add源代码：

public boolean add(e e) {ensurecapacityinternal(size 1);elementdata[size ] = e;return true; }

addall源代码：

//将collection c内的数据插入arraylist中 public boolean addall(collection c) {object[] a = c.toarray(); int numnew = a.length;ensurecapacityinternal(size numnew);// increments modcountsystem.arraycopy(a, 0, elementdata, size, numnew);size = numnew;return numnew != 0; }//将collection c中的数据插入到arraylist的指定位置 public boolean addall(int index, collection c) {rangecheckforadd(index);object[] a = c.toarray();int numnew = a.length;ensurecapacityinternal(size numnew); // increments modcountint nummoved = size - index;if (nummoved > 0)system.arraycopy(elementdata, index, elementdata, index numnew,nummoved);system.arraycopy(a, 0, elementdata, index, numnew);size = numnew;return numnew != 0; }

3.5 分析3——使用头插法

利用链表头插法为逆序的特点。

头结点和第一个节点的区别：

• 头结点是在头插法中使用的一个额外节点，这个节点不存储值；
• 第一个节点就是链表的第一个真正存储值的节点。

前两个节点的细节图如下所示（类似于链表反转）：

3.6 代码实现

public static arraylist printlistfromtailtohead3(node listnode) {// 头插法构建逆序链表node head = new node(-1);while (listnode != null) {node memo = listnode.next;listnode.next = head.next;head.next = listnode;listnode = memo;} // 构建 arraylistarraylist ret = new arraylist<>();head = head.next;while (head != null) {ret.add(head.value);head = head.next;} return ret; }

用反转链表的思想实现：

public static arraylist printlistfromtailtohead4(node head) {node cur=head;node pre=null;node next=null;while(cur!=null) {next=cur.next;cur.next=pre;pre=cur;cur=next;}arraylist ret = new arraylist<>();while(pre!=null) {ret.add(pre.value);pre=pre.next;}return ret; }

 

总结

以上是ag凯发k8国际为你收集整理的算法练习day19——190410（数组中重复的数字、替换空格、从尾到头打印链表）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得ag凯发k8国际网站内容还不错，欢迎将ag凯发k8国际推荐给好友。