/iOS-Algorithm

iOS数据结构算法

Primary LanguageC++

leetcode顺序

 题号  题目链接             答案链接              难度   完成度 
1 两数之和 twoSum easy ✅
2 两数相加 addTwoNumbers medium ✅
3 无重复字符的最长子串 lengthOfLongestSubstring medium ✅
5 最长回文子串 longestPalindrome medium ✅
6 Z字形变换 zigzag_conversion medium ✅
7 整数反转 reverse_integer easy ✅
8 字符串转换整数 (atoi) string_to_integer_atoi medium ✅
9 回文数 palindrome_number easy ✅
11 盛最多水的容器 maxArea medium ✅
12 整数转罗马数字 integer_to_roman medium ✅
13 罗马数字转整数 romanToInt easy ✅
14 最长功能前缀 longestCommonPrefix easy ✅
15 三数之和 3sum medium ✅
16 最接近的三数之和 3SumClosest medium ✅
17 电话号码的字母组合 letter_combinations_of_a_phone_number medium ✅
19 删除链表的倒数第N个节点 removeNthFromEnd medium ✅
20 有限的括号 isValid easy ✅
21 合并两个有序链表 mergeTwoLists easy ✅
22 括号生成 generateParenthesis medium ✅
24 两两交换链表中的节点 swapPairs medium ✅
26 删除排序数组中重复项 removeDuplicates easy ✅
27 移除元素 removeElement easy ✅
28 实现 strStr() strStr easy ✅
31 下一个排列 next_permutation medium ✅
33 搜索旋转排序数组 searchInRotatedSortedArray medium ✅
34 在排序数组中查找元素的第一个和最后一个位置 searchRange medium ✅
35 搜索插入位置 searchInsert easy ✅
36 有效的数独 isValidSudoku medium ✅
39 组合总和 combinationSum medium ✅
40 组合总和II combinationSumII medium ✅
46 全排列 permutations medium ✅
47 全排列II permutationsii medium ✅
50 Pow(x, n) powx medium ✅
53 最大子序和 maxSubArray easy ✅
55 跳跃游戏 jump_game medium ✅
56 合并区间 merge_intervals medium ✅
58 最后一个单词的长度 lengthOfLastWord easy ✅
60 第k个排列 permutation_sequence medium ✅
66 加一 plusOne easy ✅
67 二进制求和 addBinary easy ✅
69 x 的平方根 mySqrt easy ✅
70 爬楼梯 climbStairs easy ✅
74 搜索二维矩阵 search_a_2d_matrix medium ✅
75 颜色分类 sort_colors medium ✅
77 组合 combinations medium ✅
78 子集 subsets medium ✅
79 单词搜索 word_search medium ✅
81 搜索旋转排序数组II searchInRotatedSortedArrayII medium ✅
83 删除排序链表中的重复元素 deleteDuplicates easy ✅
88 合并两个有序数组 merge easy ✅
89 格雷编码 gray_code medium ✅
90 子集II subsets_ii medium ✅
93 复原IP地址 restore_ip_addresses medium ✅
100 相同的树 isSameTree easy ✅
134 加油站 gas_station medium ✅
153 寻找旋转排序数组中的最小值 find_minimum_in_rotated_sorted_array medium ✅
687 最长同值路径 longestUnivaluePath easy ✅

下面按照具体的分类来刷题，总结每个**的精髓。

算法**

递归 ✅

排序 ✅

二分查找 ✅

哈希算法❌

下面这四大基本算法，贪心，回溯，DP属于一类，这三个算法解决问题的模型都可以定义为“多阶段最优解问题”。

回溯算法属于万金油，基本能用DP和贪心解决的题目都能用回溯暴力解决，不过回溯算法穷举的做法使得它的复杂度非常高，是指数级别的，所以只能适用于小规模数据的问题。

DP比回溯更高效，但并不是所有问题都可以通过DP解决的。能用DP解决的问题，需要满足最优子结构，无后效性，重复子问题这三个特征。DP之所以如此高效，原因就在于它通过合并重复的状态，来达到剪枝的目的(比如矩阵从左上角移动到右下角，求最短路径这个题目，要么下一步向右走，要么下一步向下走，我们选择那条之前状态是最短路径的那条，这样我们就打到了剪枝的目的).

贪心算法能解决的问题更加局限。需要满足三个条件，最优子结构，无后效性和贪心选择性，即通过局部最优可以产生全局的最优选择。

贪心✅

回溯算法✅

分治算法🚶🚶🚶🚶

动态规划 ❌

字符串匹配

其他

数据结构

数组

链表

栈&队列

树

字符串