本文章用于算法学习、分享
个人理解算法基本要素
- 算法总体结构由if..else、for/while、recursive构成
- 找出算法问题基本规律,对于
N的问题,可以用数学归纳法 - 不要排斥递归,递归是所有复杂算法的基石
- 递归基本规律:化
f(n)为f(n-1)、f(n-2)..,考虑特殊情况f(1),f(2).. - 递归过程中利用缓存避免重复计算
- 递归和循环在汇编上没有太大区别
-
双指针对于减少遍历次数,提升效率常用妙用,参考demo 7 - 数据补位为特殊条件处理省去不必要的麻烦,参考demo 7
1.判断给定整数是否为4的n次幂
// OC
//判断是否为4的n次幂
- (BOOL)is4multiple:(int)n {
//递归
// if (n == 1) {
// return YES;
// }
// return n < 8 ? !(n^4) : [self is4multiple:n>>2];
//// if (n < 8) {
//// return !(n^4);
//// }
//// return [self is4multiple:n>>2];
/* 二进制运算符
1.n>0
2.1只出现在奇数位(n&0xAAAAAAAA) == 0
3.只有1个1 ,(n&(n-1)) == 0
*/
//int类型在不同的编译器环境下占用的字节数可能不一样,一般情况下按 4个字节考虑
return (n&0xAAAAAAAA) == 0 && (n&(n-1)) == 0 && n > 0;
}
2.字符串异位词判断
-
问题描述
给定两个字符串s = "hello"和t="elohl",如果其中一个字符串可以由另一个字符串改变字符位置生成,那么就说这两个字符串是异位词(这里设定字符串由纯小写英文字母构成) -
解决思路
首先判断两个字符串的长度是否相同,这是必要条件,满足条件后往下进行-
2.1、Hash表
- 2.1.1、建立两个长度26Hash表,分辨遍历字符串,将字符换算成索引,存入Hash表并进行计数,完成后比对相同索引的计数是否全部相同
- 2.1.2、建立一个长度26Hash表,遍历其中一个字符串,将字符换算成索引存入Hash表并计数,然后遍历另外一个,换算成索引,对索引计数-1,如果存在<0的情况,那么说明不是
-
2.2、遍历删除
遍历其中一个字符串s,依次取出字符,然后从另外一个字符串t中,删除第一个匹配的字符,- 如果查找不到匹配的字符,说明不是异位词
- 如果s所有字符都能从t中匹配删除,那么就是异位词
-
2.3、排序比较,对两个字符串进行按照一致顺序排序,比较
-
3.零钱兑换
给定不同面额的硬币 coins 和一个总金额 amount,求凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1
原题连接
//swift
class Solution {
var cache = [Int:Int]()
func coinChange(_ coins: [Int], _ amount: Int) -> Int {
if amount == 0 {
return 0
}
if let c = cache[amount] {
return c
}
var m = -1
for i in 0..<coins.count {
var n = -1
if amount == coins[i] {
m = 1
break
}
if (amount < coins[i]) {
continue;
}
let tmp = coinChange(coins, amount - coins[i])
if tmp != -1 {
n = tmp + 1
if m != -1 {
m = min(m, n)
} else {
m = n
}
}
}
cache[amount] = m
return m
}
}
- 每种兑换成功的方式,最后一步都是从
coins数组中选择一个,那么可以理解为求amount-coins[i]所需要的最少硬币个数 - 这个题目的思路和爬楼梯相同,只是每次可以爬的楼梯阶数,这里用
[coins]数组管理 - 采用
cache缓存递归过程中的重复计算,不然递归次数会是指数级别,amount的coins.count的指数,下面贴图为采用缓存前后递归次数对比
image.png
4.二叉树递归与非递归
以中序遍历为例
//swift
//递归中序
func inOrderTraversal(_ root:TreeNode?) -> [Int] {
var out = [Int]()
if let left = root?.left {
out.append(contentsOf: inOrderTraversal(left))
}
if root != nil {
out.append(root!.val)
}
if let right = root?.right {
out.append(contentsOf: inOrderTraversal(right))
}
return out
}
//非递归中序
func inOrderNoRecursive(_ root:TreeNode?)->[Int] {
//输出
var out = [Int]()
//缓存TreeNode
var stack = [TreeNode]()
var node = root
while node != nil || !stack.isEmpty {
if node != nil {
stack.append(node!)
node = node?.left
} else {
let top = stack.last!
out.append(top.val)
stack.removeLast()
node = top.right
}
}
return out
}
func treeOrderTest(){
let node = TreeNode(4)
let node2 = TreeNode(2)
node2.left = TreeNode(1)
node2.right = TreeNode(3)
node.left = node2
let node5 = TreeNode(5)
node5.right = TreeNode(6)
node.right = node5
print("num = \(inOrderTraversal(node))")
print("num = \(inOrderNoRecursive(node))")
}
- 二叉树递归与非递归测试结果
image.png
非递归关键思路:
- 非递归遍历采用数组,即栈结构缓存
- 用指针指向一个节点,节点存在,则加入栈中,然后指针继续指向该节点的left节点
- 节点不存在,则取出栈顶元素,并将指针指向栈顶的right节点
5.从非递归的非波拉契理解动态规划
//C
int fib(int n){
if (n < 3) {
return 1;
}
int a = 1,b=1,c = 0;
for (int i = 3; i <=n; i++) {
c=a+b;
a=b;
b=c;
}
return c;
}
- 将递归的过程改为
自底向上传递的过程
6.棋盘上的不同路径之动态规划
原题连接
一个机器人位于一个 m x n 网格的左上角,机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角,问总共有多少条不同的路径？
//语言:C
int uniquePaths(int m, int n){
//创建n*m的二维数组
int **board = (int **)malloc(sizeof(int *) * n);
for (int i = 0; i < n; i++) {
board[i] = (int *)malloc(sizeof(int) * m);
}
for (int i = 0 ; i < n; i++) {
for (int j = 0 ; j < m; j++) {
if (i == 0 && j== 0) {
board[i][j]= 1;
} else if (i > 0 && j == 0) {
board[i][j] = board[i - 1][j];
} else if (i == 0 && j > 0) {
board[i][j] = board[i][j - 1];
} else {
board[i][j] = board[i - 1][j] + board[i][j - 1];
}
}
}
return board[n - 1][m - 1];
}
- m*n,m为列数,n为行数
- 将中间结果
board[i][j]转化为board[i - 1][j]、board[i][j - 1]相关的运算结果
7.删除链表的倒数第N个节点
//C
struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
struct ListNode *pre = (struct ListNode *)malloc(sizeof(struct ListNode) * 1);
pre->next = head;
struct ListNode *first = pre;
struct ListNode *second = pre;
//0,1,2, 3,4,5,6
//s f f
while (first->next) {
first = first->next;
if (n > 0) {
n--;
} else {
second = second->next;
}
}
second->next = second->next->next;
return pre->next;
}
-
双指针在算法当中,对于提升遍历效率,减少遍历次数,有着显著作用 - 头部补位节点的思想,在很多处理特殊情况时,能减少很多特殊的条件判断
8.链表反转
//C
struct ListNode* reverseList(struct ListNode* head){
if (head == NULL) {
return NULL;
}
struct ListNode *node = head;
struct ListNode *next = NULL;
while (node->next) {
struct ListNode *tmp = node->next;
node->next = next;
next = node;
node = tmp;
}
node->next = next;
return node;
}
网友评论