Skip to content

jincc/iOS-Algorithm

BranchesTags

Repository files navigation

leetcode顺序

 题号  题目链接             答案链接              难度   完成度 
1 两数之和 twoSum easy ✅
2 两数相加 addTwoNumbers medium ✅
3 无重复字符的最长子串 lengthOfLongestSubstring medium ✅
5 最长回文子串 longestPalindrome medium ✅
7 整数反转 reverse_integer easy ✅
9 回文数 palindrome_number easy ✅
13 罗马数字转整数 romanToInt easy ✅
14 最长功能前缀 longestCommonPrefix easy ✅
20 有限的括号 isValid easy ✅
21 合并两个有序链表 mergeTwoLists easy ✅
26 删除排序数组中重复项 removeDuplicates easy ✅
27 移除元素 removeElement easy ✅
28 实现 strStr() strStr easy ✅
35 搜索插入位置 searchInsert easy ✅
53 最大子序和 maxSubArray easy ✅
58 最后一个单词的长度 lengthOfLastWord easy ✅
66 加一 plusOne easy ✅
67 二进制求和 addBinary easy ✅
69 x 的平方根 mySqrt easy ✅
70 爬楼梯 climbStairs easy ✅
83 删除排序链表中的重复元素 deleteDuplicates easy ✅
88 合并两个有序数组 merge easy ✅
100 相同的树 isSameTree easy ✅

数组

数组有两个关键词：123

  • 线性表结构， 就是说元素之间只有前后关系
  • 连续的内存空间，存储的是具有相同类型的数据

第二个特征决定了数组“随机访问”的能力，因为我们完全可以通过地址计算出下标对应的位置。比如:

a[i]_add = base_add + i * type_size

有利就有弊，也正是由于内存连续，所以数组的插入和删除是非常低效的，因为为了保持内存的连续，就意味着每次插入/删除都要伴随着大量的移动操作，平均负责度为o(n).

容器类在数组的基础上，封装了插入删除等操作，同时支持了动态扩容. 需要注意的是，如果实现知道数组的大小，最好提前指定容器大小，这样可以省掉多次的内存申请和数据搬移。

大多情况下的解题思路:

  • 双指针
  • DP
  • 二分查找

leetcode

 题号  题目链接             答案链接              难度   完成度 
1 两数之和 twoSum easy ✅
26 删除排序数组中重复项 removeDuplicates easy ✅
27 移除元素 removeElement easy ✅
35 搜索插入位置 searchInsert easy ✅
53 最大子序和 maxSubArray easy ✅
66 加一 plusOne easy ✅
88 合并两个有序数组 merge easy ✅
118 杨辉三角 pascals_triangle easy ✅
119 杨辉三角2 pascals_triangle_ii easy ✅
121 买卖股票的最佳时机 best_time_to_buy_and_sell_stock easy ✅
122 买卖股票的最佳时机ii best_time_to_buy_and_sell_stock_ii easy ✅
167 两数之和 II - 输入有序数组 twoSum_ii easy ✅
169 求众数 majorityElement easy ✅
189 旋转数组 rotate easy ✅
11 盛最多水的容器 maxArea ✨✨ ✅
283 移动零 moveZeroes ✨ ✅

剑指Offer

 题号  题目链接             答案链接              难度   完成度 
-- 剑指Offer（一）：二维数组中的查找 Find ✨ ✅
-- 剑指Offer（六）：旋转数组的最小数字 minNumberInRotateArray ✨ ✅
-- 剑指Offer（十三）：调整数组顺序使奇数位于偶数前面 reOrderArray ✨ ✅
-- 剑指Offer（二十八）：数组中出现次数超过一半的数字 MoreThanHalfNum_Solution ✨ ✅
-- 剑指Offer（三十）：连续子数组的最大和 -- ✨ ❌
-- 剑指Offer（三十二）：把数组排成最小的数 PrintMinNumber ✨ ✅
-- 剑指Offer（三十七）：数字在排序数组中出现的次数 GetNumberOfK ✨ ✅
-- 剑指Offer（四十）：数组中只出现一次的数字 FindNumsAppearOnce ✨ ✅

