1. 两数之和为定值的问题。给定一个整数数组和一个目标值,找出数组中两数之和为目标值的索引。
代码语言：javascript复制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
代码语言：javascript复制
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解法:
代码语言：javascript复制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解法:
代码语言：javascript复制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解法:
代码语言：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);
}
};2. 最大子数组问题。找到一个连续子数组,使得子数组元素之和最大。
Java解法:
java
代码语言：javascript复制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
代码语言：javascript复制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
代码语言：javascript复制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
代码语言：javascript复制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
代码语言：javascript复制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,最大子数组和。
3. 两个栈实现队列。使用两个栈来实现一个队列,支持队列的基本操作(push、pop、peek、empty)。
Java解法:
java
代码语言：javascript复制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
代码语言：javascript复制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
代码语言：javascript复制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
代码语言：javascript复制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
代码语言：javascript复制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中的元素。
4. 矩阵中的路径。给定一个m x n 二维数组,判断数组中是否存在一条从左上角到右下角的路径,路径上的数字之和为定值。
Java解法:
java
代码语言：javascript复制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
代码语言：javascript复制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
代码语言：javascript复制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解法:
```go
代码语言：javascript复制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
代码语言：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)。
5. 最小栈。设计一个栈,支持常规的push、pop操作,以及返回栈中最小元素的操作。
6. 字符串全排列。给定一个字符串,返回它的所有排列组合。
7. subsets问题。给定一组不重复的数字,返回它所有的子集。
8. 编辑距离。计算两个字符串之间的编辑距离,允许的编辑操作包括:插入一个字符、移除一个字符、替换一个字符。
9. 最长公共子序列。 finding the longest common subsequence (LCS) of two given strings.
10. 设计Twitter。设计推特的简易版本,实现发布推文、关注用户、查看timeline等功能。
11. 区间合并。给定一个区间的集合,需要合并所有重叠的区间。
12. 二叉树的最小深度。找出二叉树的最小深度,最小深度是从根节点到最近叶子节点的最短路径上的节点数。
13. 爬楼梯。有n个阶梯,每次可以爬1或2个阶梯,共有多少种不同的爬楼梯方法。
14. 排序算法实现。实现常见的排序算法,如冒泡排序、选择排序、插入排序、归并排序、快速排序等。
