4.多数元素
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：nums = [3,2,3] 输出：3
示例 2：
输入：nums = [2,2,1,1,1,2,2] 输出：2
提示：
/
n == nums.length 1 <= n <= 5 * 104 -109 <= nums[i] <= 109
题解
思路一：暴力解法
暴力解法是通过遍历数组并统计每个元素的出现次数，然后判断是否满足大于 n/2 的条件。以下是一个使用暴力解法的示例代码：
public class Solution { public int majorityElement(int[] nums) { int n = nums.length; for (int num : nums) { int count = 0; for (int i = 0; i < n; i++) { if (nums[i] == num) { count++; } } if (count > n / 2) { return num; } } return -1; // 如果输入的数组不符合题目要求，没有多数元素，则返回一个特定的值（例如 -1） } }
上述代码中，我们使用两层循环来遍历整个数组。外层循环用于遍历每个元素，内层循环用于统计该元素在数组中出现的次数。如果某个元素的出现次数大于 n/2，则返回该元素作为多数元素。
请注意，上述代码并没有对输入数组进行非空判断或检查是否存在多数元素。根据题目描述，假设输入数组是非空的，并且总是存在多数元素。但在实际应用中，需要增加相应的逻辑来处理这些边界情况。
思路二：复杂度为O(1)随机化法
class Solution { private int randRange(Random rand, int min, int max) { return rand.nextInt(max - min) + min; } private int countOccurences(int[] nums, int num) { int count = 0; for (int i = 0; i < nums.length; i++) { if (nums[i] == num) { count++; } } return count; } public int majorityElement(int[] nums) { Random rand = new Random(); int majorityCount = nums.length / 2; while (true) { int candidate = nums[randRange(rand, 0, nums.length)]; if (countOccurences(nums, candidate) > majorityCount) { return candidate; } } } }
这段代码的目标是找出给定整数数组中的主要元素（即出现次数超过一半的元素）。下面是该代码的思路：
- 在 randRange 方法中，使用 Random 类生成一个介于 min 和 max 之间的随机整数。
- countOccurences 方法用于计算在给定数组 nums 中等于 num 的元素个数。
- majorityElement 方法是主要的方法，它首先创建了一个 Random 对象 rand。
- 然后根据数组长度计算出了主要元素的最小出现次数 majorityCount，即数组长度的一半。
- 使用一个无限循环，在每次迭代中选择一个随机索引，并将对应的元素赋值给 candidate。
- 然后通过调用 countOccurences 方法来计算 candidate 在数组中的出现次数。
- 如果 candidate 的出现次数超过了 majorityCount，则返回 candidate，因为它是主要元素。
- 如果没有找到主要元素，则会继续循环直到找到为止。
需要注意的是，由于数组中一定存在一个主要元素，所以这个循环一定会终止并返回结果。但是，这种方法的时间复杂度可能很高，因为在每次迭代中需要遍历整个数组来计算出现次数。在某些情况下，这可能导致性能问题。
5.买卖股票的最佳时机
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
输入：[7,1,5,3,6,4] 输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 =6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：
输入：prices = [7,6,4,3,1] 输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
提示：
1 <= prices.length <= 105
0 <= prices[i] <= 104
题解
思路一：暴力法
暴力解法可以通过考虑每一天作为买入点，然后在之后的每一天作为卖出点，计算利润并找到最大值。以下是使用暴力解法的Java代码示例：
class Solution { public int maxProfit(int[] prices) { int maxProfit = 0; for (int i = 0; i < prices.length - 1; i++) { for (int j = i + 1; j < prices.length; j++) { int profit = prices[j] - prices[i]; if (profit > maxProfit) { maxProfit = profit; } } } return maxProfit; } }
上述代码中，我们使用两个循环嵌套来遍历所有可能的买入和卖出点组合。对于每个组合，我们计算卖出价格减去买入价格得到的利润，并将其与当前的最大利润进行比较。如果新计算的利润更大，则更新最大利润。
然后返回最大利润作为结果。这种暴力解法的时间复杂度为 O(n^2)，其中 n 是数组的长度。
思路二：一次遍历
public class Solution { public int maxProfit(int prices[]) { int minprice = Integer.MAX_VALUE; int maxprofit = 0; for (int i = 0; i < prices.length; i++) { if (prices[i] < minprice) { minprice = prices[i]; } else if (prices[i] - minprice > maxprofit) { maxprofit = prices[i] - minprice; } } return maxprofit; } }
- 初始化minprice为整数的最大值，maxprofit为0。minprice用于记录迄今为止最低的股票价格，maxprofit用于记录迄今为止最大的利润。
- 遍历给定的股票价格数组prices，从索引0开始到数组末尾。
- 对于每个价格prices[i]，首先检查它是否比当前的minprice更低。如果是，则更新minprice为prices[i]，因为我们找到了一个更低的购买价格。
- 如果prices[i]不是比当前的minprice更低，那么我们计算以当前价格卖出时的利润。将prices[i] - minprice与当前的maxprofit进行比较，如果大于maxprofit，则更新maxprofit为prices[i] - minprice，因为我们找到了一个更大的利润。
- 完成遍历后，maxprofit中存储的就是股票买卖的最大利润。
该算法的时间复杂度为O(n)，其中n是股票价格数组的长度。
6.罗马数字转整数
罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
/
字符 数值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。
示例
输入: s = “III” 输出: 3
输入: s = “IV” 输出: 4
输入: s = “IX” 输出: 9 :
输入: s = “LVIII” 输出: 58 解释: L = 50, V= 5, III = 3.
输入: s = “MCMXCIV” 输出: 1994 解释: M = 1000, CM = 900, XC = 90, IV = 4.
提示：
1 <= s.length <= 15
s 仅含字符 (‘I’, ‘V’, ‘X’, ‘L’, ‘C’, ‘D’, ‘M’)
题目数据保证 s 是一个有效的罗马数字，且表示整数在范围 [1, 3999] 内
题目所给测试用例皆符合罗马数字书写规则，不会出现跨位等情况。
IL 和 IM 这样的例子并不符合题目要求，49 应该写作 XLIX，999 应该写作 CMXCIX 。
关于罗马数字的详尽书写规则，可以参考 罗马数字 - Mathematics 。
题解
思路一：暴力法
class Solution { Map<Character, Integer> symbolValues = new HashMap<Character, Integer>() {{ put('I', 1); put('V', 5); put('X', 10); put('L', 50); put('C', 100); put('D', 500); put('M', 1000); }}; public int romanToInt(String s) { int ans = 0; int n = s.length(); for (int i = 0; i < n; ++i) { int value = symbolValues.get(s.charAt(i)); if (i < n - 1 && value < symbolValues.get(s.charAt(i + 1))) { ans -= value; } else { ans += value; } } return ans; } }
通常情况下，罗马数字中小的数字在大的数字的右边。若输入的字符串满足该情况，那么可以将每个字符视作一个单独的值，累加每个字符对应的数值即可。
例如 XXVII\texttt{XXVII}XXVII 可视作 X+X+V+I+I=10+10+5+1+1=27\texttt{X}+\texttt{X}+\texttt{V}+\texttt{I}+\texttt{I}=10+10+5+1+1=27X+X+V+I+I=10+10+5+1+1=27。
若存在小的数字在大的数字的左边的情况，根据规则需要减去小的数字。对于这种情况，我们也可以将每个字符视作一个单独的值，若一个数字右侧的数字比它大，则将该数字的符号取反。
例如 XIV\texttt{XIV}XIV 可视作 X−I+V=10−1+5=14\texttt{X}-\texttt{I}+\texttt{V}=10-1+5=14X−I+V=10−1+5=14。
7.最后一个单词长度
给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。
单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。
示例
输入：s = “Hello World” 输出：5 解释：最后一个单词是“World”，长度为5。
输入：s = " fly me to the moon " 输出：4 解释：最后一个单词是“moon”，长度为4。
输入：s = “luffy is still joyboy” 输出：6 解释：最后一个单词是长度为6的“joyboy”。
提示：
1 <= s.length <= 104
s 仅有英文字母和空格 ’ ’ 组成
s 中至少存在一个单词