链表

leetcode

 题号  题目链接             答案链接              难度   完成度 
21 合并两个有序链表 mergeTwoLists easy ✅
83 删除排序链表中的重复元素 deleteDuplicates easy ✅
141 环形链表 hasCycle easy ✅
24 两两交换链表中的节点 swapPairs ✨✨ ✅
142 环形链表 II detectCycle ✨✨ ✅
206 反转链表 reverseList ✨ ✅
234 回文链表 isPalindrome ✨ ✅
876 链表的中间结点 middleNode ✨ ✅
19 删除链表的倒数第N个节点 removeNthFromEnd ✨✨ [note:注意哨兵的使用] ✅
2 两数相加 addTwoNumbers medium ✅

剑指Offer

 题号  题目链接             答案链接              难度   完成度 
-- 剑指Offer（三）：从尾到头打印链表 printListFromTailToHead ✨ ✅
-- 剑指Offer（十四）：链表中倒数第k个结点 FindKthToTail ✨ ✅
-- 剑指Offer（十五）：反转链表 ReverseList ✨ ✅
-- 剑指Offer（二十五）：复杂链表的复制 Clone ✨ ✅
-- 剑指Offer（三十六）：两个链表的第一个公共结点 FindFirstCommonNode ✨ ✅
-- 剑指Offer（五十五）：链表中环的入口结点 detectCycle ✨ ✅
-- 剑指Offer（五十六）：删除链表中重复的结点 deleteDuplication ✨ ✅

栈&队列

leetcode

 题号  题目链接             答案链接              难度   完成度 
20 有限的括号 isValid easy ✅
155 最小栈 MinStack easy ✅
32 最长有效括号 longestValidParentheses ✨✨✨ ✅
150 逆波兰表达式求值 evalRPN ✨✨ ❌
641 设计循环双端队列 MyCircularDeque ✨✨ ❌
239 滑动窗口最大值 maxSlidingWindow ✨✨✨ ❌

剑指Offer

 题号  题目链接             答案链接              难度   完成度 
-- 剑指Offer（五）：用两个栈实现队列 queueByStack ✨ ✅

递归

leetcode

 题号  题目链接             答案链接              难度   完成度 
22 括号生成 -- ✨✨ ❌

剑指Offer

 题号  题目链接             答案链接              难度   完成度 
-- 剑指Offer（七）：裴波那契数列 Fibonacci ✨ ✅
-- 剑指Offer（八）：跳台阶 jumpFloor ✨ ✅
-- 剑指Offer（九）：变态跳台阶 jumpFloorII ✨ ✅
-- 剑指Offer（九）：变态跳台阶 jumpFloorII ✨ ✅
-- 剑指Offer（十）：矩形覆盖 rectCover ✨ ✅

二分查找

leetcode

 题号  题目链接             答案链接              难度   完成度 
33 搜索旋转排序数组 searchInRotatedSortedArray ✨✨ ✅
69 x 的平方根 mySqrt ✨ ✅
367 有效的完全平方数 isPerfectSquare ✨ ✅

树

二叉树

  • 实现一个二叉查找树，并且支持插入，删除，查找
  • 实现二叉查找树中某个节点的后继，前驱节点
  • 实现二叉树前，中，后序，以及按层遍历

堆

  • 实现一个小顶堆，大顶堆，优先级队列
  • 实现堆排序
  • 利用优先级队列合并K个有序数组
  • 求一组动态数据集合的最大Top K

leetcode

 题号  题目链接             答案链接              难度   完成度 
