算法之路

发表于 | 分类于 | 次

算法之路

初级算法

数组

删除排序数组中的重复项

1
由于给定的数组是有序的，相同的元素是连续的 => 可采用前后两两比较 => 双指针

买卖股票的最佳时机

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
1. 动态规划
	1.确定状态	
		dp[length][2]	
			dp[i][0]表示第i+1天（i是从0开始的）结束的时候没持有股票的最大利润
			dp[i][1]表示第i+1天（i是从0开始的）结束的时候持有股票的最大利润
	2.找到转移公式
		交易完手里没股票 => dp[i][0]
      1. 当天没有任何交易，利润=前一天没股票的利润
      2. 当天卖出股票，利润=前一天有股票的利润 + 今天卖的价格price[i]
    dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
    交易完手里有股票 => dp[i][1]
      1. 当天没有任何交易，手里的股票是前一天的
      2. 前一天手里没股票，今天买了股票
    dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])
	3.确定初始条件以及边界条件
		边界条件就是第1天的时候，如果我们不持有股票，那么
			dp[0][0]=0;
		如果持有股票，那么
			dp[0][1]=-prices[0];
	4.计算结果
		dp[length - 1][0]

旋转数组

1
2
3
4
5
1. 临时数组法
重新创建一个临时数组，直接计算“旋转”后的位置。
（i+k）% length
2. 反转数组法
将数组进行反转，然后左右再反转一次即可。

存在重复的元素

1
1. hashset

只出现一次的数字

1
2
3
1. 位运算（较好）
	主要需要考虑到异或运算的特点
2. set集合，一般不允许使用

两个数组的交集

1
2
3
1. 排序后，进行一个比较
2. hashmap中
	先把一个元素，放到map中，再遍历另一个数组

加一

1
2
3
从后往前，判断当前位的数字是否为9。
	为9，产生进位
	不为9，直接加一

移动零

1
2
3
4
5
1. 非零的往前移
	非零的往前移动，然后再把最后几个置为0
2. 双指针
	采取交换的思想
移动是比较消耗的，能交换尽量考虑交换

两数之和

1
2
3
4
5
1. 暴力破解
	双重for循环
2. HashMap解决
	new HashMap<数字，下标>
	new int[]{map.get(target - nums[i]), i}

旋转图像

1
2
数组矩阵的规律
上下交换 => 对角线交换

字符串

反转字符串

1
1. 采用双指针交换

整数反转

1
2
3
4
5
6
7
从后往前，每一位进行反转
tmp = x % 10;
int newRes = res * 10 + t;
if( (newRes - t) / 10 != res)
	return 0;
res = newRes;
x = x / 10;

字符串中的第一个唯一字符

1
2
HashMap
先统计单词出现次数，找出等于1的

有效的字母异位词

1
统计字符串中，每个字符的数量

验证回文串

1
双指针

最长公共前缀

1
2
先拿第一个字符串作为前缀，不断和下一个字符串进行比较
	indexOf

树

二叉树的深度

1
2
3
1. 递归（dfs）
	左边的高度，和右边的高度 取最大 + 1
2. bfs

二叉搜索树的验证

1
2
3
4
5
6
7
8
9
10
1. 递归
	二叉搜索树必须满足： right > root > left
  root < left ｜ right < root
  注意：引入最大值和最小值的概念。 
  1.左子树不会大于根节点
  2.右子树不会小于根节点
2. 中序遍历
	左 根 右
	定义一个全局变量：上一个节点
	左 prev = root;右

对称二叉树

1
2
1. 递归
	全局对称 = 左边对称 + 右边对称

将有序的数组转换为二叉搜索树

1
2
3
4
1. 递归
	-10 -3 0 5 9
	全局二叉搜索树 = 左二叉搜索树 + 右二叉搜索树
	取中点作为根 root = 左子树 + 右子树

排序和搜索

合并两个有序数组

1
1. 归并排序

第一个错误的版本

