找出数组中出现奇数次的数

使用异或来解决，非常巧妙。在二进制中，负数等于它的反码加一。

  1. public class EvenOddTimes {
  2.     /**
  3.      * 数组中只有一种数字，出现奇数次，找出这个数字
  4.      */
  5.     public static void printOddTimesNum1(int[] arr) {
  6.         int xor = 0;
  7.         for (int i = 0; i < arr.length; i++) {
  8.             xor ^= arr[i];      // 所有数字异或结果
  9.         }
  10.         System.out.println("数组中唯一出现奇数次的值为：" + xor);
  11.     }
  13.     public static void printOddTimesNum2(int[] arr) {
  14.         int xor = 0;
  15.         for (int i = 0; i < arr.length; i++) {
  16.             xor ^= arr[i];  // 所有数字异或结果
  17.         }
  19.         int rightOne = xor & (~xor + 1);   
  20.         int onlyOne = 0;    
  22.         for (int i = 0; i < arr.length; i++) {
  23.             if ((arr[i] & rightOne) != 0) {
  24.                 onlyOne ^= arr[i];
  25.             }
  26.         }
  27.         System.out.println("数组中出现奇数次的两个数分别是：" +onlyOne + "," + (xor ^ onlyOne));
  28.     }
  30.     public static void main(String[] args) {
  31.         int a = 5;
  32.         int b = 7;
  34.         a = a ^ b;  // 使用异或来交换两个数的值
  35.         b = a ^ b;
  36.         a = a ^ b;
  38.         System.out.println("交换过后：" + a);
  39.         System.out.println("交换过后：" + b);
  41.         int[] arr1 = {1, 1, 1, 1, 2, 2, 3};
  42.         printOddTimesNum1(arr1);
  44.         int[] arr2 = {1, 1, 1, 1, 2, 2, 3, 5, 5, 5};
  45.         printOddTimesNum2(arr2);
  47.     }
  48. }

检验链表是否是回文结构

三种方法，用栈或者是修改链表再复原。

  1. public static class Node {
  2.     public int value;
  3.     public Node next;
  4.     public Node(int data) {
  5.         this.value = data;
  6.     }
  7. }
  8. // 检验一个链表是否是回文链表
  9. // 方法1：使用栈
  10. public static boolean isPalindrome1(Node head) {
  11.     Stack<Node> stack = new Stack<Node>();
  12.     Node cur = head;
  13.     while (cur != null) {
  14.         stack.push(cur);    // 全部压入栈中
  15.         cur = cur.next;
  16.     }
  17.     while (head != null) {
  18.         if (head.value != stack.pop().value) {
  19.             return false;
  20.         }
  21.         head = head.next;
  22.     }
  23.     return true;
  24. }
  25. // 方法2：用栈，只压入一半数据
  26. public static boolean isPalindrome2(Node head) {
  27.     if (head == null || head.next == null) {
  28.         return true;
  29.     }
  30.     Node cur = head;
  31.     Node right = head.next;
  32.     // 异步指针，不论链表总数是奇数或偶数，right到达的位置很巧妙
  33.     while (cur.next != null && cur.next.next != null) {
  34.         cur = cur.next.next;
  35.         right = right.next;    // right到达的位置很巧妙
  36.     }
  37.     Stack<Node> stack = new Stack<>();
  38.     while (right != null) {
  39.         stack.push(right);  // 把右半边的数据都压入栈中
  40.         right = right.next;
  41.     }
  42.     while (!stack.isEmpty()) {
  43.         if (head.value != stack.pop().value) {
  44.             return false;
  45.         }
  46.         head = head.next;
  47.     }
  48.     return true;
  49. }
  50. // 方法3：快慢指针，反向修改链表，逐一比较，最后再把链表恢复
  51. public static boolean isPalindrome3(Node head) {
  52.     if (head == null || head.next == null) {
  53.         return true;
  54.     }
  55.     Node n1 = head;
  56.     Node n2 = head;
  57.     while (n2.next != null && n2.next.next != null) {
  58.         n1 = n1.next;       // 偶数时，n1和n2到中间两个结点
  59.         n2 = n2.next.next;  // 奇数时，n1到中间结点，n2到末尾结点
  60.     }
  61.     n2 = n1.next;   // n2 -> 重新赋值到有半边开头
  62.     n1.next = null; // 断开链表，mid.next -> null
  63.     Node n3 = null;
  64.     while (n2 != null) {    // 逆转右半边链表
  65.         n3 = n2.next;   // n3 -> save next node
  66.         n2.next = n1;   // next of right node convert
  67.         n1 = n2;        // n1 move
  68.         n2 = n3;        // n2 move
  69.     }
  70.     n3 = n1;    // n3 -> 保存原始链表的末尾结点
  71.     n2 = head;  // n2 -> left first node
  72.     boolean res = true;
  73.     while (n1 != null && n2 != null) { // 从两边开始对比
  74.         if (n1.value != n2.value) {
  75.             res = false;
  76.             break;
  77.         }
  78.         n1 = n1.next; // left to mid
  79.         n2 = n2.next; // right to mid
  80.     }
  81.     // 恢复链表
  82.     n1 = n3.next;
  83.     n3.next = null;
  84.     while (n1 != null) { // recover list
  85.         n2 = n1.next;
  86.         n1.next = n3;
  87.         n3 = n1;
  88.         n1 = n2;
  89.     }
  90.     return res;
  91. }

