Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container and n is at least 2.
The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
Example
1 2
Input: [1,8,6,2,5,4,8,3,7] Output: 49
解：方法一，枚举。记录左边bar x, 右边 bar y，遍历每一个x和y的组合，计算(x-y)*height_diff，但是时间复杂度太高了，O(n^2)，显然不是最优解法。
但是这里可以回顾一下遍历数组的固定写法，形成机械记忆，一定要熟悉。
正常遍历一维数组：
1
for(int i = 0; i < height.length; i++) {
遍历二维数组，实现 i 和 j 两个下标对数组的遍历，而且 i 和 j 不会重复
1 2 3 4
for(int i = 0; i < height.length-1; i++) { for(int j = i+1; j < height.length; j++) { } }
这一段二维数组的遍历应当形成肌肉式记忆。 整个遍历过程中，j 总是比 i 大，最后j到了最后一个元素，i还在前面。当然，这种暴力的方式很慢，开销很大。
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note: The solution set must not contain duplicate triplets.(答案不能包含重复三元组)
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ classSolution{ public ListNode reverseBetween(ListNode head, int m, int n){ if(head == null) returnnull;
// create a dummy node to mark the head of this list ListNode dummy = new ListNode(0); dummy.next = head; // make a pointer pre as a marker for the node before reversing ListNode pre = dummy; for(int i = 0; i < m-1; i++) pre = pre.next; // a pointer to the beginning of a sub-list that will be reversed ListNode start = pre.next; // a pointer to a node that will be reversed ListNode then = start.next; // 1 - 2 -3 - 4 - 5 ; m=2; n =4 ---> pre = 1, start = 2, then = 3 // dummy-> 1 -> 2 -> 3 -> 4 -> 5 for(int i=0; i < n-m; i++) { start.next = then.next; then.next = pre.next; pre.next = then; then = start.next; } // first reversing : dummy->1 - 3 - 2 - 4 - 5; pre = 1, start = 2, then = 4 // second reversing: dummy->1 - 4 - 3 - 2 - 5; pre = 1, start = 2, then = 5 (finish) return dummy.next; } }
Given a linked list, determine if it has a cycle in it.
To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.
Example 1:
1 2 3 4
Input: head = [3,2,0,-4], pos = 1 Output: true Explanation: There is a cycle in the linked list, where tail connects to the second node.
Example 2:
1 2 3
Input: head = [1,2], pos = 0 Output: true Explanation: There is a cycle in the linked list, where tail connects to the first node.
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.
Note: Do not modify the linked list.
Example 1:
1 2 3
Input: head = [3,2,0,-4], pos = 1 Output: tail connects tonode index 1 Explanation: There is a cycle in the linked list, where tail connects to the second node.
Example 2:
1 2 3
Input: head = [1,2], pos = 0 Output: tail connects tonode index 0 Explanation: There is a cycle in the linked list, where tail connects to the first node.
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
Example:
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5
Note:
Only constant extra memory is allowed.
You may not alter the values in the list’s nodes, only nodes itself may be changed.
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ classSolution{ public ListNode reverseKGroup(ListNode head, int k){ ListNode curr = head; int count = 0; while(curr != null && count != k) { // To find the k+1 node curr = curr.next; count++; } if(count == k) { curr = reverseKGroup(curr, k); // reverse list with k+1 node as head // head - head-pointer to direct part // curr - head-pointer to reversed part while(count-- > 0) { // reverse the k-group ListNode tmp = head.next; //tmp - next head in direct part head.next = curr; // preappending "direct" head to the reversed list curr = head; //move head of reversed part to a new node head = tmp; // move ""direct" head to the next node in direct part } head = curr; } return head; } }
Given a sorted array nums, remove the duplicates in-place(原地操作) such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
Example 1:
1 2 3 4 5
Given nums = [1,1,2],
Your functionshouldreturnlength = 2, with the first two elements of nums being 1and2 respectively.
It doesn't matter what you leave beyond the returned length.
Example 2:
1 2 3 4 5
Given nums = [0,0,1,1,1,2,2,3,3,4],
Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.
It doesn't matter what values are set beyond the returned length.
Clarfication: Confused why the returned value is an integer but your answer is an array?
Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.
Internally you can think of this:
1 2 3 4 5 6 7 8
// nums is passed in by reference. (i.e., without making a copy) intlen = removeDuplicates(nums);
// any modification to nums in your function would be known by the caller. // using the length returned by your function, it prints the first len elements. for (int i = 0; i < len; i++) { print(nums[i]); }
Given an array, rotate the array to the right by k steps, where k is non-negative.
Example 1:
1 2 3 4 5 6
Input: [1,2,3,4,5,6,7] and k = 3 Output: [5,6,7,1,2,3,4] Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate 2 steps to the right: [6,7,1,2,3,4,5] rotate 3 steps to the right: [5,6,7,1,2,3,4]
Example 2:
1 2 3 4 5
Input: [-1,-100,3,99] and k = 2 Output: [3,99,-1,-100] Explanation: rotate 1 steps to the right: [99,-1,-100,3] rotate 2 steps to the right: [3,99,-1,-100]
Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
Could you do it in-place with O(1) extra space?
解：给出三种解法。
方法一，双重循环，比较暴力。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
classSolution{ publicvoidrotate(int[] nums, int k){ // 按照轮次来做，每一轮操作一个数字 int len = nums.length; // 如果k太大，甚至比nums还大，那么移动过程会经过了一轮。这里k表示最后要位移的位数 k %= len; for(int i = 0; i < k; i++) { //temp 保存最后一个元素的值 int temp = nums[len - 1]; for(int j = len-1; j > 0; j--) { nums[j] = nums[j-1]; } nums[0] = temp; } } }
时间复杂度：O(kn)
空间复杂度：O(1)
方法二
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
classSolution{ publicvoidrotate(int[] nums, int k){ int nums_length = nums.length; k %= nums_length; // 第一次交换完毕后，前 k 位数字位置正确，后 n-k 位数字中最后 k 位数字顺序错误，继续交换 for (int start = 0; start < nums.length && k != 0; nums_length -= k, start += k, k %= nums_length) { for (int i = 0; i < k; i++) { swap(nums, start + i, nums.length - k + i); } } }
privatevoidswap(int [] nums, int i, int j){ int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } }
时间复杂度:O(n) 空间复杂度：O(1)
方法三，翻转，最巧妙。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
classSolution{ publicvoidrotate(int[] nums, int k){ int len = nums.length; // 如果k太大，甚至比nums还大，那么移动过程会经过一轮，在这里k表示最后要位移的位数。 k %= len; reverse(nums,0,len-1); reverse(nums,0,k-1); reverse(nums,k,len-1); } privatevoidreverse(int[] nums, int start, int end){ while(start < end) { int temp = nums[start]; nums[start++] = nums[end]; nums[end--] = temp; } } }
classSolution{ publicvoidmerge(int[] nums1, int m, int[] nums2, int n){ // 更加酷，不需要开辟额外空间，直接在nums1的末尾开始，用三个指针从后往前 // two pointers for nums1 and nums2 int p1 = m - 1; int p2 = n - 1; // set pointer for nums1 int p = m + n - 1;
// while there are still elements to compare while((p1 >= 0) && (p2 >= 0)) { // compare two elements from nums1 and nums2 and add the largest // one in nums1 nums1[p--] = (nums1[p1] < nums2[p2]) ? nums2[p2--] : nums1[p1--]; } // add missing elements from nums2 // 如果先触发了p1 < 0的条件，nums2不再能copy了，需要手动arraycopy过去 System.arraycopy(nums2, 0, nums1, 0, p2 + 1); } }
Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.
Given linked list – head = [4,5,1,9], which looks like following:
Example 1:
Input: head = [4,5,1,9], node = 5 Output: [4,1,9] Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.
Example 2:
Input: head = [4,5,1,9], node = 1 Output: [4,5,9] Explanation: You are given the third node with value 1, the linked list should become 4 -> 5 -> 9 after calling your function.
Note:
The linked list will have at least two elements.
All of the nodes’ values will be unique.
The given node will not be the tail and it will always be a valid node of the linked list.
Given a linked list, rotate the list to the right by k places, where k is non-negative.
Example 1:
1 2 3 4 5
Input: 1->2->3->4->5->NULL, k = 2 Output: 4->5->1->2->3->NULL Explanation: rotate 1 steps to the right: 5->1->2->3->4->NULL rotate 2 steps to the right: 4->5->1->2->3->NULL
Example 2:
1 2 3 4 5 6 7
Input: 0->1->2->NULL, k = 4 Output: 2->0->1->NULL Explanation: rotate 1 steps to the right: 2->0->1->NULL rotate 2 steps to the right: 1->2->0->NULL rotate 3 steps to the right: 0->1->2->NULL rotate 4 steps to the right: 2->0->1->NULL
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order 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.
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ classSolution{ public ListNode addTwoNumbers(ListNode l1, ListNode l2){ // corner case if(l1 == null) return l2; if(l2 == null) return l1; ListNode fakeNode = new ListNode(0); ListNode current = fakeNode; int carry = 0; // carry表示进位 // 第一段，l1和l2共有的部分 while(l1 != null && l2 != null) { int sum = l1.val + l2.val + carry; int val = sum % 10; carry = sum / 10; current.next = new ListNode(val); current = current.next; l1 = l1.next; l2 = l2.next; } while(l1 != null) { // 此时l1 is not null, but l2 is null int sum = l1.val + carry; int val = sum % 10; carry = sum / 10; current.next = new ListNode(val); current = current.next; l1 = l1.next; } while(l2 != null) { // 此时l2 is not null, but l1 is null int sum = l2.val + carry; int val = sum % 10; carry = sum / 10; current.next = new ListNode(val); current = current.next; l2 = l2.next; } //此时遍历完了所有l1和l2的节点，只看最后需不需要新进一位 // 进位完之后新链表长度是l1和l2长度和 +1 if(carry != 0) current.next = new ListNode(carry); return fakeNode.next; } }
Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:
1 2 3
Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 Output: Reference of the node with value = 8 Input Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,0,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.
Notes:
If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.
