面试基础算法题-日常面试足够

常见的面试算法题，主要为 数组->链表->二叉树->字符串->hash表。

其实大部分业务面试，都是只是考察一下基础算法能力，所以基本上都是常见的面试题，很少有改变，所以掌握基础的几种类型就足以应付。

数组

在计算机科学中，数组是由一组元素(值或变量)组成的数据结构。每个元素有至少一个索引或键来标识（元素的类型必须一致）

//合并两个有序数组
//输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
//输出：[1,2,2,3,5,6]
//解释：需要合并 [1,2,3] 和 [2,5,6] 。
//合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
public void merge(int[] nums1, int m, int[] nums2, int n) {int p1 = 0, p2 = 0;int[] sorted = new int[m + n];int cur;while (p1 < m || p2 < n) {if (p1 == m) {cur = nums2[p2++];} else if (p2 == n) {cur = nums1[p1++];} else if (nums1[p1] < nums2[p2]) {cur = nums1[p1++];} else {cur = nums2[p2++];}sorted[p1 + p2 - 1] = cur;}for (int i = 0; i != m + n; ++i) {nums1[i] = sorted[i];}}//两数之和
//输入：numbers = [1,2,4,6,10], target = 8
//输出：[1,3]
//解释：2 与 6 之和等于目标数 8 。因此 index1 = 1, index2 = 3 。
public int[] twoSum(int[] numbers, int target) {for (int i = 0; i < numbers.length; ++i) {int low = i + 1, high = numbers.length - 1;while (low <= high) {int mid = (high - low) / 2 + low;if (numbers[mid] == target - numbers[i]) {return new int[]{i, mid};} else if (numbers[mid] > target - numbers[i]) {high = mid - 1;} else {low = mid + 1;}}}return new int[]{-1, -1};}

链表

链表

链表是有序的列表，但是它在内存中是存储如下

小结:

1. 链表是以节点的方式来存储,是链式存储

2. 每个节点包含 data 域， next 域：指向下一个节点.

3. 如图：发现链表的各个节点不一定是连续存储.

4. 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定

从单链表中删除一个节点的思路
1.我们先找到需要删除的这个节点的前一个节点temp
2.temp.next temp.next.next
3.被删除的节点，将不会有其它引用指向，会被垃圾回收机制回收

class linkNode{static ListNode Node {        //类名 ：Java类就是一种自定义的数据结构int val;            //数据 ：节点数据Node next;      //对象 ：引用下一个节点对象。在Java中没有指针的概念，Java中的引用和C语言的指针类似Node(int val) {  //构造方法 ：构造方法和类名相同this.val = val;     //把接收的参数赋值给当前类的val变量}}private ListNode head = new ListNode(0);//尾插法public void addR(ListNode newNode){ListNode temp= head;while (true){if(temp.next == null){break;}temp = temp.next;}temp.next = newNode;}//头插法public void addH(ListNode newNode){ListNode temp = head;boolean flag = false;if(temp.next == null){temp.next = newNode;temp = temp.next;temp = null;}else{newNode.next = temp.next;temp.next = newNode;}}//删除节点public void del(int num){ListNode temp = head;while (true){if (temp.next == null){System.out.println("没有找到,遍历完毕");return;}//用删除节点的前一个temp去处理if(temp.next.num == num){temp.next = temp.next.next;System.out.println("已经找到" + num + ",删除完毕！");break;}temp = temp.next;}}//显示链表public void list(){if (head.next ==null){System.out.println("链表为空");return;}ListNode temp = head.next;while (true){if(temp == null){break;}System.out.println(temp.toString());temp = temp.next;}}
}//链表反转
public ListNode reverse(ListNode head){ListNode cur = head;ListNode prev = null;if(head == null){return null;}while(cur != null) {ListNode tem = cur.next;cur.next = prev;prev = cur;cur = tem;}return prev;}//判断两个链表是否相交public boolean areIntersecting(ListNode headA,ListNode headB){//如果任一链表为空，则返回falseif (headA ==null || headB ==null) {return false;}ListNode pointerA=headA;//指向链表A的指针ListNode pointerB=headB;//指向链表B的指针//当指针没有到达链表的末尾时进行循环while (pointerA !=pointerB) {//若pointerA到达链表A的末尾，则将其指向链表B的头pointerA = (pointerA == null) ? headB : pointerA.next;//若pointerB到达链表B的末尾，则将其指向链表A的头pointerB = (pointerB == null) ? headA : pointerB.next;}//若指针重合，则说明相交return pointerA != null;//如果不为空，那么指针相交}//环形链表(mid) 判断链表是否形成环最常用的方法是使用快慢指针。我们定义两个指针，一个快指针每次移动两步，一个慢指针每次移动一步，如果链表中存在环，那么两个指针最终会 相遇。public boolean hasCycle(ListNode head) {if (head == null || head.next == null) {return false;}ListNode slow = head;ListNode fast = head.next;while (slow != fast) {if (fast == null || fast.next == null){return false;}slow = slow.next;fast = fast.next.next;}return true;}

