一般是求值问题，核心是穷举找状态转移方程
剪绳子最大乘积、大数求余
推论一： 将绳子 以相等的长度等分为多段 ，得到的乘积最大。
推论二： 尽可能将绳子以长度 3 等分为多段时，乘积最大。
最优3等分，次优，剩下个2。最差，剩下个1，将最后一个3，分成2 + 2
快速幂解析
当我们计算出来 x^2 之后就可以只进行三次乘法就可以了，相对于之前的 7 次乘法，时间大大减少了。
正则表达式匹配
表示数值的字符串
把数字翻译成字符串
最长不含重复字符的子字符串
n个骰子的点数
股票买卖问题
打家劫舍问题
nSum问题
高楼扔鸡蛋问题
子集背包问题
完全背包问题
汉洛塔
三个人分别点了三家外卖，又一个外卖小哥配送，他有多少种配送方式
写个算法，输出2~100的素数
赛马题，网上能搜到
问一个有关花开通知蜜蜂，花关通知蜜蜂的问题；
要求想一个时间复杂度为O1的解法，来解决一个2的平方的算法题（答 无限空间换时间的策略）如何计算x^n
ACID银行家算法
一个不多于5位数的整数，反序处理problem；
一个多边形分割方法
从篮子里如何取苹果的一个算法;
火星文字
基本计算器
分治
礼物的最大价值
在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
并每次 向右 或者 向下 移动一格
class Solution {
public int maxValue(int[][] grid) {
int m = grid.length, n = grid[0].length;
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(i == 0 && j == 0) continue;
if(i == 0) grid[i][j] += grid[i][j - 1] ;
else if(j == 0) grid[i][j] += grid[i - 1][j];
else grid[i][j] += Math.max(grid[i][j - 1], grid[i - 1][j]);
}
}
return grid[m - 1][n - 1];
}
}
递归
斐波那契数列
斐波那契数列
递归法：
function Fibonacci(int n) {
if(n < 0){
return 0;
}
if(n == 0){
return 0;
}else if(n == 1){
return 1;
}else return Fibonacci(n-1)+ Fibonacci(n-2);
}
动态规划：
class Solution {
public int fib(int n) {
int a = 0, b = 1, sum;
for(int i = 0; i < n; i++){
sum = (a + b) % 1000000007;
a = b;
b = sum;
}
return a;
}
}
青蛙跳台阶问题（本质是求斐波那契数列）
问用递归写一个阶乘算法
n个骰子的点数
把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
使用动态规划解决问题一般分为三步：
表示状态
找出状态转移方程
边界处理
掷骰子
首先用数组的第一维来表示阶段，也就是投掷完了几枚骰子。
然后用第二维来表示投掷完这些骰子后，可能出现的点数。
数组的值就表示，该阶段各个点数出现的次数。
class Solution {
public:
vector
int dp[15][70];
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= 6; i ++) {
dp[1][i] = 1;
}
for (int i = 2; i <= n; i ++) {
for (int j = i; j <= 6*i; j ++) {
for (int cur = 1; cur <= 6; cur ++) {
if (j - cur <= 0) {
break;
}
dp[i][j] += dp[i-1][j-cur];
}
}
}
int all = pow(6, n);
vector
for (int i = n; i <= 6 * n; i ++) {
ret.push_back(dp[n][i] * 1.0 / all);
}
return ret;
}
};
使用随机数
使得n-1点数概率数组和1点数概率数组元素两两相乘，并将乘积结果加到n点数概率数组上。
基本思路如上，然后我们可以根据动态规划的套路：
1.构造dp数组：tmp[]为n个骰子的点数概率数组，pre[]为n-1个骰子的点数概率数组，一个骰子的点数概率数组显然是6个六分之一,不需要另设数组。
2.初始化dp数组：pre[]={1/6d,1/6d,1/6d,1/6d,1/6d,1/6d}
3.构造状态转移方程:tmp[x+y]+=pre[x]num[y];
public double[] twoSum(int n) {
double pre[]={1/6d,1/6d,1/6d,1/6d,1/6d,1/6d};
for(int i=2;i<=n;i++){
double tmp[]=new double[5i+1];
for(int j=0;j<pre.length;j++)
for(int x=0;x<6;x++)
tmp[j+x]+=pre[j]/6;
pre=tmp;
}
return pre;
}
扑克牌中的顺子
从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。
方法一： 集合 Set + 遍历
遍历五张牌，遇到大小王（即 0直接跳过。
判别重复： 利用 Set 实现遍历判重， Set
获取最大 / 最小的牌： 借助辅助变量 ma 和 mi ，遍历统计即可。
class Solution {
public boolean isStraight(int[] nums) {
Set
int max = 0, min = 14;
for(int num : nums) {
if(num == 0) continue; // 跳过大小王
max = Math.max(max, num); // 最大牌
min = Math.min(min, num); // 最小牌
if(repeat.contains(num)) return false; // 若有重复，提前返回 false
repeat.add(num); // 添加此牌至 Set
}
return max - min < 5; // 最大牌 - 最小牌 < 5 则可构成顺子
}
}
方法二：排序 + 遍历
class Solution {
public boolean isStraight(int[] nums) {
int joker = 0;
Arrays.sort(nums); // 数组排序
for(int i = 0; i < 4; i++) {
if(nums[i] == 0) joker++; // 统计大小王数量
else if(nums[i] == nums[i + 1]) return false; // 若有重复，提前返回 false
}
return nums[4] - nums[joker] < 5; // 最大牌 - 最小牌 < 5 则可构成顺子
}
}
股票的最大利润
假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
class Solution {
public int maxProfit(int[] prices) {
int cost = Integer.MAX_VALUE, profit = 0;
for(int price : prices) {
cost = Math.min(cost, price);
profit = Math.max(profit, price - cost);
}
return profit;
}
}
丑数
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
class Solution {
public int nthUglyNumber(int n) {
int a = 0, b = 0, c = 0;
int[] dp = new int[n];
dp[0] = 1;
for(int i = 1; i < n; i++) {
int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5;
dp[i] = Math.min(Math.min(n2, n3), n5);
if(dp[i] == n2) a++;
if(dp[i] == n3) b++;
if(dp[i] == n5) c++;
}
return dp[n - 1];
}
}
乘积最大子数组
动态规划
遍历数组时计算当前最大值，不断更新
class Solution {
public int maxProduct(int[] nums) {
int max = Integer.MIN_VALUE, imax = 1, imin = 1;
for(int i=0; i<nums.length; i++){
if(nums[i] < 0){
int tmp = imax;
imax = imin;
imin = tmp;
}
imax = Math.max(imaxnums[i], nums[i]);
imin = Math.min(iminnums[i], nums[i]);
max = Math.max(max, imax);
}
return max;
}
}
实现一个基本的计算器来计算一个简单的字符串表达式的值。
先把乘除法的值计算出来，最终将所有的运算简化成只有加法。
将表达式（中缀）转化为后缀
将后缀计算出结果
class Solution {
public int calculate(String s) {
Stack
char lastOp = '+';
char[] arr = s.toCharArray();
for(int i = 0; i < arr.length; i ++){
if(arr[i] == ' ') continue;
if(Character.isDigit(arr[i])){
int tempNum = arr[i] - '0';
while(++i < arr.length && Character.isDigit(arr[i])){
tempNum = tempNum * 10 + (arr[i] - '0');
} i--;
if(lastOp == '+') numStack.push(tempNum);
else if(lastOp == '-') numStack.push(-tempNum);
else numStack.push(res(lastOp, numStack.pop(), tempNum));
} else lastOp = arr[i];
}
int ans = 0;
for(int num : numStack) ans += num;
return ans;
}
private int res(char op, int a, int b){
if(op == '*') return a * b;
else if(op == '/') return a / b;
else if(op == '+') return a + b; //其实加减运算可以忽略
else return a - b;
}
}
LRU算法
class LRUCache {
// key -> Node(key, val)
private HashMap<Integer, Node> map;
// Node(k1, v1) <-> Node(k2, v2)…
private DoubleList cache;
// 最大容量
private int cap;
public LRUCache(int capacity) {
this.cap = capacity;
map = new HashMap<>();
cache = new DoubleList();
}
public int get(int key) {
if (!map.containsKey(key))
return -1;
int val = map.get(key).val;
// 利用 put 方法把该数据提前
put(key, val);
return val;
}
public void put(int key, int val) {
// 先把新节点 x 做出来
Node x = new Node(key, val);
if (map.containsKey(key)) {
// 删除旧的节点，新的插到头部
cache.remove(map.get(key));
cache.addFirst(x);
// 更新 map 中对应的数据
map.put(key, x);
} else {
if (cap == cache.size()) {
// 删除链表最后一个数据
Node last = cache.removeLast();
map.remove(last.key);
}
// 直接添加到头部
cache.addFirst(x);
map.put(key, x);
}
}
}
字符串的排列
输入一个字符串，打印出该字符串中字符的所有排列。
输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]
回溯法
对于一个长度为 n 的字符串（假设字符互不重复）n×(n−1)×(n−2)…×2×1 种方案
根据字符串排列的特点，考虑深度优先搜索所有排列方案。
重复方案与剪枝： 当字符串存在重复字符时，排列方案中也存在重复方案。为排除重复方案，需在固定某位字符时，保证 “每种字符只在此位固定一次” ，即遇到重复字符时不交换，直接跳过。从 DFS 角度看，此操作称为 “剪枝” 。
* 回溯算法框架：解决一个问题，实际上就是一个决策树的遍历过程：
* 1. 路径：做出的选择
* 2. 选择列表：当前可以做的选择
* 3. 结束条件：到达决策树底层，无法再做选择的条件
字符串的排列可以抽象为一棵决策树：
List<String> res = new LinkedList<>();
char[] c;
public String[] permutation(String s) {
c = s.toCharArray();
dfs(0);
return res.toArray(new String[res.size()]);
}
void dfs(int x) {
if(x == c.length - 1) {
res.add(String.valueOf(c)); // 添加排列方案
return;
}
HashSet<Character> set = new HashSet<>();
for(int i = x; i < c.length; i++) {
if(set.contains(c[i])) continue; // 重复，因此剪枝
set.add(c[i]);
swap(i, x); // 交换，将 c[i] 固定在第 x 位
dfs(x + 1); // 开启固定第 x + 1 位字符
swap(i, x); // 恢复交换
}
}
void swap(int a, int b) {
char tmp = c[a];
c[a] = c[b];
c[b] = tmp;
}
全排列问题
List<List
/* 主函数，输入一组不重复的数字，返回它们的全排列 */
List<List
// 记录「路径」
LinkedList
backtrack(nums, track);
return res;
}
// 路径：记录在 track 中
// 选择列表：nums 中不存在于 track 的那些元素
// 结束条件：nums 中的元素全都在 track 中出现
void backtrack(int[] nums, LinkedList
// 触发结束条件
if (track.size() == nums.length) {
res.add(new LinkedList(track));
return;
}
for (int i = 0; i < nums.length; i++) {
// 排除不合法的选择
if (track.contains(nums[i]))
continue;
// 做选择
track.add(nums[i]);
// 进入下一层决策树
backtrack(nums, track);
// 取消选择
track.removeLast();
}
}
n皇后问题
给你一个 N×N 的棋盘，让你放置 N 个皇后，使得它们不能互相攻击。
PS：皇后可以攻击同一行、同一列、左上左下右上右下四个方向的任意单位。
vector<vector
/* 输入棋盘边长 n，返回所有合法的放置 */
vector<vector
// ‘.’ 表示空，’Q’ 表示皇后，初始化空棋盘。
vector
backtrack(board, 0);
return res;
}
// 路径：board 中小于 row 的那些行都已经成功放置了皇后
// 选择列表：第 row 行的所有列都是放置皇后的选择
// 结束条件：row 超过 board 的最后一行
void backtrack(vector
// 触发结束条件
if (row == board.size()) {
res.push_back(board);
return;
}
int n = board[row].size();
for (int col = 0; col < n; col++) {
// 排除不合法选择
if (!isValid(board, row, col))
continue;
// 做选择
board[row][col] = 'Q';
// 进入下一行决策
backtrack(board, row + 1);
// 撤销选择
board[row][col] = '.';
}
}
/* 是否可以在 board[row][col] 放置皇后？ */
bool isValid(vector
int n = board.size();
// 检查列是否有皇后互相冲突
for (int i = 0; i < n; i++) {
if (board[i][col] == ‘Q’)
return false;
}
// 检查右上方是否有皇后互相冲突
for (int i = row - 1, j = col + 1;
i >= 0 && j < n; i–, j++) {
if (board[i][j] == ‘Q’)
return false;
}
// 检查左上方是否有皇后互相冲突
for (int i = row - 1, j = col - 1;
i >= 0 && j >= 0; i–, j–) {
if (board[i][j] == ‘Q’)
return false;
}
return true;
}
int openLock(String[] deadends, String target) {
// 记录需要跳过的死亡密码
Set
for (String s : deadends) deads.add(s);
// 记录已经穷举过的密码，防止走回头路
Set
Queue
// 从起点开始启动广度优先搜索
int step = 0;
q.offer(“0000”);
visited.add(“0000”);
while (!q.isEmpty()) {
int sz = q.size();
/* 将当前队列中的所有节点向周围扩散 */
for (int i = 0; i < sz; i++) {
String cur = q.poll();
/* 判断是否到达终点 */
if (deads.contains(cur))
continue;
if (cur.equals(target))
return step;
/* 将一个节点的未遍历相邻节点加入队列 */
for (int j = 0; j < 4; j++) {
String up = plusOne(cur, j);
if (!visited.contains(up)) {
q.offer(up);
visited.add(up);
}
String down = minusOne(cur, j);
if (!visited.contains(down)) {
q.offer(down);
visited.add(down);
}
}
}
/* 在这里增加步数 */
step++;
}
// 如果穷举完都没找到目标密码，那就是找不到了
return -1;
}
给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数。
输入: [10,2]
输出: 210
想法
为了构建最大数字，我们希望越高位的数字越大越好。
当数字是多位时，我们构建s1，s2，将s1+s2 和s2 + s1 进行比较，哪个大哪个放前面
class Solution {
private class LargerNumberComparator implements Comparator
@Override
public int compare(String a, String b) {
String order1 = a + b;
String order2 = b + a;
return order2.compareTo(order1);
}
}
public String largestNumber(int[] nums) {
// Get input integers as strings.
String[] asStrs = new String[nums.length];
for (int i = 0; i < nums.length; i++) {
asStrs[i] = String.valueOf(nums[i]);
}
// Sort strings according to custom comparator.
Arrays.sort(asStrs, new LargerNumberComparator());
// If, after being sorted, the largest number is `0`, the entire number
// is zero.
if (asStrs[0].equals("0")) {
return "0";
}
// Build largest number from sorted array.
String largestNumberStr = new String();
for (String numAsStr : asStrs) {
largestNumberStr += numAsStr;
}
return largestNumberStr;
}
}
摆动排序
输入: nums = [1, 5, 1, 1, 6, 4]
输出: 一个可能的答案是 [1, 4, 1, 5, 1, 6]
解法1：排序
首先，我们可以很容易想到一种简单的解法：将数组进行排序，然后从中间位置进行等分（如果数组长度为奇数，则将中间的元素分到前面），然后将两个数组进行穿插。
但是这一解法有一个问题，例如，对于数组[1, 2, 2, 3]，按照这种做法求得的结果仍为[1, 2, 2, 3]
为了方便阅读，我们在下文中定义较小的子数组为数组A，较大的子数组为数组B。显然，出现上述现象是因为nums中存在重复元素。实际上，由于穿插之后，相邻元素必来自不同子数组，所以A或B内部出现重复元素是不会出现上述现象的。所以，出现上述情况其实是因为数组A和数组B出现了相同元素，我们用r来表示这一元素。而且我们可以很容易发现，如果A和B都存在r，那么r一定是A的最大值，B的最小值，这意味着r一定出现在A的尾部，B的头部。其实，如果这一数字的个数较少，不会出现这一现象，只有当这一数字个数达到原数组元素总数的一半，才会在穿插后的出现在相邻位置。
class Solution {/**
- 先排序再穿插
- O(nlogn)+O(n)=O(nlogn)
- @param nums
- /
public void wiggleSort(int[] nums) {
//排序
Arrays.sort(nums);
int len=nums.length,i = 0;
int[] smaller=new int[len%2==0?len/2:(len/2+1)],bigger=new int[len/2];
//复制
System.arraycopy(nums,0,smaller,0,smaller.length);
System.arraycopy(nums,smaller.length,bigger,0,len/2);
//穿插
for (; i < len / 2; i++) {
}nums[2*i]=smaller[smaller.length-1-i]; nums[2*i+1]=bigger[len/2-1-i];
if (len%2!=0) nums[2*i]=smaller[smaller.length-1-i];
}
}计算右侧小于当前元素的个数
给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
输入：[5,2,6,1]
输出：[2,1,1,0]
解释：
5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素
方法一：离散化树状数组
class Solution {
private int[] c;
private int[] a;
public List
countSmaller(int[] nums) { List<Integer> resultList = new ArrayList<Integer>(); discretization(nums); init(nums.length + 5); for (int i = nums.length - 1; i >= 0; --i) { int id = getId(nums[i]); resultList.add(query(id - 1)); update(id); } Collections.reverse(resultList); return resultList;}
private void init(int length) {
c = new int[length]; Arrays.fill(c, 0);}
private int lowBit(int x) {
return x & (-x);}
private void update(int pos) {
while (pos < c.length) { c[pos] += 1; pos += lowBit(pos); }}
private int query(int pos) {
int ret = 0; while (pos > 0) { ret += c[pos]; pos -= lowBit(pos); } return ret;}
private void discretization(int[] nums) {
Set<Integer> set = new HashSet<Integer>(); for (int num : nums) { set.add(num); } int size = set.size(); a = new int[size]; int index = 0; for (int num : set) { a[index++] = num; } Arrays.sort(a);}
private int getId(int x) {
return Arrays.binarySearch(a, x) + 1;}
}小偷问题
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
方法一：动态规划 + 滚动数组
class Solution {
public int rob(int[] nums) {if (nums == null || nums.length == 0) { return 0; } int length = nums.length; if (length == 1) { return nums[0]; } int[] dp = new int[length]; dp[0] = nums[0]; dp[1] = Math.max(nums[0], nums[1]); for (int i = 2; i < length; i++) { dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]); } return dp[length - 1];}
}最长上升子序列
动态规划
public class Solution {
public int lengthOfLIS(int[] nums) {if (nums.length == 0) { return 0; } int[] dp = new int[nums.length]; dp[0] = 1; int maxans = 1; for (int i = 1; i < dp.length; i++) { int maxval = 0; for (int j = 0; j < i; j++) { if (nums[i] > nums[j]) { maxval = Math.max(maxval, dp[j]); } } dp[i] = maxval + 1; maxans = Math.max(maxans, dp[i]); } return maxans;}
}
贪心 + 二分查找
class Solution {
public:
int lengthOfLIS(vector& nums) { int len = 1, n = (int)nums.size(); if (n == 0) return 0; vector<int> d(n + 1, 0); d[len] = nums[0]; for (int i = 1; i < n; ++i) { if (nums[i] > d[len]) d[++len] = nums[i]; else{ int l = 1, r = len, pos = 0; // 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0 while (l <= r) { int mid = (l + r) >> 1; if (d[mid] < nums[i]) { pos = mid; l = mid + 1; } else r = mid - 1; } d[pos + 1] = nums[i]; } } return len;}
};零钱兑换
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
方法一、搜索回溯 [超出时间限制]
public class Solution {
public int coinChange(int[] coins, int amount) {
return coinChange(0, coins, amount);
}
private int coinChange(int idxCoin, int[] coins, int amount) {
if (amount == 0)
return 0;
if (idxCoin < coins.length && amount > 0) {
int maxVal = amount / coins[idxCoin];
int minCost = Integer.MAX_VALUE;
for (int x = 0; x <= maxVal; x++) {
if (amount >= x * coins[idxCoin]) {
int res = coinChange(idxCoin + 1, coins, amount - x * coins[idxCoin]);
if (res != -1)
minCost = Math.min(minCost, res + x);
}
}
return (minCost == Integer.MAX_VALUE)? -1: minCost;
}
return -1;
}
}
方法二、动态规划-自上而下 [通过]
public class Solution {
public int coinChange(int[] coins, int amount) {
if (amount < 1) return 0;
return coinChange(coins, amount, new int[amount]);
}
private int coinChange(int[] coins, int rem, int[] count) {
if (rem < 0) return -1;
if (rem == 0) return 0;
if (count[rem - 1] != 0) return count[rem - 1];
int min = Integer.MAX_VALUE;
for (int coin : coins) {
int res = coinChange(coins, rem - coin, count);
if (res >= 0 && res < min)
min = 1 + res;
}
count[rem - 1] = (min == Integer.MAX_VALUE) ? -1 : min;
return count[rem - 1];
}
}
方法三、动态规划：自下而上 [通过]
public class Solution {
public int coinChange(int[] coins, int amount) {
int max = amount + 1;
int[] dp = new int[amount + 1];
Arrays.fill(dp, max);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.length; j++) {
if (coins[j] <= i) {
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
}
矩阵中的最长递增路径
本文面向高阶读者者。它引入了以下概念：深度优先搜索，记忆化，动态规划和拓扑排序。本文解释了动态规划和拓扑排序的关系。
给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：
每次转换只能改变一个字母。
转换过程中的中间单词必须是字典中的单词。
输入:
beginWord = “hit”,
endWord = “cog”,
wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]
输出: 5
解释: 一个最短转换序列是 “hit” -> “hot” -> “dot” -> “dog” -> “cog”,
返回它的长度 5。
我们将问题抽象在一个无向无权图中，每个单词作为节点，差距只有一个字母的两个单词之间连一条边。问题变成找到从起点到终点的最短路径，如果存在的话。因此可以使用广度优先搜索方法。
方法 1：广度优先搜索
class Solution {
public int ladderLength(String beginWord, String endWord, List
// Since all words are of same length.
int L = beginWord.length();
// Dictionary to hold combination of words that can be formed,
// from any given word. By changing one letter at a time.
Map<String, List<String>> allComboDict = new HashMap<>();
wordList.forEach(
word -> {
for (int i = 0; i < L; i++) {
// Key is the generic word
// Value is a list of words which have the same intermediate generic word.
String newWord = word.substring(0, i) + '*' + word.substring(i + 1, L);
List<String> transformations = allComboDict.getOrDefault(newWord, new ArrayList<>());
transformations.add(word);
allComboDict.put(newWord, transformations);
}
});
// Queue for BFS
Queue<Pair<String, Integer>> Q = new LinkedList<>();
Q.add(new Pair(beginWord, 1));
// Visited to make sure we don't repeat processing same word.
Map<String, Boolean> visited = new HashMap<>();
visited.put(beginWord, true);
while (!Q.isEmpty()) {
Pair<String, Integer> node = Q.remove();
String word = node.getKey();
int level = node.getValue();
for (int i = 0; i < L; i++) {
// Intermediate words for current word
String newWord = word.substring(0, i) + '*' + word.substring(i + 1, L);
// Next states are all the words which share the same intermediate state.
for (String adjacentWord : allComboDict.getOrDefault(newWord, new ArrayList<>())) {
// If at any point if we find what we are looking for
// i.e. the end word - we can return with the answer.
if (adjacentWord.equals(endWord)) {
return level + 1;
}
// Otherwise, add it to the BFS Queue. Also mark it visited
if (!visited.containsKey(adjacentWord)) {
visited.put(adjacentWord, true);
Q.add(new Pair(adjacentWord, level + 1));
}
}
}
}
return 0;
}
}
计算网格中岛屿的数量
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
输入:
[
[‘1’,’1’,’1’,’1’,’0’],
[‘1’,’1’,’0’,’1’,’0’],
[‘1’,’1’,’0’,’0’,’0’],
[‘0’,’0’,’0’,’0’,’0’]
]
输出: 1
方法一：深度优先搜索
我们可以将二维网格看成一个无向图，竖直或水平相邻的 1 之间有边相连。
找出那个只出现了一次的元素
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
方法一：位运算
class Solution {
public int singleNumber(int[] nums) {
int single = 0;
for (int num : nums) {
single ^= num;
}
return single;
}
}
给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以字符串形式返回小数。
如果小数部分为循环小数，则将循环的部分括在括号内。
不需要复杂的数学知识，只需要数学的基本知识。了解长除法的运算规则。
注意边界情况！列出所有你可以想到的测试数据并验证你的代码。
长除法：核心思想是当余数出现循环的时候，对应的商也会循环。
需要用一个哈希表记录余数出现在小数部分的位置，当你发现已经出现的余数，就可以将重复出现的小数部分用括号括起来。
找到若干个完全平方数
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4.
class Solution {
public int numSquares(int n) {
int dp[] = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
// bottom case
dp[0] = 0;
// pre-calculate the square numbers.
int max_square_index = (int) Math.sqrt(n) + 1;
int square_nums[] = new int[max_square_index];
for (int i = 1; i < max_square_index; ++i) {
square_nums[i] = i * i;
}
for (int i = 1; i <= n; ++i) {
for (int s = 1; s < max_square_index; ++s) {
if (i < square_nums[s])
break;
dp[i] = Math.min(dp[i], dp[i - square_nums[s]] + 1);
}
}
return dp[n];
}
}