1、(206). Reverse Linked List
Reverse a singly linked list.
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */public class Solution { public ListNode reverseList(ListNode head) { if (head == null || head.next == null) { return head; } ListNode cur = head; ListNode PRev = null; ListNode tmp = null; while (cur != null) { tmp = cur.next; cur.next = prev; prev = cur; cur = tmp; } return prev; }}凡是涉及到交换,一般都要涉及到新建一个临时的第三方变量。
2、( 445). Add Two Numbers II
You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.You may assume the two numbers do not contain any leading zero, except the number 0 itself.Follow up:What if you cannot modify the input lists? In other Words, reversing the lists is not allowed.Example:Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)Output: 7 -> 8 -> 0 -> 7
方法一:利用链表转置和链表合并求和(链表合并的基础上求和)
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ /** * Way 1: Use reverse LinkedList */public class Solution { private ListNode reverseLList(ListNode head) { if (head == null || head.next == null) { return head; } ListNode cur = head; ListNode prev = null; ListNode tmp = null; while (cur != null) { tmp = cur.next; cur.next = prev; prev = cur; cur = tmp; } return prev; } private ListNode mergeSum(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(-1); ListNode backup = dummy; int overflow = 0; int tmpSum = 0; while (l1 != null && l2 != null) { tmpSum = l1.val + l2.val + overflow; if (tmpSum >= 10) { overflow = 1; tmpSum = tmpSum % 10; } else { overflow = 0; } dummy.next = new ListNode(tmpSum); dummy = dummy.next; l1 = l1.next; l2 = l2.next; } while (l1 != null) { tmpSum = l1.val + overflow; if (tmpSum >= 10) { overflow = 1; tmpSum = tmpSum % 10; } else { overflow = 0; } dummy.next = new ListNode(tmpSum); dummy = dummy.next; l1 = l1.next; } while (l2 != null) { tmpSum = l2.val + overflow; if (tmpSum >= 10) { overflow = 1; tmpSum = tmpSum % 10; } else { overflow = 0; } dummy.next = new ListNode(tmpSum); dummy = dummy.next; l2 = l2.next; } if (overflow != 0) {//错误1 dummy.next = new ListNode(overflow); dummy = dummy.next; } return backup.next; } public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode headL1 = reverseLList(l1); ListNode headL2 = reverseLList(l2); ListNode ans = mergeSum(headL1, headL2); ans = reverseLList(ans); return ans; }}这题犯的错误在于:忘了考虑两个相等位数的数相加要是有进位的时候,要把进位放进结果里。
方法二:不实际转置链表,利用stack来实现转置。写这个程序时,犯了两个错误:1) LinkedList实现stack的时候,注意如果直接使用removeLast()的方法时,当LinkedList为空,会直接返回NoSuchElement 的run time exception,而使用peekLast() 则只会返回空。另外,可以使用isEmpty()来检查是否为空。2)StackReverse是为了产生一个新的链表,当你产生一个新的链表时,需要构建的每一个都要构造一个新的节点,不能连接到旧的节点。(Deep Copy那题也犯了这个错误)
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */public class Solution { private ListNode stackReverse (ListNode head) { LinkedList<ListNode> stack = new LinkedList<ListNode>(); ListNode dummy = new ListNode(-1); ListNode backupDummy = dummy; ListNode tmp = null; //put all the listnode into the stack while (head != null) { stack.addLast(head); head = head.next; } //pop all the listnode and construct a new linkedlist while (!(stack.isEmpty())) {//注意补充下API的知识 tmp = stack.removeLast(); dummy.next = new ListNode(tmp.val); dummy = dummy.next; } return backupDummy.next; } private ListNode mergeSum(ListNode l1, ListNode l2) { int tmpSum = 0; int overFlow = 0; ListNode dummy = new ListNode(-1); ListNode backupDummy = dummy; while (l1 != null && l2 != null) { tmpSum = l1.val + l2.val + overFlow; if (tmpSum >= 10) { overFlow = 1; tmpSum = tmpSum % 10; } else { overFlow = 0; } dummy.next = new ListNode(tmpSum); dummy = dummy.next; l1 = l1.next; l2 = l2.next; } while (l1 != null) { tmpSum = l1.val + overFlow; if (tmpSum >= 10) { overFlow = 1; tmpSum = tmpSum % 10; } else { overFlow = 0; } dummy.next = new ListNode(tmpSum); dummy = dummy.next; l1 = l1.next; } while (l2 != null) { tmpSum = l2.val + overFlow; if (tmpSum >= 10) { overFlow = 1; tmpSum = tmpSum % 10; } else { overFlow = 0; } dummy.next = new ListNode(tmpSum); dummy = dummy.next; l2 = l2.next; } //do not forget the overflow if (overFlow != 0) { dummy.next = new ListNode(overFlow); overFlow = 0; dummy = dummy.next; } return backupDummy.next; } public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode newListOne = stackReverse(l1); ListNode newListTwo = stackReverse(l2); ListNode ans = mergeSum(newListOne, newListTwo); ListNode answer = stackReverse(ans); return answer; }}3/ (138.)Copy List with Random Pointer
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.Return a deep copy of the list.
这道题有两种方法,具体的可以参考刷题题库1.这里作简略描述:
方法一:使用hashtable,遍历整个链表,把每个节点的新节点(注意不是random节点,这里想错了)存在hashtable,同时创建一个没有random pointer但其余一样的链表。然后第二遍再通过hashtable连接random pointer。(注意,是新建的random节点,不是旧的节点。)
/** * Definition for singly-linked list with a random pointer. * class RandomListNode { * int label; * RandomListNode next, random; * RandomListNode(int x) { this.label = x; } * }; */public class Solution { public RandomListNode copyRandomList(RandomListNode head) { if (head == null) { return null; } HashMap<RandomListNode, RandomListNode> nodeNewNode = new HashMap<RandomListNode, RandomListNode>(); RandomListNode cur = head; RandomListNode dummy = new RandomListNode(-1); // new linkedlist's dummy RandomListNode backDummy = dummy; RandomListNode tmp = null; while (cur != null) { tmp = new RandomListNode(cur.label); dummy.next = tmp; nodeNewNode.put(cur,tmp); cur = cur.next; dummy = dummy.next; } // scan the new linked list and write the random pointers cur = head; RandomListNode newHead = backDummy.next; while (cur != null && newHead != null) { RandomListNode randomTmp = nodeNewNode.get(cur.random); newHead.random = randomTmp; cur = cur.next; newHead = newHead.next; } return backDummy.next; }}方法二:Follow up的题目如果是想利用空间复杂度为O(1)的方法实现呢?这时候就要巧妙一点了。具体的图可以参考链接:http://blog.csdn.net/firehotest/article/details/52665467。简而言之,就是先把复制的节点放在原节点后面,然后再扫一遍的时候,复制random域和断开多余的链接。(明天写这个版本)
/** * Definition for singly-linked list with a random pointer. * class RandomListNode { * int label; * RandomListNode next, random; * RandomListNode(int x) { this.label = x; } * }; */public class Solution { public RandomListNode copyRandomList(RandomListNode head) { if (head == null) { return null; } RandomListNode tmp = null; RandomListNode cur = head; RandomListNode prev = null; while (cur != null) { prev = cur; cur = cur.next; tmp = new RandomListNode(prev.label); tmp.next = cur; prev.next = tmp; } //connect the random fields cur = head.next; prev = head; tmp = cur; while (cur != null) { if (prev.random != null) { cur.random = prev.random.next; } else { cur.random = null; } if (cur.next == null) { break; } prev = prev.next.next; cur = cur.next.next; } cur = head.next; prev = head; //disconnect the copy and origin while (cur != null) { prev.next = cur.next; if (cur.next != null) { cur.next = cur.next.next; } else { cur.next = null; break; } prev = prev.next; cur = cur.next; } return tmp; }}4/ (121.) Best Time to Buy and Sell Stock
这道题的做法参考插入排序的做法,设立一个变量作为临时的结果变量,不断更新,直到遍历完整个数组。在这里的临时结果变量有哪些呢?想要获得最大的profit,必须是以当前的或者之后的价格减去目前已有的最小价格。
所以这道题应该这么做:
public class Solution { public int maxProfit(int[] prices) { if (prices == null || prices.length == 0) { return 0; } int profit = 0; int minPrice = prices[0]; for (int i = 0; i < prices.length; i++) { if (prices[i] < minPrice) { minPrice = prices[i]; } for (int j = i + 1; j < prices.length; j++) { profit = Math.max(profit, prices[j] - minPrice); } } return profit; }}但这个算法其实不用写两个循环,可以用一个算法解决:public class Solution { public int maxProfit(int[] prices) { if (prices == null || prices.length == 0) { return 0; } int minPrice = prices[0]; int profit = 0; for (int tmp : prices) { if (tmp < minPrice) { minPrice = tmp; } profit = Math.max(profit, tmp - minPrice); } return profit; }}之前还写过一个算法,实现把每一个时间点买入的最大profit求出来,更新最大的profit即可。但还是上述的方法最简单。5/ (283.) Move Zeroes
Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].Note:You must do this in-place without making a copy of the array.Minimize the total number of Operations.
其实这道题的思路也十分简单,利用移位复制的方法,这个方法称为insertion index.
public class Solution { public void moveZeroes(int[] nums) { int index = 0; int n = 0; while (n < nums.length) { if (nums[n] != 0) { nums[index++] = nums[n]; } n = n + 1; } while (index < nums.length) { nums[index++] = 0; } }}6/ (1.) Two Sum
Given an array of integers, return indices of the two numbers such that they add up to a specific target.You may assume that each input would have exactly one solution, and you may not use the same element twice.Example:Given nums = [2, 7, 11, 15], target = 9,Because nums[0] + nums[1] = 2 + 7 = 9,return [0, 1].
public class Solution { public int[] twoSum(int[] nums, int target) { if (nums == null || nums.length < 2) { return null; } HashMap<Integer, Integer> valIndex = new HashMap<Integer, Integer>(); for (int i = 0; i < nums.length; i++) { if (valIndex.containsKey(target - nums[i])) { return new int[]{i,valIndex.get(target - nums[i])}; } else { valIndex.put(nums[i],i); } } return new int[2]; }}这题犯的错是,一开始打算把所有的值当做key,然后存在index作为value。但是,漏了考虑要是有重复值的话,就会被覆盖了。只有像答案这样,优先检查是否有匹配值,有匹配值就马上匹配就好。
新闻热点
疑难解答