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

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

2023-05-13 114
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
本文涉及的产品
服务治理 MSE Sentinel/OpenSergo，Agent数量 不受限
Serverless 应用引擎免费试用套餐包，4320000 CU，有效期3个月
应用实时监控服务-用户体验监控，每月100OCU免费额度
简介： 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
关键词：
JavaScript算法
Go算法
Python算法
Java算法
Java面试
zhaokk
目录
相关文章
陌陌谣
|
11天前
|
存储 监控 算法
员工上网行为监控中的Go语言算法：布隆过滤器的应用
在信息化高速发展的时代，企业上网行为监管至关重要。布隆过滤器作为一种高效、节省空间的概率性数据结构，适用于大规模URL查询与匹配，是实现精准上网行为管理的理想选择。本文探讨了布隆过滤器的原理及其优缺点，并展示了如何使用Go语言实现该算法，以提升企业网络管理效率和安全性。尽管存在误报等局限性，但合理配置下，布隆过滤器为企业提供了经济有效的解决方案。
陌陌谣
52 8
员工上网行为监控中的Go语言算法：布隆过滤器的应用
vohelon
|
2月前
|
人工智能 安全 Java
Java和Python在企业中的应用情况
Java和Python在企业中的应用情况
vohelon
62 7
tech1024
|
6天前
|
算法 安全 Go
Go 语言中实现 RSA 加解密、签名验证算法
随着互联网的发展，安全需求日益增长。非对称加密算法RSA成为密码学中的重要代表。本文介绍如何使用Go语言和[forgoer/openssl](https://github.com/forgoer/openssl)库简化RSA加解密操作，包括秘钥生成、加解密及签名验证。该库还支持AES、DES等常用算法，安装简便，代码示例清晰易懂。
tech1024
34 12
陌陌谣
|
9天前
|
监控 算法 安全
解锁企业计算机监控的关键：基于 Go 语言的精准洞察算法
企业计算机监控在数字化浪潮下至关重要，旨在保障信息资产安全与高效运营。利用Go语言的并发编程和系统交互能力，通过进程监控、网络行为分析及应用程序使用记录等手段，实时掌握计算机运行状态。具体实现包括获取进程信息、解析网络数据包、记录应用使用时长等，确保企业信息安全合规，提升工作效率。本文转载自：[VIPShare](https://www.vipshare.com)。
陌陌谣
19 0
廖小凡
|
2月前
|
JSON JavaScript 前端开发
[JS]面试官：你的简历上写着熟悉jsonp，那你说说它的底层逻辑是怎样的？
本文介绍了JSONP的工作原理及其在解决跨域请求中的应用。首先解释了同源策略的概念，然后通过多个示例详细阐述了JSONP如何通过动态解释服务端返回的JavaScript脚本来实现跨域数据交互。文章还探讨了使用jQuery的`$.ajax`方法封装JSONP请求的方式，并提供了具体的代码示例。最后，通过一个更复杂的示例展示了如何处理JSON格式的响应数据。
廖小凡
42 2
[JS]面试官：你的简历上写着熟悉jsonp，那你说说它的底层逻辑是怎样的？
vohelon
|
2月前
|
Java 程序员 开发工具
在比较Java和Python哪个更易学
在比较Java和Python哪个更易学
vohelon
40 4
vohelon
|
2月前
|
Java 程序员 Python
Java和Python
Java和Python
vohelon
26 2
游客zi3qmblbcdexu
|
3月前
|
Web App开发 JavaScript 前端开发
前端Node.js面试题
前端Node.js面试题
游客zi3qmblbcdexu
25 0
热爱技术的小郑
|
5月前
|
存储 Java
【IO面试题 四】、介绍一下Java的序列化与反序列化
Java的序列化与反序列化允许对象通过实现Serializable接口转换成字节序列并存储或传输，之后可以通过ObjectInputStream和ObjectOutputStream的方法将这些字节序列恢复成对象。
热爱技术的小郑
62 2
程序员皮皮林
|
2月前
|
存储 缓存 算法
面试官：单核 CPU 支持 Java 多线程吗？为什么？被问懵了！
本文介绍了多线程环境下的几个关键概念，包括时间片、超线程、上下文切换及其影响因素，以及线程调度的两种方式——抢占式调度和协同式调度。文章还讨论了减少上下文切换次数以提高多线程程序效率的方法，如无锁并发编程、使用CAS算法等，并提出了合理的线程数量配置策略，以平衡CPU利用率和线程切换开销。
程序员皮皮林
82 1
面试官：单核 CPU 支持 Java 多线程吗？为什么？被问懵了！

云原生

热门文章

最新文章

  • 1
    开发者说：Sentinel 流控功能在 SpringMVC/SpringBoot 上的实践
  • 2
    玩转阿里云Serverless Kubernetes新功能
  • 3
    如何配置阿里云容器服务K8S Ingress Controller使用私网SLB
  • 4
    什么是 stack？- 每天5分钟玩转 Docker 容器技术（111）
  • 5
    部署 Prometheus Operator - 每天5分钟玩转 Docker 容器技术（179）
  • 6
    SwarmKit的概念和架构
  • 7
    Java Worker 设计模式
  • 8
    B站高性能微服务架构
  • 9
    在Kubernetes上使用RDMA
  • 10
    Aliplayer快速入门：资源引用、添加容器元素与初始化
  • 1
    为了提升运维工程师及开发者
    17
  • 2
    一个接口4个步骤轻松搞定最新版Chrome、Edge、Firefox浏览器集成ActiveX控件
    44
  • 3
    加速阿里云部署：Terraform在甄云科技的深度应用
    24
  • 4
    AI驱动的开发者工具：打造沉浸式API集成体验
    17
  • 5
    API First:模型驱动的阿里云API保障体系
    27
  • 6
    API稳定安全最佳实践:用阿里云SDK为业务保驾护航
    30
  • 7
    长桥科技：通过Terraform自动化为客户提供安全、高效的产品服务体验
    24
  • 8
    云卓越架构：稳定性支柱整体解决方案综述
    19
  • 9
    云卓越架构：云上网络稳定性建设和应用稳定性治理最佳实践
    19
  • 10
    云卓越架构：企业稳定性架构体系和AI业务场景探秘
    23

    • 相关课程

    更多
  • Java面试疑难点解析 - 面试技巧及语言基础
  • Java面试疑难点解析 - Java Web开发
  • Java面试疑难点解析 - 系统架构及项目设计
  • Java编程入门
  • Java面向对象编程
  • Java高级编程

    • 相关电子书

    更多
  • Spring Cloud Alibaba - 重新定义 Java Cloud-Native
  • The Reactive Cloud Native Arch
  • JAVA开发手册1.5.0

    • 相关实验场景

    更多
  • 用Python画圣诞树
  • 使用Swing算法实现商品推荐
  • Html5和Webpack2：Webpack5打包JS和样式表
  • 前端开发基础6：Node.js和LESS预编译工具
  • 阿里云平台上进行Java程序的编译与运行
  • RSA密码算法设计与实现

    • 推荐镜像

    更多
  • python-release
  • nodejs-release
  • composer
    • 下一篇
    阿里云无影云电脑免费试用，最长可试用3个月