2023算法面试题JAVA,python,go,rust ,js,C++,Swift,Kotlin,Scala解法大全
【摘要】 算法面试题以链表、树、图算法和动态规划为主,以下是典型的面试真题:1. 两数之和:给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。```jspublic int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums...
算法面试题以链表、树、图算法和动态规划为主,以下是典型的面试真题:
1. 两数之和:给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。
```js
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");
}
```
python
```
def twoSum(nums, target):
map = {}
for i in range(len(nums)):
complement = target - nums[i]
if complement in map:
return [map[complement], i]
map[nums[i]] = i
raise ValueError("No two sum solution")
```
go
```js
func twoSum(nums []int, target int) []int {
m := make(map[int]int)
for i, num := range nums {
complement := target - num
if _, ok := m[complement]; ok {
return []int{m[complement], i}
}
m[num] = i
}
panic("No two sum solution")
}
```
rust
```js
fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
let mut map = std::collections::HashMap::new();
for i in 0..nums.len() {
let complement = target - nums[i];
if map.contains_key(&complement) {
return vec![map[&complement], i as i32];
}
map.insert(nums[i], i as i32);
}
panic!("No two sum solution");
}
```
js
```js
function twoSum(nums, target) {
let map = new Map();
for (let i = 0; i < nums.length; i++) {
let complement = target - nums[i];
if (map.has(complement)) {
return [map.get(complement), i];
}
map.set(nums[i], i);
}
throw new Error("No two sum solution");
}
```
1. 三数之和:给定一个含有 n 个整数的数组,判断该数组是否含有三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。
Java解法:
```
java
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if (nums == null || nums.length < 3) return res;
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue; // 去重
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
res.add(Arrays.asList(nums[i], nums[left], nums[right]));
left++;
right--;
while (left < right && nums[left] == nums[left - 1]) left++; // 去重
while (left < right && nums[right] == nums[right + 1]) right--; // 去重
} else if (sum < 0) left++;
else right--;
}
}
return res;
}
```
Python解法:
```
python
def threeSum(self, nums: List[int]) -> List[List[int]]:
res = []
nums.sort()
for i in range(len(nums)):
if i > 0 and nums[i] == nums[i - 1]:
continue
left, right = i + 1, len(nums) - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total == 0:
res.append([nums[i], nums[left], nums[right]])
left += 1
right -= 1
while left < right and nums[left] == nums[left - 1]:
left += 1
while left < right and nums[right] == nums[right + 1]:
right -= 1
elif total < 0:
left += 1
else:
right -= 1
return res
```
Go解法:
```go
func threeSum(nums []int) [][]int {
sort.Ints(nums)
n := len(nums)
res := make([][]int, 0)
for i := 0; i < n; i++ {
if i > 0 && nums[i] == nums[i-1] {
continue
}
left, right := i+1, n-1
for left < right {
sum := nums[i] + nums[left] + nums[right]
if sum == 0 {
res = append(res, []int{nums[i], nums[left], nums[right]})
left++
right--
for left < right && nums[left] == nums[left-1] {
left++
}
for left < right && nums[right] == nums[right+1] {
right--
}
} else if sum < 0 {
left++
} else {
right--
}
}
}
return res
}
```
Rust解法:
```rust
impl Solution {
pub fn three_sum(nums: Vec<i32>) -> Vec<Vec<i32>> {
let mut nums = nums;
nums.sort();
let mut res = Vec::new();
for i in 0..nums.len()-2 {
if i > 0 && nums[i] == nums[i-1] {continue;}
let mut left = i + 1;
let mut right = nums.len() - 1;
while left < right {
let sum = nums[i] + nums[left] + nums[right];
if sum == 0 {
res.push(vec![nums[i], nums[left], nums[right]]);
left += 1; right -= 1;
while left < right && nums[left] == nums[left-1] {left += 1;}
while left < right && nums[right] == nums[right+1] {right -= 1;}
} else if sum < 0 {
left += 1;
} else {
right -= 1;
}
}
}
res
}
}
```
JS解法:
```js
var threeSum = function(nums) {
let res = [];
nums.sort((a, b) => a - b);
for (let i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] === nums[i - 1]) continue;
let left = i + 1;
let right = nums.length - 1;
while (left < right) {
let sum = nums[i] + nums[left] + nums[right];
if (sum === 0) {
res.push([nums[i], nums[left], nums[right]]);
left++;
right--;
while (left < right && nums[left] === nums[left - 1]) left++;
while (left < right && nums[right] === nums[right + 1]) right--;
} else if (sum < 0) left++;
else right--;
}
}
return res;
};
```
1. 数组排序,方便去重和左右夹逼
2. 遍历每个数numsi,左右查找numsleft和numsright,使得numsi + numsleft + numsright == 0
3. 如果sum == 0,加入结果res,并去重
4. 如果sum < 0,left指针右移,如果sum > 0,right指针左移
5. 返回结果res
时间复杂度:O(N^2),其中N是数组长度。我们首先需要O(NlogN)的时间来排序数组,然后需要O(N^2)的时间来枚举和搜索所有可能的三元组。
空间复杂度:O(1)。
6. 两两交换链表中的节点:给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。
Java解法:
```java
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode cur = dummy;
while (cur.next != null && cur.next.next != null) {
ListNode first = cur.next;
ListNode second = cur.next.next;
cur.next = second;
first.next = second.next;
second.next = first;
cur = first;
}
return dummy.next;
}
```
Python解法:
```python
def swapPairs(self, head: ListNode) -> ListNode:
dummy = ListNode(0)
dummy.next = head
cur = dummy
while cur.next and cur.next.next:
first = cur.next
second = cur.next.next
cur.next = second
first.next = second.next
second.next = first
cur = first
return dummy.next
```
Go解法:
```go
func swapPairs(head _ListNode)_ ListNode {
dummy := &ListNode{Next: head}
cur := dummy
for cur.Next != nil && cur.Next.Next != nil {
first := cur.Next
second := cur.Next.Next
cur.Next = second
first.Next = second.Next
second.Next = first
cur = first
}
return dummy.Next
}
```
Rust解法:
```rust
impl Solution {
pub fn swap_pairs(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let mut dummy = Some(Box::new(ListNode::new(0)));
dummy.as_mut().unwrap().next = head;
let mut cur = dummy.as_mut().unwrap();
while let Some(first) = cur.next.as_mut() {
if let Some(second) = first.next.as_mut() {
cur.next = Some(second.clone());
first.next = second.next.clone();
second.next = Some(first.clone());
cur = first;
} else {
break;
}
}
dummy.unwrap().next
}
}
```
JS解法:
```js
var swapPairs = function(head) {
let dummy = new ListNode(0);
dummy.next = head;
let cur = dummy;
while (cur.next && cur.next.next) {
let first = cur.next;
let second = cur.next.next;
cur.next = second;
first.next = second.next;
second.next = first;
cur = first;
}
return dummy.next;
};
```
算法思路相同,都是使用dummy节点和cur指针,两两交换链表节点,并返回dummy.next作为结果。
时间复杂度:O(n),需要遍历链表一次。
空间复杂度:O(1)。
反转链表:给定单链表的头节点 head ,请反转链表,并返回反转后的链表的头节点。
合并两个有序链表:将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
6. 回文链表:判断给定的链表是否为回文链表。回文链表是指正序和反序读都是一样的链表。
Java解法:
```javascript
java
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) return true;
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode reversed = reverse(slow);
while (reversed != null && head != null) {
if (reversed.val != head.val) return false;
reversed = reversed.next;
head = head.next;
}
return true;
}
private ListNode reverse(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
```
Python解法:
```javascript
python
def is_palindrome(self, head: ListNode) -> bool:
if not head or not head.next: return True
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
prev, node = None, slow
while node:
next = node.next
node.next = prev
prev = node
node = next
while prev and head:
if prev.val != head.val:
return False
prev = prev.next
head = head.next
return True
```
Go解法:
```javascript
go
func isPalindrome(head *ListNode) bool {
if head == nil || head.Next == nil {
return true
}
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
prev := reverse(slow)
for prev != nil && head != nil {
if prev.Val != head.Val {
return false
}
prev = prev.Next
head = head.Next
}
return true
}
func reverse(head *ListNode) *ListNode {
var prev *ListNode = nil
for head != nil {
next := head.Next
head.Next = prev
prev = head
head = next
}
return prev
}
```
Rust解法:
```javascript
rust
impl Solution {
pub fn is_palindrome(head: Option<Box<ListNode>>) -> bool {
let mut slow = head.as_ref();
let mut fast = head.as_ref();
while fast.is_some() && fast.as_ref().unwrap().next.is_some() {
slow = slow.unwrap().next.as_ref();
fast = fast.unwrap().next.as_ref().unwrap().next.as_ref();
}
let mut prev = None;
let mut slow = slow.unwrap().clone();
while slow.is_some() {
let next = slow.as_ref().unwrap().next.take();
slow.as_mut().unwrap().next = prev.take();
prev = Some(slow.take());
slow = next;
}
let mut prev = prev.unwrap();
let mut head = head.unwrap();
while prev.is_some() && head.is_some() {
if prev.as_ref().unwrap().val != head.as_ref().unwrap().val {
return false;
}
prev = prev.unwrap().next.take();
head = head.unwrap().next.take();
}
true
}
}
```
JS解法:
```javascript
js
var isPalindrome = function(head) {
if (!head || !head.next) return true;
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
let prev = null;
while (slow) {
let next = slow.next;
slow.next = prev;
prev = slow;
slow = next;
}
while (prev && head) {
if (prev.val != head.val) return false;
prev = prev.next;
head = head.next;
}
return true;
};
```
算法思路是使用快慢指针找到链表中点,然后反转后半部分链表,最后比较前半部分和反转后的后半部分是否相等。
如果相等则为回文链表。
时间复杂度O(n),空间复杂度O(1)
C++解法:
```javascript
cpp
bool isPalindrome(ListNode* head) {
if (!head || !head->next) return true;
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
ListNode* prev = NULL;
while (slow) {
ListNode* next = slow->next;
slow->next = prev;
prev = slow;
slow = next;
}
while (prev && head) {
if (prev->val != head->val) return false;
prev = prev->next;
head = head->next;
}
return true;
}
```
Swift解法:
```javascript
swift
func isPalindrome(_ head: ListNode?) -> Bool {
guard let head = head else { return true }
guard head.next != nil else { return true }
var slow = head
var fast = head
while fast?.next != nil && fast?.next?.next != nil {
slow = slow?.next
fast = fast?.next?.next
}
var prev: ListNode? = nil
var node = slow
while node != nil {
let next = node?.next
node?.next = prev
prev = node
node = next
}
while prev != nil && head != nil {
if prev!.val != head!.val {
return false
}
prev = prev?.next
head = head?.next
}
return true
}
```
Kotlin解法:
```javascript
kotlin
fun isPalindrome(head: ListNode?): Boolean {
var slow = head
var fast = head
while (fast != null && fast.next != null) {
slow = slow?.next
fast = fast.next?.next
}
var prev: ListNode? = null
var node = slow
while (node != null) {
val next = node.next
node.next = prev
prev = node
node = next
}
while (prev != null && head != null) {
if (prev.`val` != head.`val`) return false
prev = prev.next
head = head.next
}
return true
}
```
Scala解法:
```javascript
scala
def isPalindrome(head: ListNode): Boolean = {
if (head == null || head.next == null) true
else {
var slow, fast = head, head
while (fast.next != null && fast.next.next != null) {
slow = slow.next
fast = fast.next.next
}
var prev: ListNode = null
var node = slow
while (node != null) {
val next = node.next
node.next = prev
prev = node
node = next
}
while (prev != null && head != null) {
if (prev.x != head.x) return false
prev = prev.next
head = head.next
}
true
}
}
```
希望这个多语言的回文链表实现可以帮助你加深对这个算法的理解
7. 二叉树的最大深度:给定一个二叉树,找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
Java解法:
```javascript
java
public int maxDepth(TreeNode root) {
if (root == null) return 0;
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}
```
Python解法:
```javascript
python
def maxDepth(self, root: TreeNode) -> int:
if not root: return 0
left_depth = self.maxDepth(root.left)
right_depth = self.maxDepth(root.right)
return max(left_depth, right_depth) + 1
```
Go解法:
```javascript
go
func maxDepth(root *TreeNode) int {
if root == nil {
return 0
}
leftDepth := maxDepth(root.Left)
rightDepth := maxDepth(root.Right)
return int(math.Max(float64(leftDepth), float64(rightDepth))) + 1
}
```
Rust解法:
```javascript
rust
impl Solution {
fn max_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
if root.is_none() {
return 0;
}
let root = root.unwrap();
let left_depth = self.max_depth(root.borrow().left.clone());
let right_depth = self.max_depth(root.borrow().right.clone());
return std::cmp::max(left_depth, right_depth) + 1;
}
}
```
JS解法:
```javascript
js
var maxDepth = function(root) {
if (!root) return 0;
let leftDepth = maxDepth(root.left);
let rightDepth = maxDepth(root.right);
return Math.max(leftDepth, rightDepth) + 1;
};
```
C++解法:
```javascript
cpp
int maxDepth(TreeNode* root) {
if (!root) return 0;
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return std::max(leftDepth, rightDepth) + 1;
}
```
Swift解法:
```javascript
swift
func maxDepth(_ root: TreeNode?) -> Int {
if root == nil {
return 0
}
let leftDepth = maxDepth(root!.left)
let rightDepth = maxDepth(root!.right)
return max(leftDepth, rightDepth) + 1
}
```
Kotlin解法:
```javascript
kotlin
fun maxDepth(root: TreeNode?): Int {
if (root == null) return 0
val leftDepth = maxDepth(root.left)
val rightDepth = maxDepth(root.right)
return Math.max(leftDepth, rightDepth) + 1
}
```
Scala解法:
```javascript
scala
def maxDepth(root: TreeNode): Int = {
if (root == null) 0
else {
val leftDepth = maxDepth(root.left)
val rightDepth = maxDepth(root.right)
Math.max(leftDepth, rightDepth) + 1
}
}
```
时间复杂度O(n),空间复杂度O(n)。 dfs遍历整棵树,存储左右子树深度,返回最大深度。
8. 翻转二叉树:给定一个二叉树,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧看过来的二叉树的节点值。
Java解法:
```javascript
java
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
root.left = right;
root.right = left;
return root;
}
```
Python解法:
```javascript
python
def invertTree(self, root: TreeNode) -> TreeNode:
if not root:
return None
root.left, root.right = root.right, root.left
self.invertTree(root.left)
self.invertTree(root.right)
return root
```
Go解法:
```javascript
go
func invertTree(root *TreeNode) *TreeNode {
if root == nil {
return nil
}
root.Left, root.Right = invertTree(root.Right), invertTree(root.Left)
return root
}
```
Rust解法:
```javascript
rust
impl Solution {
fn invert_tree(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
if root.is_none() {
return root;
}
let node = root.as_ref().unwrap().borrow_mut();
let left = node.left.take();
let right = node.right.take();
node.left = self.invert_tree(right);
node.right = self.invert_tree(left);
root
}
}
```
JS解法:
```javascript
js
var invertTree = function(root) {
if (!root) return null;
let left = invertTree(root.left);
let right = invertTree(root.right);
root.left = right;
root.right = left;
return root;
};
```
C++解法:
```javascript
cpp
TreeNode* invertTree(TreeNode* root) {
if (!root) return nullptr;
TreeNode* left = invertTree(root->left);
TreeNode* right = invertTree(root->right);
root->left = right;
root->right = left;
return root;
}
```
Swift解法:
```javascript
swift
func invertTree(_ root: TreeNode?) -> TreeNode? {
if root == nil {
return nil
}
let left = invertTree(root!.left)
let right = invertTree(root!.right)
root!.left = right
root!.right = left
return root
}
```
Kotlin解法:
```javascript
kotlin
fun invertTree(root: TreeNode?): TreeNode? {
if (root == null) return null
val left = invertTree(root.left)
val right = invertTree(root.right)
root.left = right
root.right = left
return root
}
```
Scala解法:
```javascript
scala
def invertTree(root: TreeNode): TreeNode = {
if (root == null) null
else {
val left = invertTree(root.left)
val right = invertTree(root.right)
root.left = right
root.right = left
root
}
}
```
时间复杂度O(n),空间复杂度O(n),递归遍历整棵树,翻转左右子树。
9. 二叉树展开为链表:给定一棵二叉树,将其展开为链表。展开后的链表应该与前序遍历得到的顺序相同。
Java解法:
```javascript
java
public void flatten(TreeNode root) {
if (root == null) return;
TreeNode left = root.left;
TreeNode right = root.right;
root.left = null;
flatten(left);
flatten(right);
root.right = left;
TreeNode cur = root;
while (cur.right != null) cur = cur.right;
cur.right = right;
}
```
Python解法:
```javascript
python
def flatten(self, root: TreeNode) -> None:
if not root: return
self.flatten(root.left)
self.flatten(root.right)
tmp = root.right
root.right = root.left
root.left = None
while root.right:
root = root.right
root.right = tmp
```
Go解法:
```javascript
go
func flatten(root *TreeNode) {
if root == nil {
return
}
left, right := root.Left, root.Right
root.Left = nil
flatten(left)
flatten(right)
root.Right = left
for root.Right != nil {
root = root.Right
}
root.Right = right
}
```
Rust解法:
```javascript
rust
impl Solution {
fn flatten(root: Option<Rc<RefCell<TreeNode>>>) {
if let Some(node) = root {
let mut node = node.borrow_mut();
let left = node.left.take();
let right = node.right.take();
self.flatten(left);
self.flatten(right);
node.right = left;
let mut cur = node.as_mut();
while let Some(right) = cur.right.as_mut() {
cur = right;
}
cur.right = right;
}
}
}
```
JS解法:
```javascript
js
var flatten = function(root) {
if (!root) return;
let left = root.left;
let right = root.right;
root.left = null;
flatten(left);
flatten(right);
root.right = left;
let cur = root;
while (cur.right) cur = cur.right;
cur.right = right;
};
```
C++解法:
```javascript
cpp
void flatten(TreeNode* root) {
if (!root) return;
TreeNode* left = root->left;
TreeNode* right = root->right;
root->left = nullptr;
flatten(left);
flatten(right);
root->right = left;
TreeNode* cur = root;
while (cur->right) cur = cur->right;
cur->right = right;
}
```
Swift解法:
```javascript
swift
func flatten(_ root: TreeNode?) {
if root == nil {
return
}
let left = root!.left
let right = root!.right
root!.left = nil
flatten(left)
flatten(right)
root!.right = left
var cur = root
while cur!.right != nil {
cur = cur!.right
}
cur!.right = right
}
```
Kotlin解法:
```javascript
kotlin
fun flatten(root: TreeNode?) {
if (root == null) return
val left = root.left
val right = root.right
root.left = null
flatten(left)
flatten(right)
root.right = left
var cur = root
while (cur.right != null) cur = cur.right
cur.right = right
}
```
Scala解法:
```javascript
scala
def flatten(root: TreeNode): Unit = {
if (root != null) {
val left = root.left
val right = root.right
root.left = null
flatten(left)
flatten(right)
root.right = left
var cur = root
while (cur.right != null) cur = cur.right
cur.right = right
}
}
```
时间复杂度O(n),空间复杂度O(1)。前序遍历展开左右子树,直接修改根节点的右子节点。
10. 从上往下打印出每层二叉树的节点值:给定一个二叉树,按层序从上往下遍历,每层打印一个节点值。
Java解法:
```javascript
java
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
List<Integer> level = new ArrayList<>();
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
res.add(level);
}
return res;
}
```
Python解法:
```javascript
python
def levelOrder(self, root: TreeNode) -> List[List[int]]:
res = []
if not root: return res
queue = [root]
while queue:
size = len(queue)
level = []
for i in range(size):
node = queue.pop(0)
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(level)
return res
```
Go解法:
```javascript
go
func levelOrder(root *TreeNode) [][]int {
var res [][]int
if root == nil {
return res
}
queue := []*TreeNode{root}
for len(queue) > 0 {
var level []int
size := len(queue)
for i := 0; i < size; i++ {
node := queue[0]
queue = queue[1:]
level = append(level, node.Val)
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
res = append(res, level)
}
return res
}
```
Rust解法:
```javascript
rust
impl Solution {
fn level_order(mut root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
let mut result = vec![];
if root.is_none() {
return result;
}
let mut queue = vec![root.as_ref().unwrap().clone()];
while !queue.is_empty() {
let mut level = vec![];
let size = queue.len();
for _ in 0..size {
let node = queue.remove(0);
level.push(node.borrow().val);
if node.borrow().left.is_some() {
queue.push(node.borrow().left.as_ref().unwrap().clone());
}
if node.borrow().right.is_some() {
queue.push(node.borrow().right.as_ref().unwrap().clone());
}
}
result.push(level);
}
result
}
}
```
JS解法:
```javascript
js
var levelOrder = function(root) {
if (!root) return [];
let res = [];
let queue = [root];
while (queue.length) {
let size = queue.length;
let level = [];
for (let i = 0; i < size; i++) {
let node = queue.shift();
level.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
res.push(level);
}
return res;
};
```
```js
C++解法:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if (!root) return res;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
vector<int> level;
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode* node = q.front();
q.pop();
level.push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
res.push_back(level);
}
```
时间复杂度O(n),空间复杂度O(n)。使用队列层序遍历整棵树。
11. 黑白图像翻转:给定一个黑白图像,实现翻转图像的函数,翻转后,左边的黑色像素点保持不变,而右边的黑色像素点被翻转成白色,右边的白色像素点被翻转成黑色。
12. 排序链表:给定单链表的头指针和一个数k,实现对链表进行k交换的算法。
13. 最长回文子串:给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。
14. 编辑距离:给你两个单词 word1 和 word2,请你计算出将 word1 转换成 word2 所使用的最少操作数 。你可以对一个单词进行如下三种操作:
插入一个字符
删除一个字符
替换一个字符
15. 跳跃游戏:给定一个非负整数数组,你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。
16. 子集:给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集。
17. 电话号码的字母组合:给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。给出数字到字母的映射如下(与电话按键相同)。
18. N皇后:n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。给你一个整数 n ,返回所有不同的 n 皇后问题的解决方案。
19. 整数拆分:给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
第20题:打家劫舍问题描述:你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。示例 1:输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。示例 2:输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。提示:0 <= nums.length <= 100
0 <= nums[i] <= 400
```js
解析
这是一个典型的动态规划问题。
dp[i]表示前i个房屋中能偷窃到的最高金额
当房屋i不偷窃,dp[i]=dp[i-1]
当房屋i偷窃,dp[i]=dp[i-2]+nums[i]
从dp数组的定义可以得出转移方程dp[i]=max(dp[i-1],dp[i-2]+nums[i])
初始化dp[0]=0,dp[1]=nums[0]
遍历nums数组,使用上述转移方程即可得到最终结果dp[n-1]
```
21.最大子序和:给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
附加题：
- 爬楼梯:假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
- 三角形最小路径和:给定一个三角形 triangle ,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
- buying和selling股票的最佳时机:给定一个数组 prices ,它的第 i 个元素 pricesi 表示一支给定股票第 i 天的价格。你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。
- 组合总数:给定两个整数 n 和 k,返回 1 ... n 中所有可能的 k 个数的组合。
- 合并区间:以数组 intervals 表示若干个区间的集合,其中单个区间为 intervalsi = starti, endi 。请你合并所有重叠的区间,并返回一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间。
- 缺失的第一个正数:给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。
- 环形链表:给定一个链表,判断链表中是否有环。如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。
- 两数相加:给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。请你将两个数相加,并以相同形式返回一个表示和的链表。
- 不同路径:一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。问总共有多少条不同的路径?
- 验证二叉搜索树:给定一个二叉树,判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征:
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）