经典的10个常见的算法问题及(java、python)代码示例，你知多少，卷起来吧

忘是亡心i 2023-10-12 19:44 6阅读 0赞

#### 目录 ####

*   *   *  1. 写一个函数来计算斐波那契数列的第n项。
         *  2. 给定一个字符串，判断它是否是回文字符串。
         *  3. 实现一个冒泡排序算法。
         *  4. 给定一个整数数组，找到其中的最大值和最小值。
         *  5. 给定一个二叉树，求它的深度。
         *  6. 给定一个字符串，找到其中出现次数最多的字符。
         *  7. 实现一个快速排序算法。
         *  8. 给定一个整数数组和一个目标值，找到数组中两个数的和等于目标值。
         *  9. 实现一个堆排序算法。
         *  10. 给定一个二叉树，求它的前序遍历、中序遍历和后序遍历。

以下是10道算法题，包括斐波那契数列、回文字符串、冒泡排序、找到数组中的最大值和最小值、二叉树的深度、字符串中出现次数最多的字符、快速排序、找到数组中两个数的和等于目标值、堆排序以及二叉树的前序遍历、中序遍历和后序遍历。这些题目适合练习算法和编程技能，帮助提高解决问题的能力和代码实现的效率。

#### 1. 写一个函数来计算斐波那契数列的第n项。 ####

以下是使用Python和Java编写的计算斐波那契数列第n项的函数示例：  
Python示例代码：

def fibonacci(n):
        if n <= 1:
            return n
        else:
            return (fibonacci(n-1) + fibonacci(n-2))

Java示例代码：

public static int fibonacci(int n) {
        
        if (n <= 1) {
        
            return n;
        } else {
        
            return (fibonacci(n-1) + fibonacci(n-2));
        }
    }

这两个函数都使用递归的方式来计算斐波那契数列的第n项。在Python中，函数名为 `fibonacci` ，接受一个参数 `n` ，返回斐波那契数列的第n项。在Java中，函数名为 `fibonacci` ，接受一个整数参数 `n` ，返回斐波那契数列的第n项。

#### 2. 给定一个字符串，判断它是否是回文字符串。 ####

以下是使用Python和Java编写的判断字符串是否为回文字符串的函数示例：  
Python示例代码：

def is_palindrome(s):
        s = s.lower() # 将字符串转换为小写
        left, right = 0, len(s) - 1 # 定义左右指针
        while left < right:
            if s[left] != s[right]: # 如果左右指针所指字符不相同，则不是回文字符串
                return False
            left += 1
            right -= 1
        return True # 如果左右指针所指字符都相同，则是回文字符串

Java示例代码：

public static boolean isPalindrome(String s) {
        
        s = s.toLowerCase(); // 将字符串转换为小写
        int left = 0, right = s.length() - 1; // 定义左右指针
        while (left < right) {
        
            if (s.charAt(left) != s.charAt(right)) {
         // 如果左右指针所指字符不相同，则不是回文字符串
                return false;
            }
            left++;
            right--;
        }
        return true; // 如果左右指针所指字符都相同，则是回文字符串
    }

这两个函数都将字符串转换为小写，并使用左右指针的方式判断字符串是否为回文字符串。在Python中，函数名为 `is_palindrome` ，接受一个字符串参数 `s` ，返回一个布尔值表示是否为回文字符串。在Java中，函数名为 `isPalindrome` ，接受一个字符串参数 `s` ，返回一个布尔值表示是否为回文字符串。

#### 3. 实现一个冒泡排序算法。 ####

以下是使用Python和Java实现冒泡排序算法的示例代码：  
Python示例代码：

def bubble_sort(arr):
        n = len(arr)
        for i in range(n):
            for j in range(0, n-i-1):
                if arr[j] > arr[j+1]:
                    arr[j], arr[j+1] = arr[j+1], arr[j]
        return arr

Java示例代码：

