七.数组
1.给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
解题思路：使用hash来做，会达到o（1）的效果
map的key值存放值，value存放下标值，每次比较target与元素的差值是否和当前元素相等，就可以得到答案
public static int[] twoSumYouhua(int[] nums, int target) {
if(nums == null){
return null;
}
Map<Integer,Integer> map = new HashMap<>();
for(int i = 0;i<nums.length;i++){
if(map.containsKey(target-nums[i])){
return new int[]{map.get(target-nums[i]),i};
}
map.put(nums[i],i);
}
return null;
}
2.给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
解题思路：双指针法
public static int maxAreaYouHua(int[] height) {
int max = 0;
int minData = 0;
int i = 0;
int j = height.length-1;
max = (j-i)*(height[j]>height[i]?height[i]:height[j]);
while (i<j){
if(height[i]>height[j]){
j--;
}else {
i++;
}
minData = height[j]>height[i]?height[i]:height[j];
max = minData*(j-i)>max?minData*(j-i):max;
}
return max;
}
3.给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
解题思路：双指针法，固定一个值得，跳过重复的，左右循环即可
public static List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
for(int i = 0;i<nums.length-2;i++){
if (i>0 && nums[i] == nums[i-1]) continue;
int l = i+1;int r = nums.length-1;
while (l<r){
if(nums[i]+nums[l]+nums[r]>0){
while (l<r && nums[r-1] == nums[r]) r--;
r--;
}else if(nums[i]+nums[l]+nums[r]<0){
while (l<r && nums[l] == nums[l+1]) l++;
l++;
} else {
res.add(Arrays.asList(nums[i],nums[l],nums[r]));
while (l<r && nums[l] == nums[l+1]) l++;
while (l<r && nums[r] == nums[r-1]) r--;
l++;
r--;
}
}
}
return res;
}
4.给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
public static int removeDuplicates(int[] nums) {
int j = 0;
for(int i = 0;i<nums.length;i++){
if(i == 0){
nums[j++]=nums[i];
}
else if(nums[i-1]!=nums[i]){
nums[j++] = nums[i];
}
}
return j;
}
5.给出一组有序数列，找出目标数值，要求时间复杂度为log(n)
解题思路：二分查找
public static int index(int[] nums,int target){
if(nums == null){
return -1;
}
int l = 0;int r = nums.length-1;
while (l<=r){
int mid = l+(r-l)/2;
if(nums[mid] == target) return mid;
else if(nums[mid]>target){
r = mid -1;
}else{
l = mid+1;
}
}
return -1;
}
6.给出一串数字，比如[1,2,3,4,5,6,7,8,9],根据某一个数字翻转,得到[6,7,8,9,1,2,3,4],给一个目标
值，找出目标值的索引，没有返回-1，要求时间复杂度为log(n)
解题思路：二分查找
if(nums == null){
return -1;
}
int l = 0;int r = nums.length-1;
while (l<=r){
int mid = l+(r-l)/2;
if(nums[mid] == target) return mid;
if(nums[mid]>nums[r]){
if(nums[mid]>target && target<nums[r]|| nums[mid]<target){
l = mid+1;
} else if(target == nums[r]){
return r;
}
else if(nums[mid]>target && target>nums[r]){
r = mid-1;
}
}else {
if(nums[mid]>target || target>nums[r]){
r = mid-1;
}
else if(target == nums[r]){
return r;
}
else if(nums[mid]<target && target<nums[r]){
l = mid+1;
}
}
}
return -1;
思路：中间数和目标数以及和最右边数的比较
7.给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别
二分查找：找到一个位置，左右遍历，找到边界
if(nums == null){
return new int[]{-1,-1};
}
int l =0;int r = nums.length-1;
while (l<=r){
int mid = l+(r-l)/2;
int i = 0;int j = 0;
if(nums[mid] == target){
while (mid-i >=0 && nums[mid-i] == nums[mid])
{
i++;
continue;
}
while (mid+j <nums.length && nums[mid+j] == nums[mid])
{
j++;
continue;
}
return new int[]{mid-i+1,mid+j-1};
}else if(nums[mid]>target){
r = mid-1;
} else {
l = mid+1;
}
}
return new int[]{-1,-1};
8.组合问题
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
解题思路：回溯+剪枝
9.给定一个 n × n 的二维矩阵表示一个图像。
将图像顺时针旋转 90 度。
说明：
你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
示例 1:
给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
原地旋转输入矩阵，使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
解题思路1:找到规律，记录已经交换的数组，碰到之后不进行操作。
public static int[][] rotate(int[][] matrix) {
if(matrix == null || matrix[0].length != matrix.length){
return null;
}
//矩阵高度
int length = matrix.length;
//保留修改轨迹
int[][] d = new int[matrix.length][matrix.length];
for(int i = 0;i<matrix.length;i++){
for(int j = 0;j<matrix[i].length;j++){
if(d[i][j] == Integer.MAX_VALUE){
continue;
}
else {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][matrix.length-i-1];
matrix[j][matrix.length-i-1] = temp;
d[i][j] = Integer.MAX_VALUE;
d[j][matrix.length-i-1] = Integer.MAX_VALUE;
}
}
}
return matrix;
}
解题思路2:从外圈到内圈循环，有时间写一下
10.给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
示例 1:
输入: [2,3,1,1,4]
输出: true
解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。
a.递归求解
public static boolean canJump(int[] nums) {
if(nums == null){
return false;
}
if(nums.length == 1){
return true;
}
boolean flag = false;
flag = dfs(0,nums);
return flag;
}
/**
* 递归所有的可能情况,深度优先
*
* @param nums
* @return
*/
private static boolean dfs(int index, int[] nums) {
if(index == nums.length-1){
return true;
}
if(index > nums.length-1){
return false;
}
//在哪一个位置的数值大小
int num = nums[index];
if(num == 0){
return false;
}
//遍历步数
for(int i = num;i>=1;i--){
boolean flag = dfs(index+i,nums);
if(flag){
return true;
}
}
return false;
}
b.找规律
/**
* 算法思想
* 1.找出0的位置
* 2.用一个数记录下0之前的位置上的每个元素能跳到最远的位置(nums[i]+i))
* 3.最终比较0的位置和之前的最大值之间是否可以跳过0，跳不过去认为不可达
*/
public class Jump {
public static boolean canJump(int[] nums) {
if(nums == null){
return false;
}
if(nums.length == 1){
return true;
}
//0之前的数字能跳到的最大位置
int max = 0;
for(int i= 0;i<nums.length-1;i++){
if(nums[i] == 0 && i>=max){
return false;
}
max = Math.max(max,nums[i]+i);
}
return true;
}
public static void main(String[] args) {
int[] a = {1,2,0,0};
System.out.println(Jump.canJump(a));
}
}
11.给出一个区间的集合，请合并所有重叠的区间。
示例 1:
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间
解题思路：先排序，然后判断左边数组第二个元素和右边第一个元素大小，小于不合并，大于吞掉
合并，设置两个值，一个待比较值的下标，一个是结果数组的下标
public static int[][] merge(int[][] intervals) {
if(intervals == null || intervals.length == 0){
return new int[][]{};
}
//一个的情况直接返回
if(intervals.length == 1){
return intervals;
}
int k = 0;
int index = 1;
int n = intervals.length;
//map存放所有的一纬数组
Map<Integer,List<int[]>> map = new TreeMap<>();
for(int i = 0;i<intervals.length;i++){
if(map.containsKey(intervals[i][0])){
map.get(intervals[i][0]).add(intervals[i]);
map.put(intervals[i][0],map.get(intervals[i][0]));
}else {
List<int[]> tempList = new ArrayList<>();
tempList.add(intervals[i]);
map.put(intervals[i][0],tempList);
}
}
int[][] tt_temp = new int[intervals.length][2];
Iterator it = map.keySet().iterator();
while (it.hasNext()){
int key = (Integer) it.next();
List<int[]> list = map.get(key);
for(int[] element:list){
tt_temp[k][0] = element[0];
tt_temp[k][1] = element[1];;
k++;
}
}
//目标数组的位置
k = 0;
//需要比较的数组
index = 1;
int[][] temp = new int[intervals.length][2];
//初始化
temp[0] = tt_temp[0];
while (index<n && k<n){
int[] b = tt_temp[index];
if(temp[k][1]>=b[0]){
temp[k][0] = Math.min(temp[k][0],b[0]);
temp[k][1] = Math.max(temp[k][1],b[1]);
}else {
k++;
temp[k][0] = b[0];
temp[k][1] = b[1];
}
//比较过了就加1
index++;
}
//汇总
int[][] res = new int[k+1][2];
for(int j = 0;j<=k;j++){
res[j] = temp[j];
}
return res;
}
12.实现 pow(x, n) ，即计算 x 的 n 次幂函数。
示例 1:
输入: 2.00000, 10
输出: 1024.00000
示例 2:
输入: 2.10000, 3
输出: 9.26100
思路：移位运算，非常棒，n可以用二进制表示，n可以被拆解成
二进制位数，可以表示成2的k1次方+2的k2次方+2的k3次方
这样n次幂就转变成为求x的2的k1乘以x的2的k2乘以x的2的k3次方，
可以根据移位，每次根据对应位置上的x的多少次方
public static double myPow(double x, int n) {
if(x == -1){
if((n&1)==0){
return 1;
}else {
return -1;
}
}
if(x == 1.0 || n == 0){
return 1;
}
if(n == -2147483648){
return 0;
}
if(n<0){
x = 1/x;
n = -n;
}
if(n == 1){
return x;
}
return qpow(x,n);
}
static double qpow(double x, long n){
double res = 1;
while(n>0){
if((n&1)!=0) res = res*x;
n >>= 1;
x *= x;
}
return res;
}
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
解题思路：有2的幂次方（幂集）可以想到和2有关，这时候可以往移位和与运算上靠
n个数字，这时候会有2的n次方个集合，可以抽象成如果有三个数字，则可以有下面二进制
组合000,001,010,011,100,101,110,111，这几个都不重复，每个1表示可以取到哪个元素
这时候可以把每个排列排出来，然后根据&云算法找每个组合的具体取值了
用具体需要找原始数组的结果数组的二进制和第j个元素进行&运算，第0个原始元素位置表示1，
第二个原始元素位置表示1<<1,依次类推,第n个原始元素表示1<<n-1
具体算法如下：
public static List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
int n = 1<<nums.length;
for(int i = 0 ;i<n;i++){
List<Integer> list = new ArrayList<>();
for(int j = 0;j<nums.length;j++){
if((i&(1<<j))!=0){
list.add(nums[j]);
}
}
res.add(list);
}
return res;
}
14.给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
解题思路一：
数组排序然后每个元素一次遍历，比较左右两边大小
public static int singleNumber(int[] nums) {
if(nums.length ==1){
return nums[0];
}
Arrays.sort(nums);
int res = 0;
for(int i = 0;i<nums.length;i++){
if(i>0&&i<nums.length-1){
if(nums[i]!=nums[i-1]&&nums[i]!=nums[i+1]){
res = nums[i];
}
}
else if(i == 0){
if(nums[i]!=nums[i+1]){
res = nums[i];
}
}
else{
if(nums[i] != nums[i-1]){
res = nums[i];
}
}
}
return res;
}
解题思路二：异或运算
a所有数和0异或等于数字本身
b异或遵循交换律
c相同两个值异或为0
所有解题思路如下：
public static int singleNumberOk(int[] nums) {
if(nums.length ==1){
return nums[0];
}
int res = nums[0];
for(int i = 1;i<nums.length;i++){
res ^= nums[i];
}
return res;
}
15.编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。
示例 1：
输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
&和移位一般会经常配合使用
public static int hammingWeight(int n) {
if(n == 0) return 0;
int count = 0;
for(int i = 0; i < 32; i++){
count += n & 1;
n = n >> 1;
}
return count;
}
16 s1在s2中的子排列
public static boolean checkInclusion(String s1, String s2) {
Map<Integer,Integer> map1 = new HashMap<>();
int[] kk = new int[26];
for(int i = 0;i<s1.length();i++){
map1.put(s1.charAt(i)-'a',kk[s1.charAt(i)-'a']++);
}
boolean flag = false;
for(int i = 0;i<s2.length();i++){
int j = i;
while (j<s2.length() && j-i<s1.length() && map1.containsKey(s2.charAt(j)-'a')){
j++;
}
if(j-i == s1.length()){
int[] temp = new int[26];
flag = true;
for(int k = i;k<j;k++){
temp[s2.charAt(k)-'a']++;
}
for(int k = 0;k<s1.length();k++){
if(temp[s1.charAt(k)-'a']!=kk[s1.charAt(k)-'a']){
flag = false;
break;
}
}
}
if(flag){
break;
}
}
return flag;
}
八.字符串
1.给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度
解题思路：
滑动窗口：双指针法
public static int lengthOfLongestSubstring(String s) {
int n = s.length();
Set<Character> set = new HashSet<>();
int result = 0;
int left = 0;
int right = 0;
while (left<n&&right<n){
if(!set.contains(s.charAt(right))){
set.add(s.charAt(right++));
result = Math.max(result,right-left);
}else {
set.remove(s.charAt(left++));
}
}
return result;
}
2.找出一个字符串的最长回文子串
比如输入"abbbbcbc"
输出："bbbb"
解法1:双指针法，相同的跳过
public static String longestPalindrome(String s) {
if(s == null||s.length()>1000){
return "";
}
int max = 0;
String res = "";
int l = 0;int r = 0;
int i = 0;
while (i<s.length()){
l = i-1;
r = i+1;
while (l>=0 && s.charAt(l) == s.charAt(i)){
l--;
}
while (r<s.length() && s.charAt(r) == s.charAt(i)){
r++;
}
i = r;
while (l>=0 && r<s.length() && s.charAt(l) == s.charAt(r)){
l--;
r++;
}
String temp = s.substring(l+1,r);
if(temp.length()>max){
max = temp.length();
res = temp;
}
}
return res;
}
解法2:动态规划解法（状态变量，状态方程）
public static String longestPalindrome(String s) {
String res = "";
int n = s.length();
boolean[][] f = new boolean[n][n];
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
if(s.charAt(i) == s.charAt(j) && (j - i <= 1 || f[i + 1][j - 1])) {
f[i][j] = true;
if(j - i >= res.length()){
res = s.substring(i, j + 1);
}
}
}
}
return res;
}
3.将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：
L C I R
E T O E S I I G
E D H N
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);
示例 1:
输入: s = "LEETCODEISHIRING", numRows = 3
输出: "LCIRETOESIIGEDHN"
示例 2:
输入: s = "LEETCODEISHIRING", numRows = 4
输出: "LDREOEIIECIHNTSG"
解释:
L D R
E O E I I
E C I H N
T S G
解题思路：画图找规律，运用数学，注意判断边界条件
public static String convert(String s, int numRows) {
if (numRows == 0 || s == null) {
return "";
}
if(s.length()<=numRows || numRows<2){
return s;
}
StringBuilder sb = new StringBuilder();
//最终字符串的索引
int resultIndex = 0;
for (int i = 0; i < numRows; i++) {
//表示奇数或偶数
int k = 0;
//字符串索引
int index = i;
sb.append(s.charAt(i));
if(i == numRows-1 || i == 0){
while (index<s.length()){
index+=2*(numRows-1);
if(index<s.length()){
sb.append(s.charAt(index));
}
}
}
else {
while (index < s.length()) {
if (k%2 == 0) {
index = index + 2 * (numRows - i - 1);
} else {
index = index + 2 * i;
}
if(index<s.length()){
sb.append(s.charAt(index));
k++;
}
}
}
}
return sb.toString();
}
4.罗马数字包含以下七种字符： 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。
给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。
示例 1:
输入: 3
输出: "III"
示例 2:
输入: 4
输出: "IV"
示例 3:
输入: 9
输出: "IX"
解法1:递归
取余，取整法，判断特殊条件
public static String intToRoman(int num) {
StringBuilder sb = new StringBuilder();
int divided = num/1000;
while (divided>0){
sb.append("M");
divided--;
}
initSb(num%1000,sb);
return sb.toString();
}
private static void initSb(int remainder, StringBuilder sb) {
if(remainder>=500){
if(remainder/900>0){
sb.append("CM");
initSb(remainder%900,sb);
}else {
int temp = remainder/500;
while (temp>0){
sb.append("D");
temp--;
}
initSb(remainder%500,sb);
}
}
else if(remainder>=100){
if(remainder/400>0){
sb.append("CD");
initSb(remainder%400,sb);
}else {
int temp = remainder/100;
while (temp>0){
sb.append("C");
temp--;
}
initSb(remainder%100,sb);
}
}else if(remainder>=50){
if(remainder/90>0){
sb.append("XC");
initSb(remainder%90,sb);
}else {
int temp = remainder/50;
while (temp>0){
sb.append("L");
temp--;
}
initSb(remainder%50,sb);
}
}else if(remainder>=10){
if(remainder/40>0){
sb.append("XL");
initSb(remainder%40,sb);
} else {
int temp = remainder/10;
while (temp>0){
sb.append("X");
temp--;
}
initSb(remainder%10,sb);
}
}else if(remainder>=5){
if(remainder/9>0){
sb.append("IX");
initSb(remainder%9,sb);
}else {
int temp = remainder/5;
while (temp>0){
sb.append("V");
temp--;
}
initSb(remainder%5,sb);
}
}else if (remainder>=1) {
if (remainder / 4 > 0) {
sb.append("IV");
initSb(remainder % 4, sb);
} else {
while (remainder > 0) {
sb.append("I");
remainder--;
}
}
return;
}
}
解法2:贪心算法
初始化两个数组，把映射关系搞好，相当于纸币组合，多少个纸币数量最小即可
public static String intToRoman2(int num) {
int[] a = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
String[] b = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
String res = "";
int index = 0;
while(index<13){
while (num>=a[index]){
res += b[index];
num -= a[index];
}
index++;
}
return res;
}
5.给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
解题思路：
a.把数字和字母映射成一个数组
b.用char特有的“-'0'“映射成数字
c.使用手工栈模拟深度优先
d.使用递归把所有的组合模拟出来
e.用两个变化值，一个是char数组栈的栈底元素，一个是深度，不停的出栈入栈
f.需要知道char数组把最后的元素删除可以使用char[i]='\u0000';
g.需要知道char数组变成字符串可以用new String(chars);
public List<String> letterCombinations(String digits){
if(digits == null || digits.equals("")){
return new ArrayList<>();
}
String[] keyMap = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
//模拟栈
char[] chars = new char[digits.length()];
List<String> res = new ArrayList<>();
//栈的索引值
int chars_index = -1;
//深度
int cur_num = 0;
//深度优先
dfs(cur_num,chars,keyMap,chars_index,digits,res);
return res;
}
private void dfs(int cur_num,char[] chars, String[] keyMap, int chars_index, String digits, List<String> res) {
//超过深度，直接返回
if(cur_num == digits.length()){
res.add(new String(chars));
return;
}
//第n层深度的数字
int cur_index = digits.charAt(cur_num)-'0';
//数字为0或者1直接返回
if(cur_index<=1){
return;
}
//遍历对应数字映射的字符串
for(int i = 0;i<keyMap[cur_index].length();i++){
//char字符入栈
chars_index++;
chars[chars_index] = keyMap[cur_index].charAt(i);
//深入一层搜索
dfs(cur_num+1,chars,keyMap,chars_index,digits,res);
//搜索完后需要出栈,为下一个数进栈做准备
chars[chars_index] = '\u0000';
chars_index--;
}
}
九 栈
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
解题思路：经典栈用法
public static boolean isValid(String s) {
if(s == null || s.length() == 0 || (s.length()&1) == 1){
return false;
}
char[][] window = {{'(',')'},{'[',']'},{'{','}'}};
Stack<Character> stack = new Stack<>();
for(int i = 0;i<s.length();i++){
for(int j = 0;j<3;j++){
if(s.charAt(i) == window[j][0]){
stack.push(s.charAt(i));
break;
} else if(s.charAt(i) == window[j][1] && !stack.isEmpty() && stack.peek() == window[j][0]){
stack.pop();
break;
}
}
}
return stack.isEmpty();
}
2.设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) -- 将元素 x 推入栈中。
pop() -- 删除栈顶的元素。
top() -- 获取栈顶元素。
getMin() -- 检索栈中的最小元素。
示例:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
解题思路：
/**
* 栈长度
*/
private int length;
/**
* 栈中最小值
*/
private int min = Integer.MIN_VALUE;
/**
* 元素list
*/
private List<Integer> stack = new LinkedList<>();
/**
* 栈顶元素
*/
int element;
/**
* 初始化栈
*/
public MinStack() {
length = 0;
}
public void push(int x) {
if(length == 0){
min = x;
}
stack.add(x);
length++;
min = Math.min(x,min);
}
public void pop() {
element = stack.get(length-1);
stack.remove(length-1);
length--;
//如果移除的是最小值，找到新的最小值
if(!stack.isEmpty() && min == element){
min = stack.get(length-1);
int i = length-1;
while (i>=0){
min = Math.min(min,stack.get(i--));
}
} else if(stack.isEmpty()){
min = Integer.MIN_VALUE;
}
}
public int top() {
return stack.get(length-1);
}
public int getMin() {
return min;
}
public int getLength() {
return length;
}
public void setLength(int length) {
this.length = length;
}
public void setMin(int min) {
this.min = min;
}
public List<Integer> getStack() {
return stack;
}
public void setStack(List<Integer> stack) {
this.stack = stack;
}
public int getElement() {
return element;
}
public void setElement(int element) {
this.element = element;
}
网友评论