常见简单算法

快速排序

快速排序算法其实很简单，采用分治策略。步骤如下:

1. 选取一个基准元素（pivot）
2. 比pivot小的放到pivot左边，比pivot大的放到pivot右边
3. 对pivot左边的序列和右边的序列分别递归的执行步骤1和步骤2

/*
 * l：需要排序的左边界
 * r：需要排序的右边界
 * a：需要排序的数组 
 */
// C
void quickSort(int *a, int l, int r)  {
    if (l < r)  {
        int i,j,x; 
        i = l;
        j = r;
        x = a[i];
        while (i < j) { 
             while(i < j && a[j] > x) {
                j--; // 从右向左找第一个小于x的数
             } 
             if(i < j)
             a[i++] = a[j]; //这里是i++所以是先赋值后自加
             while(i < j && a[i] < x) {
                i++; // 从左向右找第一个大于x的数
             }
             if(i < j)
             a[j--] = a[i];
         } 
    a[i] = x;
    quickSort(a, l, i-1); /* 递归调用 */
    quickSort(a, i+1, r); /* 递归调用 */
   }
}

// OC
- (NSMutableArray *)quickSortFromArray:(NSMutableArray *)arr forleft:(NSInteger)left right:(NSInteger)right {
    if (left < right) {
        NSInteger i = left;
        NSInteger j = right - 1;
        NSInteger x = [arr[left] integerValue];
        while (i < j) {
            while (i < j && [arr[j] integerValue] >= x) { // 从右向左找第一个小于x的数
                j--;
            }
            arr[i] = arr[j];
            while (i < j && [arr[i] integerValue] < x) { // 从左向右找第一个大于等于x的数
                i++;
            }
            arr[j] = arr[i];
        }
        arr[i] = @(x);
        
        [self quickSortFromArray:arr forleft:left right:i];
        [self quickSortFromArray:arr forleft:i + 1 right:right];
    }
    return arr;
}

冒泡排序

- (NSMutableArray *)bublleSort:(NSMutableArray *)arr {
    if (arr.count < 2) {
        return arr;
    }
    for (int i = 0; i < arr.count; i++) {
        for (int j = 0; j < arr.count - i - 1; j++) {
            if ([arr[j] intValue] > [arr[j + 1] intValue]) {
                [arr exchangeObjectAtIndex:j withObjectAtIndex:j + 1];
            }
        }
    }
    return arr;
}

折半查找

- (NSInteger)findFromArray:(NSArray *)arr forKey:(NSInteger)key {
    if (arr.count < 2) {
        return -1;
    }
    NSInteger min = 0;
    NSInteger max = arr.count - 1;
    while (min <= max) {
        NSInteger mid = (min + max) / 2;
        if ([arr[mid] integerValue] == key) {
            return mid;
        } else if ([arr[mid] integerValue] < key) {
            min = mid + 1;
        } else {
            max = mid - 1;
        }
    }
    return -1;
}

字符串翻转

- (NSMutableString *)reverse:(NSMutableString *)str {
    if (str.length == 0) {
        return nil;
    } else if (str.length == 1) {
        return str;
    } else {
        NSMutableString * str1 = [NSMutableString string];
        for (int i = 0; i < str.length; i++) {
            NSMutableString * lastC = [str substringWithRange:NSMakeRange(str.length - 1 - i, 1)].mutableCopy;
            [str1 appendString:lastC];
        }
        return str1;
    }
}

二叉树遍历

// 前序遍历
typedef struct TreeNode
{
    int data;
    TreeNode * left;
    TreeNode * right;
    TreeNode * parent;
}TreeNode;
 
void pre_order(TreeNode * Node)
{
    if(Node != NULL)
    {
        printf("%d ", Node->data);
        pre_order(Node->left);
        pre_order(Node->right);
    }
}

// 中序遍历
typedef struct TreeNode
{
    int data;
    TreeNode * left;
    TreeNode * right;
    TreeNode * parent;
}TreeNode;
 
