当前位置： 首页 > article >正文

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

article 2024/11/14 11:32:59

常见的面试算法题，主要为 数组->链表->二叉树->字符串->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};
    }

链表

链表

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

image-20220316110310316

小结:

  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){
        //如果任一链表为空，则返回false
        if (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()) {
            // 将当前字符出现次数向下取偶数，并计入 res
            int count = kv.getValue();
            int rem = count % 2;
            res += count - rem;
            // 若当前字符出现次数为奇数，则将 odd 置 1
            if (rem == 1) odd = 1;
        }
        return res + odd;
    }


http://www.kler.cn/a/390393.html

相关文章：

  • python购物计算 2024年6月青少年电子学会等级考试 中小学生python编程等级考试一级真题答案解析
  • 不对称信息
  • MyBatis CRUD快速入门
  • K8s进阶使用
  • AtomicInteger 和 AtomicIntegerFieldUpdater的区别
  • 去地面算法——depth_clustering算法调试（1）
  • 网络管理之---3种网络模式配置
  • C++11新特性（二）
  • NFS服务、内核配置菜单
  • JVM学习之路（5）垃圾回收
  • 【Qt】QTreeView 和 QStandardItemModel的关系
  • SpringBoot基础系列学习(五):JdbcTemplate 访问数据库
  • 航展畅想：从F35机载软件研发来看汽车车载软件研发
  • 表格理解专题（二）：单元格的特征提取
  • Android源码中如何编译出fastboot.exe和adb.exe程序
  • JavaScript (JS)网页设计案例
  • 理解C语言之深入理解指针
  • 第R2周：LSTM算法详解
  • vscode Markdown
  • 37 string类关键函数的模拟实现
  • linux 下查看程序启动的目录
  • 抢抓5G机遇，AORO A23防爆手机如何直击园区巡检挑战？
  • Spring系统框架
  • Pytorch学习--神经网络--完整的模型训练套路
  • 【韩老师零基础30天学会Java 】06章 数组、排序和查找
  • Android 源码的下载与编译