[TOC]
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1. 斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 2
输出：1
示例 2：
输入：n = 5
输出：5
提示：
0 <= n <= 100
class Solution {
public int fib(int n) {
int first = 0, second = 1, sum;
for (int i = 0; i < n; i++) {
sum = (first + second) % 1000000007;
first = second;
second = sum;
}
return first;
}
}class Solution {
int[] temp;
public int fib(int n) {
temp = new int[n + 1];
return dfs(n);
}
public int dfs(int n) {
if (n < 2) {
return n;
}
if (temp[n] != 0) {
return temp[n];
}
temp[n] = (dfs(n - 1) + dfs(n - 2)) % 1000000007;
return temp[n];
}
}一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 2
输出：2
示例 2：
输入：n = 7
输出：21
示例 3：
输入：n = 0
输出：1
提示：
0 <= n <= 100
我们用 f(x) 表示爬到第 x 级台阶的方案数，考虑最后一步可能跨了一级台阶，也可能跨了两级台阶，所以我们可以列出如下式子：
class Solution {
public int numWays(int n) {
if (n == 0) {
return 1;
}
if (n <= 2) {
return n;
}
int first = 1, second = 2;
for (int i = 3; i <= n; i++) {
int sum = (first + second) % 1000000007;
first = second;
second = sum;
}
return second;
}
}0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。
例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
示例 1：
输入: n = 5, m = 3
输出: 3
示例 2：
输入: n = 10, m = 17
输出: 2
限制：
1 <= n <= 10^5
1 <= m <= 10^6
详解见leetcode
class Solution {
int recursion(int n, int m) {
if (n == 1) {
return 0;
}
int x = recursion(n - 1, m);
return (m + x) % n;
}
public int lastRemaining(int n, int m) {
return recursion(n, m);
}
}求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
示例 1：
输入: n = 3
输出: 6
示例 2：
输入: n = 9
输出: 45
限制：
1 <= n <= 10000
class Solution {
public int sumNums(int n) {
return n == 0 ? 0 : n + sumNums(n - 1);
}
}违规用for训练，快速乘了解一下
class Solution {
public int sumNums(int n) {
// 1+2+...+n = (n * (n + 1)) / 2
return quickMulti(n, n + 1);
}
int quickMulti(int A, int B) {
int ans = 0;
// 计算 n * (n + 1)
for (; B != 0; B >>= 1) {
if ((B & 1) > 0) {
ans += A;
}
A <<= 1;
}
return ans / 2;
}
}实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。
示例:
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 true
trie.search("app"); // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");
trie.search("app"); // 返回 true
说明:
你可以假设所有的输入都是由小写字母 a-z 构成的。
保证所有输入均为非空字符串。
class Trie {
/** Initialize your data structure here. */
public Trie() {
}
private class Node {
Node[] children = new Node[26];
boolean isLeaf;
}
private Node root = new Node();
/** Inserts a word into the trie. */
public void insert(String word) {
insert(word, root);
}
private void insert(String word, Node node) {
if (node == null) {
return;
}
if (word.length() == 0) {
node.isLeaf = true;
return;
}
int index = indexForChar(word.charAt(0));
if (node.children[index] == null) {
node.children[index] = new Node();
}
insert(word.substring(1), node.children[index]);
}
private int indexForChar(char c) {
return c - 'a';
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
return search(word, root);
}
private boolean search(String word, Node node) {
if (node == null) {
return false;
}
if (word.length() == 0) {
return node.isLeaf;
}
int index = indexForChar(word.charAt(0));
return search(word.substring(1), node.children[index]);
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
return startsWith(prefix, root);
}
private boolean startsWith(String prefix, Node node) {
if (node == null) {
return false;
}
if (prefix.length() == 0) {
return true;
}
int index = indexForChar(prefix.charAt(0));
return startsWith(prefix.substring(1), node.children[index]);
}
}
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.insert(word);
* boolean param_2 = obj.search(word);
* boolean param_3 = obj.startsWith(prefix);
*/