94 二叉树的中序遍历 inorderTraversal ✨✨ ✅
98 验证二叉搜索树 isValidBST ✨✨ ✅
100 相同的树 isSameTree easy ✅
104 二叉树的最大深度 maxDepth ✨ ✅
105 从前序与中序遍历序列构造二叉树 buildTree ✨✨ ✅
111 二叉树的最小深度 minDepth ✨ ✅
112 路径总和 hasPathSum ✨ ✅
144 二叉树的前序遍历 preorderTraversal ✨✨ ✅
226 翻转二叉树 invertTree ✨ ✅
230 二叉搜索树中第K小的元素 kthSmallestInTree ✨✨ ✅
236 二叉树的最近公共祖先 -- ✨✨ ❌
297 二叉树的序列化与反序列化 -- ✨✨✨ ❌
429 N叉树的层序遍历 -- ✨ ❌
589 N叉树的前序遍历 -- ✨ ❌
590 N叉树的后序遍历 -- ✨ ❌

剑指offer

 题号  题目链接             答案链接              难度   完成度 
-- 剑指Offer（十七）：树的子结构 HasSubtree ✨ ✅
-- 剑指Offer（十八）：二叉树的镜像 Mirror ✨ ✅
-- 剑指Offer（二十四）：二叉树中和为某一值的路径 FindPath ✨ ✨ [注意] ✅
-- 剑指Offer（三十九）：平衡二叉树 IsBalanced_Solution ✨ ✨[注意] ✅
-- 剑指Offer（五十七）：二叉树的下一个结点 GetNext ✨✨✨[注意] ✅
-- 剑指Offer（五十八）：对称的二叉树 isSymmetrical ✨ ✅
-- 剑指Offer（二十三）：二叉搜索树的后序遍历序列 VerifySquenceOfBST ✨ ✅
-- 剑指Offer（二十六）：二叉搜索树与双向链表 -- ✨ ❌
-- 剑指Offer（六十二）：二叉搜索树的第k个结点 -- ✨ ❌

字符串

leetcode

 题号  题目链接             答案链接              难度   完成度 
13 罗马数字转整数 romanToInt easy ✅
14 最长功能前缀 longestCommonPrefix easy ✅
28 实现 strStr() strStr easy ✅
58 最后一个单词的长度 lengthOfLastWord easy ✅
67 二进制求和 addBinary easy ✅
3 无重复字符的最长子串 lengthOfLongestSubstring medium ✅

剑指offer

 题号  题目链接             答案链接              难度   完成度 
-- 剑指Offer(二)：替换空格 replaceSpace ✨ ✅
-- 剑指Offer（二十七）：字符串的排列 Permutation ✨ ✅
-- 剑指Offer（三十四）：第一个只出现一次的字符 FirstNotRepeatingChar ✨ ✅
-- 剑指Offer（四十四）：翻转单词顺序序列 ReverseSentence ✨ ✅
-- 剑指Offer（四十九）：把字符串转换成整数 StrToInt ✨ ✅
-- 剑指Offer（五十二）：正则表达式匹配 match ✨ ❌
-- 剑指Offer（五十三）：表示数值的字符串 -- ✨ ❌

解决多阶段决策最优解模型的算法

解决问题的过程中，需要经过多个决策阶段，每个决策都会对应一个状态。我们寻找一组决策序列，经过这组决策序列，能够产生最终期望的最优值。我们把这种问题模型称为多阶段决策最优解模型. DP，回溯，贪心都可以解决这类问题.

利用动态规划解决的问题，需要满足三个特征：

  1. 最优子结构, 就是说后面的状态可以通过前面的状态推导出来
  2. 无后效性， 就是说一旦状态确定，就不会更改
  3. 重复子问题， 就是说不同的决策序列，到达某个相同的阶段时，可能会产生不同的状态。

贪心算法实际上是DP的一种特殊情况，它能解决的问题更加有限。需要满足三个条件:

  1. 最优子结构
  2. 无后效性
  3. 贪心选择性， 意思就是局部最优选择，能产生全局最优选择。

所以贪心算法能否解决算法问题的关键在于: 局部最优能不能达到全局最优？

回溯算法是”万金油“。基本上贪心和dp能解决的问题，回溯都能解决。回溯相当于穷举搜索，列举出所有的情况，然后对比得到最优解。不过回溯的复杂度一般都是指数级的，只能用来解决小规模数据的问题。

