基本计算器(栈、递归)
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
示例 1： 输入：s = "1 + 1" 输出：2 示例 2： 输入：s = " 2-1 + 2 " 输出：3 示例 3： 输入：s = "(1+(4+5+2)-3)+(6+8)" 输出：23
提示：
- 1 <= s.length <= 3 * 105
- s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
- s 表示一个有效的表达式
解答：
class Solution {
public int calculate(String s) {
int res = 0, num = 0;
Stack<Integer> sta = new Stack<Integer>();
char preSign = '+';
int len = s.length();
for (int i = 0; i < len; i++) {
char ch = s.charAt(i);
if (Character.isDigit(ch)) {
num = num * 10 + ch - '0';
}
if ((!Character.isDigit(ch) && ch != ' ') || i == len - 1) {
if (preSign == '+') {
sta.push(num);
} else if (preSign == '-') {
sta.push(-1 * num);
} else if (preSign == '*') {
sta.push(num * sta.pop());
} else if (preSign == '/') {
sta.push(sta.pop() / num);
}
num = 0;
preSign = ch;
}
}
while (!sta.isEmpty()) {
res += sta.pop();
}
return res;
}
}
两数之和 II(数组、双指针)
给定一个已按照**_ 非递减顺序排列 **的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。 函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。_numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。 你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
示例 1： 输入：numbers = [2,7,11,15], target = 9 输出：[1,2] 解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。 示例 2： 输入：numbers = [2,3,4], target = 6 输出：[1,3] 示例 3： 输入：numbers = [-1,0], target = -1 输出：[1,2]
提示：
- 2 <= numbers.length <= 3 * 104
- -1000 <= numbers[i] <= 1000
- numbers 按 非递减顺序 排列
- -1000 <= target <= 1000
- 仅存在一个有效答案
解答：
class Solution {
public int[] twoSum(int[] numbers, int target) {
int[] answer = new int[2];
int n = numbers.length;
for (int i = 0; i < n - 1; i++) {
int t = target - numbers[i];
answer[0] = i + 1;
for (int j = i + 1; j < n; j++) {
if (numbers[j] > t) {
break;
}
if (numbers[j] == t) {
answer[1] = j + 1;
break;
}
}
if (answer[1] != 0) {
break;
}
}
return answer;
}
}
搜索旋转排序数组 II(数组、二分查找)
已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。 在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 **旋转 **，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。 给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。
示例 1：
输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true
示例 2：
输入：nums = [2,5,6,0,0,1,2], target = 3
输出：false
提示：
- 1 <= nums.length <= 5000
- -104 <= nums[i] <= 104
- 题目数据保证 nums 在预先未知的某个下标上进行了旋转
- -104 <= target <= 104
进阶：
- 这是 搜索旋转排序数组 的延伸题目，本题中的 nums 可能包含重复元素。
- 这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？
解答：
class Solution {
public boolean search(int[] nums, int target) {
int low = 0;
int high = nums.length - 1;
while (low <= high) {
while (low < high && nums[low] == nums[low + 1]) {
low++;
}
while (low < high && nums[high] == nums[high - 1]) {
high--;
}
int mid = (low + high) / 2;
if (nums[mid] == target) {
return true;
}
if (nums[mid] >= nums[0] && (target > nums[mid] || target < nums[0])) {
low = mid + 1;
} else if (nums[mid] < nums[0] && target > nums[mid] && target < nums[0]) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return false;
}
}
本文内容到此结束了， 如有收获欢迎点赞????收藏????关注✔️，您的鼓励是我最大的动力。 如有错误❌疑问????欢迎各位大佬指出。 主页：共饮一杯无的博客汇总????????
保持热爱，奔赴下一场山海。????????????