1
2
1. 二分查找
技巧： mid = start + (end-start)/2

动态规划

爬楼梯

1
2
3
4
分析：
1. 当n=1，只有一种跳法 f(1)=1
2. 当n=2, 有两种跳法，1+1 2 f(2)=2
3. 当n=3, 1+2 和 2+1 两种跳法 f(3) = f(2) + f(1)

最大子序和

1
2
3
4
5
6
7
8
9
10
1. 动态规划
	1.确定状态	
		定义dp[i]表示数组中下标i为右端点的连续子数组的最大和
	2.找到转移公式
		dp[i-1] > 0 ? dp[i-1]+num[i](继续累加) : num[i](放弃dp[i-1]，重新计算)
		dp[i] = max(dp[i-1],0)+num[i];
	3.确定初始条件以及边界条件
		dp[0]=num[0]
	4.计算结果
		max = Math.max(max, dp[i]);

打家劫舍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
1. 动态规划
	1.确定状态
		dp[length][2]
			dp[i][0] 第i+1家没偷的金额 
			dp[i][1] 第i+1家偷了的金额 
		
	2.找到转移公式
		i+1家没偷，第i家已经偷 或者 没偷：
			dp[i][0] = max(dp[i-1][0],dp[i-1][1])
		i+1家偷了，第i家没有偷
			dp[i][1] = dp[i-1][0] + num[i]
	3.确定初始条件以及边界条件
		第一家没偷
			dp[0][0]=0
		第一家偷了
			dp[0][1]=num[0]
	4.计算结果
		Math.max(dp[length - 1][0], dp[length - 1][1]);

中级算法

数组和字符串

三数之和

1
2
3
双指针
	固定一个数字，然后移动left 和 right
	注：为了保存不重复的结果，将数组进行排序，nums[i] == num[i+1] continue直接跳过

矩阵置零

1
2
3
4
两次遍历
	如果我们一次遍历当遇到0的时候把对应的行和列全部置为0，这个时候就会出现一个问题，你遇到的0是矩阵中本来就有的还是前面修改的，这个我们没法确定。
	第一次遍历，确定哪些行哪些列需要置为0
	第二次遍历，行和列全部置为0

字母异位词

1
2
3
4
5
6
7
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

1. 排序后再判断
	排序后再判断两个字符串相等，就是字母异位词
2. 统计字母出现的次数
	如果出现的次数相同，就是字母异位词

无重复的最长子串

1
2
3
双指针
	left right
	right指针一直往右移动，遇到重复则修改left(重新开始记录子串)

最长回文子串

1
中心，往两边扩散法

链表

相交链表

1
双指针法

两数相加

1
2
3
1. 计算sum
2. 保存进位
3. preNode = preNode.next

树

二叉搜索树中的第k小的元素

1
2
3
4
5
中序遍历
	左 根 右
传入一个count
--count == 0
	就是第k小的元素

回溯算法

电话号码的字母组合

