上海做网站吧,东莞网站托管,psd素材,建筑招聘网站有哪些桶排序 e*len/(max1)
e为每个元素#xff0c;根据上式判断该元素放入哪个桶
桶排序适用于分布均匀的数组1.arr-length,max
2.Node[]-new Node[length]
3.扫描-hash-下标-元素入桶
4.出桶排序排序的输出private void sort(int[] arr){int lengtharr.le…桶排序 e*len/(max1)
e为每个元素根据上式判断该元素放入哪个桶
桶排序适用于分布均匀的数组1.arr-length,max
2.Node[]-new Node[length]
3.扫描-hash-下标-元素入桶
4.出桶排序排序的输出private void sort(int[] arr){int lengtharr.length;LinkedNode[] bucketnew LinkedNode[length];//桶的数等于lengthint maxUtil.maxOf(arr);//求max//入桶for(int i0;ilength;i){int valuearr[i];//扫描每个元素int hashhash(arr[i],max,length);//桶的下标if(bucket[hash]null){//初始化链表表头bucket[hash]new LinkedNode(value);}else{insertInto(value,bucket[hash],bucket,hash);//插入链表}}int k0;//记录数组下标//出桶for(LinkedNode node:bucket){if(node!null){while(node!null){//遍历整个桶arr[k]node.value;nodenode.next;}}}}private void insertInto(int value,LinkedNode head,LinkedNode[] bucket,int hash){LinkedNode newNodenew LinkedNode(value);//小于头节点放在头上if(valuehead.value){//替换头节点bucket[hash]newNode;return;}//往后找第一个比当前值大的结点放在这个结点的前面LinkedNode phead;LinkedNode prep;while(p!nullvaluep.value){prep;pp.next;}if(pnull){//搜到末尾了pre.nextnewNode;}else{//插入pre和p之间pre.nextnewNode;newNode.nextp;}}删除重复元素 //创建链表
//单向链表
class Node{Node nextnull;int data;public Node(int d){datad;}
}void appendToTail(int d){Node endnew Node(d);Node nthis;while(n.next!null){nn.next;}n.nextend;
} 移除未排序链表中的重复部分 拉链法散列hash
若hash表已经标记过就删除
public class RemovRepeation{public static void main(String[] args){int[] data{1,6,7,3,6};Node headnew Node(null);Node phead;for(int i0;idata.length;i){p.nextnew Node(data[i]);pp.next;}rr(head);//移除重复Node p1head.next;while(p1!null){System.out.println(p1.value);p1p1.next;}private static void rr(Node head){HashSet setnew HashSet();Node prehead;Node p1head.next;while(p1!null){if(set.contains(p1.value)){//存在说明重复-删除pre.nextp1.next;}else{set.add(p1.data);}p1p1.next;}}private static class Node{Node next;Object value;public Node(Object value){this.valuevalue;}}
} 删除倒数第k个元素 public class KtNode{//特别要注意边界地问题public ListNode FindeKthToTail(ListNode head,int k){if(headnull||k0){return null;}ListNode p1head;ListNode p2-head;int count0;while(countk){//先让p2到第k1个结点上p2p2.next;count;}while(p2!null){//两个指针相差k个结点距离p1p1.next;//两指针同时平移p2p2.next;//当p2到nullp1就到了倒数第k个结点}System.out.println(p1.val);return p1;}public static void main(String[] args){int[] arr{1,2,3,4,5}ListNode headnew ListNode(0);for(int i0;iarr.length;i){p.nextnew ListNode(arr[i]);pp.next;}System.out.println(head);obj.FindKthToTail(head,3);}
} 删除单项链表中的某节点 若该节点为尾结点返回false否则true
public class _2_3RemoveNode3{public boolean removeNode(ListNode pNode){if(pNode nextnull){return false;pNode.valpNode.next.val;//复制后继的内容pNode.nextpNode.next.next;//跨越后继return true;}}
} 以给定值x为基准将链表分割为两部分所有小于x的结点排在大于或等于x的结点之前 给定一个链表的头指针ListNode* pHead,请返回重新排列后的链表的头指针 注意分割后2-3-4-5-62-1-3-5-6
L-head L-tail r-head r-tailpublic ListNode parttition(ListNode pHead,int x){ListNode leftTailnull;ListNode rightTailnull;ListNode ppHead;ListNode leftFirstnull;ListNode rightFirstnull;while(p!null){//顺序扫描所有结点· int pValuep.val;if(pvaluex){//小于xif(leftTailnull){leftFirstp;leftTailp;}else{leftTail.nextp;leftTailleftTail.next;}}else{//大于xif(rightTailnull){rightFirstp;rightTailp;}else{rightTail.nextp;rightTailrightTail.next;}}pp.next;}if(leftFirstnull){//左边链表可能为空return rightFirst;}leftTail.nextrightFirst;//左右两个链表连接起来if(rightTail!null){rightTail.nextnull;}return leftFirst;
} 有两个用链表来表示的整数每个结点包含一个数位 这些数位是反向存放的也就是个位排在链表的首位编写函数对这两个整数求和 给定两个链表ListNode* A ListNode* B请返回AB的结果ListNode*
public ListNode plusAB(ListNode a,ListNode b){return plusAB(a,b,0);}public ListNode plusAB(ListNode a,ListNode b,int i){if(anullbnulli0)return null;int valuei;if(a!null){valuea.val;}if(b!null){valueb.val;}ListNode resultnew ListNode(value%10);result.nextplusAB(anull?null:a.next,bnull?null:b.next,value10?1:0)
//递归链表return result;
} 给定一个有环链表实现一个算法返回环路的开头结点 有环链表的定义在链表中某个结点的next元素指向在它前面出现过的结点则表明该链表存在环路HashSet判断重复判断元素是否存在
hash-equealpublic ListNode check(ListNode head){ListNode phead;//传一个链表HashSet setnew HashSet();//hashsetwhile(true){if(set.contains(p))return p;//遍历链表如果存在相同结点则退出else{set.add(p);pp.next;}//不存在相同结点则加入hashset链表继续往下面遍历}
}快慢指针
S一步一进f两步一进》sf相遇于某一点
如果存在环必定在某一点相遇若是没有环则不相遇
public boolean hashCircle(ListNode head){ListNode shead;ListNode fhead;while(true){ss.next;ff.next.next;if(sf)return true;if(snull||fnull||f.nextnull)return false;}
}
s和f相聚于何处
f差l-k步
s走l-k步后相遇
他们离的起点还有k步
public ListNode beginOfCircle(ListNode head){ListNode shead;ListNode fhead;while(f!nullf.next!null){ss.next;ff.next.next;if(sf)break;}//何种方式退出的?if(fnull||f.nextnull){return null; }ListNode phead;while(p!s){pp.next;ss.next;}return p;
}回文链表 检查链表是否回文翻转链表
a-b-c-b-a
a b c c b a
借助栈一半入栈一半匹配出栈
前半部分压栈public boolean isPalindrome(ListNnode,pHead){if(pHeadnull){return false;}if(pHead.nextnull){return true;}ListNode slowerpHead;ListNode fasterpHead;StackListNodestacknew Stack();boolean isOddtrue;while(faster!nullfaster.next!null){stack.push(slower);//压栈slowerslower.next;fasterfaster.next.next;if(fasternull){isOddfalse;}}//奇数个结点slower还要next一下if(isOdd)slowerslower.next;while(!stack.empty()){if(stack.pop().val!slower.val){return false;}else{slowerslower.next;}}
}
