算法练习day19——190410（数组中重复的数字、替换空格、从尾到头打印链表）
1.数组中重复的数字
在一个长度为 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.替换空格
将一个字符串中的空格替换成 "%20"。
2.1 分析
在字符串尾部填充任意字符，使得字符串的长度等于替换之后的长度。
因为一个空格要替换成三个字符（%20） ，因此当遍历到一个空格时，需要在尾部填充两个任意字符。
令 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.从尾到头打印链表
输入链表的第一个节点，从尾到头反过来打印出每个结点的值。
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;
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！