AI 助理
备案控制台
开发者社区 云原生 文章 正文

2023java面试算法真题 python go rust js 解法

2023-05-13 112
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
本文涉及的产品
服务治理 MSE Sentinel/OpenSergo，Agent数量 不受限
应用实时监控服务-可观测链路OpenTelemetry版，每月50GB免费额度
容器镜像服务 ACR，镜像仓库100个 不限时长
简介： 2023java面试算法真题 python go rust js 解法
  1. 两数之和为定值的问题。给定一个整数数组和一个目标值,找出数组中两数之和为目标值的索引。

​

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[] {map.get(complement), i};
        }
        map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}

​

解题思路:

  1. 创建一个Map,key为数组中的数字,value为该数字在数组中的索引。
  2. 遍历数组中的每个数字num。
  3. 计算目标值target与num的差值complement。
  4. 如果Map中已经存在complement,则返回num的索引与complement对应的索引。
  5. 将num和其索引添加到Map中。
  6. 如果数组中不存在两数之和为target,则抛出异常。

时间复杂度:O(N),其中N为数组长度。我们只遍历数组一次。

空间复杂度:O(N), Map中最多可存储N/2个元素。

例如:

int[] nums = {2, 7, 11, 15};

int target = 9;

​

输出: [0, 1]

因为nums[0] + nums[1] = 2 + 7 = 9,所以返回索引0和索引1。

​

python


public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[] {map.get(complement), i};
        }
        map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}

​

Go解法:

func twoSum(nums []int, target int) []int {
    m := make(map[int]int)
    for i, num := range nums {
        if j, ok := m[target-num]; ok {
            return []int{j, i}
        }
        m[num] = i
    }
    return nil
}

​

Rust解法:

​

fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
    let mut map = HashMap::new();
    for (i, num) in nums.iter().enumerate() {
        match map.get(&(target - num)) {
            Some(&j) => return vec![j as i32, i as i32],
            None => map.insert(num, i),
        }
    }
    vec![]
}

​

JavaScript解法:

var twoSum = function(nums, target) {
    const map = new Map();
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (map.has(complement)) {
            return [map.get(complement), i]; 
        }
        map.set(nums[i], i);
    }
};

​

​

​

  1. 最大子数组问题。找到一个连续子数组,使得子数组元素之和最大。

Java解法:

java

public int maxSubArray(int[] nums) {
    int maxSum = 0;
    int currentSum = 0;
    for (int num : nums) {
        currentSum = Math.max(0, currentSum + num);
        maxSum = Math.max(maxSum, currentSum);
    }
    return maxSum; 
}

​

Python解法:

python

def maxSubArray(self, nums):
    maxSum = 0
    currentSum = 0
    for num in nums:
        currentSum = max(0, currentSum + num)
        maxSum = max(maxSum, currentSum)
    return maxSum

​

Rust解法:

rust

fn max_subarray(nums: Vec<i32>) -> i32 {
    let mut max_sum = 0;
    let mut current_sum = 0;
    for num in nums {
        current_sum = current_sum.max(0) + num;
        max_sum = max_sum.max(current_sum);
    }
    max_sum
}

​

Go解法:

go

func maxSubArray(nums []int) int {
    maxSum, currentSum := 0, 0
    for _, num := range nums {
        currentSum = max(0, currentSum+num)
        maxSum = max(maxSum, currentSum)
    }
    return maxSum
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

​

JavaScript解法:

js

var maxSubArray = function(nums) {
    let maxSum = 0;
    let currentSum = 0;
    for (let num of nums) {
        currentSum = Math.max(0, currentSum + num);
        maxSum = Math.max(maxSum, currentSum);
    }
    return maxSum;
};

​

这五种语言的解法思路都是动态规划,主要步骤是:

  1. 定义当前最大子数组和maxSum和当前子数组和currentSum。
  2. 遍历数组中的每个数字num。
  3. currentSum = max(0, currentSum + num),即当前子数组和要么归0,要么继续增大。
  4. maxSum = max(maxSum, currentSum),即最大子数组和是当前子数组和和历史最大子数组和的最大值。
  5. 返回maxSum,最大子数组和。

​

  1. 两个栈实现队列。使用两个栈来实现一个队列,支持队列的基本操作(push、pop、peek、empty)。

Java解法:

java

class MyQueue {
    Stack<Integer> stack1;
    Stack<Integer> stack2;
    
    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }
    
    public void push(int x) {
        stack1.push(x);
    }
    
    public int pop() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        } 
        return stack2.pop();
    }
    
    public int peek() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.peek();
    }
    
    public boolean empty() {
        return stack1.isEmpty() && stack2.isEmpty(); 
    }
}

