斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给你 n ，请计算 F(n) 。
class Solution {
public int fib(int n) {
if (n <= 1) {
return n;
}
int i = 0;
int j = 0;
int k = 1;
for (int index = 2; index <= n; index++) {
i = j;
j = k;
k = i + j;
}
return k;
}
}
给定一个单词，你需要判断单词的大写使用是否正确。
我们定义，在以下情况时，单词的大写用法是正确的：
否则，我们定义这个单词没有正确使用大写字母。
示例 1:
输入: "USA"
输出: True
class Solution {
public boolean detectCapitalUse(String word) {
int n = word.length();
if (n <= 1) {
return true;
}
int count = 0;
boolean first = false;
if (word.charAt(0) >= 'A' && word.charAt(0) <= 'Z'){
first = true;
}
for (int i = 0; i < n; i++) {
if (word.charAt(i) >= 'a' && word.charAt(i) <= 'z'){
count ++;
}
}
if (count == n || (first && count + 1 == n)|| count == 0) {
return true;
}
return false;
}
}
给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。
示例：
输入：
1
\
3
/
2
输出：
1
解释：
最小绝对差为 1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。
class Solution {
int pre = -1;
int ans = Integer.MAX_VALUE;
public int getMinimumDifference(TreeNode root) {
dfs(root);
return ans;
}
public void dfs(TreeNode root) {
if (root == null) {
return;
}
dfs(root.left);
if (pre == -1) {
pre = root.val;
} else {
ans = Math.min(ans, Math.abs(pre - root.val));
pre = root.val;
}
dfs(root.right);
}
}
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
示例 : 给定二叉树
1
/ \
2 3
/ \
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
class Solution {
int ans;
public int diameterOfBinaryTree(TreeNode root) {
depth(root);
return ans;
}
public int depth(TreeNode root) {
if (root == null) {
return 0;
}
int left = depth(root.left);
int right = depth(root.right);
ans = Math.max(ans, left + right);
return Math.max(left, right) + 1;
}
}
给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
示例：
输入："Let's take LeetCode contest"
输出："s'teL ekat edoCteeL tsetnoc"
class Solution {
public String reverseWords(String s) {
StringBuffer sb = new StringBuffer();
int n = s.length();
int i = 0;
while (i < n) {
int start = i;
while (i < n && s.charAt(i) != ' ') {
i++;
}
int end = i;
for (; end > start; end--) {
sb.append(s.charAt(end - 1));
}
sb.append(' ');
i++;
}
sb.delete(sb.length() - 1, sb.length());
return sb.toString();
}
}
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
进阶：
O(log n) 的算法解决此问题吗？示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
class Solution {
public int[] searchRange(int[] nums, int target) {
if (nums.length == 0) {
return new int[]{-1, -1};
}
int first = firstSearch(nums, target);
if (first == -1) {
return new int[]{-1, -1};
}
int last = lastSearch(nums, target);
return new int[]{first, last};
}
public int firstSearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
right = mid - 1;
}
else if (nums[mid] < target) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
if (left < nums.length && nums[left] == target)
return left;
return -1;
}
public int lastSearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
left = mid + 1;
}
else if (nums[mid] < target) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
if (right < nums.length && nums[right] == target)
return right;
return -1;
}
}