第155题-最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) —— 将元素 x 推入栈中。 pop() —— 删除栈顶的元素。 top() —— 获取栈顶元素。 getMin() —— 检索栈中的最小元素。
示例:
输入： ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]]
输出： [null,null,null,null,-3,null,0,-2]
解释： MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.
解题思路
就是用一个最小栈来记录最小值
Stack<Integer> stack; Stack<Integer> minStack; /** initialize your data structure here. */ public MinStack() { stack = new Stack<Integer>(); minStack = new Stack<Integer>(); } public void push(int x) { if(minStack.size()==0||x<=minStack.peek()) { minStack.push(x); } stack.push(x); } public void pop() { if(stack.peek().equals(minStack.peek())) { minStack.pop(); } stack.pop(); } public int top() { return stack.peek(); } public int getMin() { return minStack.peek(); }点击复制代码复制出错复制成功
第160题-相交链表
编写一个程序，找到两个单链表相交的起始节点。
如下面的两个链表：
在节点 c1 开始相交。
解题思路
分别计算出链表A，链表B的长度，让长的链表先走n步，直到两个链表剩余节点长度一样，然后每个链表都走一步，直到节点相等，即为相交节点。
public ListNode getIntersectionNode(ListNode headA, ListNode headB) { int lengthA=0; ListNode nodeA = headA; while(nodeA!=null) { lengthA++; nodeA=nodeA.next; } int lengthB=0; ListNode nodeB = headB; while(nodeB!=null) { lengthB++; nodeB=nodeB.next; } nodeA = headA; nodeB = headB; while(lengthA!=lengthB) { if (lengthA>lengthB) { lengthA--; nodeA = nodeA.next; } else { lengthB--; nodeB = nodeB.next; } } while(nodeA!=null && nodeB!=null) { if(nodeA == nodeB) { return nodeA; } nodeA = nodeA.next; nodeB = nodeB.next; } return null; }点击复制代码复制出错复制成功
第142题-环形链表II
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
说明：不允许修改给定的链表。
进阶：
你是否可以使用 O(1) 空间解决此题？
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：返回索引为 1 的链表节点 解释：链表中有一个环，其尾部连接到第二个节点。
解题思路
public ListNode detectCycle(ListNode head) { //快慢节点在圆中相遇 //然后慢节点在圆中走一圈，计算出圆的周长 //快节点凑头 if (head==null || head.next == null) { return null; } ListNode slow = head.next; ListNode quick = head.next.next; //通过快慢指针，让两个指针在环中相遇 while (quick!=slow) { if (quick == slow && quick!=null) { break; } slow = slow.next; if (quick==null||quick.next == null) { return null; } quick = quick.next; quick = quick.next; } //计算环的长度 int circleLength = 1; ListNode copySlow = slow.next; while (copySlow != slow) { copySlow = copySlow.next; circleLength++; } //快指针先走环的长度步 quick = head; while (circleLength>0) { quick = quick.next; circleLength--; } slow = head; //慢指针出发，相遇的节点就是环的入口 while (quick!=slow) { quick = quick.next; slow = slow.next; } return quick; }点击复制代码复制出错复制成功
第739题-每日温度
请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。
例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。
解题思路
其实跟滑动窗口最大值那个题的解题思路很像，就是维护一个还没有排序好的栈，每次把栈中比当前遍历元素小的，都出栈，然后计算等待天数，然后将当前元素入栈。
public int[] dailyTemperatures(int[] T) { if (T == null || T.length==0) { return null; } int[] result = new int[T.length]; Stack<Integer> stack = new Stack<>(); stack.add(0); for (int i = 1; i < T.length; i++) { //比栈顶元素小，栈 if (stack.size() == 0 || T[i] <= T[stack.peek()]) { stack.push(i); } else { // 比栈顶元素大，就一直出栈 while (stack.size() >0 && T[i] > T[stack.peek()]) { int index = stack.pop(); result[index] = i - index; } stack.push(i); } } return result; }点击复制代码复制出错复制成功
第347题-前K个高频元素
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2] 示例 2:
输入: nums = [1], k = 1 输出: [1]
解题思路
先使用一个HashMap来统计各元素的频率，然后取前k个元素建立小顶堆，然后对后面的元素进行遍历，如果频率高于堆顶元素，就与堆顶元素交换，然后对堆进行调整。
public int[] topKFrequent(int[] nums, int k) { HashMap<Integer,Integer> map = new HashMap<Integer,Integer>(); for(int i = 0;i<nums.length;i++) { Integer value = map.get(nums[i]); value = value == null ? 1 : value+1; map.put(nums[i],value); } Object[] array = map.keySet().toArray(); //进行堆排 int[] result = new int[k]; for (int i = 0; i < k; i++) { result[i] = (Integer)array[i]; } //建立小顶堆 for (int i = result.length/2-1; i >= 0; i--) { adjustHeap(result,i,result.length,map); } for (int i = k; i < array.length ; i++) { Integer key = (Integer) array[i]; if (map.get(key) >= map.get(result[0])) { result[0] = (Integer)array[i]; adjustHeap(result,0,result.length,map); } } return result; } void adjustHeap(int[] array, int i,int length,HashMap<Integer,Integer> map) { while (2*i+1<length) {//左节点存在 int left = 2*i+1; int right = 2*i+2; int min = map.get(array[i]) < map.get(array[left]) ? i : left; if (right<length && map.get(array[right]) < map.get(array[min])) {//右节点存在，并且还比最大值大 min = right; } if (min == i) {//当前已经是最小值 break; } else {//左节点或者右节点是最小值，那么就将当前节点与最小的节点交换 swap(array,i,min); i = min; } } } void swap(int[] array, int a,int b) { int temp = array[a]; array[a] = array[b]; array[b] = temp; }点击复制代码复制出错复制成功
第49题-字母异位词分组
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"] 输出: [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ] 说明：
所有输入均为小写字母。 不考虑答案输出的顺序。
解题思路
就是对字符串进行遍历，取出每个字符串，计算它对应的字典序最小的字符串(例如："ate","eat","tea"，他们字典序最小的字符串是"aet")，然后判断map中是否存在，不存在就创建一个List，将字符串添加进去，存在就在原List中添加该字符串。
public List<List<String>> groupAnagrams(String[] strs) { HashMap<String,List> map = new HashMap<String,List>(); for (String str : strs) { char[] charArray = str.toCharArray(); Arrays.sort(charArray); String sortedString = new String(charArray); List strList = map.get(sortedString); if (strList == null) { strList = new LinkedList(); } strList.add(str); map.put(sortedString,strList); } ArrayList totalList = new ArrayList<>(); totalList.addAll(map.values()); return totalList; }点击复制代码复制出错复制成功
第32题-最长有效括号
给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
示例 1:
输入: "(()" 输出: 2 解释: 最长有效括号子串为 "()" 示例 2:
输入: ")()())" 输出: 4 解释: 最长有效括号子串为 "()()"
解题思路
判断一个字符是否在是有效括号，就是对字符串遍历，如果是(，就将(字符入栈，如果是）字符，就判断栈是否为有元素，有元素代表括号匹配上了，将当前括号和栈顶元素括号都标记为有效括号。标记的方式是将recordArray数组中相应下标置为1，然后统计最长有效括号就是统计recordArray数组中连续1的个数。
public int longestValidParentheses(String s) { Stack<Integer> stack = new Stack(); int[] recordArray = new int[s.length()]; for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (c=='(') { stack.push(i); } else if (c==')' && stack.size()>0) { //说明这个位置可以匹配 recordArray[i]=1; int leftIndex = stack.pop(); recordArray[leftIndex] = 1; } } //统计recordArray张连续1的长度 int max = 0; int currentSize =0; for (int i = 0; i < recordArray.length; i++) { if (recordArray[i] ==0) { currentSize=0; } else if (recordArray[i] ==1) { currentSize++; } max = max > currentSize ? max : currentSize; } return max; }
