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

YangQG 面试题汇总

一、交叉链表

问题:

给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。

解题思想:

双指针

备注:不是快慢指针,如果两个长度相同可以用快慢指针,因为两个链表长度不同。

package org.example.YangQianGuan;

class Node {
    int data;
    Node next;

    Node(int val) {
        this.data = val;
        this.next = null;
    }

    @Override
    public String toString() {
        return " {data: " + this.data + " next: " + this.next + "} ";
    }
}

public class IntersectionNode {
    public Node getStartInter(Node headA, Node headB) {
        if (headA == null || headB == null) {
            return null;
        }
        Node pA = headA;
        Node pB = headB;

        while (pA!= pB) {
            pA = pA == null? headB : pA.next;
            pB = pB == null? headA : pB.next;
        }
        return pA;
    }


    public static void main(String[] args) {
        // node list
        Node node8 = new Node(8);
        Node node4 = new Node(4);
        Node node5 = new Node(5);

        node8.next = node4;
        node4.next = node5;

        // A list
        Node headA = new Node(4);
        Node nodeA1 = new Node(1);
        headA.next = nodeA1;
        nodeA1.next = node8;

        // B List
        Node headB = new Node(5);
        Node nodeB1 = new Node(6);
        Node nodeB2 = new Node(1);
        headB.next = nodeB1;
        nodeB1.next = nodeB2;
        nodeB2.next = node8;

        IntersectionNode intersectionNode = new IntersectionNode();
        Node startInter = intersectionNode.getStartInter(headA, headB);
        System.out.println(startInter);
    }
}

二、对称二叉树

Tree

package org.example.YangQianGuan;

class Tree{
    int data;
    Tree left;
    Tree right;

    public Tree(int data, Tree left, Tree right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }
}

public class IsMirrorTree {

    public boolean isMirror(Tree root) {
        if (root == null) {
            return true;
        }

        return this.isMirrorCore(root.left, root.right);
    }

    public boolean isMirrorCore(Tree left, Tree right) {
        if (left == null && right == null) {
            return true;
        }

        if (left == null || right == null) {
            return false;
        }

        if (left.data != right.data) {
            return false;
        }

        return isMirrorCore(left.left, right.right) && isMirrorCore(left.right, right.left);
    }

    public static void main(String[] args) {
        Tree right4 = new Tree(3, null, null);
        Tree right3 = new Tree(4, null, null);
        Tree right2 = new Tree(2, right3, right4);

        Tree left4 = new Tree(4, null, null);
        Tree left3 = new Tree(3, null, null);
        Tree left2 = new Tree(2, left3, left4);
        Tree node1 = new Tree(1, left2, right2);

        IsMirrorTree isMirrorTree = new IsMirrorTree();
        boolean mirror = isMirrorTree.isMirror(node1);
        System.out.println(mirror);
    }

}

三、轮转数组

package org.example.YangQianGuan;

import java.util.Arrays;
import java.util.List;

public class RightRunArr {

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5, 6, 7};
        int n = 3;

        RightRunArr rightRunArr = new RightRunArr();
        int[] core = rightRunArr.core(nums, n);
        System.out.println(Arrays.toString(core));
    }

    private int[] core(int[] nums, int n) {
        int[] res = new int[nums.length];
        int bit = n % nums.length;
        System.out.println(bit);

        int[] left = Arrays.copyOfRange(nums, 0, nums.length - bit);
        int[] right = Arrays.copyOfRange(nums, nums.length - bit, nums.length);

        int i = 0;
        for (int i1 : right) {
            res[i] = i1;
            i++;
        }

        for (int i1 : left) {
            res[i] = i1;
            i++;
        }

        return res;
    }
}

四、接雨水

题目描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

示例 1:

输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出:6
解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。 
示例 2:输入:height = [4,2,0,3,2,5]   输出:9

提示:

n == height.length
1 <= n <= 2 * 
0 <= height[i] <= 

package org.example.YangQianGuan;

