算法初级——数组中只出现一次的数字

一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。 知识点:异或操作,任何数与本身异或等于0 异或就是同为0,异为1. 位运算 右移一位 判断两个只出现了一次的数字,先将所有元素异或操作,结果为两个只出现一次的的元素异或的结果,找出sum的第一位为1的数字,(两个不一样的数字一定有某些位置数字不一样,找出第一个不一样的数字),以这个位置将元素分为两部分,一部分该位置是一种,另一部分是另一种,完成两部分的分隔,此时每一部分包含一个单次元素,将两部分分别全部异或操 ......

算法初级——二叉树的前驱结点

/* * 前驱节点,中序遍历的前面的节点 * 如果有左子树,那么就是左子树上最右的节点,如果没有左子树,那么一起向上移动,直到该节点位于右子树, */ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566public class 二叉树的前驱节点 {         public static class Node {         public int value;         public Node left;         public Node right; ......

算法初级——二叉树的后继节点

在二叉树中找到一个节点的后继节点 【题目】 现在有一种新的二叉树节点类型如下: public class Node { public int value; public Node left; public Node right; public Node parent; public Node(int data) { this.value = data; }} 该结构比普通二叉树节点结构多了一个指向父节点的parent指针。假设有一棵Node类型的节点组成的二叉树,树中每个节点的parent指针都正确地指向 自己的父节点,头节点的parent指向null。只给一个在二叉树中的某个节点 node,请实现返回node的后继节点的函数。在二叉树的中序遍历的序列中, node的 ......

算法初级——直观打印二叉树

如何直观的打印一颗二叉树 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172public class 直观打印二叉树 {     public static class Node {         public int value;         public Node left;         public Node right;         public Node(int data) {             this.value = data;   & ......

算法初级——二叉树的遍历

实现二叉树的先序、中序、后序遍历,包括递归方式和非递归方式 /* * 二叉树的遍历,二叉树每个节点在遍历的过程中访问三次,第一次访问打印为先序遍历,第二次访问打印为中序打印,第三次访问打印为后序打印。 */ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122import java.util.Stack; public cla ......

算法初级——两个单链表相交的有关问题

两个单链表相交的一系列问题 【题目】 在本题中,单链表可能有环,也可能无环。给定两个单链表的头节点 head1和head2,这两个链表可能相交,也可能不相交。请实现一个函数, 如果两个链表相交,请返回相交的第一个节点;如果不相交,返回null 即可。 要求:如果链表1的长度为N,链表2的长度为M,时间复杂度请达到 O(N+M),额外空间复杂度请达到O(1)。 /* * 1.如何判断单链表有环无环 * 如果单链表有环,返回第一个入环节点,如果无环,返回空,可用哈希表实现(hashset); * 不用哈希表实现单链表有环判断,准备两个指针,快指针 ......

算法初级——复制含有随机节点的链表

复制含有随机指针节点的链表 【题目】 一种特殊的链表节点类描述如下: public class Node { public int value; public Node next; public Node rand; public Node(int data) { this.value = data; }} Node类中的value是节点值,next指针和正常单链表中next指针的意义一 样,都指向下一个节点,rand指针是Node类中新增的指针,这个指针可 能指向链表中的任意一个节点,也可能指向null。 给定一个由Node节点类型组成的无环单链表的头节点head,请实现一个 函数完成这个链表中所有结构的复制,并返回复制的新链表的头节点。 进阶: ......

算法初级——单链表划分区域

将单向链表按某值划分成左边小、中间相等、右边大的形式 【题目】 给定一个单向链表的头节点head,节点的值类型是整型,再给定一个整 数pivot。实现一个调整链表的函数,将链表调整为左部分都是值小于 pivot的节点,中间部分都是值等于pivot的节点,右部分都是值大于 pivot的节点。除这个要求外,对调整后的节点顺序没有更多的要求。 例如:链表9->0->4->5->1,pivot=3。 调整后链表可以是1->0->4->9->5,也可以是0->1->9->5->4。总之,满 足左部分都是小于3的节点,中间部分都是等于3的节点(本例中这个部 分为空),右部分都是大 ......

算法初级——单链表逆序

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647public class 单链表逆序 {     public  static class Node{         public int value;         public Node next;         public Node(int data) {             this.value = data;         }     }     public static void main(String[] args) {         / ......

算法初级——判断链表是否回文

判断一个链表是否为回文结构 【题目】 给定一个链表的头节点head,请判断该链表是否为回文结构。 例如: 1->2->1,返回true。 1->2->2->1,返回true。 15->6->15,返回true。 1->2->3,返回false。 进阶: 如果链表长度为N,时间复杂度达到O(N),额外空间复杂度达到O(1)。 /* * 回文结构判断: * 1、列表所有元素入栈,然后再依次弹出,弹出的过程与链表每次读取的元素比较,如果全部相同则为回文结构 (空间复杂度为n) * 2、两个指针,一个快指针,一个慢指针,快指针每次走两步,慢指针每次走一步,当快指针走到末尾时,慢指 ......