void pre_order(TreeNode * Node)
{
    if(Node != NULL)
    {
        pre_order(Node->left);
        printf("%d ", Node->data);
        pre_order(Node->right);
    }
}

// 后序遍历
typedef struct TreeNode
{
    int data;
    TreeNode * left;
    TreeNode * right;
    TreeNode * parent;
}TreeNode;
 
void pre_order(TreeNode * Node)
{
    if(Node != NULL)
    {
        pre_order(Node->left);
        pre_order(Node->right);
        printf("%d ", Node->data);
    }
}

判断两棵二叉树是否相同

// 利用先序遍历来每个点进行判断
struct TreeNode {
    int value;
    TreeNode *leftTreeNode;
    TreeNode *rightTreeNode;
};

bool isSameTree(TreeNode *firstTreeNode, TreeNode *secondTreeNode) {
    if (firstTreeNode == NULL && secondTreeNode == NULL) { // 两个点都为空
        return true;
    } else if (firstTreeNode == NULL || secondTreeNode == NULL) { // 其中一个点为空
        return false;
    } else { // 两个点都不为空
        if (firstTreeNode->value == secondTreeNode->value) {
            return isSameTree(firstTreeNode->leftTreeNode, secondTreeNode->leftTreeNode) && isSameTree(firstTreeNode->rightTreeNode, secondTreeNode->rightTreeNode);
        } else {
            return false;
        }
    }
}

按层遍历二叉树

    /**
     * 二叉树结构
     */
    public class Node {
        public int value;
        public Node left;
        public Node right;
        public Node(int value) {
            this.value = value;
        }
    }

    public void levelTraversalBT(Node head) {
        if (head == null) {
            return;
        }
        // 用队列实现
        Queue<Node> queue = new LinkedList<>();
        queue.add(head);
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            System.out.println(node.value);
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
    }

返回二叉树的最大深度

int maxDepth(TreeNode* root) {
    TreeNode *tempTreeNode = root;
    if (tempTreeNode == NULL) {
        return 0;
    }
    int left = maxDepth(tempTreeNode->left);
    int right = maxDepth(tempTreeNode->right);
    return (left > right ? left : right) + 1;
}

返回二叉树的最小深度

int minDepth(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    if (root->left == NULL && root->right == NULL) {
        return 1;
    }
    if (root->left == NULL) {
        return minDepth(root->right) + 1;
    }
    if (root->right == NULL) {
        return minDepth(root->left) + 1;
    }
    return min(minDepth(root->left), minDepth(root->right)) + 1;
}

平衡树

平衡树的定义就是对于每一个节点，他的两棵子树的深度之差不能大于1

1. 递归判断每个节点
2. 具体判断是每个节点的两个子树的深度比较

bool isBalanced(TreeNode* root) {
    TreeNode *tempTreeNode = root;
    if (tempTreeNode == NULL) {
        return true;
    }
    if (abs(getMaxDeepth(tempTreeNode->left) - getMaxDeepth(tempTreeNode->right)) > 1) {
        return false;
    }
    return isBalanced(tempTreeNode->left) && isBalanced(tempTreeNode->right);
}
    
int getMaxDeepth(TreeNode *treeNode) {
    if (treeNode == NULL) {
       return 0;
    }
    int left = getMaxDeepth(treeNode->left);
    int right = getMaxDeepth(treeNode->right);
    return (left > right ? left : right) + 1;
}

反转二叉树

对于二叉树中的每个节点，将左右子节点互换

TreeNode* invertTree(TreeNode* root) {
    if(root == NULL) {
        return NULL;
    }
    if(root->left == NULL && root->right == NULL) {
        return root;
    }
    TreeNode *left = invertTree(root->right);
    TreeNode *right = invertTree(root->left);
    root->left = left;
    root->right = right;
    return root;
}

最小公共祖先

给出一个二叉搜索树，求出给定了两个节点的最小公共祖先