public static int[] bubbleSort(int[] arr) {
        
        int n = arr.length;
        for (int i = 0; i < n; i++) {
        
            for (int j = 0; j < n-i-1; j++) {
        
                if (arr[j] > arr[j+1]) {
        
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
        return arr;
    }

这两个函数都实现了冒泡排序算法，对于给定的数组进行排序。在Python中，函数名为 `bubble_sort` ，接受一个整数数组参数 `arr` ，返回一个排序后的整数数组。在Java中，函数名为 `bubbleSort` ，接受一个整数数组参数 `arr` ，返回一个排序后的整数数组。

#### 4. 给定一个整数数组，找到其中的最大值和最小值。 ####

以下是使用Python和Java找到整数数组中最大值和最小值的示例代码：  
Python示例代码：

def find_max_min(arr):
        max_val = arr[0]
        min_val = arr[0]
        for i in range(1, len(arr)):
            if arr[i] > max_val:
                max_val = arr[i]
            elif arr[i] < min_val:
                min_val = arr[i]
        return max_val, min_val

Java示例代码：

public static int[] findMaxMin(int[] arr) {
        
        int maxVal = arr[0];
        int minVal = arr[0];
        for (int i = 1; i < arr.length; i++) {
        
            if (arr[i] > maxVal) {
        
                maxVal = arr[i];
            } else if (arr[i] < minVal) {
        
                minVal = arr[i];
            }
        }
        return new int[]{
        maxVal, minVal};
    }

这两个函数都接受一个整数数组参数，并返回数组中的最大值和最小值。在Python中，函数名为 `find_max_min` ，返回一个元组，包含最大值和最小值。在Java中，函数名为 `findMaxMin` ，返回一个包含最大值和最小值的整数数组。

#### 5. 给定一个二叉树，求它的深度。 ####

以下是使用Python和Java求二叉树深度的示例代码：  
Python示例代码：

class TreeNode:
        def __init__(self, val=0, left=None, right=None):
            self.val = val
            self.left = left
            self.right = right
     def max_depth(root):
        if not root:
            return 0
        left_depth = max_depth(root.left)
        right_depth = max_depth(root.right)
        return max(left_depth, right_depth) + 1

Java示例代码：

class TreeNode {
        
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) {
         val = x; }
    }
     public static 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中，函数名为 `max_depth` ，使用递归的方式求解二叉树的深度。在Java中，函数名为 `maxDepth` ，同样使用递归的方式求解二叉树的深度。

#### 6. 给定一个字符串，找到其中出现次数最多的字符。 ####

以下是使用Python和Java找到字符串中出现次数最多的字符的示例代码：  
Python示例代码：

def most_common_char(s):
        freq_map = {
        }
        for char in s:
            if char in freq_map:
                freq_map[char] += 1
            else:
                freq_map[char] = 1
        max_freq = 0
        max_char = ''
        for char, freq in freq_map.items():
            if freq > max_freq:
                max_freq = freq
                max_char = char
        return max_char

Java示例代码：

public static char mostCommonChar(String s) {
        
        Map<Character, Integer> freqMap = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
        
            char c = s.charAt(i);
            freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);
        }
        int maxFreq = 0;
        char maxChar = ' ';
        for (Map.Entry<Character, Integer> entry : freqMap.entrySet()) {
        
            char c = entry.getKey();
            int freq = entry.getValue();
            if (freq > maxFreq) {
        
                maxFreq = freq;
                maxChar = c;
            }
        }
        return maxChar;
    }

这两个函数都接受一个字符串参数，并返回出现次数最多的字符。在Python中，函数名为 `most_common_char` ，使用字典（dictionary）记录每个字符出现的次数，并返回出现次数最多的字符。在Java中，函数名为 `mostCommonChar` ，使用 `Map` 记录每个字符出现的次数，并返回出现次数最多的字符。

#### 7. 实现一个快速排序算法。 ####

以下是使用Python和Java实现快速排序算法的示例代码：  
Python示例代码：

def quick_sort(arr):
        if len(arr) <= 1:
            return arr
        pivot = arr[len(arr) // 2]
        left = [x for x in arr if x < pivot]
        middle = [x for x in arr if x == pivot]
        right = [x for x in arr if x > pivot]
        return quick_sort(left) + middle + quick_sort(right)

Java示例代码：

public static void quickSort(int[] arr, int left, int right) {
        
        if (left >= right) {
        
            return;
        }
        int pivot = arr[(left + right) / 2];
        int i = left, j = right;
        while (i <= j) {
        
            while (arr[i] < pivot) {
        
                i++;
            }
            while (arr[j] > pivot) {
        
                j--;
            }
            if (i <= j) {
        
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
                j--;
            }
        }
        quickSort(arr, left, j);
        quickSort(arr, i, right);
    }

这两个函数都接受一个整数数组参数，并使用快速排序算法对数组进行排序。在Python中，函数名为 `quick_sort` ，使用列表推导式和递归的方式实现快速排序。在Java中，函数名为 `quickSort` ，使用双指针的方式实现快速排序。

#### 8. 给定一个整数数组和一个目标值，找到数组中两个数的和等于目标值。 ####

以下是使用Python和Java找到数组中两个数的和等于目标值的示例代码：  
Python示例代码：

def two_sum(nums, target):
        seen = {
        }
        for i, num in enumerate(nums):
            if target - num in seen:
                return [seen[target - num], i]
            seen[num] = i
        return []

Java示例代码：

public static int[] twoSum(int[] nums, int target) {
        
        Map<Integer, Integer> seen = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
        
            int complement = target - nums[i];
            if (seen.containsKey(complement)) {
        
                return new int[] {
         seen.get(complement), i };
            }
            seen.put(nums[i], i);
        }
        return new int[0];
    }