​

Python解法:

python

class MyQueue:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
        
    def push(self, x):
        self.stack1.append(x)
        
    def pop(self):
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop()
        
    def peek(self):
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2[-1]
    
    def empty(self):
        return not self.stack1 and not self.stack2

​

Rust解法:

rust

struct MyQueue {
    stack1: Vec<i32>,
    stack2: Vec<i32>, 
}

impl MyQueue {
    fn new() -> MyQueue {
        MyQueue { 
            stack1: Vec::new(),
            stack2: Vec::new() 
        }
    }
    
    fn push(&mut self, x: i32) {
        self.stack1.push(x);
    }
    
    fn pop(&mut self) -> i32 {
        if self.stack2.is_empty() {
            while let Some(x) = self.stack1.pop() {
                self.stack2.push(x);
            }
        }
        self.stack2.pop().unwrap()
    }  
    
    fn peek(&mut self) -> i32 {
        if self.stack2.is_empty() {
            while let Some(x) = self.stack1.pop() {
                self.stack2.push(x);
            } 
        }
        *self.stack2.last().unwrap()
    }  
    
    fn empty(&self) -> bool {
        self.stack1.is_empty() && self.stack2.is_empty()
    }
}

​

Go解法:

go

type MyQueue struct {
    stack1 []int
    stack2 []int
}

func Constructor() MyQueue {
    return MyQueue{
        stack1: []int{},
        stack2: []int{},
    }
}

func (q *MyQueue) Push(x int)  {
    q.stack1 = append(q.stack1, x)
}

func (q *MyQueue) Pop() int {
    if len(q.stack2) == 0 {
        for len(q.stack1) > 0 {
            q.stack2 = append(q.stack2, q.stack1[len(q.stack1)-1])
            q.stack1 = q.stack1[:len(q.stack1)-1]
        }
    }
    val := q.stack2[len(q.stack2)-1]
    q.stack2 = q.stack2[:len(q.stack2)-1]
    return val 
}

func (q *MyQueue) Peek() int {
    if len(q.stack2) == 0 {
        for len(q.stack1) > 0 {
            q.stack2 = append(q.stack2, q.stack1[len(q.stack1)-1])
            q.stack1 = q.stack1[:len(q.stack1)-1]
        }
    } 
    return q.stack2[len(q.stack2)-1]
}

func (q *MyQueue) Empty() bool {
    return len(q.stack1) == 0 && len(q.stack2) == 0 
}

​

JavaScript解法:

js

class MyQueue {
  constructor() {
    this.stack1 = [];
    this.stack2 = [];
  }
  
  push(x) {
    this.stack1.push(x);
  }
  
  pop() {
    if (this.stack2.length === 0) {
      while (this.stack1.length > 0) {
        this.stack2.push(this.stack1.pop());
      }
    }
    return this.stack2.pop();
  }
  
  peek() {
    if (this.stack2.length === 0) {
      while (this.stack1.length > 0) {
        this.stack2.push(this.stack1.pop());
      } 
    }
    return this.stack2[this.stack2.length - 1];
  }
  
  empty() {
    return this.stack1.length === 0 && this.stack2.length === 0; 
  }
}

​

解题思路:

  1. stack1用作输入栈,stack2用作输出栈。
  2. push操作直接将元素添加到stack1。
  3. pop和peek操作首先将stack1的所有元素弹出并推入stack2,然后从stack2弹出元素。
  4. empty操作判断stack1和stack2是否均为空。
  5. 使用两个栈模拟队列先入先出的特性。

时间复杂度:push O(1), pop O(N), peek O(N),空 O(1)。其中N为stack1的大小。

空间复杂度:O(N),我们需要额外的栈stack2来存储stack1中的元素。

