charlschun/ios-algorithm

iOS数据结构算法

排序

排序算法

字符串

3.longest_substring_without_repeating_characters
5.Longest Palindromic Substring
8.String to Integer (atoi)
20.Valid Parentheses
22.Generate Parentheses
28.Implement strStr()
91.Decode Ways
125.Valid Palindrome
151.Reverse Words in a String
13.Roman to Integer
387.first-unique-character-in-a-string

数组

1.two_sum
4.Median of Two Sorted Arrays
153.Find Minimum in Rotated Sorted Array
33.Search in Rotated Sorted Array
find num in yang array
169.Majority Element
215.Kth Largest Element in an Array
Find specific num count in Orderly array
15.3Sum
49.Group Anagrams
73.Set Matrix Zeroes
79.Word Search
724.Find Pivot Index
747.Largest Number At Least Twice of Others
498.Diagonal Traverse
54. Spiral Matrix
136.single-number
350.intersection-of-two-arrays-ii
217.contains-duplicate
66.plus-one
283.move-zeroes

双指针技巧

其基本**是将第一个元素和末尾进行交换，再向前移动，直到到达中间位置。使用场景比如，翻转字符串等等.

344.Reverse String
561.Array Partition I

双指针技巧二:使用快慢指针,解决给定一个数组和一个值，原地删除该值的所有实例并返回新的长度。

int removeElement(vector& nums, int val) {
    int k = 0;
    for (int i = 0; i < nums.size(); ++i) {
        if (nums[i] != val) {
            nums[k] = nums[i];
            ++k;
        }
    }
    return k;
}

在上面的例子中，我们使用两个指针，一个快指针 i 和一个慢指针 k 。i 每次移动一步，而 k 只在添加新的被需要的值时才移动一步。

27.Remove Element
485.Max Consecutive Ones
209. Minimum Size Subarray Sum
189.Rotate Array

链表

链表相关的问题:

• 双指针技巧
  • 是否存在环
  • 环的长度
  • 是否相交
  • 移除倒数第N个节点

双指针技巧
19.Remove Nth Node From End of List
21.Merge Two Sorted Lists
23.Merge k Sorted Lists
61.Rotate List
82.Remove Duplicates from Sorted List II
206.Reverse Linked List
234.Palindrome Linked List

树

• 前序遍历（首先访问根节点，然后遍历左子树，最后遍历右子树）
• 中序遍历 (先遍历左子树，然后访问根节点，然后遍历右子树。)
• 后序遍历 (先遍历左子树，然后遍历右子树，最后访问树的根节点)

先序中序后序层级遍历

运用递归来解决树的问题,通常我们可以通过自顶向下或者自底向上的递归来解决树的问题.
对于某个节点来说，如果我们可以通过某节点的答案，知道它子节点的答案的话，那么可以使用自顶向下递归，反之如此.

递归解决问题
101.symmetric_tree
112.Path_Sum
106.Construct_Binary_Tree_from_Inorder_and_Postorder Traversal
105.construct-binary-tree-from-preorder-and-inorder-traversal

算法

算法

分治

有点类似“大事化小、小事化了”的**，经典的归并排序和快速排序都用到这种**.

4.Median of Two Sorted Arrays
23.Merge k Sorted Lists
169.Majority Element

动态规划

算法-动态规划 Dynamic Programming--从菜鸟到老鸟

动态规划的核心是记住已经解决过的子问题的解，然后通过子问题推导出问题的解.比如说Fibonacci数列

int Fibonacci2(int n){
    int s[n+1];
    s[0]=1;
    s[1]=1;
    int i = 2;
    while (i<=n) {
        s[i]=s[i-1]+s[i-2];
        i++;
    }
    return s[n];
};

有点类似数学中的归纳总结法，找出状态转移方程，然后逐步求解。

切割钢筋
53.maximum-subarray
70.climbing-stairs
121.best-time-to-buy-and-sell-stock
62.unique-paths
78.subsets
198.house-robber
55.jump-game
322.coin-change
300.longest-increasing-subsequence

上面的题都有一个规律就是:题目中类似都有一个排列组合，然后求出最优解或者共有多少种排列方式。这种题目，如果能求出子问题的解并且能够通过子问题推导出问题的解，那么优先考虑DP.

贪心算法

有时候只顾局部利益，最终也会有最好的全局收益。122. Best Time to Buy and Sell Stock II 看看该如何“贪心”。

122.best-time-to-buy-and-sell-stock-ii

搜索算法(深度优先，广度优化,二分查找)

在有限的解空间中找出满足条件的解，深度和广度通常比较费时间，二分搜索每次可以将问题规模缩小一半，所以比较高效。

33.Search in Rotated Sorted Array
148.sort-list
215.Kth Largest Element in an Array
124.binary-tree-maximum-path-sum

回溯

不断地去试错，同时要注意回头是岸，走不通就换条路，最终也能找到解决问题方法或者知道问题无解，可以看看 131. Palindrome Partitioning。