概述

Permutaion是一个很经典的问题，可以有多种变形，很多问题也可以抽象为permutation，然后进行求解。

本文主要内容:

• 经典Permutation
• next-Permutation
• \(kth\) Permutation

问题描述

Your task is to calculate \(a^{b}\) mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array.

Example1:

1
2
3
4

a = 2
b = [3]
Result: 8

Example2:

1
2
3
4

a = 2
b = [1,0]
Result: 1024

思路

解法一：

最初的想法是利用 快速幂 的思想，由于指数特别大，所以在index >> 1这一步需要自己写一个大数的除2方法来代替。

vscode安装

vscode是微软官方推出的一款功能强大的编辑器，适合多种语言，能够分布调试程序。本来我使用的是codeblocks来写小程序，但是调试起来需要建工程，听人推荐，所以用了下vscode，发现很好用。记录一下环境搭建过程。

下载

官方网站就可以下载。

more >>

1.前言

关于动态规划（dyamic programming 后文都用DP代替），见过很多无从下手的问题，最后用一个神奇的DP就解决了，感觉十分的神奇，感叹这个方法的强大，同时我也很费解，为什么有人能想出如此巧妙的方法？

最近看了左程云老师的书，以及听了他的算法课。其中他所讲的关于DP的章节，让我重新认识了DP，准确来说，DP不算是一种方法，而是人们长期总结出的一种优化方法。

问题描述

这个题是学弟跟我说的一道Hulu的面试题，感觉还是挺意思的，所以记录一下。问题如下：

求两个数a、b的和，不使用加法。（当然乘除法减法也是不能使用的）。

简介

KMP是经典的字符串匹配算法。假设子串长度为M，母串长度为N，暴力的字符串匹配的时间复杂度为\(\Theta(M*N)\), 因为对于母串中的N个字符，每个字符与字串比较的复杂度都可能是\(\Theta(M)\)。

KMP算法能将时间复杂度降到\(\Theta(N)\)。其中最重要的计算next数组。