有环链表的相交结点

判断两个链表是否有环。
判断两个链表是否相交。

  1. package problems;
  2. public class ListWithCircle {
  3.     public static class Node {
  4.         public int value;
  5.         public Node next;
  7.         public Node(int data) {
  8.             this.value = data;
  9.         }
  10.     }
  11.     public static Node getCircleNode(Node head1, Node head2) {
  12.         if (head1 == null || head2 == null) {
  13.             return null;
  14.         }
  15.         // 先判断两个链表是否有环
  16.         Node circle1 = ringList(head1);
  17.         Node circle2 = ringList(head2);
  19.         // 都是无环链表，如果相交，返回相交结点，否则返回null
  20.         if (circle1 == null && circle2 == null) {
  21.             return joinPoint(head1, head2);
  22.         }
  24.         // 都是有环链表
  25.         // 三种情况：
  26.         if (circle1 != null && circle2 != null) {
  27.             return boothRing(head1, circle1, head2, circle2);
  28.         }
  30.         return null;
  31.     }
  33.     // 1. 判断链表是否有环
  34.     // 有环返回第一个入环结点，否则返回null
  35.     public static Node ringList(Node head) {
  36.         if (head == null || head.next == null || head.next.next == null) {
  37.             return null;
  38.         }
  40.         Node slow = head.next;
  41.         Node fast = head.next.next;
  43.         // 快慢指针，如果有环，它们会在环中某个结点相遇，否则返回null
  44.         while (slow != fast) {
  45.             if (fast.next == null || fast.next.next == null) {
  46.                 return null;
  47.             }
  48.             slow = slow.next;
  49.             fast = fast.next.next;
  50.         }
  52.         // 有环，两个指针相遇，一个指针回到开头，两个指针一起走，刚好走到入环结点
  53.         slow = head;
  54.         while (slow != fast) {
  55.             slow = slow.next;
  56.             fast = fast.next;
  57.         }
  58.         return slow;
  59.     }
  61.     // 2. 判断两个无环链表是否相交
  62.     // 如果相交，返回第一个相交结点
  63.     public static Node joinPoint(Node head1, Node head2) {
  64.         if (head1 == null || head2 == null) {
  65.             return null;
  66.         }
  67.         Node cur1 = head1;
  68.         Node cur2 = head2;
  69.         int n = 0;
  70.         while (cur1.next != null) {
  71.             n++;
  72.             cur1 = cur1.next;
  73.         }
  74.         while (cur2.next != null) {
  75.             n--;
  76.             cur2 = cur2.next;
  77.         }
  78.         // 如果两个末尾结点不相同，则这两个单链表不相交
  79.         if (cur1 != cur2) {
  80.             return null;
  81.         }
  83.         cur1 = head1;
  84.         cur2 = head2;
  85.         // 长的先走 n 步
  86.         if (n > 0) {
  87.             cur1 = head1;  // 从末尾重定位到开头
  88.             while (n != 0) {    // 先走n步
  89.                 n--;
  90.                 cur1 = cur1.next;
  91.             }
  92.         } else {
  93.             // 不能放到这里，如果走if语句，就不会走到这一步，那么cur2就没有从末尾重定位到开头。。。
  94. //            cur2 = head2;
  95.             n = Math.abs(n);
  96.             while (n != 0) {
  97.                 n--;
  98.                 cur2 = cur2.next;
  99.             }
  100.         }
  101.         while (cur1 != cur2) {
  102.             cur1 = cur1.next;
  103.             cur2 = cur2.next;
  104.         }
  105.         return cur1;
  106.     }
  108.     // 3. 寻找两个有环链表的相交结点
  109.     public static Node boothRing(Node head1, Node loop1, Node head2, Node loop2) {
  110.         Node cur1 = null;
  111.         Node cur2 = null;
  112.         if (loop1 == loop2) {
  113.             cur1 = head1;
  114.             cur2 = head2;
  115.             int n = 0;
  116.             while (cur1 != loop1) {
  117.                 n++;
  118.                 cur1 = cur1.next;
  119.             }
  120.             while (cur2 != loop2) {
  121.                 n--;
  122.                 cur2 = cur2.next;
  123.             }
  124.             cur1 = n > 0 ? head1 : head2;
  125.             cur2 = cur1 == head1 ? head2 : head1;
  126.             n = Math.abs(n);
  127.             while (n != 0) {
  128.                 n--;
  129.                 cur1 = cur1.next;
  130.             }
  131.             while (cur1 != cur2) {
  132.                 cur1 = cur1.next;
  133.                 cur2 = cur2.next;
  134.             }
  135.             return cur1;
  136.         } else {
  137.             cur1 = loop1.next;
  138.             while (cur1 != loop1) {
  139.                 if (cur1 == loop2) {
  140.                     return loop1;
  141.                 }
  142.                 cur1 = cur1.next;
  143.             }
  144.             return null;
  145.         }
  146.     }
  148.     public static void main(String[] args) {
  149.         // 1->2->3->4->5->6->7->null
  150.         Node head1 = new Node(1);
  151.         head1.next = new Node(2);
  152.         head1.next.next = new Node(3);
  153.         head1.next.next.next = new Node(4);
  154.         head1.next.next.next.next = new Node(5);
  155.         head1.next.next.next.next.next = new Node(6);
  156.         head1.next.next.next.next.next.next = new Node(7);
  158.         // 0->9->8->6->7->null
  159.         Node head2 = new Node(0);
  160.         head2.next = new Node(9);
  161.         head2.next.next = new Node(8);
  162.         head2.next.next.next = head1.next.next.next.next.next; // 8->6
  164.         System.out.println(getCircleNode(head1, head2).value);
  166.         // 1->2->3->4->5->6->7->4...
  167.         head1 = new Node(1);
  168.         head1.next = new Node(2);
  169.         head1.next.next = new Node(3);
  170.         head1.next.next.next = new Node(4);
  171.         head1.next.next.next.next = new Node(5);
  172.         head1.next.next.next.next.next = new Node(6);
  173.         head1.next.next.next.next.next.next = new Node(7);
  174.         head1.next.next.next.next.next.next = head1.next.next.next; // 7->4
  176.         // 0->9->8->2...
  177.         head2 = new Node(0);
  178.         head2.next = new Node(9);
  179.         head2.next.next = new Node(8);
  180.         head2.next.next.next = head1.next; // 8->2
  182.         System.out.println(getCircleNode(head1, head2).value);
  184.         // 0->9->8->6->4->5->6..
  185.         head2 = new Node(0);
  186.         head2.next = new Node(9);
  187.         head2.next.next = new Node(8);
  188.         head2.next.next.next = head1.next.next.next.next.next; // 8->6
  189.         System.out.println(getCircleNode(head1, head2).value);
  190.     }
  191. }

