剑指 Offer 46. 把数字翻译成字符串
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
class Solution {
public int translateNum(int num) {
int ans = 0;
// f(i) = f(i - 1) + f(i - 2);
// 当后两位可以组成一个数字的时候，才存在f(i - 2);
// f (-1) = 0 f(0) = 1 f(1) = 1;
// 1 4 0 2
// 0 1 2 3
String s = String.valueOf(num);
int a = 0;
int b = 1;
int c = 1;
if (s.length() == 1) {
return 1;
}
for (int i = 2; i <= s.length(); i++){
a = b;
b = c;
… }
}
动态规划问题，比如以 1212 为例。
如果把 2 当作一个结果来看，那么就是 121 的种类即可。
如果把 12 当作一个结果来看，那么就是 12 的种类。
于是，这个 12 符不符合规则便是关键，规则即这个数字是不是在 10 和 25 之间。
f(1) 就是从 1 开始的答案；在初始条件下，这里的 f(-1) = 0; f(0) = 1;
给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1: 输入: prices = [7,1,5,3,6,4] 输出: 7 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
class Solution {
public int maxProfit(int[] prices) {
int ans = 0;
for (int i = 1; i < prices.length; i++) {
int profit = prices[i] - prices[i - 1];
if (profit > 0) {
ans += profit;
}
}
return ans;
}
}
贪心算法，只要这一天是上涨的，那么就进行买卖操作盈利，平或者跌不操作。（要仔细考虑为什么每天都操作才是最优解）
面试题 10.01. 合并排序的数组 给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法，将 B 合并入 A 并排序。
初始化 A 和 B 的元素数量分别为 m 和 n。
示例:
输入: A = [1,2,3,0,0,0], m = 3 B = [2,5,6], n = 3
输出: [1,2,2,3,5,6]
class Solution {
public void merge(int[] A, int m, int[] B, int n) {
int length = A.length;
int bLength = B.length;
int aLength = length - bLength;
int pa = aLength - 1;
int pb = bLength - 1;
int cur = length - 1;
while (cur >= 0) {
if (pa < 0 && pb >= 0) {
while (cur >= 0) {
A[cur--] = B[pb--];
}
return;
}
if (pb < 0 && pa >= 0) {
while (cur >= 0) {
A[cur--] = A[pa--];
}
return;
}
if (A[pa] >= B[pb]) {
A[cur] = A[pa];
pa--;
} else {
A[cur] = B[pb];
pb--;
}
cur--;
}
}
}
双指针，由于 a 数组有足够的空间，还有一个指针指向当前在的位置。双指针指向需要排序的两个数组。（美团一面）
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> ans = new ArrayList<>();
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return ans;
}
int rows = matrix.length;
int columns = matrix[0].length;
int left = 0;
int right = columns - 1;
int top = 0;
int buttom = rows - 1;
while (left <= right && top <= buttom) {
for (int c = left; c <= right; c++) {
ans.add(matrix[top][c]);
}
for (int r = top + 1; r <= buttom; r++) {
ans.add(matrix[r][right]);
}
if (left < right && top < buttom) {
for (int c = right - 1; c >= left; c--) {
ans.add(matrix[buttom][c]);
}
for (int r = buttom - 1; r >= top + 1; r--) {
ans.add(matrix[r][left]);
}
}
left++;
right--;
top++;
buttom--;
}
return ans;
}
}
简单的模拟一层一层就好，注意开头和起始的位置，和当遇到只有一层或一列的情况应该怎么特殊处理（用一个 if 判断一下就好了）。