 树

树是一类重要的非线性数据结构，是以分支关系定义的层次结构。每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树

1.BFS(广度优先遍历)
一层层的遍历，结合队列
2.DFS(深度优先遍历)
先往深走，遇到叶子节点再往回走，递归或者结合栈

前序遍历（前根遍历）：根——>左——>右

中序遍历（中根遍历）：左——>根——>右
后序遍历（后根遍历）：左——>右——>根
前中后是根据遍历时根所在的相对位置来命名

class Node{//定义一个节点，包含自身数据，对左子树的引用，右子树的引用。String val;Node left;Node right;public Node(String val){this.val = val;}
}public class Mytree { public static Node Tree(){ //初始化二叉树，并且手动连接Node a = new Node("A");Node b = new Node("B");Node c = new Node("C");Node d = new Node("D");Node e = new Node("E");Node f = new Node("F");Node g = new Node("G");Node h = new Node("H");a.left = b;a.right = c;b.left = d;b.right = e;e.left = g;g.right = h;c.right = f;return a;}public static void PreOrder(Node root){ //先序遍历if (root == null) {return;}System.out.print(root.val+" ");PreOrder(root.left);PreOrder(root.right);}public static void MidOrder(Node root){//中序遍历if (root == null) {return;}MidOrder(root.left);System.out.print(root.val+" ");MidOrder(root.right);}public static void LastOrder(Node root){//后序遍历if (root == null) {return;}LastOrder(root.left);LastOrder(root.right);System.out.print(root.val+" ");}public static void LevalOrder(Node root){ //层序遍历LinkedList<Node> list = new LinkedList<>(); //定义一个链表保存遍历到的数字if(root == null)return; //如果为空则返回list.add(root);//不为空，将根加入链表while (list.isEmpty() == false ) {//链表不为空的时候，循环输出链表中的元素，并且继续遍历，直到遍历结束Node tem = list.poll();System.out.print(tem.val+" ");if(tem.left != null){list.add(tem.left);}if(tem.right != null){list.add(tem.right);}}}public static int Size(Node root){ //计算链表节点个数if(root == null)return 0;int tem = 0;tem = 1+Size(root.left)+Size(root.right);return tem;}public static int LeafNode(Node root){//计算叶子节点个数if(root == null)return 0;if(root.left == null && root.right == null)return 1;return LeafNode(root.left)+ LeafNode(root.right);}public static int LvelSize(Node root,int k){ //计算第K层节点个数if(k < 1 || root == null)return 0;if(k == 1)return 1;return LvelSize(root.left,k-1)+LvelSize(root.right,k-1);}public static Node Find(Node root,String a){//查找指定节点值if(root == null)return null;if(root.val.equals(a))return root;Node result = Find(root.left,a);if(result != null) return result;else return Find(root.right,a);}public static void main(String[] args) { //测试函数Node root = Tree();System.out.print("先序遍历：");PreOrder(root);System.out.println("");System.out.print("中序遍历：");MidOrder(root);System.out.println("");System.out.print("后序遍历：");LastOrder(root);System.out.println("");System.out.print("层序遍历：");LevalOrder(root);System.out.println("");System.out.print("节点个数为：");System.out.print(Size(root));System.out.println("");System.out.print("叶子节点个数为：");System.out.print(LeafNode(root));System.out.println("");System.out.print("K层节点个数为：");System.out.print(LvelSize(root,3));System.out.println("");System.out.print("该值对应节点为：");System.out.print(Find(root,"F"));System.out.println("");
先序遍历：A B D E G H C F 
中序遍历：D B G H E A C F 
后序遍历：D H G E B F C A 
层序遍历：A B C D E F G H 
节点个数为：8
叶子节点个数为：3
K层节点个数为：3
该值对应节点为：Node@4554617c}}

字符串

//字符串中的单词反转
//输入: message = "the sky is blue"
//输出: "blue is sky the"
public String reverseMessage(String message) {message = message.trim();                               // 删除首尾空格int j = message.length() - 1, i = j;StringBuilder res = new StringBuilder();while (i >= 0) {while (i >= 0 && message.charAt(i) != ' ') i--;     // 搜索首个空格res.append(message.substring(i + 1, j + 1) + " ");  // 添加单词while (i >= 0 && message.charAt(i) == ' ') i--;     // 跳过单词间空格j = i;                                              // j 指向下个单词的尾字符}return res.toString().trim();                           // 转化为字符串并返回}//最长回文串
//输入:s = "abccccdd"
//输出:7
//解释:我们可以构造的最长的回文串是"dccaccd", 它的长度是 7
public int longestPalindrome(String s) {// 统计各字符数量HashMap<Character, Integer> counter = new HashMap<>();for (int i = 0; i < s.length(); i++)counter.merge(s.charAt(i), 1, (a, b) -> a + b);// 统计构造回文串的最大长度int res = 0, odd = 0;for (Map.Entry<Character, Integer> kv : counter.entrySet()) {// 将当前字符出现次数向下取偶数，并计入 resint count = kv.getValue();int rem = count % 2;res += count - rem;// 若当前字符出现次数为奇数，则将 odd 置 1if (rem == 1) odd = 1;}return res + odd;}