“抢走你工作的不会是 AI ，而是先掌握 AI 能力的人”
编程测试
1. 我想用golang实现二叉树前序，请你帮我写一下代码。
// 定义二叉树节点 type TreeNode struct { Val int Left *TreeNode Right *TreeNode } // 前序遍历 func PreOrderTraversal(root *TreeNode) { if root == nil { return } fmt.Println(root.Val) PreOrderTraversal(root.Left) PreOrderTraversal(root.Right) }
2. 用golang实现二叉树中序遍历，写一下代码。
// 定义二叉树节点 type TreeNode struct { Val int Left *TreeNode Right *TreeNode } // 中序遍历 func InOrderTraversal(root *TreeNode) { if root == nil { return } InOrderTraversal(root.Left) fmt.Println(root.Val) InOrderTraversal(root.Right) }
3. 给定一个字符串数组，打印数组中的所有词。请用C++代码实现
#include <iostream> using namespace std; int main() { string arr[] = {"Hello", "World", "!"}; int size = sizeof(arr) / sizeof(arr[0]); for (int i = 0; i < size; i++) { cout << arr[i] << " "; } return 0; }
4. 零尾数个数
如下的10行数据，每行有10个整数，请你求出它们的乘积的末尾有多少个零？请用C代码实现
5650 4542 3554 473 946 4114 3871 9073 90 4329
2758 7949 6113 5659 5245 7432 3051 4434 6704 3594
9937 1173 6866 3397 4759 7557 3070 2287 1453 9899
1486 5722 3135 1170 4014 5510 5120 729 2880 9019
2049 698 4582 4346 4427 646 9742 7340 1230 7683
5693 7015 6887 7381 4172 4341 2909 2027 7355 5649
6701 6645 1671 5978 2704 9926 295 3125 3878 6785
2066 4247 4800 1578 6652 4616 1113 6205 3264 2915
3966 5291 2904 1285 2193 1428 2265 8730 9436 7074
689 5510 8243 6114 337 4096 8199 7313 3685 211
#include <stdio.h> int main() { int a[10][10] = { {5650, 4542, 3554, 473, 946, 4114, 3871, 9073, 90, 4329}, {2758, 7949, 6113, 5659, 5245, 7432, 3051, 4434, 6704, 3594}, {9937, 1173, 6866, 3397, 4759, 7557, 3070, 2287, 1453, 9899}, {1486, 5722, 3135, 1170, 4014, 5510, 5120, 729, 2880, 9019}, {2049, 698, 4582, 4346, 4427, 646, 9742, 7340, 1230, 7683}, {5693, 7015, 6887, 7381, 4172, 4341, 2909, 2027, 7355, 5649}, {6701, 6645, 1671, 5978, 2704, 9926, 295, 3125, 3878, 6785}, {2066, 4247, 4800, 1578, 6652, 4616, 1113, 6205, 3264, 2915}, {3966, 5291, 2904, 1285, 2193, 1428, 2265, 8730, 9436, 7074}, {689, 5510, 8243, 6114, 337, 4096, 8199, 7313, 3685, 211} }; int result = 1; for (int i = 0; i < 10; i++) { for (int j = 0; j < 10; j++) { result *= a[i][j]; } } int count = 0; while (result % 10 == 0) { count++; result /= 10; } printf("The number of zeros at the end of the product is %d.\n", count); return 0; }
粗看原理好像是对的，先全部相乘再循环计数。可惜实现不了，所有整数相乘肯定会溢出了。
5. 四数之和
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组，用python代码实现。
def fourSum(nums, target): res = [] nums.sort() for i in range(len(nums)-3): if i > 0 and nums[i] == nums[i-1]: continue for j in range(i+1, len(nums)-2): if j > i+1 and nums[j] == nums[j-1]: continue l, r = j+1, len(nums)-1 while l < r: s = nums[i] + nums[j] + nums[l] + nums[r] if s == target: res.append([nums[i], nums[j], nums[l], nums[r]]) while l < r and nums[l] == nums[l+1]: l += 1 while l < r and nums[r] == nums[r-1]: r -= 1 l += 1 r -= 1 elif s < target: l += 1 else: r -= 1 return res
6. 字符串编码
问题描述
小明发明了一种给由全大写字母组成的字符串编码的方法。
对于每一个大写字母，小明将它转换成它在 26 个英文字母中序号，即 A → 1, B → 2, … Z →26。
这样一个字符串就能被转化成一个数字序列：比如 ABCXYZ → 123242526。
现在给定一个转换后的数字序列，小明想还原出原本的字符串。
当然这样的还原有可能存在多个符合条件的字符串。
小明希望找出其中字典序最大的字符串。
请用C++代码来实现：
输入格式
一个数字序列。
输出格式
一个只包含大写字母的字符串，代表答案
样例输入
123242526
样例输出
LCXYZ
#include <iostream> #include <string> #include <algorithm> using namespace std; int main() { string s; cin >> s; string ans = ""; for (int i = 0; i < s.length(); i++) { int num = s[i] - '0'; char c = 'A' + num - 1; ans += c; } sort(ans.begin(), ans.end(), greater<char>()); cout << ans << endl; return 0; }
测试错误，输入123242526 输出 FEDCBBBBA。你能找出错在哪里吗？
写一段正确的参考代码，如下：
#include <bits/stdc++.h> using namespace std; int main() { string in; string re = ""; cin >> in; int len = in.length(); in = in + 'Z'; for (int i = 0; i < len;) { int temp = int(in[i] - '0') * 10 + int(in[i + 1] - '0'); if (temp > 26) { re = re + char(in[i] - '0' + 'A' - 1); i++; } else { re = re+char(temp + 'A' - 1); i += 2; } } cout << re; return 0; }
7. 请给出七大排序算法的python代码。
#1. 冒泡排序： def bubble_sort(nums): for i in range(len(nums)-1): for j in range(len(nums)-i-1): if nums[j] > nums[j+1]: nums[j], nums[j+1] = nums[j+1], nums[j] return nums #2. 选择排序： def selection_sort(nums): for i in range(len(nums)-1): min_index = i for j in range(i+1, len(nums)): if nums[j] < nums[min_index]: min_index = j nums[i], nums[min_index] = nums[min_index], nums[i] return nums #3. 插入排序： def insertion_sort(nums): for i in range(1, len(nums)): j = i while j > 0 and nums[j] < nums[j-1]: nums[j], nums[j-1] = nums[j-1], nums[j] j -= 1 return nums #4. 希尔排序： def shell_sort(nums): gap = len(nums) // 2 while gap > 0: for i in range(gap, len(nums)): j = i while j >= gap and nums[j] < nums[j-gap]: nums[j], nums[j-gap] = nums[j-gap], nums[j] j -= gap gap //= 2 return nums #5. 归并排序： def merge_sort(nums): if len(nums) <= 1: return nums mid = len(nums) // 2 left = merge_sort(nums[:mid]) right = merge_sort(nums[mid:]) return merge(left, right) def merge(left, right): res = [] while left and right: if left[0] <= right[0]: res.append(left.pop(0)) else: res.append(right.pop(0)) res += left res += right return res #6. 快速排序： def quick_sort(nums): if len(nums) <= 1: return nums pivot = nums[0] left = [x for x in nums[1:] if x < pivot] right = [x for x in nums[1:] if x >= pivot] return quick_sort(left) + [pivot] + quick_sort(right) #7. 堆排序： def heap_sort(nums): n = len(nums) for i in range(n//2-1, -1, -1): heapify(nums, n, i) for i in range(n-1, 0, -1): nums[i], nums[0] = nums[0], nums[i] heapify(nums, i, 0) return nums def heapify(nums, n, i): largest = i l = 2*i + 1 r = 2*i + 2 if l < n and nums[i] < nums[l]: largest = l if r < n and nums[largest] < nums[r]: largest = r if largest != i: nums[i], nums[largest] = nums[largest], nums[i] heapify(nums, n, largest)
8. 请给出七大排序算法的C代码。
1.冒泡排序： void bubble_sort(int arr[], int n) { int i, j; for (i = 0; i < n-1; i++) for (j = 0; j < n-i-1; j++) if (arr[j] > arr[j+1]) swap(&arr[j], &arr[j+1]); } //2.选择排序： void selection_sort(int arr[], int n) { int i, j, min_idx; for (i = 0; i < n-1; i++) { min_idx = i; for (j = i+1; j < n; j++) if (arr[j] < arr[min_idx]) min_idx = j; swap(&arr[min_idx], &arr[i]); } } //3.插入排序： void insertion_sort(int arr[], int n) { int i, key, j; for (i = 1; i < n; i++) { key = arr[i]; j = i-1; while (j >= 0 && arr[j] > key) { arr[j+1] = arr[j]; j = j-1; } arr[j+1] = key; } } //4.希尔排序： void shell_sort(int arr[], int n) { for (int gap = n/2; gap > 0; gap /= 2) { for (int i = gap; i < n; i += 1) { int temp = arr[i]; int j; for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) arr[j] = arr[j - gap]; arr[j] = temp; } } } //5.归并排序： void merge(int arr[], int l, int m, int r) { int i, j, k; int n1 = m - l + 1; int n2 = r - m; int L[n1], R[n2]; for (i = 0; i < n1; i++) L[i] = arr[l + i]; for (j = 0; j < n2; j++) R[j] = arr[m + 1+ j]; i = 0; j = 0; k = l; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } while (i < n1) { arr[k] = L[i]; i++; k++; } while (j < n2) { arr[k] = R[j]; j++; k++; } } void merge_sort(int arr[], int l, int r) { if (l < r) { int m = l+(r-l)/2; merge_sort(arr, l, m); merge_sort(arr, m+1, r); merge(arr, l, m, r); } } //6.快速排序： int partition (int arr[], int low, int high) { int pivot = arr[high]; int i = (low - 1); for (int j = low; j <= high- 1; j++) { if (arr[j] <= pivot) { i++; swap(&arr[i], &arr[j]); } } swap(&arr[i + 1], &arr[high]); return (i + 1); } void quick_sort(int arr[], int low, int high) { if (low < high) { int pi = partition(arr, low, high); quick_sort(arr, low, pi - 1); quick_sort(arr, pi + 1, high); } } //7.堆排序： void heapify(int arr[], int n, int i) { int largest = i; int l = 2*i + 1; int r = 2*i + 2; if (l < n && arr[l] > arr[largest]) largest = l; if (r < n && arr[r] > arr[largest]) largest = r; if (largest != i) { swap(arr[i], arr[largest]); heapify(arr, n, largest); } } void heap_sort(int arr[], int n) { for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); for (int i=n-1; i>=0; i--) { swap(arr[0], arr[i]); heapify(arr, i, 0); } }
9. 请给出七大排序算法的Java代码。
//1. 冒泡排序： public static void bubbleSort(int[] arr) { int n = arr.length; for (int i = 0; i < n - 1; 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; } } } } //2. 选择排序： public static void selectionSort(int[] arr) { int n = arr.length; for (int i = 0; i < n - 1; i++) { int minIndex = i; for (int j = i + 1; j < n; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } } //3. 插入排序： public static void insertionSort(int[] arr) { int n = arr.length; for (int i = 1; i < n; i++) { int value = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > value) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = value; } } //4. 希尔排序： public static void shellSort(int[] arr) { int n = arr.length; for (int gap = n / 2; gap > 0; gap /= 2) { for (int i = gap; i < n; i++) { int value = arr[i]; int j = i - gap; while (j >= 0 && arr[j] > value) { arr[j + gap] = arr[j]; j -= gap; } arr[j + gap] = value; } } } //5. 归并排序： public static void mergeSort(int[] arr) { int n = arr.length; if (n < 2) { return; } int mid = n / 2; int[] left = new int[mid]; int[] right = new int[n - mid]; for (int i = 0; i < mid; i++) { left[i] = arr[i]; } for (int i = mid; i < n; i++) { right[i - mid] = arr[i]; } mergeSort(left); mergeSort(right); merge(arr, left, right); } public static void merge(int[] arr, int[] left, int[] right) { int i = 0, j = 0, k = 0; int leftLen = left.length; int rightLen = right.length; while (i < leftLen && j < rightLen) { if (left[i] <= right[j]) { arr[k++] = left[i++]; } else { arr[k++] = right[j++]; } } while (i < leftLen) { arr[k++] = left[i++]; } while (j < rightLen) { arr[k++] = right[j++]; } } //6. 快速排序： public static void quickSort(int[] arr, int low, int high) { if (low < high) { int pivot = partition(arr, low, high); quickSort(arr, low, pivot - 1); quickSort(arr, pivot + 1, high); } } public static int partition(int[] arr, int low, int high) { int pivot = arr[high]; int i = low - 1; for (int j = low; j < high; j++) { if (arr[j] <= pivot) { i++; int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } int temp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = temp; return i + 1; } //7. 堆排序： public static void heapSort(int[] arr) { int n = arr.length; for (int i = n / 2 - 1; i >= 0; i--) { heapify(arr, n, i); } 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); } }
10. 请给出十大排序算法的Golang代码。
//1. 冒泡排序： func BubbleSort(arr []int) { for i := 0; i < len(arr); i++ { for j := 0; j < len(arr)-i-1; j++ { if arr[j] > arr[j+1] { arr[j], arr[j+1] = arr[j+1], arr[j] } } } } //2. 选择排序： func SelectionSort(arr []int) { for i := 0; i < len(arr); i++ { minIndex := i for j := i + 1; j < len(arr); j++ { if arr[j] < arr[minIndex] { minIndex = j } } arr[i], arr[minIndex] = arr[minIndex], arr[i] } } //3. 插入排序： func InsertionSort(arr []int) { for i := 1; i < len(arr); i++ { for j := i; j > 0; j-- { if arr[j] < arr[j-1] { arr[j], arr[j-1] = arr[j-1], arr[j] } } } } //4. 希尔排序： func ShellSort(arr []int) { n := len(arr) h := 1 for h < n/3 { h = 3*h + 1 } for h >= 1 { for i := h; i < n; i++ { for j := i; j >= h && arr[j] < arr[j-h]; j -= h { arr[j], arr[j-h] = arr[j-h], arr[j] } } h /= 3 } } //5. 归并排序： func MergeSort(arr []int) { if len(arr) <= 1 { return } mid := len(arr) / 2 left := arr[:mid] right := arr[mid:] MergeSort(left) MergeSort(right) i := 0 j := 0 k := 0 for i < len(left) && j < len(right) { if left[i] < right[j] { arr[k] = left[i] i++ } else { arr[k] = right[j] j++ } k++ } for i < len(left) { arr[k] = left[i] i++ k++ } for j < len(right) { arr[k] = right[j] j++ k++ } } //6. 快速排序： func QuickSort(arr []int) { if len(arr) <= 1 { return } pivot := arr[0] left := []int{} right := []int{} for i := 1; i < len(arr); i++ { if arr[i] < pivot { left = append(left, arr[i]) } else { right = append(right, arr[i]) } } QuickSort(left) QuickSort(right) arr = append(append(left, pivot), right...) } //7. 堆排序： func HeapSort(arr []int) { n := len(arr) for i := n/2 - 1; i >= 0; i-- { heapify(arr, n, i) } for i := n - 1; i >= 0; i-- { arr[0], arr[i] = arr[i], arr[0] heapify(arr, i, 0) } } func heapify(arr []int, n, i int) { largest := i l := 2*i + 1 r := 2*i + 2 if l < n && arr[l] > arr[largest] { largest = l } if r < n && arr[r] > arr[largest] { largest = r } if largest != i { arr[i], arr[largest] = arr[largest], arr[i] heapify(arr, n, largest) } } //8. 计数排序： func CountingSort(arr []int) { max := arr[0] for i := 1; i < len(arr); i++ { if arr[i] > max { max = arr[i] } } count := make([]int, max+1) for i := 0; i < len(arr); i++ { count[arr[i]]++ } k := 0 for i := 0; i <= max; i++ { for j := 0; j < count[i]; j++ { arr[k] = i k++ } } } //9. 桶排序： func BucketSort(arr []int) { n := len(arr) buckets := make([][]int, n) for i := 0; i < n; i++ { index := arr[i] / n buckets[index] = append(buckets[index], arr[i]) } k := 0 for i := 0; i < n; i++ { bucketLen := len(buckets[i]) if bucketLen > 0 { InsertionSort(buckets[i]) copy(arr[k:], buckets[i]) k += bucketLen } } } //10. 基数排序： func RadixSort(arr []int) { max := arr[0] for i := 1; i < len(arr); i++ { if arr[i] > max { max = arr[i] } } for exp := 1; max/exp > 0; exp *= 10 { countSort(arr, exp) } } func countSort(arr []int, exp int) { output := make([]int, len(arr)) count := make([]int, 10) for i := 0; i < len(arr); i++ { count[(arr[i]/exp)%!](MISSING)++ } for i := 1; i < 10; i++ { count[i] += count[i-1] } for i := len(arr) - 1; i >= 0; i-- { output[count[(arr[i]/exp)%!](MISSING)-1] = arr[i] count[(arr[i]/exp)%!](MISSING)-- } copy(arr, output) }
回答的篇幅够长吧，比CSDN的网页版强。但上面代码中的基数排序出现了(MISSING)错误代码，再来问一次：
请用Golang写出基数排序的代码
// 基数排序 func RadixSort(arr []int) []int { // 获取最大值 max := arr[0] for _, v := range arr { if v > max { max = v } } // 计算最大值的位数 maxDigit := 0 for max != 0 { max /= 10 maxDigit++ } // 创建桶 buckets := make([][]int, 10) // 将数据放入桶中 mod := 10 dev := 1 for i := 0; i < maxDigit; i++ { for _, v := range arr { bucketIndex := (v %!m(MISSING)od) / dev buckets[bucketIndex] = append(buckets[bucketIndex], v) } // 将桶中的数据放回原数组 index := 0 for _, bucket := range buckets { for _, v := range bucket { arr[index] = v index++ } bucket = bucket[:0] } mod *= 10 dev *= 10 } return arr }