这两个函数都接受一个整数数组和一个目标值参数，并返回数组中两个数的索引，使得这两个数的和等于目标值。在Python中，函数名为 `two_sum` ，使用字典（dictionary）记录已经遍历过的数和它们的索引，以便在后面的遍历中查找目标数的补数。在Java中，函数名为 `twoSum` ，使用 `Map` 记录已经遍历过的数和它们的索引，以便在后面的遍历中查找目标数的补数。

#### 9. 实现一个堆排序算法。 ####

以下是使用Python和Java实现堆排序算法的示例代码：  
Python示例代码：

def heap_sort(arr):
        n = len(arr)
        # Build a max heap
        for i in range(n // 2 - 1, -1, -1):
            heapify(arr, n, i)
        # Extract elements from the heap one by one
        for i in range(n - 1, 0, -1):
            arr[i], arr[0] = arr[0], arr[i]  # swap
            heapify(arr, i, 0)
     def heapify(arr, n, i):
        largest = i
        left = 2 * i + 1
        right = 2 * i + 2
        if left < n and arr[left] > arr[largest]:
            largest = left
        if right < n and arr[right] > arr[largest]:
            largest = right
        if largest != i:
            arr[i], arr[largest] = arr[largest], arr[i]  # swap
            heapify(arr, n, largest)

Java示例代码：

public static void heapSort(int[] arr) {
        
        int n = arr.length;
        // Build a max heap
        for (int i = n / 2 - 1; i >= 0; i--) {
        
            heapify(arr, n, i);
        }
        // Extract elements from the heap one by one
        for (int i = n - 1; i > 0; i--) {
        
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr, i, 0);
        }
    }
     public static void heapify(int[] arr, int n, int i) {
        
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        if (left < n && arr[left] > arr[largest]) {
        
            largest = left;
        }
        if (right < n && arr[right] > arr[largest]) {
        
            largest = right;
        }
        if (largest != i) {
        
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;
            heapify(arr, n, largest);
        }
    }

这两个函数都接受一个整数数组参数，并使用堆排序算法对数组进行排序。在Python中，函数名为 `heap_sort` ，使用递归的方式实现堆排序，其中 `heapify` 函数用于维护堆的性质。在Java中，函数名为 `heapSort` ，使用迭代的方式实现堆排序，其中 `heapify` 函数用于维护堆的性质。

#### 10. 给定一个二叉树，求它的前序遍历、中序遍历和后序遍历。 ####

以下是使用Python和Java给定二叉树，求它的前序遍历、中序遍历和后序遍历的示例代码：  
Python示例代码：

# Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, val=0, left=None, right=None):
    #         self.val = val
    #         self.left = left
    #         self.right = right
     class Solution:
        def __init__(self):
            self.preorder = []
            self.inorder = []
            self.postorder = []
         def preorderTraversal(self, root: TreeNode) -> List[int]:
            if root:
                self.preorder.append(root.val)
                self.preorderTraversal(root.left)
                self.preorderTraversal(root.right)
            return self.preorder
         def inorderTraversal(self, root: TreeNode) -> List[int]:
            if root:
                self.inorderTraversal(root.left)
                self.inorder.append(root.val)
                self.inorderTraversal(root.right)
            return self.inorder
         def postorderTraversal(self, root: TreeNode) -> List[int]:
            if root:
                self.postorderTraversal(root.left)
                self.postorderTraversal(root.right)
                self.postorder.append(root.val)
            return self.postorder

Java示例代码：

* Definition for a binary tree node.
     * public class TreeNode {
        
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) {
         val = x; }
     * }
     */
    class Solution {
        
        List<Integer> preorder = new ArrayList<>();
        List<Integer> inorder = new ArrayList<>();
        List<Integer> postorder = new ArrayList<>();
         public List<Integer> preorderTraversal(TreeNode root) {
        
            if (root != null) {
        
                preorder.add(root.val);
                preorderTraversal(root.left);
                preorderTraversal(root.right);
            }
            return preorder;
        }
         public List<Integer> inorderTraversal(TreeNode root) {
        
            if (root != null) {
        
                inorderTraversal(root.left);
                inorder.add(root.val);
                inorderTraversal(root.right);
            }
            return inorder;
        }
         public List<Integer> postorderTraversal(TreeNode root) {
        
            if (root != null) {
        
                postorderTraversal(root.left);
                postorderTraversal(root.right);
                postorder.add(root.val);
            }
            return postorder;
        }
    }

这两个函数都接受一个二叉树参数，并返回树的前序遍历、中序遍历和后序遍历结果。在Python中，使用递归的方式实现三种遍历，分别将遍历的结果存储在 `preorder` 、 `inorder` 和 `postorder` 列表中。在Java中，同样使用递归的方式实现三种遍历，分别将遍历的结果存储在 `preorder` 、 `inorder` 和 `postorder` 列表中。