​

  1. 矩阵中的路径。给定一个m x n 二维数组,判断数组中是否存在一条从左上角到右下角的路径,路径上的数字之和为定值。

Java解法:

java

public boolean exist(int[][] matrix, int target) {
    if (matrix == null || matrix.length == 0) return false;
    int rows = matrix.length, cols = matrix[0].length;
    boolean[][] visited = new boolean[rows][cols];
    return dfs(matrix, 0, 0, rows, cols, 0, target, visited);
}

private boolean dfs(int[][] matrix, int r, int c, int rows, int cols, int sum, int target, boolean[][] visited) {
    if (r == rows || c == cols) return false; 
    if (sum + matrix[r][c] == target) return true; 
    if (visited[r][c]) return false;
    visited[r][c] = true;
    
    boolean exist = dfs(matrix, r + 1, c, rows, cols, sum + matrix[r][c], target, visited) || 
                    dfs(matrix, r - 1, c, rows, cols, sum + matrix[r][c], target, visited) ||
                    dfs(matrix, r, c + 1, rows, cols, sum + matrix[r][c], target, visited) ||
                    dfs(matrix, r, c - 1, rows, cols, sum + matrix[r][c], target, visited);
                    
    visited[r][c] = false;
    return exist; 
}

​

Python解法:

python

def exist(self, matrix, target):
    if not matrix or not matrix[0]:
        return False
    rows, cols = len(matrix), len(matrix[0])
    visited = set()
    
    def dfs(r, c, sum):
        if r < 0 or c < 0 or r == rows or c == cols or (r, c) in visited or sum > target:
            return False
        if sum == target:
            return True
        visited.add((r, c))
        exist = dfs(r + 1, c, sum + matrix[r][c]) or dfs(r - 1, c, sum + matrix[r][c]) or \
                dfs(r, c + 1, sum + matrix[r][c]) or dfs(r, c - 1, sum + matrix[r][c])
        visited.remove((r, c))
        return exist
    
    return dfs(0, 0, 0)

​

Rust解法:

rust

fn exist(matrix: Vec<Vec<i32>>, target: i32) -> bool {
    if matrix.is_empty() || matrix[0].is_empty() {
        return false; 
    }
    let rows = matrix.len();
    let cols = matrix[0].len();
    let mut visited = HashSet::new();

    fn dfs(matrix: &Vec<Vec<i32>>, r: usize, c: usize, rows: usize, cols: usize, 
          sum: i32, target: i32, visited: &mut HashSet<(usize, usize)>) -> bool {
        if r == rows || c == cols || visited.contains(&(r, c)) || sum > target {
            return false; 
        }   
        if sum == target {
            return true;
        }
        visited.insert((r, c));
        let exist = dfs(matrix, r + 1, c, rows, cols, sum + matrix[r][c], target, visited) ||  
                    dfs(matrix, r - 1, c, rows, cols, sum + matrix[r][c], target, visited) ||   
                    dfs(matrix, r, c + 1, rows, cols, sum + matrix[r][c], target, visited) ||
                    dfs(matrix, r, c - 1, rows, cols, sum + matrix[r][c], target, visited);
        visited.remove(&(r, c));
        exist     
    }
    
    dfs(&matrix, 0, 0, rows, cols, 0, target, &mut visited) 
}

​

Go解法:

func exist(matrix [][]int, target int) bool {
if r < 0 || c < 0 || r == rows || c == cols || visitedr || sum > target {

    return false
}
if sum == target {
    return true
}
visited[r][c] = true
exist := dfs(r+1, c, sum+matrix[r][c]) || dfs(r-1, c, sum+matrix[r][c]) ||
         dfs(r, c+1, sum+matrix[r][c]) || dfs(r, c-1, sum+matrix[r][c])
visited[r][c] = false
return exist

}
return dfs(0, 0, 0)
}


​

JavaScript解法:

var exist = function(matrix, target) {
    if (!matrix || !matrix[0]) return false;
    const rows = matrix.length;
    const cols = matrix[0].length;
    const visited = new Set();
    
    function dfs(r, c, sum) {
        if (r < 0 || c < 0 || r === rows || c === cols || visited.has(`${r}-${c}`) || sum > target) 
            return false;
        if (sum === target) return true;
        visited.add(`${r}-${c}`);
        let exist = dfs(r + 1, c, sum + matrix[r][c]) || 
                    dfs(r - 1, c, sum + matrix[r][c]) || 
                    dfs(r, c + 1, sum + matrix[r][c]) ||
                    dfs(r, c - 1, sum + matrix[r][c]);
        visited.delete(`${r}-${c}`);
        return exist;
    }
    
    return dfs(0, 0, 0);
};

​

解题思路:

  1. 进行深度优先搜索,判断从左上角到达右下角的路径是否存在。
  2. dfs函数参数包含行r、列c、当前路径和sum和目标值target。
  3. base case:如果r、c超出矩阵边界或该位置已访问或当前路径和大于目标值,返回false。
  4. 如果当前路径和等于目标值,返回true。
  5. 标记当前位置已访问,并递归调用四个方向的位置。
  6. 回溯时,取消当前位置的已访问标记。
  7. 如果找到一条路径,则返回true,否则返回false。

时间复杂度:O(mn),其中m和n分别为矩阵的行数和列数。

空间复杂度:O(mn),由于递归调用,栈的深度可能达到O(mn)。

​

  1. 最小栈。设计一个栈,支持常规的push、pop操作,以及返回栈中最小元素的操作。
  2. 字符串全排列。给定一个字符串,返回它的所有排列组合。
  3. subsets问题。给定一组不重复的数字,返回它所有的子集。
  4. 编辑距离。计算两个字符串之间的编辑距离,允许的编辑操作包括:插入一个字符、移除一个字符、替换一个字符。
  5. 最长公共子序列。 finding the longest common subsequence (LCS) of two given strings.
  6. 设计Twitter。设计推特的简易版本,实现发布推文、关注用户、查看timeline等功能。
  7. 区间合并。给定一个区间的集合,需要合并所有重叠的区间。
  8. 二叉树的最小深度。找出二叉树的最小深度,最小深度是从根节点到最近叶子节点的最短路径上的节点数。
  9. 爬楼梯。有n个阶梯,每次可以爬1或2个阶梯,共有多少种不同的爬楼梯方法。
  10. 排序算法实现。实现常见的排序算法,如冒泡排序、选择排序、插入排序、归并排序、快速排序等。
文章标签：
Java
JavaScript
Python
Go
前端开发
搜索推荐
索引
算法
存储
Rust
关键词：
面试解法
Java Python
Java面试
Python算法
算法go
zhaokk
目录
相关文章
技术自由圈/原疯狂创客圈
|
1月前
|
算法 Java 数据库
美团面试：百亿级分片，如何设计基因算法？
40岁老架构师尼恩分享分库分表的基因算法设计，涵盖分片键选择、水平拆分策略及基因法优化查询效率等内容，助力面试者应对大厂技术面试，提高架构设计能力。
技术自由圈/原疯狂创客圈
49 1
美团面试：百亿级分片，如何设计基因算法？
java冯坚持
|
1月前
|
算法 前端开发 Java
数据结构与算法学习四：单链表面试题，新浪、腾讯【有难度】、百度面试题
这篇文章总结了单链表的常见面试题，并提供了详细的问题分析、思路分析以及Java代码实现，包括求单链表中有效节点的个数、查找单链表中的倒数第k个节点、单链表的反转以及从尾到头打印单链表等题目。
java冯坚持
33 1
数据结构与算法学习四：单链表面试题，新浪、腾讯【有难度】、百度面试题
汀丶人工智能
|
1月前
|
机器学习/深度学习 算法 Java
机器学习、基础算法、python常见面试题必知必答系列大全：（面试问题持续更新）
机器学习、基础算法、python常见面试题必知必答系列大全：（面试问题持续更新）
汀丶人工智能
59 1
技术自由圈/原疯狂创客圈
|
1月前
|
算法 Java 数据库
美团面试：百亿级分片，如何设计基因算法？
40岁老架构师尼恩在读者群中分享了关于分库分表的基因算法设计，旨在帮助大家应对一线互联网企业的面试题。文章详细介绍了分库分表的背景、分片键的设计目标和建议，以及基因法的具体应用和优缺点。通过系统化的梳理，帮助读者提升架构、设计和开发水平，顺利通过面试。
技术自由圈/原疯狂创客圈
97 0
美团面试：百亿级分片，如何设计基因算法？
LKIDTI数据
|
1月前
|
Go Docker Python
docker的python与go镜像的制作
docker的python与go镜像的制作
LKIDTI数据
30 1
喜欢猪猪
|
1月前
|
算法 Java 数据中心
探讨面试常见问题雪花算法、时钟回拨问题，java中优雅的实现方式
【10月更文挑战第2天】在大数据量系统中，分布式ID生成是一个关键问题。为了保证在分布式环境下生成的ID唯一、有序且高效，业界提出了多种解决方案，其中雪花算法（Snowflake Algorithm）是一种广泛应用的分布式ID生成算法。本文将详细介绍雪花算法的原理、实现及其处理时钟回拨问题的方法，并提供Java代码示例。
喜欢猪猪
73 2
糜终
|
1月前
|
算法 安全 Go
RSA加密算法详解与Python和Go实现
RSA加密算法详解与Python和Go实现
糜终
105 1
糜终
|
1月前
|
算法 安全 Go
Python与Go语言中的哈希算法实现及对比分析
Python与Go语言中的哈希算法实现及对比分析
糜终
41 0
糜终
|
1月前
|
安全 测试技术 Go
Python 和 Go 实现 AES 加密算法的技术详解
Python 和 Go 实现 AES 加密算法的技术详解
糜终
88 0
简简单单做算法
|
1月前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中，通过游戏理论优化动态频谱访问，提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本：Matlab 2022a。完整代码包含详细中文注释和操作视频。
简简单单做算法
41 2