1. 对于一棵二叉搜索树来说，两个节点的公共祖先肯定是大于等于其中一个节点，小于等于另外一个节点的
2. 根据二叉搜索树的特性，在递归的过程中，如果当前节点值大于两个给定节点的话，那么下一步递归将要递归左节点，如果当前节点值小于两个给定节点的话，那么下一步递归将要递归右节点

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root->val > p->val && root->val > q->val) {
        return lowestCommonAncestor(root->left, p, q);
    } else if (root->val < p->val && root->val < q->val) {
        return lowestCommonAncestor(root->right, p, q);
    } else {
        return root;
    }
}

单链表反转

//1、循环反转
public ListNode reverseList(ListNode head) {
  ListNode prev = null;
  ListNode curr = head;
  while (curr != null) {
    ListNode nextTemp = curr.next;
    curr.next = prev;
    prev = curr;
    curr = nextTemp;
  }
  return prev;
}


//2、递归反转
public ListNode reverseList(ListNode head) {
  if (head == null || head.next = null) {
    return head; 
  }
  ListNode nextTemp = head.next;
  reverseList(nextTemp);
  nextTemp.next = head;
  head.next = null;
}

单链表删除节点

public class ListNode {
  int val;
  ListNode next;
  ListNode(int x) { val = x; }
}

public static void deleteNode(ListNode node) {
  if (node == null || node.next == null) {
    return;
  }
  node.val = node.next.val;
  node.next = node.next.next;
  return;
}

移除链表中的指定元素

初步判断可以发现有两种情况的删除，一种是第一个节点的删除，一种是中间节点的删除，为了保持统一，让算法保持简洁的设计，所以手动添加一个新的节点辅助作为第一个节点

ListNode* removeElements(ListNode* head, int val) {
    ListNode *newNode = new ListNode(-1);
    newNode->next = head;
    ListNode *currentNode = head;
    ListNode *previousNode = newNode;
    while (currentNode != NULL) {
        if (currentNode->val == val) {
            currentNode = currentNode->next;
            previousNode->next = currentNode;
        } else {
            previousNode = currentNode;
            currentNode = currentNode->next;
        }
    }
    return newNode->next;
}

单链表插入节点

//1、插入头节点
public class ListNode {
  int val;
  ListNode next;
  ListNode(int x) { val = x; }
}

public static void insertNode(ListNode node) {
  node.next = head.next;
  head.next = node;
}

//2、插入尾节点
public static void insertNode(ListNode node) {
  ListNode curr = head;
  while (curr.next != null) {
    curr = curr.next;
  }
  curr.next = node;
}

//3、插入任意节点
public static void insertNode(ListNode node, int pos) {
  if (pos < 0 || pos >= getLength() + 1) {
    return false;
  }
  ListNode curr = head;
  for (int i = 0; i <= pos - 1; I++) {
    curr = curr.next;
  }
  node.next = curr.next;
  curr.next = node;
  return true;
}

循环链表

给出一个链表，判断他是否是一个循环链表（不开辟多余的内存空间进行解决，意思是在利用链表本身的特性进行解决问题）
我们可以开辟两个指针节点，一个快的节点，每次跳跃两步，一个慢的节点，每次跳跃一步，然后进行一个while循环，如果两个指针节点相同出现相同的情况下，那么说明是存在环的

bool hasCycle(ListNode *head) {
    if (head == NULL || head->next == NULL) {
        return false;
    }
    ListNode *fastNode = head;
    ListNode *slowNode = head;
    while (fastNode->next != NULL && fastNode->next->next != NULL) { // 由于fastNode比slowNode增长快，所以只需要判断fastNode，同时对于fastNode需要判断后两位，所以第一位的判断也是必须的，不然会出现Runtime Error
        fastNode = fastNode->next->next; // 每次往后移动两步
        slowNode = slowNode->next; // 每次往后移动一步
        if (fastNode == slowNode) {
            return true;
        }
    }
    return false;
}