1
2
3
4
5
6
7
8
9
10
11
12
13
回溯模版
void backtrack(参数) {
	if (终止条件) {
        存放结果;
        return;
   }
    
	for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtrack(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

括号生成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
思想：
出现一个左括号，必须有一个右括号来补。
intact 已生成的括号对的个数
need 待生成的括号对的个数
		public void generate(int intact,int need,int n){
    		// 条件判断
        if(intact==n){
            words.add(sb.toString());
            return;
        }
        if((intact+need)<n)
        {
        		// 处理
            sb.append('(');
            generate(intact, need+1, n);		// 递归
            sb.deleteCharAt(sb.length()-1);		// 回退
        }
        if(need!=0){
            sb.append(')');
            generate(intact+1,need-1, n);
            sb.deleteCharAt(sb.length()-1);
        }
    }

全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// list结果
// 临时存储其中一个排列
// 原排列
private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums) {
    //终止条件，如果数字都被使用完了，说明找到了一个排列，（可以把它看做是n叉树到
    //叶子节点了，不能往下走了，所以要返回）
    if (tempList.size() == nums.length) {
        //因为list是引用传递，这里必须要重新new一个
        list.add(new ArrayList<>(tempList));
        return;
    }
    //（可以把它看做是遍历n叉树每个节点的子节点）
    for (int i = 0; i < nums.length; i++) {
        //因为不能有重复的，所以有重复的就跳过
        if (tempList.contains(nums[i]))
            continue;
        //选择当前值
        tempList.add(nums[i]);
        //递归（可以把它看做遍历子节点的子节点）
        backtrack(list, tempList, nums);
    }
}

子集

1
2
参考全排列
终止条件，取消

单词搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 待搜索的矩阵board
// 搜索的单词
// i，j为矩阵的下标
// 单词的下标
boolean dfs(char[][] board, char[] word, int i, int j, int index) {
    //边界的判断，如果越界直接返回false。index表示的是查找到字符串word的第几个字符，
    //如果这个字符不等于board[i][j]，说明验证这个坐标路径是走不通的，直接返回false
    if (i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[index])
        return false;
    //如果word的每个字符都查找完了，直接返回true
    if (index == word.length - 1)
        return true;
    //把当前坐标的值保存下来，为了在最后复原
    char tmp = board[i][j];
    //然后修改当前坐标的值
    board[i][j] = '.';
    //走递归，沿着当前坐标的上下左右4个方向查找
    boolean res = dfs(board, word, i + 1, j, index + 1)
            || dfs(board, word, i - 1, j, index + 1)
            || dfs(board, word, i, j + 1, index + 1)
            || dfs(board, word, i, j - 1, index + 1);
    //递归之后再把当前的坐标复原
    board[i][j] = tmp;
    return res;
}

排序与搜索

颜色分类

1
红色往左移，蓝色往右移

前k个高频元素

1
2
3
4
5
6
7
8
统计每个元素的次数
构建大根堆

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

		1，3
	2，2	3，1

数组中的第k个最大元素

1
2
3
4
5
输入: [3,2,1,5,6,4], k = 2
输出: 5
小根堆
 6
4 5

寻找峰值

1
2
3
二分查找
1. 两次二分查找 找最左边的值，和最右边的值
2. 一次二分查找，先找到值。 然后往左，和往右找

动态规划

跳跃游戏

1
2
3
4
5
6
7
8
9
10
11
12
13
1.确定状态	
	定义dp[i]为在下标i处，可以最多往后跳几步
2.找到转移公式
	1. 不在当前位置停留	从上一个位置往后跳 = dp[i-1] - 1
	2. 在当前位置停留 num[i]
	dp[i] = Math.max(dp[i-1] - 1, nums[i])
3.确定初始条件以及边界条件
	dp[i] + i + 1 >= nums.length
		return true
	else
		return false
4.计算结果
	max = Math.max(max, dp[i]);

不同路径

1
2
3
4
5
6
7
8
9
10
11
12
13
1.确定状态	
	dp[i][j]为 i * j 网格中Robot 从左上角到右下角的总路径数量
2.找到转移公式
	1. 从上边走过来 dp[i][j-1]
	2. 从左边走过来 dp[i-1][j]
	dp[i][j] = (j > 0 ? dp[i][j - 1] : 0) + (i > 0 ? dp[i - 1][j] : 0);
3.确定初始条件以及边界条件
	dp[i] + i + 1 >= nums.length
		return true
	else
		return false
4.计算结果
	max = Math.max(max, dp[i]);

零钱兑换

1
2
3
4
5
6
7
8
9
10
1.确定状态	
	dp[i] 为组成金额 i 所需最少的硬币数量
2.找到转移公式
	coins = {1,2,5}
	dp[i] = min(dp[i- coins[0]], dp[i-coins[1], dp[i-coins[2]]]) + 1
3.确定初始条件以及边界条件
	dp[0] = 0;
	
4.计算结果
	max = Math.max(max, dp[i]);