云原生

热门文章

最新文章

  • 1
    Docker CE 镜像源站
  • 2
    在阿里云容器服务上开发基于Docker的Spring Cloud微服务应用
  • 3
    阿里中间件首席架构师钟华：《企业IT架构转型之道：阿里巴巴中台战略思想与架构实战》新书出版（含试读PDF）！
  • 4
    开发函数计算的正确姿势 —— 移植 next.js 服务端渲染框架
  • 5
    阿里云容器服务新建集群优化方案
  • 6
    Docker Engine 镜像源站
  • 7
    Java编码技巧之高效代码50例
  • 8
    一键托管，阿里云全链路追踪服务正式商用：成本仅自建1/5或更少
  • 9
    如何设置Docker容器中Java应用的内存限制
  • 10
    开发者说：Sentinel 流控功能在 SpringMVC/SpringBoot 上的实践
  • 1
    朗新科技集团如何用云消息队列 RocketMQ 版“快、准、狠”破解业务难题？
    18
  • 2
    C 语言动态内存分配 —— 灵活掌控内存资源
    11
  • 3
    046_pdb_debug_调试赋值语句_先声明赋值_再使用
    13
  • 4
    如何自己独立制作网站？
    21
  • 5
    如何进行网站建设？
    15
  • 6
    N 种值得一看的前后端鉴权方案
    19
  • 7
    轻松管理Linux服务器的5个优秀管理面板
    30
  • 8
    React 文件上传组件 File Upload
    14
  • 9
    做架构设计过程，因为新产品发布，新的领域，客串产品经理
    12
  • 10
    【Azure 环境】使用Azure bicep对多个ServicePrinciple 进行role assignment分配
    27

    • 相关课程

    更多
  • Python爬虫实战
  • Python开发基础入门
  • Python常用数据科学库
  • Java面试疑难点解析 - 面试技巧及语言基础
  • Java面试疑难点解析 - Java Web开发
  • Java面试疑难点解析 - 系统架构及项目设计

    • 相关电子书

    更多
  • 阿里云技术面试红宝书
  • 超全算法笔试-模拟题精解合集
  • 程序员面试宝典

    • 相关实验场景

    更多
  • 用Python画圣诞树
  • 使用Swing算法实现商品推荐
  • Html5和Webpack2：Webpack5打包JS和样式表
  • 阿里云平台上进行Java程序的编译与运行
  • RSA密码算法设计与实现
  • RSA非对称加密算法

    • 推荐镜像

    更多
  • python-release
  • nodejs-release
  • golang
    • 下一篇
    无影云桌面