动态规划

经典题型

 题型  答案链接 完成度
0-1背包问题及变种 knapsack ✅
双11打折优惠问题 double11advance ✅
硬币找零问题 coinChange2 ✅
莱文斯坦最短编辑距离 -- ❌
两个字符串的最长公共子序列 -- ❌
数据序列的最长递增子序列 -- ❌

leetcode

 题号  题目链接             答案链接              难度   完成度 
64 最小路径和 minPathSum ✨✨ ❌
10 正则表达式匹配 -- ✨✨✨ ❌
121 买卖股票的最佳时机 -- ✨ ❌
152 乘积最大子序列 -- ✨✨ ❌
120 三角形最小路径和 -- ✨✨ ❌
70 爬楼梯 climbStairs easy ✅

贪心算法

leetcode

 题号  题目链接             答案链接              难度   完成度 
455 分发饼干 -- ✨ ❌
860 柠檬水找零 -- ✨ ❌
874 模拟行走机器人 -- ✨ ❌

回溯算法

数独，八皇后，0-1背包，正则表达式, 图的着色，旅行商，全排列

经典题型

 题型  答案链接 完成度
八皇后问题 eightQueens ✅
0-1背包问题 knapsack ✅

剑指Offer

 题号  题目链接             答案链接              难度   完成度 
-- 剑指Offer（六十五）：矩阵中的路径 -- ✨ ❌
-- 剑指Offer（六十六）：机器人的运动范围 -- ✨ ❌

分治算法

经典题型

 题型  答案链接 完成度
求一组数据里面的逆序对 reversedOrderPairs ✅
二维平面上有n个点，如何快速求出最近的两个点之间的距离 closestPair ❌

leetcode

 题号  题目链接             答案链接              难度   完成度 
17 电话号码的字母组合 -- ✨✨ ❌
50 Pow(x, n) -- ✨✨ ❌
78 子集 -- ✨✨ ❌
169 求众数 -- ✨ ❌

其他

剑指offer

 题号  题目链接             答案链接              难度   完成度 
-- 剑指Offer（十一）：二进制中1的个数 NumberOf1 ✨ ✅
-- 剑指Offer（十二）：数值的整数次方 Power ✨ ✅
-- 剑指Offer（十九）：顺时针打印矩阵 printMatrix ✨ ✅
-- 剑指Offer（二十九）：最小的K个数 GetLeastNumbers_Solution ✨ ✅
-- 剑指Offer（三十一）：整数中1出现的次数（从1到n整数中1出现的次数） -- ✨ ❌
-- 剑指Offer（三十三）：丑数 -- ✨ ✅
-- 剑指Offer（四十一）：和为S的连续正数序列 -- ✨ ✅
-- 剑指Offer（四十二）：和为S的两个数字 -- ✨ ✅
-- 剑指Offer（四十五）：扑克牌顺子 -- ✨ ✅
-- 剑指Offer（四十六）：孩子们的游戏（圆圈中最后剩下的数） -- ✨ ❌
-- 剑指Offer（四十七）：求1+2+3+…+n -- ✨ ❌
-- 剑指Offer（四十八）：不用加减乘除的加法 -- ✨ ❌
-- 剑指Offer（五十四）：字符流中第一个不重复的字符 -- ✨ ❌
-- 剑指Offer（六十三）：数据流中的中位数 -- ✨ ❌
-- 剑指Offer（六十四）：滑动窗口的最大值 maxInWindows ✨ ✅

leetcode

 题号  题目链接             答案链接              难度   完成度 
7 整数反转 reverse_integer easy ✅
9 回文数 palindrome_number easy ✅

About

iOS数据结构算法

Topics

c-plus-plus ios algorithm objective-c algorithms leetcode interview data-structures offer leetcode-solutions coding-interviews codinginterviews ios-algorithm

Resources

Readme
Activity

Stars

23 stars

Watchers

2 watching

Forks

6 forks
Report repository

Releases

No releases published

Packages

No packages published

Languages