20. 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
括号必须以正确的顺序闭合。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
示例 4：
输入：s = "([)]"
输出：false
示例 5：
输入：s = "{[]}"
输出：true
提示：
1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成
解题思路：利用栈的后进先出的特性
- 根据题意可知，有效括号的前提是字符串长度为偶数，若长度为奇数，则直接返回false，这里用按位与1运算可快速判断长度的奇偶
- 遍历字符串中的每个字符
- 若字符为起始括号，则将对应的结束括号入栈（栈中只对结束括号进行操作，当字符为结束括号时方便出栈）
- 若为结束括号，则要出栈，并且判断出栈的结束括号与当前结束括号是否相同（从左往右，首个结束括号的左边那个一定是对应的起始括号），不相同则返回false
- 另外，出栈时如果栈里没有元素，则会异常，因此在出栈前判断栈是否为空栈，为空表示当前结束括号的左边没有对应的起始括号，直接返回false
- 遍历完后，若栈里为空，表示所有的结束括号都与起始括号一一对应消除了，可以认定为该字符串为有效括号，否则为无效括号，因此直接返回栈大小是否等于0
代码如下：
public static boolean isValid(String s) {
if (0 != (s.length() & 1)) {
return false;
}
Stack<Character> stack = new Stack<>();
for (char character : s.toCharArray()) {
if (character == '(') {
stack.push(')');
} else if (character == '[') {
stack.push(']');
} else if (character == '{') {
stack.push('}');
} else if (stack.isEmpty() || character != stack.pop()) {
return false;
}
}
return stack.isEmpty();
}
1299. 将每个元素替换为右侧最大元素
给你一个数组arr，请你将每个元素用它右边最大的元素替换，如果是最后一个元素，用 -1替换。
完成所有替换操作后，请你返回这个数组。
示例 1：
输入：arr = [17,18,5,4,6,1]
输出：[18,6,6,6,1,-1]
解释：
下标 0 的元素 --> 右侧最大元素是下标 1 的元素 (18)
下标 1 的元素 --> 右侧最大元素是下标 4 的元素 (6)
下标 2 的元素 --> 右侧最大元素是下标 4 的元素 (6)
下标 3 的元素 --> 右侧最大元素是下标 4 的元素 (6)
下标 4 的元素 --> 右侧最大元素是下标 5 的元素 (1)
下标 5 的元素 --> 右侧没有其他元素，替换为 -1
示例 2：
输入：arr = [400]
输出：[-1]
解释：下标 0 的元素右侧没有其他元素。
提示：
1 <= arr.length <= 104
1 <= arr[i] <= 105
解题思路：
- 从右往左遍历数组
- 记录当前元素，并且将当前位置上的元素替换为最大值（初始值为-1）
- 若当前元素大于最大值，则更新最大值为当前元素
代码如下：
public static int[] replaceElements(int[] arr) {
int length = arr.length;
int max = -1;
int temp;
for (int i = length-1; i >= 0; i--) {
temp = arr[i];
arr[i] = max;
if (temp > max) {
max = temp;
}
}
return arr;
}
1748. 唯一元素的和
给你一个整数数组nums。数组中唯一元素是那些只出现恰好一次的元素。
请你返回 nums中唯一元素的 和。
示例 1：
输入：nums = [1,2,3,2]
输出：4
解释：唯一元素为 [1,3] ，和为 4 。
示例 2：
输入：nums = [1,1,1,1,1]
输出：0
解释：没有唯一元素，和为 0 。
**示例 3 **：
输入：nums = [1,2,3,4,5]
输出：15
解释：唯一元素为 [1,2,3,4,5] ，和为 15 。
提示：
1 <= nums.length <= 100
1 <= nums[i] <= 100
解题思路：
- 遍历数组
- 每次判断哈希表中是否存在该元素
- 若不存在，则作为key添加到哈希表中，同时将value设为1，表示出现次数，同时累加到变量sum中作为唯一元素的和
- 若存在，则判断该元素出现次数是否为1，若已经出现过一次，表示sum中已经加累过一次了，则需要减去该重复元素，同时记录次数+1；
- 若已出现不止一次了，则表示已经减过了，直接记录次数+1即可
代码如下：
public static int sumOfUnique1(int[] nums) {
int sum = 0;
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
if (!map.containsKey(num)) {
map.put(num, 1);
sum += num;
} else {
int count = map.get(num);
if (count == 1) {
sum -= num;
map.put(num, 2);
} else {
map.put(num, count + 1);
}
}
}
return sum;
}