遍历二叉树

对二叉树进行遍历，先序、中序、后序和宽度遍历。
非递归版本，用到栈结构和队列结构。

  1. package problems;
  3. import java.util.Deque;
  4. import java.util.LinkedList;
  5. import java.util.Queue;
  7. /**
  8.  * 遍历二叉树
  9.  * 先序、中序、后序
  10.  */
  11. public class TraversalTree {
  13.     public static class Node {
  14.         private int value;
  15.         private Node left;
  16.         private Node right;
  18.         public Node(int value) {
  19.             this.value = value;
  20.         }
  21.     }
  23.     // 层次遍历
  24.     // 宽度遍历，每层从左到右顺序遍历
  25.     public static void levelOrder(Node cur) {
  26.         if (cur == null) {
  27.             return;
  28.         }
  29.         System.out.print("宽度遍历：");
  30.         Queue<Node> queue = new LinkedList<>(); // 队列
  31.         queue.add(cur);
  33.         while (!queue.isEmpty()){
  34.             cur = queue.poll();     // 先进先出
  35.             System.out.print(cur.value + ", ");
  37.             if (cur.left != null) {
  38.                 queue.add(cur.left);
  39.             }
  40.             if (cur.right != null) {
  41.                 queue.add(cur.right);
  42.             }
  43.         }
  44.     }
  46.     // 先序遍历
  47.     // 用栈结构，先压右，再压左
  48.     public static void preOrder(Node cur) {
  49.         System.out.print("先序遍历：");
  50.         if (cur != null) {
  51.             // Java中stack已过时，推荐用Deque
  52.             Deque<Node> deque = new LinkedList<>();
  53.             deque.push(cur);
  55.             while (!deque.isEmpty()) {
  56.                 cur = deque.pop();      // 弹出栈顶元素并打印
  57.                 System.out.print(cur.value + ",");
  59.                 // 先压入右子树进栈，再压入左子树
  60.                 if (cur.right != null) {
  61.                     deque.push(cur.right);
  62.                 }
  63.                 if (cur.left != null) {
  64.                     deque.push(cur.left);
  65.                 }
  66.             }
  67.         }
  68.     }
  70.     // 中序遍历
  71.     // 用栈结构，先把左子树全部压入栈，为空就弹出栈顶元素，再向右走
  72.     public static void inOrder(Node cur) {
  73.         System.out.print("中序遍历：");
  74.         if (cur != null) {
  75.             Deque<Node> deque = new LinkedList<>();
  76.             while (!deque.isEmpty() || cur != null) {
  77.                 if (cur != null) {
  78.                     deque.push(cur);
  79.                     cur = cur.left;
  80.                 } else {
  81.                     cur = deque.pop();
  82.                     System.out.print(cur.value + ",");
  83.                     cur = cur.right;
  84.                 }
  85.             }
  86.         }
  87.     }
  89.     // 后序遍历
  90.     // 用两个栈，很巧妙，能看懂，但写不出
  91.     public static void postOrder(Node cur) {
  92.         System.out.print("后序遍历：");
  93.         if (cur != null) {
  94.             Deque<Node> deque1 = new LinkedList<>();
  95.             Deque<Node> deque2 = new LinkedList<>();
  96.             deque1.push(cur);
  98.             while (!deque1.isEmpty() ) {
  99.                 cur = deque1.pop();
  100.                 deque2.push(cur);       // 全部压入栈2，顺序是头 右 左
  102.                 if (cur.left != null) { // 先压入栈1，又被压入栈2
  103.                     deque1.push(cur.left);
  104.                 }
  105.                 if (cur.right != null) {
  106.                     deque1.push(cur.right);
  107.                 }
  108.             }
  109.             // 栈2，打印结果：左 右 头
  110.             while (!deque2.isEmpty()) {
  111.                 cur = deque2.pop();
  112.                 System.out.print(cur.value + ",");
  113.             }
  114.         }
  115.     }
  117.     public static void postOrder2(Node h) {
  118.         System.out.print("后序遍历2: ");
  119.         if (h != null) {
  120.             Deque<Node> stack = new LinkedList<>();
  121.             stack.push(h);
  122.             Node c = null;
  123.             while (!stack.isEmpty()) {
  124.                 c = stack.peek();
  125.                 if (c.left != null && h != c.left && h != c.right) {
  126.                     stack.push(c.left);
  127.                 } else if (c.right != null && h != c.right) {
  128.                     stack.push(c.right);
  129.                 } else {
  130.                     System.out.print(stack.pop().value + " ");
  131.                     h = c;
  132.                 }
  133.             }
  134.         }
  135.     }
  137.     public static void main(String[] args) {
  138.         // 创建一个满二叉树
  139.         Node head = new Node(1);
  140.         head.left = new Node(2);
  141.         head.right = new Node(3);
  142.         head.left.left = new Node(4);
  143.         head.left.right = new Node(5);
  144.         head.right.left = new Node(6);
  145.         head.right.right = new Node(7);
  147.         // 经过先序遍历后，cur会指向最末尾的结点，为什么head的指向不变呢？
  148.         // 网上查了一下，说Java是值传递，基本类型传递值，引用类型传递的是引用的拷贝
  149.         preOrder(head);     // 先序遍历
  150.         System.out.println();
  152.         inOrder(head);
  153.         System.out.println();
  155.         postOrder(head);
  156.         System.out.println();
  158.         postOrder2(head);
  159.         System.out.println();
  161.         levelOrder(head);
  162.         System.out.println();
  163.     }
  164. }

TraversalTree.java

2021年12月上传的算法视频课：面试官急了，算法大神左神（左程云）耗时3个月打造100道算法与数据结构大厂高频面试题精讲，不出意外十年后仍是最好的算法刷题教程！
https://www.bilibili.com/video/BV1vi4y1R7g9?p=4&spm_id_from=pageDriver