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

举报
赵KK日常技术记录 发表于 2023/06/25 10:45:06 2023/06/25
【摘要】 两数之和为定值的问题。给定一个整数数组和一个目标值,找出数组中两数之和为目标值的索引。public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int comple...
  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解法:


```js
func exist(matrix [][]int, target int) bool {
   if r < 0 || c < 0 || r == rows || c == cols || visited[r][c] || 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解法:


```js
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. 排序算法实现。实现常见的排序算法,如冒泡排序、选择排序、插入排序、归并排序、快速排序等。

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。