1.两数相加:
1.1. 题目描述：
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例:
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807
1.2. 题解：
参考链解：动画演示 2. 两数相加
我们不断的遍历两个链表，每次遍历都将链表a和链表b的值相加，再赋给链表a。如果有进位我们还需要记录一个进位标志。循环的条件是链表a不为空或者链表b不为空，这样当整个循环结束时，链表就被串起来了。
当循环结束时，如果进位标志>0还需要处理下边界条件。我们不用生成一个新的节点，直接将两个节点相加的值赋给节点a就可以了，这样只用改变节点的内容，速度会更快一些。
代码：
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode p = null;
ListNode a = l1;
ListNode b = l2;
//定义一个进位标志
int carry = 0;
while(a!=null || b!=null) {
//a和b节点的值相加，如果有进位还要加上进位的值
int val = (a==null?0:a.val) + (b==null?0:b.val) + carry;
//根据val判断是否有进位
carry = val>=10? 1:0;
//不管有没有进位，val都应该小于10
val = val%10;
p = (a==null? b : a);
p.val = val;
//a和b指针都前进一位
a = (a==null? null : a.next);
b = (b==null? null : b.next);
//根据a和b是否为空，p指针也前进一位
p.next = (a==null? b : a);
}
//不要忘记最后的边界条件，如果循环结束carry>0说明有进位需要处理这个条件
if(carry>0) {
p.next = new ListNode(1);
}
//每次迭代实际上都是将val赋给a指针的，所以最后返回的是l1
return l1;
}
}
2.有效的括号：
2.1. 题目描述：
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例1：
输入:"()"
输出:true
示例2
输入:"(){}[]"
输出:true
示例3
输入:"(]"
输出:false
2.1. 题解：
这道题就像开心消消乐一样，同一组括号可以被消去，看是否可以将所有的括号消去。这里要用到栈这一种数据结构
栈教程：https://zhuanlan.zhihu.com/p/26944032
消去的方式有两种：
- 对于每一个新的括号，若其能与栈顶的括号匹配，则栈顶出栈，若不能匹配，则将当前的括号入栈，进入下一次循环………..
伪代码：
for s1 in s: // 遍历所有括号字符串s的全部括号
若栈不为空 并且 s1与栈顶元素匹配
栈顶元素出栈
不然
s1入栈
判断是否消去完成
代码:
import java.util.*;
class Solution {
boolean equals(char s1, char s2){
if(s1=='(' && s2==')')
return true;
if(s1=='{' && s2=='}')
return true;
if(s1=='[' && s2==']')
return true;
return false;
}
public boolean isValid(String s) {
if(s.length()==0)
return true;
if(s.length()==1)
return false;
Stack<Character> stack = new Stack();
stack.push(s.charAt(0));
for(int i=1;i<s.length();++i){
if(!stack.empty()&&equals(stack.peek(), s.charAt(i)))
stack.pop();
else
stack.push(s.charAt(i));
}
return stack.empty();
}
}
但这种方式是可以优化的，因为只要出现了")"，"]"，"}"与栈顶元素不匹配的情形，对于整个字符串都应该是不匹配的。下一种消去方法就应用了这种原理
遍历所有括号 ，若当前括号为"("、"["、"{"就将其入栈，若不是就推出栈顶元素，并将其与当前括号匹配，若失配则返回false，成功就进入下一次循环 …. ……. .
class Solution {
public static boolean isValid(String s) {
char[] chars=s.toCharArray();
char[] stack=new char[chars.length];
int len=-1;
for (int i = 0; i < chars.length; i++) {
switch (chars[i]) {
case '[':
case '(':
case '{':
stack[++len]=chars[i];
break;
default:
if (len>-1) {
char pre=stack[len--];
if (chars[i]==']' && pre != '[' || chars[i]==')' && pre !='(' || chars[i]=='}' && pre!='{') {
return false;
}
}else {
return false;
}
break;
}
}
if (len==-1) {
return true;
}
return false;
}
}
3.和至少为K的最短子数组
3.1 题目描述：
返回 A 的最短的非空连续子数组的长度，该子数组的和至少为 K 。
如果没有和至少为 K 的非空子数组，返回 -1 。
示例 1：
输入：A = [1], K = 1
输出：1
示例2：
输入：A = [1,2], K = 4
输出：-1
示例 3：
输入：A = [2,-1,2], K = 3 输出：3
提示：
1 <= A.length <= 50000
-10 ^ 5 <= A[i] <= 10 ^ 5
1 <= K <= 10 ^ 9
3.2. 题解:
参考链接:和至少为 K 的最短子数组详解Shortest Subarray with Sum at Least K
思路:看题目的连续子数组就和容易想到用动态规划的思想来减少计算.
preSum[i+1] = A[0]+A[1]+A[2]+...+A[i]
这样就可以通过相减的方式,得到所有的连续子数组,并且preSum[0]=0(得到长度为1的子数组),不这样的话,需要添加许多if语句.
找到能满足这个不等式 preSum[ i ] – preSum[ j ] >= K 并且i-j最小,preSum[ i ] – preSum[ j ] 表示第j个元素到第i个元素的和.
class Solution {
public int shortestSubarray(int[] A, int K) {
int minLen = A.length + 1;
int[] preSum = new int[A.length + 1];
preSum[0] = 0; // 可省略
for (int i = 0; i < A.length; i++) {
preSum[i + 1] = preSum[i] + A[i];
}
for (int i = 0; i < A.length; i++) {
for (int j = i + 1; j < A.length + 1; j++) {
if (preSum[j] - preSum[i] >= K) {
if ((j - i) < minLen) {
minLen = j - i;
}
}
}
}
return minLen == A.length + 1 ? -1 : minLen;
}
}
这种方式的时间复杂度是O(N*N),并不能AC这道题,主要是因为在循环中, 存在着不必要的执行步骤.
在上面那个双层循环中，还有一定的优化空间的。
1. 比如当preSum[x2] <= preSum[x1]（其中x1 < x2）时，表明x1到x2之间的元素的和是负数或0，那么就是当preSum[xn] - preSum[x1] >= K则必然有preSum[xn] - preSum[x2] >= K，那么这个时候我们只计算xn - x2即可（x1到x2之间的元素可以全部跳过了，耶！），就不需要计算xn - x1了，因为后者一定是更大的，不满足我们要选最小的条件。
2. 另一个角度，当preSum[x2] - preSum[x1] >= K时，x1就可以跳过了，为什么呢？因为x1到x2已经满足了大于K，再继续从x1开始向后再早，也不会再有比x2距离x1更近的了，毕竟我们要求的是最小的x2 - x1。
以上的两种分析，情况1是把位于末尾没用的x1扔掉，情况2是把指向前面的已经满足条件的x1的指针向后移动1位，这是就需要比较当前最小值与此时刚符合条件的值的大小了。
class Solution {
public int shortestSubarray(int[] A, int K) {
int minLen = A.length + 1;
int[] preSum = new int[A.length + 1];
preSum[0] = 0;
for (int i = 0; i < A.length; i++) {
preSum[i + 1] = preSum[i] + A[i];
}
Deque<Integer> deque = new LinkedList<>();
for (int i = 0; i < A.length + 1; i++) {
while (!deque.isEmpty() && preSum[i] <= preSum[deque.getLast()]) {
// 1.
deque.pollLast();
}
while (!deque.isEmpty() && preSum[i] - preSum[deque.getFirst()] >= K) {
// 2.
int new_len = i - deque.pollFirst();
if (new_len < minLen) {
minLen = new_len;
}
}
deque.addLast(i);
}
return minLen == A.length + 1 ? -1 : minLen;
}
}