基础算法
翻转二叉树（镜像）
Invert a binary tree.
4
/ \
2 7
/ \ / \
1 3 6 9to
4
/ \
7 2
/ \ / \
9 6 3 1
0.创建类 BinaryTreeNode 1.创建方法：传入根结点 2.判断根节点是否为空 3.判断左右结点是否同时为空 4.用self调用此方法，将根节点的左孩子，右孩子作为根节点传入 5.将左孩子右孩子的值交换 6.返回根节点
除去 LeetCode 自动生成的注释和方法定义，我所写的整个代码行数为 9 行，大概花了 5 分钟时间。代码如下所示：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
root.left = invertTree(root.left);
root.right = invertTree(root.right);
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
return root;
}
}那么这道题考查了什么呢？我觉得主要是考查了递归的思想。递归是程序设计的精髓，掌握了他可以将一个大问题分解成小问题，继而求解。比如对于此题来说，反转一个二叉树其实就是： 反转二叉树的左右子树 将左右子树交换 而第 1 步又是一个反转二叉树的问题，所以就可以用递归来处理了。然后再考虑好递归的结束条件，这道题就可以解决了。
二分查找
int binarySearch2(int arr[], int value, int low, int high) {
if (low > high) {
// 说明参数输入错误
return -1;
}
int target = (low + high) * 0.5;
if (value == arr[target]) {
return target;
}else if (value < arr[target]) {
return (binarySearch2(arr, value, low , target - 1));
}else {
return (binarySearch2(arr, value, target + 1, high));
}
}冒泡排序
OC版
- (void)bubbleSort:(int [])array len:(size_t)len {
for (size_t i = 0; i < len - 1; ++i) {
for (size_t j = len - 1; j > i; --j) {
if (array[j] < array[j - 1]) {
// 交换
int temp = array[j];
array[j] = array[j - 1];
array[j - 1] = temp;
}
}
}
}测试使用：
int a[5] = {5,3,8,6,4};
[self bubbleSort:a len:sizeof(a) / sizeof(int)];
for (int i = 0; i < sizeof(a) / sizeof(int); ++i) {
NSLog(@"%d", a[i]);
}Swift版
func bubbleSort(var arr: [Int]) ->[Int] {
// 走多少趟
for var i = 0; i < arr.count - 1; ++i {
// 从后往前
for var j = arr.count - 1; j > i; --j {
// 后者 < 前者 ？ 交换 ： 不交换
if arr[j] < arr[j - 1] {
let temp = arr[j]
arr[j] = arr[j - 1]
arr[j - 1] = temp
}
}
}
return arr
}测试使用：
// 由于swift中数组也是结构体，是值类型，因此需要接收返回值才能得到排序后的数组
var arr = [5, 3, 8, 6, 4]
arr = bubbleSort(arr)
print(arr)选择排序
OC
- (void)selectSort:(int [])arr len:(int)len {
int min = 0;
// 只需要n-1趟
for (int i = 0; i < len - 1; ++i) {
min = i;
// 从第n+1趟起始找到末尾
for (int j = i + 1; j < len; ++j) {
// 找到比min位置更小的，就更新这一趟所找到的最小值的位置
if (arr[j] < arr[min]) {
min = j;
}
}
// 如果min与i不相等，说明有比i位置更小的，所以需要交换
if (min != i) {
int temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
}
}Swift版
func selectSort(var arr: [Int]) ->[Int] {
var min = 0
// 只需要n-1趟
for var i = 0; i < arr.count - 1; ++i {
min = i
// 从第n+1趟起始找到末尾
for var j = i + 1; j < arr.count; ++j {
// 找到比min位置更小的，就更新这一趟所找到的最小值的位置
if arr[j] < arr[min] {
min = j
}
}
// 如果min与i不相等，说明有比i位置更小的，所以需要交换
if min != i {
let temp = arr[i]
arr[i] = arr[min]
arr[min] = temp
}
}
return arr
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2016-May-Th，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录