A project for arithmetic study , daily update
1.给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
2.给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
[73.Pow(x, n)](#73.Pow(x, n))
[75.779. 第K个语法符号](#75.779. 第K个语法符号)
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1: 输入: [3,2,3] 输出: 3
示例 2: 输入: [2,2,1,1,1,2,2] 输出: 2
解题：
public int majorityElement(int[] nums) {
//投票算法
int count = 1;
//将起始值作为计数开始的值
int temp = nums[0];
for (int i = 1; i < nums.length; i++) {
//若遇到一样的+1遇到不一样的-1
if (temp == nums[i]) {
count++;
} else {
count--;
}
if (count == 0) {
//当计数器重新为0的时候说明前面的数全都抵消，假设下一个数为众数。题目假设必有众数，也就是该数出现的次数比其他数加起来出现的次数都多
temp = nums[i + 1];
}
}
return temp;
}
优化后：
public int majorityElement(int[] nums) {
//投票算法
int count = 0;
//将起始值作为计数开始的值
Integer temp = null;
for (Integer num : nums) {
//若计数器为0，则将循环中的元素赋值给temp
if (count == 0) temp = num;
//计算count值，进行下一次轮询
count += temp.equals(num) ? 1 : -1;
}
return temp;
}
示例:
输入: [0,1,0,3,12] 输出: [1,3,12,0,0] 说明:
必须在原数组上操作，不能拷贝额外的数组。 尽量减少操作次数。
题解：
public void moveZeroes(int[] nums) {
//思路 1.使用index记录下当前不为0的数的位置
int index = 0;
for (Integer num : nums) {
if (num != 0) {
//将每个不等于0的数字按照顺序往数组中排列，并增加index值
nums[index++] = num;
}
}
//最后将index后面的值赋值为0
while (nums.length - index > 0) {
nums[index++] = 0;
}
}
找到所有在 [1, n] 范围之间没有出现在数组中的数字。
您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。
示例:
输入: [4,3,2,7,8,2,3,1]
输出: [5,6]
题解：
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> result = new ArrayList<>();
//思路：因为要求原地且要求0（N），所以暴力解法不符合要求
//遍历所有元素，以当前遍历到的值为数组的下标，将对应下标的值置成负数，遍历到的值使用绝对值去计算角标
for (Integer num: nums) {
//遍历所有元素，然后将对应下标的值置成负数
nums[Math.abs(num)-1] = -Math.abs(nums[Math.abs(num)-1]);
}
for (int i = 1; i <=nums.length; i++) {
//遍历所有值，发现值为正数值位置的角标即为数组中缺省的数字
if (nums[i-1]>0){
result.add(i);
}
}
return result;
}
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
示例 1:
输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。 示例 2:
输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。 进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
题解：
//寻找谷底谷峰[7,1,5,3,6,4],记录最大收益和最小价格，然后依次与当前价格和收益比较
public int maxProfit(int[] prices) {
if(prices.length<=0){
return 0;
}
//定义最大收益和最小价格
int max = 0;
int minPrice = prices[0];
for (int i = 1; i < prices.length; i++) {
if (prices[i] < minPrice) {
//如果当天的价格比最小价格还要小，赋值最小价格
minPrice = prices[i];
} else if (max < prices[i] - minPrice) {
max = prices[i] - minPrice;
}
}
return max;
}
题解：
public int maxSubArray(int[] nums) {
// 思路：贪心算法 设置最大和，和当前最大和，遍历
// 最大子序和[-2,1,-3,4,-1,2,1,-5,4]
int maxSum = nums[0];
int currentSum = nums[0];
for (int i = 1; i < nums.length; ++i) {
//若当前位置大于前面的和，指针就会移动到当前位置
currentSum = Math.max(currentSum + nums[i], nums[i]);
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
题解：
public int[] twoSum(int[] nums, int target) {
//使用hash表存储相应的数据，在一次遍历中根据遍历到的元素去哈希表中去查询是否有target-num[i]对应的值，如果有就是所需要的答案
int length = nums.length;
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < length; i++) {
if (map.containsKey(target - nums[i])) {
return new int[]{map.get(target - nums[i]),i};
} else {
map.put(nums[i],i);
}
}
return null;
}
给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
你找到的子数组应是最短的，请输出它的长度。
示例 1:
输入: [2, 6, 4, 8, 10, 9, 15] 输出: 5 解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。 说明 :
输入的数组长度范围在 [1, 10,000]。 输入的数组可能包含重复元素 ，所以升序的意思是<=。
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
public static int findUnsortedSubarray(int[] nums) {
//本题目查找的就是左边界和右边界的问题，
// 最开始的想法是使用两个循环一个正着找左边界，
// 一个倒着找右边界，后来发现可以合并为一个循环
int length = nums.length;
int max = nums[0];
int min = nums[length - 1];
int right = -1;
int left = 0;
for (int i = 0; i < length; i++) {
//如果右边有比max还大的值，则赋值给max,如果遇到了小于max的值说明顺序要调整
if (nums[i] >= max) {
max = nums[i];
} else {
right = i;
}
//同理找最小值和左边界
if (nums[length - i - 1] <= min) {
min = nums[length - i - 1];
} else {
left = length - i - 1;
}
}
return right - left + 1;
}
public List<List<Integer>> subsets(int[] nums) {
//思路 使用while循环控制当前添加进数组的长度 内循环for用来向数组中添加值
List<List<Integer>> result = new ArrayList<>();
result.add(new ArrayList<Integer>());
for (Integer n : nums) {
//内循环的循环次数，因为要从result取值，所以最大角标就是result的当前size
int size = result.size();
for (int i = 0; i < size; i++) {
//每次从result数组中添加轮训的值
List<Integer> list = new ArrayList<>(result.get(i));
list.add(n);
result.add(list);
}
}
return result;
}
public List<List<Integer>> subsets2(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
//二进制做法
//一共1<<nums.length个数
for (int i = 0; i <( 1 << nums.length); i++) {
List<Integer> list = new ArrayList<>();
for (int j = 0; j < nums.length; j++) {
//每次循环先找(i >> j) & 1为1的值若为1则添加进来
if (((i >> j) & 1) == 1) list.add(j);
}
result.add(list);
}
return result;
}
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。 解集不能包含重复的组合。 示例 1:
输入: candidates = [2,3,6,7], target = 7, 所求解集为: [ [7], [2,2,3] ] 示例 2:
输入: candidates = [2,3,5], target = 8, 所求解集为: [ [2,2,2,2], [2,3,3], [3,5] ]
题解： （39和40）题为类似问题，采用回溯算法的方式进行求解，解答的过程中采用画图的方式找到解答题目的思路，两道题目中唯一的不同点是一个可以使用重复的元素而一个不可以使用，这就使得这道题目的解题思路一致。
List<List<Integer>> result;
public List<List<Integer>> combinationSum(int[] candidates, int target) {
result = new ArrayList<>();
//边界条件判断
if (candidates == null || candidates.length <= 0) {
return result;
}
Arrays.sort(candidates);
List<Integer> list = new ArrayList<>();
helper(candidates, list, 0, target);
return result;
}
public void helper(int[] cadidaes, List<Integer> list, int index, int target) {
if (target == 0) {
result.add(new ArrayList<>(list));
return;
}
for (int i = index; i < cadidaes.length && target >= cadidaes[i]; i++) {
list.add(cadidaes[i]);
//遍历过程中采用重复的元素
helper(cadidaes, list, i, target - cadidaes[i]);
list.remove(list.size()-1);
}
}
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
所有数字（包括目标数）都是正整数。 解集不能包含重复的组合。 示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8, 所求解集为: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ] 示例 2:
输入: candidates = [2,5,2,1,2], target = 5, 所求解集为: [ [1,2,2], [5] ]
List<List<Integer>> result;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
result = new ArrayList<>();
if (candidates == null || candidates.length <= 0) {
return result;
}
Arrays.sort(candidates);
helper2(candidates, new ArrayList<Integer>(), 0, target);
return result;
}
public void helper2(int[] cadidaes, List<Integer> list, int index, int target) {
if (target == 0) {
if (!result.contains(list)) {
result.add(new ArrayList<>(list));
}
return;
}
for (int i = index; i < cadidaes.length && target >= cadidaes[i]; i++) {
list.add(cadidaes[i]);
//遍历过程中不采用重复的元素，将index移动到下个元素
helper2(cadidaes, list, ++index, target - cadidaes[i]);
list.remove(list.size() - 1);
}
}
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: [1,2,2] 输出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]
public List<List<Integer>> subsetsWithDup(int[] num) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
List<Integer> empty = new ArrayList<Integer>();
result.add(empty);
Arrays.sort(num);
for (int i = 0; i < num.length; i++) {
int dupCount = 0;
//判断当前是否是重复数字，并且记录重复的次数
while( ((i+1) < num.length) && num[i+1] == num[i]) {
dupCount++;
i++;
}
int prevNum = result.size();
//遍历之前几个结果的每个解
for (int j = 0; j < prevNum; j++) {
List<Integer> element = new ArrayList<Integer>(result.get(j));
//每次在上次的结果中多加 1 个重复数字
for (int t = 0; t <= dupCount; t++) {
element.add(num[i]); //加入当前重复的数字
result.add(new ArrayList<Integer>(element));
}
}
}
return result;
}
给定一个没有重复数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
public void backtrack(int[] nums, int length, List<Integer> list, List<List<Integer>> output, int depth, boolean[] used) {
if (depth == length) {
//当深度和长度一样的时候则，就是答案
output.add(new ArrayList<>(list));
return;
}
for (int i = 0; i < length; i++) {
if (!used[i]) {
//如果当前没有用过，则进入下一层
list.add(nums[i]);
used[i] = true;
backtrack(nums, length, list, output, depth + 1, used);
//回溯
used[i] = false;
list.remove(depth);
}
}
}
public List<List<Integer>> permute(int[] nums) {
int length = nums.length;
List<List<Integer>> output = new LinkedList<>();
ArrayList<Integer> nums_lst = new ArrayList<>();
boolean[] used = new boolean[length];
backtrack(nums, length, nums_lst, output, 0, used);
return output;
}
给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例:
输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1] ]
public static List<List<Integer>> permuteUnique(int[] nums) {
//先排列出所有的可能,和上一题相比较只是多了一步去重工作
List<List<Integer>> result = new ArrayList<>();
List<Integer> list = new ArrayList<>();
//是否使用过当前节点深度
int length = nums.length;
boolean[] isUsed = new boolean[length];
helper(nums, length, result, list, isUsed, 0);
return result;
}
private static void helper(int[] nums, int length, List<List<Integer>> result, List<Integer> list, boolean[] isUsed, int depth) {
ArrayList<Integer> element = new ArrayList<>(list);
//去重元素
if (length == depth && !result.contains(element)) {
result.add(element);
return;
}
for (int i = 0; i < length; i++) {
if (!isUsed[i]) {
list.add(nums[i]);
isUsed[i] = true;
helper(nums, length, result, list, isUsed, depth + 1);
isUsed[i] = false;
list.remove(depth);
}
}
}
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
示例 1:
输入:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
输出:
合并后的树:
3
/
4 5
/ \ \
5 4 7
注意: 合并必须从两个树的根节点开始。
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if (t1 == null)
return t2;
if (t2 == null)
return t1;
t1.val += t2.val;
t1.left = mergeTrees(t1.left, t2.left);
t1.right = mergeTrees(t1.right, t2.right);
return t1;
}
给你一个整数 n，请你帮忙计算并返回该整数「各位数字之积」与「各位数字之和」的差。
示例 1：
输入：n = 234 输出：15 解释： 各位数之积 = 2 * 3 * 4 = 24 各位数之和 = 2 + 3 + 4 = 9 结果 = 24 - 9 = 15 示例 2：
输入：n = 4421 输出：21 解释： 各位数之积 = 4 * 4 * 2 * 1 = 32 各位数之和 = 4 + 4 + 2 + 1 = 11 结果 = 32 - 11 = 21
提示：
1 <= n <= 10^5
//这种题目才配叫做简单
public int subtractProductAndSum(int n) {
int product = 1;
int plus = 0;
while (n/10 > 0) {
int num = n % 10;
product *= num;
plus += num;
n = n / 10;
if (n < 10) {
int i = product * n - plus - n;
return i;
}
}
return 0;
}
给你一个整数数组 nums，请你返回其中位数为 偶数 的数字的个数。
示例 1：
输入：nums = [12,345,2,6,7896] 输出：2 解释： 12 是 2 位数字（位数为偶数） 345 是 3 位数字（位数为奇数） 2 是 1 位数字（位数为奇数） 6 是 1 位数字 位数为奇数） 7896 是 4 位数字（位数为偶数） 因此只有 12 和 7896 是位数为偶数的数字 示例 2：
输入：nums = [555,901,482,1771] 输出：1 解释： 只有 1771 是位数为偶数的数字。
提示：
1 <= nums.length <= 500 1 <= nums[i] <= 10^5
//思路1：由于题目很简单，思路也比较清晰，可以先将数字转成字符串然后用字符串的长度判断即可
//思路2：log以10为底去计算num的出来的数字+1即为位数，效率会比转换成字符串效率高，也是判断一个数字位数比较好的计算方法
//思路3：因为直接给出了范围，直接用范围去判断对于这个题目也是可以的，但是不推荐
public int findNumbers(int[] nums) {
int count = 0;
for (Integer num : nums) {
if (String.valueOf(num).length() % 2 == 0) {
count++;
}
}
return count;
}
给你一个仅由数字 6 和 9 组成的正整数 num。
你最多只能翻转一位数字，将 6 变成 9，或者把 9 变成 6 。
请返回你可以得到的最大数字。
示例 1：
输入：num = 9669 输出：9969 解释： 改变第一位数字可以得到 6669 。 改变第二位数字可以得到 9969 。 改变第三位数字可以得到 9699 。 改变第四位数字可以得到 9666 。 其中最大的数字是 9969 。 示例 2：
输入：num = 9996 输出：9999 解释：将最后一位从 6 变到 9，其结果 9999 是最大的数。 示例 3：
输入：num = 9999 输出：9999 解释：无需改变就已经是最大的数字了。
提示：
1 <= num <= 10^4 num 每一位上的数字都是 6 或者 9 。
//思路： 替换第一个数字为9
public int maximum69Number (int num) {
String str = String.valueOf(num);
str = str.replaceFirst("6", "9");
return Integer.valueOf(str);
}
平面上有 n 个点，点的位置用整数坐标表示 points[i] = [xi, yi]。请你计算访问所有这些点需要的最小时间（以秒为单位）。
你可以按照下面的规则在平面上移动：
每一秒沿水平或者竖直方向移动一个单位长度，或者跨过对角线（可以看作在一秒内向水平和竖直方向各移动一个单位长度）。 必须按照数组中出现的顺序来访问这些点。
示例 1：
输入：points = [[1,1],[3,4],[-1,0]]
输出：7
解释：一条最佳的访问路径是： [1,1] -> [2,2] -> [3,3] -> [3,4] -> [2,3] -> [1,2] -> [0,1] -> [-1,0]
从 [1,1] 到 [3,4] 需要 3 秒
从 [3,4] 到 [-1,0] 需要 4 秒
一共需要 7 秒
示例 2：
输入：points = [[3,2],[-2,2]] 输出：5
提示：
points.length == n 1 <= n <= 100 points[i].length == 2 -1000 <= points[i][0], points[i][1] <= 1000
public int minTimeToVisitAllPoints(int[][] points) {
//思路：根据画图得知，两点之间的距离由，两个点的x的差值和y的差值比较大的决定，
// 因为要按照数组顺序进行计算距离，所以，遍历所有点分别求出各个点之间的距离后相加
int startX = points[0][0];
int startY = points[0][1];
int disance = 0;
for (int i = 1; i < points.length; i++) {
disance += Math.max(Math.abs(points[i][0] - startX), Math.abs(points[i][1] - startY));
startX = points[i][0];
startY = points[i][1];
}
return disance;
}
给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。
请你返回该链表所表示数字的 十进制值 。
示例 1：
输入：head = [1,0,1] 输出：5 解释：二进制数 (101) 转化为十进制数 (5) 示例 2：
输入：head = [0] 输出：0 示例 3：
输入：head = [1] 输出：1 示例 4：
输入：head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0] 输出：18880 示例 5：
输入：head = [0,0] 输出：0
提示：
链表不为空。 链表的结点总数不超过 30。 每个结点的值不是 0 就是 1。
public int getDecimalValue(ListNode head) {
ListNode node = head;
int result = 0;
while (node != null) {
result = (result << 1) + node.val;
node = node.next;
}
return result;
}
在一个「平衡字符串」中，'L' 和 'R' 字符的数量是相同的。
给出一个平衡字符串 s，请你将它分割成尽可能多的平衡字符串。
返回可以通过分割得到的平衡字符串的最大数量。
示例 1：
输入：s = "RLRRLLRLRL" 输出：4 解释：s 可以分割为 "RL", "RRLL", "RL", "RL", 每个子字符串中都包含相同数量的 'L' 和 'R'。 示例 2：
输入：s = "RLLLLRRRLR" 输出：3 解释：s 可以分割为 "RL", "LLLRRR", "LR", 每个子字符串中都包含相同数量的 'L' 和 'R'。 示例 3：
输入：s = "LLLLRRRR" 输出：1 解释：s 只能保持原样 "LLLLRRRR".
提示：
1 <= s.length <= 1000 s[i] = 'L' 或 'R'
public int balancedStringSplit(String s) {
int count = 0;
int result = 0;
char[] chars = s.toCharArray();
for (int i = 0; i < chars.length; i++) {
if (String.valueOf(chars[i]).equals("R")) {
count++;
} else {
count--;
}
if (count == 0) {
result++;
}
}
return result;
}
翻转一棵二叉树。
示例：
输入：
4
/
2 7
/ \ /
1 3 6 9
输出：
4
/
7 2
/ \ /
9 6 3 1
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/invert-binary-tree
//思路：从根节点向下一次交换左右节点就可以翻转这棵树
public TreeNode invertTree(TreeNode root) {
if(root == null){
return null;
}
//交换节点
TreeNode temp;
temp = root.left;
root.left = root.right;
root.right = temp;
if (root.left != null) {
invertTree(root.left);
}
if (root.right != null) {
invertTree(root.right);
}
return root;
}
给定二叉搜索树的根结点 root，返回 L 和 R（含）之间的所有结点的值的和。
二叉搜索树保证具有唯一的值。
示例 1：
输入：root = [10,5,15,3,7,null,18], L = 7, R = 15 输出：32 示例 2：
输入：root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10 输出：23
提示：
树中的结点数量最多为 10000 个。 最终的答案保证小于 2^31。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/range-sum-of-bst
public int rangeSumBST(TreeNode root, int L, int R) {
if (root == null) {
return 0;
}
int result = 0;
if (root.val >= L && root.val <= R) {
//累加结果并向下查找合适的值
result = root.val + rangeSumBST(root.left, L, R) + rangeSumBST(root.right, L, R);
} else if (root.val < L) {
//往子树的右边查找
return rangeSumBST(root.right,L,R);
}else {
//往子树的左边查找
return rangeSumBST(root.left,L,R);
}
return result;
}
给你一个整数 n，请你返回 任意 一个由 n 个 各不相同 的整数组成的数组，并且这 n 个数相加和为 0 。
示例 1：
输入：n = 5 输出：[-7,-1,1,3,4] 解释：这些数组也是正确的 [-5,-1,1,2,3]，[-3,-1,2,-2,4]。 示例 2：
输入：n = 3 输出：[-1,0,1] 示例 3：
输入：n = 1 输出：[0]
提示：
1 <= n <= 1000
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/find-n-unique-integers-sum-up-to-zero
public int[] sumZero(int n) {
//思路 在循环中一直添加相反数，如果是奇数个的话就将最后一个赋值为0
int[] result = new int[n];
for (int i = 0; i < n; i++) {
if (i % 2 == 0) {
result[i] = i + 1;
} else {
result[i] = -i;
}
}
if (n % 2 != 0) {
result[n - 1] = 0;
}
return result;
}
自除数 是指可以被它包含的每一位数除尽的数。
例如，128 是一个自除数，因为 128 % 1 == 0，128 % 2 == 0，128 % 8 == 0。
还有，自除数不允许包含 0 。
给定上边界和下边界数字，输出一个列表，列表的元素是边界（含边界）内所有的自除数。
示例 1：
输入： 上边界left = 1, 下边界right = 22 输出： [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22] 注意：
每个输入参数的边界满足 1 <= left <= right <= 10000。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/self-dividing-numbers
public List<Integer> selfDividingNumbers(int left, int right) {
List<Integer> ans = new ArrayList();
for (int n = left; n <= right; ++n) {
if (selfDividing(n)) ans.add(n);
}
return ans;
}
public boolean selfDividing(int n) {
for (char c: String.valueOf(n).toCharArray()) {
if (c == '0' || (n % (c - '0') > 0))
return false;
}
return true;
}
国际摩尔斯密码定义一种标准编码方式，将每个字母对应于一个由一系列点和短线组成的字符串， 比如: "a" 对应 ".-", "b" 对应 "-...", "c" 对应 "-.-.", 等等。
为了方便，所有26个英文字母对应摩尔斯密码表如下：
[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."] 给定一个单词列表，每个单词可以写成每个字母对应摩尔斯密码的组合。例如，"cab" 可以写成 "-.-..--..."，(即 "-.-." + "-..." + ".-"字符串的结合)。我们将这样一个连接过程称作单词翻译。
返回我们可以获得所有词不同单词翻译的数量。
例如: 输入: words = ["gin", "zen", "gig", "msg"] 输出: 2 解释: 各单词翻译如下: "gin" -> "--...-." "zen" -> "--...-." "gig" -> "--...--." "msg" -> "--...--."
共有 2 种不同翻译, "--...-." 和 "--...--.".
注意:
单词列表words 的长度不会超过 100。 每个单词 words[i]的长度范围为 [1, 12]。 每个单词 words[i]只包含小写字母。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/unique-morse-code-words
//思路：使用hashset进行排重，剩下的就是结果
private static String[] map = {
".-",
"-...",
"-.-.",
"-..",
".",
"..-.",
"--.",
"....",
"..",
".---",
"-.-",
".-..",
"--",
"-.",
"---",
".--.",
"--.-",
".-.",
"...",
"-",
"..-",
"...-",
".--",
"-..-",
"-.--",
"--.."
};
public int uniqueMorseRepresentations(String[] words) {
if (words == null) return 0;
HashSet<String> set = new HashSet<String>();
for (String s : words) {
StringBuilder sb = new StringBuilder();
for (char c : s.toCharArray()) {
sb.append(map[c - 'a']);
}
set.add(sb.toString());
}
return set.size();
}
给你一个数组 arr ，请你将每个元素用它右边最大的元素替换，如果是最后一个元素，用 -1 替换。
完成所有替换操作后，请你返回这个数组。
示例：
输入：arr = [17,18,5,4,6,1] 输出：[18,6,6,6,1,-1]
提示：
1 <= arr.length <= 10^4 1 <= arr[i] <= 10^5
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/replace-elements-with-greatest-element-on-right-side
public int[] replaceElements(int[] arr) {
int max = arr[arr.length - 1];
arr[arr.length - 1] = -1;
for (int i = arr.length - 2; i >= 0; i--) {
int temp = arr[i];
arr[i] = max;
if (temp > max) max = temp;
}
return arr;
}
给定一个正整数，输出它的补数。补数是对该数的二进制表示取反。
注意:
给定的整数保证在32位带符号整数的范围内。 你可以假定二进制数不包含前导零位。 示例 1:
输入: 5 输出: 2 解释: 5的二进制表示为101（没有前导零位），其补数为010。所以你需要输出2。 示例 2:
输入: 1 输出: 0 解释: 1的二进制表示为1（没有前导零位），其补数为0。所以你需要输出0。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/number-complement
public int findComplement(int num) {
//通过异或运算
int temp = num;
int temp2 = 1;
while (temp > 0) {
temp >>= 1;
temp2 <<= 1;
}
temp2 -= 1;
return num ^ temp2;
}
给定只含 "I"（增大）或 "D"（减小）的字符串 S ，令 N = S.length。
返回 [0, 1, ..., N] 的任意排列 A 使得对于所有 i = 0, ..., N-1，都有：
如果 S[i] == "I"，那么 A[i] < A[i+1] 如果 S[i] == "D"，那么 A[i] > A[i+1]
示例 1：
输出："IDID" 输出：[0,4,1,3,2] 示例 2：
输出："III" 输出：[0,1,2,3] 示例 3：
输出："DDI" 输出：[3,2,0,1]
提示：
1 <= S.length <= 1000 S 只包含字符 "I" 或 "D"。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/di-string-match
//思路： 通过观察可以确定的是最大值可以设置为string的长度，最小值为0
遇到'I'就增长一个，遇到'D'就减小一个就可以得到所需要的数组
public int[] diStringMatch(String s) {
int length = s.length();
int max = length;
int min = 0;
int[] result = new int[length + 1];
for (int i = 0; i < length; i++) {
if (s.charAt(i) == 'I') {
result[i] = min++;
} else {
result[i] = max--;
}
}
result[length] = min;
return result;
}
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/reverse-linked-list
//定义翻转链表的头结点
ListNode pre = null;
ListNode current = head;
//定义临时结点
ListNode temp = current.next;
while (current != null) {
//让当前节点指向上一个节点
current.next = pre;
//pre 节点往前走一个节点
pre = current;
//current节点也往前走一个节点
current = temp;
}
//返回翻转后的链表的头结点
return pre;
public ListNode reverseList(ListNode head) {
//再次做到了反转链表的题目，递归的算法，相当于，假设我的子节点都已经完成了反转，就只剩下我自己和子节点进行反转了所以node.next.next = node;然后再断开node.next = null;
if(head == null || head.next == null )return head;
ListNode temp =reverseList(head.next);
head.next.next = head;
head.next = null;
return temp;
}
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。 写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。
进阶:
你是否可以在 O(1) 时间复杂度内完成这两种操作？
示例:
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
cache.put(1, 1); cache.put(2, 2); cache.get(1); // 返回 1 cache.put(3, 3); // 该操作会使得密钥 2 作废 cache.get(2); // 返回 -1 (未找到) cache.put(4, 4); // 该操作会使得密钥 1 作废 cache.get(1); // 返回 -1 (未找到) cache.get(3); // 返回 3 cache.get(4); // 返回 4
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/lru-cache
class LRUCache extends LinkedHashMap<Integer,Integer> {
private int capacity;
public LRUCache(int capacity) {
super(capacity,0.75f,true);
this.capacity = capacity;
}
public int get(int key) {
return super.getOrDefault(key,-1);
}
public void put(int key, int value) {
super.put(key,value);
}
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity;
}
}
给定两个数组，编写一个函数来计算它们的交集。
示例 1:
输入: nums1 = [1,2,2,1], nums2 = [2,2] 输出: [2] 示例 2:
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出: [9,4] 说明:
输出结果中的每个元素一定是唯一的。 我们可以不考虑输出结果的顺序。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/intersection-of-two-arrays
public int[] intersection(int[] nums1, int[] nums2) {
HashSet<Integer> set1 = new HashSet<Integer>();
for (Integer n : nums1) set1.add(n);
HashSet<Integer> set2 = new HashSet<Integer>();
for (Integer n : nums2) set2.add(n);
set1.retainAll(set2);
int [] output = new int[set1.size()];
int idx = 0;
for (int s : set1) output[idx++] = s;
return output;
}
在大小为 2N 的数组 A 中有 N+1 个不同的元素，其中有一个元素重复了 N 次。
返回重复了 N 次的那个元素。
示例 1：
输入：[1,2,3,3] 输出：3 示例 2：
输入：[2,1,2,5,3,2] 输出：2 示例 3：
输入：[5,1,5,2,5,3,5,4] 输出：5
提示：
4 <= A.length <= 10000 0 <= A[i] < 10000 A.length 为偶数
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/n-repeated-element-in-size-2n-array
//思路比较简单，如果是数组中一半的元素都是相同的数字，那么无论怎么排列都会有一组连续三个数字其中有两个是相同的，如果没有就是最后两个
public int repeatedNTimes(int[] A) {
for (int i = 0; i < A.length - 2; i++) {
if (A[i] == A[i + 1] || A[i] == A[i + 2]) {
return A[i];
}
}
return A[A.length - 1];
}
给定一个按非递减顺序排序的整数数组 A，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。
示例 1：
输入：[-4,-1,0,3,10] 输出：[0,1,9,16,100] 示例 2：
输入：[-7,-3,2,3,11] 输出：[4,9,9,49,121]
提示：
1 <= A.length <= 10000 -10000 <= A[i] <= 10000 A 已按非递减顺序排序。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/squares-of-a-sorted-array
public static int[] sortedSquares(int[] nums) {
//双指针法，声明首位两个指针，然后判断平方的大小再插入新的数组中
int start = 0;
int length = nums.length;
int end = length - 1;
int[] result = new int[length];
for (int i = 0; i < length ; i++) {
if (nums[start] * nums[start] > nums[end] * nums[end]) {
result[length - i - 1] = nums[start] * nums[start++];
} else {
result[length - i - 1] = nums[end] * nums[end--];
}
}
return result;
}
斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1. 给定 N，计算 F(N)。
示例 1：
输入：2 输出：1 解释：F(2) = F(1) + F(0) = 1 + 0 = 1. 示例 2：
输入：3 输出：2 解释：F(3) = F(2) + F(1) = 1 + 1 = 2. 示例 3：
输入：4 输出：3 解释：F(4) = F(3) + F(2) = 2 + 1 = 3.
提示：
0 ≤ N ≤ 30
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/fibonacci-number
public int fib(int num) {
if (num == 0 || num == 1) {
return num;
} else {
return fib(num - 1) + fib(num - 2);
}
}
编写一个程序，找到两个单链表相交的起始节点。
如下面的两个链表：
在节点 c1 开始相交。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 输出：Reference of the node with value = 8 输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
示例 2：
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 输出：Reference of the node with value = 2 输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 输出：null 输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。 解释：这两个链表不相交，因此返回 null。
注意：
如果两个链表没有交点，返回 null. 在返回结果后，两个链表仍须保持原有的结构。 可假定整个链表结构中没有循环。 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
来源：力扣（LeetCode）/题目中有图片可以参考链接 链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists
/**
* 1-2-3-4-5-6-7
* |
* 8
* 如上两个相交的链表，如果相交那么分辨用两个指针，当指针1从A的头开始走，走到尾的时候接上B的头继续走，如果相交则指针也会相交
* 有点像赛跑，两人路程一样，速度一样，如果有焦点，那么必定有一段路程是一起走的
* */
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode p1 = headA;
ListNode p2 = headB;
while (p1 != p2) {
p1 = p1==null?p2:p1.next;
p2 = p2==null?p1:p2.next;
}
return p1;
}
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/merge-two-sorted-lists
//采用递归的方式进行拼接
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null) {
return l2;
}
if(l2 == null) {
return l1;
}
if(l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。
示例：
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof
//思路：比较蠢想了两个，一个是先测量出来链表长度，返回长度-k的那段链表，另一个是翻转链表然后正着数k个然后再翻转回来
其实最简单的是双指针算法，指定两个指针，让其中一个先走K步，直到为null的这段就是结果
虽然蠢但是也通过了时间复杂度O(N)
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode temp = head;
ListNode result = null;
int index = 1;
while (temp.next != null) {
temp = temp.next;
index++;
}
if(index == k){
return head;
}
for (int i = 0; i < index - k; i++) {
result = head.next;
head = head.next;
}
return result;
}
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2 输出： 2 解释： 有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶 示例 2：
输入： 3 输出： 3 解释： 有三种方法可以爬到楼顶。
- 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 2 阶 + 1 阶
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/climbing-stairs
//思路：此题使用递归会超时，故采用动态规划，使用数组存储每一级台阶的可能性
//爬楼梯 到达第n层，可以分解为到达第n-1层和到达第n-2层之和也就是
// p(n) = p(n-1)+p(n-2)，因为楼梯的走法有走一步和走两步这种。
public int climbStairs(int n) {
//递归
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
return climbStairs(n - 1) + climbStairs(n - 2);
}
//剪枝
public class Solution {
public int climbStairs(int n) {
int memo[] = new int[n + 1];
return climb_Stairs(0, n, memo);
}
public int climb_Stairs(int i, int n, int memo[]) {
if (i > n) {
return 0;
}
if (i == n) {
return 1;
}
if (memo[i] > 0) {
return memo[i];
}
memo[i] = climb_Stairs(i + 1, n, memo) + climb_Stairs(i + 2, n, memo);
return memo[i];
}
}
public int climbStairs(int n) {
//动态规划
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
//记忆化递归，使用map存储计算过的值，这样就可以减少同样的值得计算。
public int climbStairs(int n) {
return helper(n,new HashMap<Integer, Integer>());
}
public int helper(int n, HashMap<Integer, Integer> cache) {
if (n < 3) return n;
if (cache.containsKey(n)) return cache.get(n);
int value = helper(n - 1, cache) + helper(n - 2, cache);
cache.put(n, value);
return value;
}
实现一个算法，确定一个字符串 s 的所有字符是否全都不同。
示例 1：
输入: s = "leetcode" 输出: false 示例 2：
输入: s = "abc" 输出: true 限制：
0 <= len(s) <= 100 如果你不使用额外的数据结构，会很加分。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/is-unique-lcci
public boolean isUnique(String str) {
char[] chars = str.toCharArray();
for (int i = 0; i < chars.length; i++) {
if (str.indexOf(String.valueOf(chars[i])) != str.lastIndexOf(String.valueOf(chars[i]))){
return false;
}
}
return true;
}
给定两个字符串 s1 和 s2，请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。
示例 1：
输入: s1 = "abc", s2 = "bca" 输出: true 示例 2：
输入: s1 = "abc", s2 = "bad" 输出: false 说明：
0 <= len(s1) <= 100 0 <= len(s2) <= 100
//思路:转成数组后排序然后再对比字符串，相等则为true
//也可以转成数组，循环来判断是否相等
public boolean CheckPermutation(String s1, String s2) {
char[] chars1 = s1.toCharArray();
char[] chars2 = s2.toCharArray();
Arrays.sort(chars1);
Arrays.sort(chars2);
return String.valueOf(chars1).equals(String.valueOf(chars2));
}
给你两个数组，arr1 和 arr2，
arr2 中的元素各不相同 arr2 中的每个元素都出现在 arr1 中 对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
示例：
输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6] 输出：[2,2,2,1,4,3,3,9,6,7,19]
提示：
arr1.length, arr2.length <= 1000 0 <= arr1[i], arr2[i] <= 1000 arr2 中的元素 arr2[i] 各不相同 arr2 中的每个元素 arr2[i] 都出现在 arr1 中
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/relative-sort-array
public int[] relativeSortArray(int[] arr1, int[] arr2) {
int[] m = new int[1001];
int[] ref = new int[arr1.length];
for(int i = 0; i < arr1.length; i++) {
m[arr1[i]]++;
}
int cnt = 0;
for(int i = 0; i < arr2.length; i++) {
while(m[arr2[i]] > 0) {
ref[cnt++] = arr2[i];
m[arr2[i]]--;
}
}
for(int i = 0; i < 1001; i++) {
while(m[i] > 0) {
ref[cnt++] = i;
m[i]--;
}
}
return ref;
}
给定一个偶数长度的数组，其中不同的数字代表着不同种类的糖果，每一个数字代表一个糖果。你需要把这些糖果平均分给一个弟弟和一个妹妹。返回妹妹可以获得的最大糖果的种类数。
示例 1:
输入: candies = [1,1,2,2,3,3] 输出: 3 解析: 一共有三种种类的糖果，每一种都有两个。 最优分配方案：妹妹获得[1,2,3],弟弟也获得[1,2,3]。这样使妹妹获得糖果的种类数最多。 示例 2 :
输入: candies = [1,1,2,3] 输出: 2 解析: 妹妹获得糖果[2,3],弟弟获得糖果[1,1]，妹妹有两种不同的糖果，弟弟只有一种。这样使得妹妹可以获得的糖果种类数最多。 注意:
数组的长度为[2, 10,000]，并且确定为偶数。 数组中数字的大小在范围[-100,000, 100,000]内。
//思路：排序后查找不一样的数
public int distributeCandies(int[] candies) {
Arrays.sort(candies);
int count = 1;
for (int i = 1; i < candies.length && count < candies.length / 2; i++)
if (candies[i] > candies[i - 1])
count++;
return count;
}
作者：LeetCode
链接：https://leetcode-cn.com/problems/distribute-candies/solution/fen-tang-guo-by-leetcode/
来源：力扣（LeetCode）
输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
示例 1：
输入：nums = [2,7,11,15], target = 9 输出：[2,7] 或者 [7,2] 示例 2：
输入：nums = [10,26,30,31,47,60], target = 40 输出：[10,30] 或者 [30,10]
限制：
1 <= nums.length <= 10^5 1 <= nums[i] <= 10^6
public int[] twoSum(int[] nums, int target) {
int left=0,right=nums.length-1;
int [] res=new int[2];
while(left<right){
if (nums[left]+nums[right]==target){
res[0]=nums[left];
res[1]=nums[right];
return res;
}
else if (nums[left]+nums[right]<target)
left++;
else
right--;
}
return res;
}
作者：wei-yu-13
链接：https://leetcode-cn.com/problems/he-wei-sde-liang-ge-shu-zi-lcof/solution/2msshuang-100-by-wei-yu-13/
来源：力扣（LeetCode）
给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
说明： 你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。
示例 1:
输入: root = [3,1,4,null,2], k = 1
3
/
1 4
2
输出: 1
示例 2:
输入: root = [5,3,6,2,4,null,null,1], k = 3
5
/
3 6
/
2 4
/
1
输出: 3
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst
//思路，先进行中序遍历，得到排序好的数组，然后第k-1个就是所找的答案
public int kthSmallest(TreeNode root, int k) {
List<Integer> result = inOrder(root,new ArrayList<Integer>());
return result.get(k-1);
}
public ArrayList<Integer> inOrder(TreeNode node, ArrayList<Integer> arrs) {
if (node == null) return arrs;
inOrder(node.left, arrs);
arrs.add(node.val);
inOrder(node.right, arrs);
return arrs;
}
小A 和 小B 在玩猜数字。小B 每次从 1, 2, 3 中随机选择一个，小A 每次也从 1, 2, 3 中选择一个猜。他们一共进行三次这个游戏，请返回 小A 猜对了几次？
输入的guess数组为 小A 每次的猜测，answer数组为 小B 每次的选择。guess和answer的长度都等于3。
示例 1：
输入：guess = [1,2,3], answer = [1,2,3] 输出：3 解释：小A 每次都猜对了。
示例 2：
输入：guess = [2,2,3], answer = [3,2,1] 输出：1 解释：小A 只猜对了第二次。
限制：
guess的长度 = 3 answer的长度 = 3 guess的元素取值为 {1, 2, 3} 之一。 answer的元素取值为 {1, 2, 3} 之一。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/guess-numbers
//两个相同的数字亦或后等于0
public int game(int[] guess, int[] answer) {
if (guess == null) return 0;
int result = 0;
for (int i = 0; i < guess.length; i++) {
if ((guess[i] ^ answer[i]) == 0) result++;
}
return result;
}
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12] 输出: [1,3,12,0,0] 说明:
必须在原数组上操作，不能拷贝额外的数组。 尽量减少操作次数。
public void moveZeroes(int[] nums) {
int index = 0;
int length = nums.length;
for (int i = 0; i < length; i++) {
if (nums[i] != 0) {
nums[index++] = nums[i];
}
}
for (int i = 0; i < length - index; i++) {
nums[length - i - 1] = 0;
}
}
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
示例 1：
输入：["h","e","l","l","o"] 输出：["o","l","l","e","h"] 示例 2：
输入：["H","a","n","n","a","h"] 输出：["h","a","n","n","a","H"]
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/reverse-string
//思路1：类似于双指针法，将首位的两个字段相互调换
public void reverseString(char[] s) {
int length = s.length;
for (int i = 0; i < length / 2; i++) {
char temp;
temp = s[i];
s[i] = s[length - i - 1];
s[length - i - 1] = temp;
}
}
//思路2：使用递归从两头开始交换，交换完成后将指针进行加减，再次调用自己
public void reverseString(char[] s) {
helper(s, 0, s.length - 1);
}
private void helper(char[] s, int left, int right) {
if (left >= right) return;
char temp = s[left];
s[left++] = s[right];
s[right--] = temp;
helper(s, left, right);
}
给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。
换而言之，对于每个 nums[i] 你必须计算出有效的 j 的数量，其中 j 满足 j != i 且 nums[j] < nums[i] 。
以数组形式返回答案。
示例 1：
输入：nums = [8,1,2,2,3] 输出：[4,0,1,1,3] 解释： 对于 nums[0]=8 存在四个比它小的数字：（1，2，2 和 3）。 对于 nums[1]=1 不存在比它小的数字。 对于 nums[2]=2 存在一个比它小的数字：（1）。 对于 nums[3]=2 存在一个比它小的数字：（1）。 对于 nums[4]=3 存在三个比它小的数字：（1，2 和 2）。 示例 2：
输入：nums = [6,5,4,8] 输出：[2,1,0,3] 示例 3：
输入：nums = [7,7,7,7] 输出：[0,0,0,0]
提示：
2 <= nums.length <= 500 0 <= nums[i] <= 100
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/how-many-numbers-are-smaller-than-the-current-number
public int[] smallerNumbersThanCurrent(int[] nums) {
int len = nums.length;
int[] res = new int[len];
for (int i = 0; i < len; i++) { // 枚举所有元素
for (int j = 0; j < len; j++) { // 枚举其他元素
if (i == j) continue;
if (nums[i] > nums[j]) res[i]++;
}
}
return res;
}
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。
示例 1：
输入: s = "abcdefg", k = 2 输出: "cdefgab" 示例 2：
输入: s = "lrloseumgh", k = 6 输出: "umghlrlose"
限制：
1 <= k < s.length <= 10000
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof
public String reverseLeftWords(String s, int n) {
return s.substring(n)+s.substring(0,n);
}
给定两个排序后的数组 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]
public void merge(int[] A, int m, int[] B, int n) {
if (m >= 0 && n >= 0) {
for (int i = 0; i < n; i++) {
A[m + i ] = B[n - i - 1];
}
Arrays.sort(A);
}
}
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入： [2, 3, 1, 0, 2, 5, 3] 输出：2 或 3
限制：
2 <= n <= 100000
//使用hashset进行判重，如果之前有重复的数字添加进来，则返回false,这时候将重复的数字返回回去即可。
public int findRepeatNumber(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
if (!set.add(nums[i])) return nums[i];
}
return 0;
}
给定一个 N 叉树，找到其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
例如，给定一个 3叉树 :
我们应返回其最大深度，3。
说明:
树的深度不会超过 1000。 树的节点总不会超过 5000。 结合求数的最大深度的递归方法，得出，如果不仅仅有左右子孩子，则考虑分别求出每个孩子对应的最大深度就是树的最大深度。
public int maxDepth(Node root) {
if (root == null) {
return 0;
}
int leftHeight = maxDepth(root.left);
int rightHeight = maxDepth(root.right);
return Math.max(leftHeight,rightHeight)+1;
}
作者：cool_tang123 链接：https://leetcode-cn.com/problems/maximum-depth-of-n-ary-tree/solution/di-gui-qiu-jie-by-cool_tang123/ 来源：力扣（LeetCode）
public int maxDepth(Node root) {
if (root == null) {
return 0;
}
int maxHeight = 0;
for (Node node : root.children) {
int depth = maxDepth(node);
if (depth > maxHeight) maxHeight = depth;
}
return maxHeight + 1;
}
排排坐，分糖果。
我们买了一些糖果 candies，打算把它们分给排好队的 n = num_people 个小朋友。
给第一个小朋友 1 颗糖果，第二个小朋友 2 颗，依此类推，直到给最后一个小朋友 n 颗糖果。
然后，我们再回到队伍的起点，给第一个小朋友 n + 1 颗糖果，第二个小朋友 n + 2 颗，依此类推，直到给最后一个小朋友 2 * n 颗糖果。
重复上述过程（每次都比上一次多给出一颗糖果，当到达队伍终点后再次从队伍起点开始），直到我们分完所有的糖果。注意，就算我们手中的剩下糖果数不够（不比前一次发出的糖果多），这些糖果也会全部发给当前的小朋友。
返回一个长度为 num_people、元素之和为 candies 的数组，以表示糖果的最终分发情况（即 ans[i] 表示第 i 个小朋友分到的糖果数）。
示例 1：
输入：candies = 7, num_people = 4 输出：[1,2,3,1] 解释： 第一次，ans[0] += 1，数组变为 [1,0,0,0]。 第二次，ans[1] += 2，数组变为 [1,2,0,0]。 第三次，ans[2] += 3，数组变为 [1,2,3,0]。 第四次，ans[3] += 1（因为此时只剩下 1 颗糖果），最终数组变为 [1,2,3,1]。 示例 2：
输入：candies = 10, num_people = 3 输出：[5,2,3] 解释： 第一次，ans[0] += 1，数组变为 [1,0,0]。 第二次，ans[1] += 2，数组变为 [1,2,0]。 第三次，ans[2] += 3，数组变为 [1,2,3]。 第四次，ans[0] += 4，最终数组变为 [5,2,3]。
提示：
1 <= candies <= 10^9 1 <= num_people <= 1000
public int[] distributeCandies(int candies, int num_people) {
int[] ans = new int[num_people];
int i = 0;
while (candies != 0) {
ans[i % num_people] += Math.min(candies, i + 1);
candies -= Math.min(candies, i + 1);
i += 1;
}
return ans;
}
输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
示例 1：
输入：target = 9 输出：[[2,3,4],[4,5]] 示例 2：
输入：target = 15 输出：[[1,2,3,4,5],[4,5,6],[7,8]]
限制：
1 <= target <= 10^5
//滑动窗口，使用两个指针记录滑动窗口的左右边界，计算窗口内值得和是否符合target符合的话就加入集合。
public int[][] findContinuousSequence(int target) {
int i = 1; // 滑动窗口的左边界
int j = 1; // 滑动窗口的右边界
int sum = 0; // 滑动窗口中数字的和
List<int[]> res = new ArrayList<>();
while (i <= target / 2) {
if (sum < target) {
// 右边界向右移动
sum += j;
j++;
} else if (sum > target) {
// 左边界向右移动
sum -= i;
i++;
} else {
// 记录结果
int[] arr = new int[j-i];
for (int k = i; k < j; k++) {
arr[k-i] = k;
}
res.add(arr);
// 左边界向右移动
sum -= i;
i++;
}
}
return res.toArray(new int[res.size()][]);
}
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
示例 1:
输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。 示例 2:
输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
//思路，动态规划。第i天的最大收益 = max(前一天的最大收入，当天的价格-前i天的最小价格)
public int maxProfit(int[] prices) {
if(prices.length<=0) return 0;
int min = prices[0];
int max = 0;
for (int i = 0; i < prices.length; i++) {
max = Math.max(max, prices[i] - min);
min = Math.min(min, prices[i]);
}
return max;
}
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。
示例 : 给定二叉树
1
/ \
2 3
/ \
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
注意：两结点之间的路径长度是以它们之间边的数目表示。
class Solution {
int result = 0;
public int diameterOfBinaryTree(TreeNode root) {
//不能分别计算左右两边的最大深度然后求和+1，因为最长路径不一定是路过根节点的
dfs(root);
return result;
}
private int dfs(TreeNode node) {
if (node == null) return 0;
int left = dfs(node.left);
int right= dfs(node.right);
result = Math.max(result,left+right);
return Math.max(left,right)+1;
}
}
给你一个整数数组 A，只有可以将其划分为三个和相等的非空部分时才返回 true，否则返回 false。
形式上，如果可以找出索引 i+1 < j 且满足 (A[0] + A[1] + ... + A[i] == A[i+1] + A[i+2] + ... + A[j-1] == A[j] + A[j-1] + ... + A[A.length - 1]) 就可以将数组三等分。
示例 1：
输出：[0,2,1,-6,6,-7,9,1,2,0,1] 输出：true 解释：0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1 示例 2：
输入：[0,2,1,-6,6,7,9,-1,2,0,1] 输出：false 示例 3：
输入：[3,3,6,5,-2,2,5,1,-9,4] 输出：true 解释：3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4
//思路：1.双指针，从两端开始查找，如果两端都找到sum为total/3的集合后，则中间部分一定为total/3
2.直接找，平分后查找，index有可能大于3，如[-1,1,-1,1,-1,1-1,1],采用的第二种思路解答
public boolean canThreePartsEqualSum(int[] A) {
int total = 0;
for (Integer num : A) {
total += num;
}
if (total%3 !=0){
return false;
}
int index = 0;
int temp = total /3;
for (int i = 0; i < A.length; i++) {
if (temp-A[i] == 0){
index++;
temp = total /3;
}else {
temp -=A[i];
}
}
return index >=3;
}
对于字符串 S 和 T，只有在 S = T + ... + T（T 与自身连接 1 次或多次）时，我们才认定 “T 能除尽 S”。
返回最长字符串 X，要求满足 X 能除尽 str1 且 X 能除尽 str2。
示例 1：
输入：str1 = "ABCABC", str2 = "ABC" 输出："ABC" 示例 2：
输入：str1 = "ABABAB", str2 = "ABAB" 输出："AB" 示例 3：
输入：str1 = "LEET", str2 = "CODE" 输出：""
提示：
1 <= str1.length <= 1000 1 <= str2.length <= 1000 str1[i] 和 str2[i] 为大写英文字母
//若存在公约数，必然 (str1 + str2).equals(str2 + str1)。然后再通过迭代找最大公约数。
public String gcdOfStrings(String str1, String str2) {
if (!(str1 + str2).equals(str2 + str1)) return "";
int str1Length = str1.length();
int str2Length = str2.length();
while (str2Length != 0) {
int temp = str2Length;
str2Length = str1Length % str2Length;
str1Length = temp;
}
return str1.substring(0, str1Length);
}
给定一个字符串和一个整数 k，你需要对从字符串开头算起的每个 2k 个字符的前k个字符进行反转。如果剩余少于 k 个字符，则将剩余的所有全部反转。如果有小于 2k 但大于或等于 k 个字符，则反转前 k 个字符，并将剩余的字符保持原样。
示例:
输入: s = "abcdefg", k = 2 输出: "bacdfeg" 要求:
该字符串只包含小写的英文字母。 给定字符串的长度和 k 在[1, 10000]范围内。
public String reverseStr(String s, int k) {
char[] a = s.toCharArray();
for (int start = 0; start < a.length; start += 2 * k) {
int i = start, j = Math.min(start + k - 1, a.length - 1);
while (i < j) {
char tmp = a[i];
a[i++] = a[j];
a[j--] = tmp;
}
}
return new String(a);
}
字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短，则返回原先的字符串。你可以假设字符串中只包含大小写英文字母（a至z）。
示例1:
输入："aabcccccaaa" 输出："a2b1c5a3" 示例2:
输入："abbccd" 输出："abbccd" 解释："abbccd"压缩后为"a1b2c2d1"，比原字符串长度更长。 提示：
字符串长度在[0, 50000]范围内。
public String compressString(String S) {
if (S.length() <= 0) return "";
char[] chars = S.toCharArray();
int index = 0;
char current = chars[0];
StringBuilder result = new StringBuilder();
for (int i = 0; i <= chars.length; i++) {
if (i != chars.length && current != chars[i]) {
result.append( String.valueOf(current) + index);
current = chars[i];
index = 1;
} else if (i == chars.length) {
result.append( String.valueOf(current) + index);
} else {
index++;
}
}
if (S.length() <= result.length()) {
return S;
} else {
return result.toString();
}
}
给你一份『词汇表』（字符串数组） words 和一张『字母表』（字符串） chars。
假如你可以用 chars 中的『字母』（字符）拼写出 words 中的某个『单词』（字符串），那么我们就认为你掌握了这个单词。
注意：每次拼写时，chars 中的每个字母都只能用一次。
返回词汇表 words 中你掌握的所有单词的 长度之和。
示例 1：
输入：words = ["cat","bt","hat","tree"], chars = "atach" 输出：6 解释： 可以形成字符串 "cat" 和 "hat"，所以答案是 3 + 3 = 6。 示例 2：
输入：words = ["hello","world","leetcode"], chars = "welldonehoneyr" 输出：10 解释： 可以形成字符串 "hello" 和 "world"，所以答案是 5 + 5 = 10。
提示：
1 <= words.length <= 1000 1 <= words[i].length, chars.length <= 100 所有字符串中都仅包含小写英文字母
public int countCharacters(String[] words, String chars) {
int[] c = new int[26];
for(char cc : chars.toCharArray()) {
c[(int)(cc - 'a')] += 1;
}
int res = 0;
a: for(String word : words) {
int[] w = new int[26];
for(char ww : word.toCharArray()) {
w[(int)(ww - 'a')] += 1;
}
for(int i=0; i<26; i++) {
if(w[i] > c[i]) {
continue a;
}
}
res += word.length();
}
return res;
}
给定一个带有头结点 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例 1：
输入：[1,2,3,4,5] 输出：此列表中的结点 3 (序列化形式：[3,4,5]) 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。 注意，我们返回了一个 ListNode 类型的对象 ans，这样： ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL. 示例 2：
输入：[1,2,3,4,5,6] 输出：此列表中的结点 4 (序列化形式：[4,5,6]) 由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
提示：
给定链表的结点数介于 1 和 100 之间。
public ListNode middleNode(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null &&fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
# 62.409.最长回文串
给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。
在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。
注意:
假设字符串的长度不会超过 1010。
示例 1:
输入:
"abccccdd"
输出:
7
解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
public int longestPalindrome(String s) {
int result = 0;
boolean isSingle = false;
char[] chars = s.toCharArray();
int[] arrays = new int[58];
for (char c : chars) {
arrays[c - 'A']+=1;
}
for (int i = 0; i < arrays.length; i++) {
if (arrays[i] % 2 == 0) {
result += arrays[i];
} else if ( arrays[i] % 2 == 1) {
isSingle = true;
result += arrays[i] - 1;
}
}
return isSingle ? result + 1 : result;
}
# 63.面试题17.16.按摩师
一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。
注意：本题相对原题稍作改动
示例 1：
输入： [1,2,3,1]
输出： 4
解释： 选择 1 号预约和 3 号预约，总时长 = 1 + 3 = 4。
示例 2：
输入： [2,7,9,3,1]
输出： 12
解释： 选择 1 号预约、 3 号预约和 5 号预约，总时长 = 2 + 9 + 1 = 12。
示例 3：
输入： [2,1,4,5,3,1,1,3]
输出： 12
解释： 选择 1 号预约、 3 号预约、 5 号预约和 8 号预约，总时长 = 2 + 4 + 3 + 3 = 12。
public int massage(int[] nums) {
int a = 0, b = 0;
for (int i = 0; i < nums.length; i++) {
int c = Math.max(b, a + nums[i]);
a = b;
b = c;
}
return b;
}
# 64.892.三维形体的表面积
在 N * N 的网格上，我们放置一些 1 * 1 * 1 的立方体。
每个值 v = grid[i][j] 表示 v 个正方体叠放在对应单元格 (i, j) 上。
请你返回最终形体的表面积。
示例 1：
输入：[[2]]
输出：10
示例 2：
输入：[[1,2],[3,4]]
输出：34
示例 3：
输入：[[1,0],[0,2]]
输出：16
示例 4：
输入：[[1,1,1],[1,0,1],[1,1,1]]
输出：32
示例 5：
输入：[[2,2,2],[2,1,2],[2,2,2]]
输出：46
提示：
1 <= N <= 50
0 <= grid[i][j] <= 50
public int surfaceArea(int[][] grid) {
if(grid == null || grid.length < 1 || grid[0].length < 1) return 0;
//计算总面积
int total = 0;
int lost = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
//统计所有的立方体
total += grid[i][j];
//统计因堆叠损失的面数
lost += grid[i][j] > 1 ? grid[i][j] - 1 : 0;
//统计行因堆叠损失的面数
if (i > 0) lost += Math.min(grid[i - 1][j], grid[i][j]);
if (j > 0) lost += Math.min(grid[i][j - 1], grid[i][j]);
}
}
return total * 6 - lost * 2;
}
# 65.999.车的可用捕获量
在一个 8 x 8 的棋盘上，有一个白色车（rook）。也可能有空方块，白色的象（bishop）和黑色的卒（pawn）。它们分别以字符 “R”，“.”，“B” 和 “p” 给出。大写字符表示白棋，小写字符表示黑棋。
车按国际象棋中的规则移动：它选择四个基本方向中的一个（北，东，西和南），然后朝那个方向移动，直到它选择停止、到达棋盘的边缘或移动到同一方格来捕获该方格上颜色相反的卒。另外，车不能与其他友方（白色）象进入同一个方格。
返回车能够在一次移动中捕获到的卒的数量。
示例 1：
输入：[[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","R",".",".",".","p"],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]
输出：3
解释：
在本例中，车能够捕获所有的卒。
示例 2：
输入：[[".",".",".",".",".",".",".","."],[".","p","p","p","p","p",".","."],[".","p","p","B","p","p",".","."],[".","p","B","R","B","p",".","."],[".","p","p","B","p","p",".","."],[".","p","p","p","p","p",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]
输出：0
解释：
象阻止了车捕获任何卒。
示例 3：
输入：[[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","p",".",".",".","."],["p","p",".","R",".","p","B","."],[".",".",".",".",".",".",".","."],[".",".",".","B",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."]]
输出：3
解释：
车可以捕获位置 b5，d6 和 f5 的卒。
提示：
board.length == board[i].length == 8
board[i][j] 可以是 'R'，'.'，'B' 或 'p'
只有一个格子上存在 board[i][j] == 'R'
public int numRookCaptures(char[][] board) {
//确定左上右下四个方向
int[] dx = new int[]{-1, 1, 0, 0};
int[] dy = new int[]{0, 0, -1, 1};
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
//找车所在的坐标
if (board[i][j] == 'R') {
int result = 0;
for (int k = 0; k < 4; k++) {
int x = i;
int y = j;
while (true) {
x += dx[k];
y += dy[k];
if (x < 0 || x >= 8 || y < 0 || y >= 8 || board[x][y] == 'B') {
break;
}
if (board[x][y] == 'p') {
result++;
break;
}
}
}
return result;
}
}
}
return 0;
}
# 66.24.两两交换链表中的节点
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.
public ListNode swapPairs(ListNode head) {
if (head == null) return null;
ListNode index = head;
if (index.next != null) {
int temp = index.val;
index.val = index.next.val;
index.next.val = temp;
swapPairs(index.next.next);
}
return head;
}
# 67.面试题62.圆圈中最后剩下的数字
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
通过次数21,420提交次数35,389
//本题的思路主要是找数学规律，推导出递推公式 即f(n) = (f(n-1)+m)%n fn为幸存下来的最终数字的当前角标 public int lastRemaining(int n, int m) { int index = 0;//最后一个活下来的人的角标 for (int i = 2; i <= n; i++) { index = (index + m) % i; } return index; }
# 68.118.杨辉三角
给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
在杨辉三角中，每个数是它左上方和右上方的数的和。
示例:
输入: 5
输出:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
fun generate(numRows: Int): List<List<Int>> {
val result = ArrayList<List<Int>>()
for (i in 0..numRows-1) {
val row = ArrayList<Int>()
for (j in 0..i) {
if (j == 0 || j == i) {
row.add(1)
} else {
row.add(result[i - 1][j - 1] + result[i - 1][j]);
}
}
result.add(row)
}
return result
}
# 69.119.杨辉三角II
给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。
在杨辉三角中，每个数是它左上方和右上方的数的和。
示例:
输入: 3
输出: [1,3,3,1]
进阶：
你可以优化你的算法到 O(k) 空间复杂度吗？
fun getRow(rowIndex: Int): List { val result = ArrayList<List>() for (i in 0..rowIndex) { val sub = ArrayList() for (j in 0 .. i) { if (j == 0 || j == i) { sub.add(1) } else { sub.add(result[i - 1][j - 1] + result[i - 1][j]) } } result.add(sub) } return result[rowIndex] }
# 70.面试题01.07.旋转矩阵
给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。
不占用额外内存空间能否做到？
示例 1:
给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
原地旋转输入矩阵，使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
示例 2:
给定 matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
],
原地旋转输入矩阵，使其变为:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]
public void rotate(int[][] matrix) { int length = matrix.length; //对角线交换 for (int i = 0; i < length - 1; i++) { for (int j = i + 1; j < length; j++) { int temp = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = temp; } } //进行对折交换 for (int i = 0; i <= length - 1; i++) { for (int j = 0; j < length >> 1 ; j++) { int temp = matrix[i][j]; matrix[i][j] = matrix[i][length - j-1]; matrix[i][length - j-1] = temp; } } }
# 71.66.斐波那契数列
斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
给定 N，计算 F(N)。
示例 1：
输入：2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1.
示例 2：
输入：3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2.
示例 3：
输入：4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3.
提示：
0 ≤ N ≤ 30
public int fib(int N) {
if(N<2) return N;
return fib(N-1)+fib(N-2);
}
# 72.二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
public int maxDepth(TreeNode root) { if (root == null) return 0; int left = maxDepth(root.left); int right = maxDepth(root.right); return Math.max(left, right) + 1; }
# 73.Pow(x, n)
实现 pow(x, n) ，即计算 x 的 n 次幂函数。
示例 1:
输入: 2.00000, 10
输出: 1024.00000
示例 2:
输入: 2.10000, 3
输出: 9.26100
示例 3:
输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25
说明:
-100.0 < x < 100.0
n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。
public double myPow(double x, int n) { if (n == 0) return 1; if (n < 0) { return fastPow(1/x,-n); } else { return fastPow(x,n); } }
public double fastPow(double x, int n) {
if (n == 0) return 1;
double fast = fastPow(x, n / 2);
if (n % 2 == 0) {
return fast * fast;
} else {
return fast * fast * x;
}
}
# 74.21合并两个有序链表
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
# 75.779. 第K个语法符号
在第一行我们写上一个 0。接下来的每一行，将前一行中的0替换为01，1替换为10。
给定行数 N 和序数 K，返回第 N 行中第 K个字符。（K从1开始）
例子:
输入: N = 1, K = 1
输出: 0
输入: N = 2, K = 1
输出: 0
输入: N = 2, K = 2
输出: 1
输入: N = 4, K = 5
输出: 1
解释:
第一行: 0
第二行: 01
第三行: 0110
第四行: 01101001
注意：
N 的范围 [1, 30].
K 的范围 [1, 2^(N-1)].
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/k-th-symbol-in-grammar
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
public int kthGrammar(int N, int K) {
if (N == 1) return 0;
if (K <= 1 << N-2)
return kthGrammar(N-1, K);
return kthGrammar(N-1, K - (1 << N-2)) ^ 1;
}