/**
 * 暴力求解法
 * 总水量 = 除了左右两个边界,【1,lenth-1】所有点位能接水的量的总和
 * 题目转化为如何求解每个点位的接水量 = Math.min(次点左边最大高度,此点右边最大高度)-heiht(i)
 */
public class TrapSolution {
    public int trap(int[] height) {
        if (height.length<=1) {
            return 0;
        }

        int totleWater = 0;
        int leftMax = 0, rightMax = 0;

        for (int i = 1; i < height.length-1; i++) {
            // left max
            for (int j = 0; j < i; j++) {
                leftMax = Math.max(leftMax, height[j]);
            }

            // right max
            for (int j = i+1; j < height.length; j++) {
                rightMax = Math.max(rightMax, height[j]);
            }

            totleWater += Math.min(leftMax,rightMax)-height[i];

        }

        return totleWater;
    }

    public static void main(String[] args) {
        TrapSolution solution = new TrapSolution();

        // 测试用例 1
        int[] height1 = {0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println(solution.trap(height1)); // 输出: 6

        // 测试用例 2
        int[] height2 = {4,2,0,3,2,5};
        System.out.println(solution.trap(height2)); // 输出: 9
    }
}

五、字母异位词分组

给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"] 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:输入: strs = [""] 输出: [[""]]

示例 3:输入: strs = ["a"] 输出: [["a"]]

提示:

1 <= strs.length <= 
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母

package org.example.YangQianGuan;

import java.util.*;

public class GroupAnagrams {

    public static void main(String[] args) {
        String[] s = {"eat", "tea", "tan", "ate", "nat", "bat"};

        GroupAnagrams groupAnagrams = new GroupAnagrams();
        String[] res = groupAnagrams.getGroup(s);
    }

    private String[] getGroup(String[] s) {
        int length = s.length;
        if (length==0) {
            return new String[0];
        }

        Map<String, List<String>> map = new HashMap<>();
        for (String string : s) {
            char[] charArray = string.toCharArray();
            Arrays.sort(charArray);
            String s1 = new String(charArray);

            List<String> orDefault = map.getOrDefault(s1, new ArrayList<>());
            orDefault.add(string);
            map.put(s1, orDefault);
        }

        String res[] = new String[map.size()];
        int n = 0;

        for (Map.Entry<String, List<String>> stringListEntry : map.entrySet()) {
            List<String> value = stringListEntry.getValue();
            String[] array = value.toArray(String[]::new);
            res[n] = Arrays.toString(array);
            n++;
        }

        System.out.println(Arrays.toString(res));

        return res;
    }
}

原文地址:https://blog.csdn.net/m0_37145844/article/details/145043091
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/502486.html

相关文章:

  • 1.8 GPT-4:开创人工智能的新纪元
  • opencv进行人脸识别环境搭建
  • centos使用dpdk库
  • 【学习笔记】Macbook管理多个不同的Python版本
  • Linux 查看内存命令
  • ESP8266固件烧录
  • Java安全—SPEL表达式XXESSTI模板注入JDBCMyBatis注入
  • 玩转大语言模型——langchain调用ollama视觉多模态语言模型
  • Ubuntu Server挂载AWS S3成一个本地文件夹
  • Nginx简述
  • MySQL表的增删改查(进阶)-上篇
  • Vue.js组件开发-图片剪裁性能优化最佳方案实例
  • 【JVM-2.3】深入解析JVisualVM:Java性能监控与调优利器
  • 【解决问题】WSL报错 Netlink send error : Invalid argument
  • 认识机器学习中的经验风险最小化准则
  • torch.einsum计算张量的外积
  • 每天五分钟深度学习框架pytorch:快速搭建VGG网络的基础模块VGG块
  • docker 日常使用(进入容器、查看日志)
  • [vue] $refs和$el的使用
  • Clojure语言的正则表达式
  • 代码随想录day24 | 贪心算法理论基础 leetcode 455.分发饼干 376.摆动序列 53. 最大子序和
  • 计算机网络 (40)域名系统DNS
  • django华为产品销售的数据爬虫与可视化分析
  • CSS语言的数据类型
  • [Python学习日记-75] 计算机基础与网络
  • SpringBoot + 事务钩子函数