阿里巴巴的算法面试题JAVA,python,go,rust ,js,C++,Swift,Kotlin,Scala解法大全

阿里巴巴的算法面试题以链表、树、图算法和动态规划为主,以下是典型的面试真题:

1. 两数之和:给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。

public int[] twoSum(int[] nums, int target) {
    
    MapInteger, 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

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

fn two_sum(nums: Veci32>
    , target: i32) ->
     Veci32>
 {
    

    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

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 ListListInteger>
    >
 threeSum(int[] nums) {
    
    ListListInteger>
    >
     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解法:

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解法:

impl Solution {
    
    pub fn three_sum(nums: Veci32>
    ) ->
     VecVeci32>
    >
 {
    
        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解法:

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解法:

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解法:

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解法:

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解法:

impl Solution {
    


pub fn swap_pairs(head: OptionBoxListNode>
    >
    ) ->
     OptionBoxListNode>
    >
 {
    



    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解法:

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解法:

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解法:

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解法:

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解法:

rust
impl Solution {
    
    pub fn is_palindrome(head: OptionBoxListNode>
    >
    ) ->
 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解法:

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++解法:

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解法:

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解法:

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解法:

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解法:

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解法:

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解法:

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解法:

rust
impl Solution {
    
    fn max_depth(root: OptionRcRefCellTreeNode>
    >
    >
    ) ->
 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解法:

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++解法:

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解法:

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解法:

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解法:

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解法:

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解法:

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解法:

go
func invertTree(root *TreeNode) *TreeNode {

    if root == nil {

        return nil 
    }

    root.Left, root.Right = invertTree(root.Right), invertTree(root.Left) 
    return root
}

Rust解法:

rust
impl Solution {
    
    fn invert_tree(root: OptionRcRefCellTreeNode>
    >
    >
    ) ->
     OptionRcRefCellTreeNode>
    >
    >
 {

        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解法:

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++解法:

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解法:

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解法:

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解法: 

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解法:

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解法:

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解法:

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解法:

rust
impl Solution {
    
    fn flatten(root: OptionRcRefCellTreeNode>
    >
    >
) {

        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解法: 

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++解法:

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解法: 

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解法: 

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解法:

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解法:

java
public ListListInteger>
    >
 levelOrder(TreeNode root) {
    
    ListListInteger>
    >
     res = new ArrayList>
    ();
    
    if (root == null) return res;
    
    QueueTreeNode>
     queue = new LinkedList>
    ();
    
    queue.add(root);

    while (!queue.isEmpty()) {
    
        ListInteger>
     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解法:

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解法:

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解法:

rust
impl Solution {
    
    fn level_order(mut root: OptionRcRefCellTreeNode>
    >
    >
    ) ->
     VecVeci32>
    >
 {
    
        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解法: 

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;

}
    ;
    

C++解法:
vectorvectorint>
    >
 levelOrder(TreeNode* root) {
    
    vectorvectorint>
    >
     res;
    
    if (!root) return res;
    
    queueTreeNode*>
     q;
    
    q.push(root);

    while (!q.empty()) {
    
        vectorint>
     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

解析

这是一个典型的动态规划问题。
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” )。问总共有多少条不同的路径?
• 验证二叉搜索树:给定一个二叉树,判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征:

节点的左子树只包含小于当前节点的数。

节点的右子树只包含大于当前节点的数。

所有左子树和右子树自身必须也是二叉搜索树。

声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！