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:
Input: [1,8,6,2,5,4,8,3,7]
Output: 49
class Solution {
public int maxArea(int[] height) {
if(height.length<2)return 0;
int head=0,tail=height.length-1;
int max = 0;
while (head!=tail) {
if (height[head]>height[tail]) {
if((tail-head)*height[tail]>max) {
max=(tail-head)*height[tail];
}
tail--;
}else {
if((tail-head)*height[head]>max) {
max=(tail-head)*height[head];
}
head++;
}
}
return max;
}
}
定义两个下标变量从两端往中间遍历，比较俩下标对应的高度，若想中间的面积更大，则只改变高度较低的那一端的下标值向中间靠拢，最后通过一个变量记录最大值即可。
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.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
if(nums.length<3) return Arrays.asList();
List<List<Integer>> aList=new ArrayList<>();
Arrays.sort(nums);
for(int i=0;i+2<nums.length;i++) {
if (i>0&&nums[i]==nums[i-1]) continue;
if (nums[i]>0) break;
int target=-nums[i];
int j=i+1,k=nums.length-1;
while(k>j) {
if(target==nums[j]+nums[k]) {
aList.add(Arrays.asList(nums[i],nums[j],nums[k]));
j++;
k--;
while(j<k&&nums[j]==nums[j-1])j++;
while(j<k&&nums[k]==nums[k+1])k--;
}else if(target<nums[j]+nums[k]){
k--;
}else {
j++;
}
}
}
return aList;
}
}
大概思想就是让每个数负数作为和，定义两个指针从这个数的右边和数组末向中间遍历，若有符合条件的加入list，跳过重复项
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Example:
Input: “23”
Output: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].
Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.
class Solution {
HashMap<Character, List<Character>> map=new HashMap<>();
StringBuilder stringBuilder=new StringBuilder();
List<String> aList=new ArrayList<>();
public List<String> letterCombinations(String digits) {
if(digits.length()==0||digits==null) return Arrays.asList();
map.put('2', Arrays.asList('a','b','c'));
map.put('3', Arrays.asList('d','e','f'));
map.put('4', Arrays.asList('g','h','i'));
map.put('5', Arrays.asList('j','k','l'));
map.put('6', Arrays.asList('m','n','o'));
map.put('7', Arrays.asList('p','q','r','s'));
map.put('8', Arrays.asList('t','u','v'));
map.put('9', Arrays.asList('w','x','y','z'));
doAdd(digits,0);
return aList;
}
private void doAdd(String digits, int i) {
if (i<digits.length()) {
for (Character character : map.get(digits.charAt(i))) {
stringBuilder.append(character);
doAdd(digits, i+1);
stringBuilder.deleteCharAt(i);
}
}else {
aList.add(stringBuilder.toString());
return;
}
}
}
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
Example:
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1==null) return l2;
if(l2==null) return l1;
ListNode node;
if(l1.val>l2.val) {
node=l2;
l2=l2.next;
}else {
node=l1;
l1=l1.next;
}
ListNode head=new ListNode(0);
head.next=node;
while(l1!=null||l2!=null) {
if(l1==null) {
node.next=l2;
break;
}else if(l2==null) {
node.next=l1;
break;
}
if (l1.val>l2.val) {
node.next=l2;
l2=l2.next;
}else {
node.next=l1;
l1=l1.next;
}
node=node.next;
}
return head.next;
}
}
Given _n_ pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given _n_ = 3, a solution set is:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
class Solution {
public List<String> generateParenthesis(int n) {
List<String> aList=new ArrayList<>();
StringBuilder sBuilder=new StringBuilder();
doListCur(0,0,sBuilder,n,aList);
return aList;
}
private void doListCur(int left, int right, StringBuilder sBuilder,int n,List<String> aList) {
if(n==right) {
aList.add(sBuilder.toString());
return;
}
if (left<n) {
sBuilder.append('(');
doListCur(left+1, right, sBuilder, n, aList);
sBuilder.deleteCharAt(sBuilder.length()-1);
}
if (right<left) {
sBuilder.append(')');
doListCur(left, right+1, sBuilder, n, aList);
sBuilder.deleteCharAt(sBuilder.length()-1);
}
}
}
类似上题
Merge _k_ sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Example:
Input:
[
1->4->5,
1->3->4,
2->6
]
Output: 1->1->2->3->4->4->5->6
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
Comparator<ListNode> cmp;
cmp = new Comparator<ListNode>() {
@Override
public int compare(ListNode o1, ListNode o2) {
// TODO Auto-generated method stub
return o1.val-o2.val;
}
};
Queue<ListNode> q = new PriorityQueue<ListNode>(cmp);
for(ListNode l : lists){
if(l!=null){
q.add(l);
}
}
ListNode head = new ListNode(0);
ListNode point = head;
while(!q.isEmpty()){
point.next = q.poll();
point = point.next;
ListNode next = point.next;
if(next!=null){
q.add(next);
}
}
return head.next;
}
}
另外还可以利用第21题的两两链表合并，速度更快
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place and use only constant extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,23,2,1 → 1,2,31,1,5 → 1,5,1
class Solution {
public void nextPermutation(int[] nums) {
if(nums.length<2) return;
int n=nums.length-1;
List<Integer> aList=new ArrayList<>();
aList.add(nums[n]);
while(n>0) {
int j=n-1;
for(int i=0;i<aList.size();i++) {
if (aList.get(i)>nums[j]) {
int anum=nums[nums.length-1-i];
nums[nums.length-1-i]=nums[j];
nums[j]=anum;
Arrays.sort(nums, j+1, nums.length);
return;
}
}
aList.add(nums[j]);
n--;
}
Arrays.sort(nums);
}
}
用list里的数去和它前面一位的数比较，如果遇到某一个数大于这个数，就互换这两个数的位置，并把前面数后面的位置重新排序。否则就把这个数加入到list里，再次循环。如果一直到循环结束未发现任何后面的数大于前面的数，就把数组从小到大重新排序。