11. Container With Most Water
这道题不是说是两根线中间所有线中的最小值决定面积，而是仅仅根据左右两根线中的最小值决定面积，所以用两个指针，一个从左一个从右来遍历数组，每次更新最小值即可。
class Solution {
public int maxArea(int[] height) {
int maxHeight = 0;
int left = 0; int right = height.length-1;
while(left < right){
maxHeight = Math.max(maxHeight,Math.min(height[left],height[right]) * (right-left));
if(height[left] < height[right])
left ++;
else
right --;
}
return maxHeight;
}
}
14. Longest Common Prefix
从前往后两两判断，具体的可以看下图：
class Solution {
public String longestCommonPrefix(String[] strs) {
if(strs.length==0) return "";
String prefix = strs[0];
for(int i=1;i<strs.length;i++){
while(strs[i].indexOf(prefix) != 0){
prefix = prefix.substring(0,prefix.length()-1);
if(prefix == "") return "";
}
}
return prefix;
}
}
15. 3Sum
借鉴2个数求和的思路，但是这里要注意的是，要避免重复情况的出现。
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> res = new LinkedList<>();
for(int i = 0;i<nums.length-2;i++){
if(i==0 || nums[i] != nums[i-1]){
int left = i + 1;
int right = nums.length - 1;
int sum = 0 - nums[I];
while(left < right){
if(nums[left] + nums[right] == sum){
res.add(Arrays.asList(nums[i],nums[left],nums[right]));
while(left < right && nums[left] == nums[left + 1]) left++;
while(left < right && nums[right] == nums[right -1]) right--;
left ++;
right --;
}
else if(nums[left] + nums[right] < sum) left++;
else right--;
}
}
}
return res;
}
}
16. 3Sum Closest
思路同15题
class Solution {
public int threeSumClosest(int[] nums, int target) {
int minNumber = 0xfffffff;
int res = 0;
Arrays.sort(nums);
for(int i=0;i<nums.length-2;i++){
int left = i + 1;
int right = nums.length - 1;
while(left < right){
int sum = nums[i] + nums[left] + nums[right];
if(sum == target)
return target;
else if(sum > target){
if(minNumber > Math.abs(sum-target)){
minNumber = Math.abs(sum-target);
res = sum;
}
right --;
}
else{
if(minNumber > Math.abs(sum-target)){
minNumber = Math.abs(sum-target);
res = sum;
}
left ++;
}
}
}
return res;
}
}
17. Letter Combinations of a Phone Number
使用先进先出的队列来存储我们的返回结果。关键是ans.peek().length()==i来循环得到所有上一轮的结果，并拼接上这一次的结果。
class Solution {
public List<String> letterCombinations(String digits) {
String[] mapping = new String[] {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
LinkedList<String> ans = new LinkedList<String>();
if(digits.isEmpty()) return ans;
ans.add("");
for(int i=0;i<digits.length();i++){
int x = Character.getNumericValue(digits.charAt(i));
while(ans.peek().length()==i){
String t = ans.remove(0);
for(char s:mapping[x].toCharArray()){
ans.add(t+s);
}
}
}
return ans;
}
}
18. 4Sum
借鉴3个数求和的思路，但是这里要注意的是，要避免重复情况的出现,同时可以添加一些提前结束循环的条件。
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> res = new LinkedList<>();
if(nums.length<4)
return res;
Arrays.sort(nums);
for(int i=0;i<nums.length-3;i++){
if(i>0 && nums[i]==nums[i-1])
continue;
if(4 * nums[i] > target)
return res;
for(int j=i+1;j<nums.length-2;j++){
if(j>i+1 && nums[j]==nums[j-1])
continue;
if(nums[i] + 3 * nums[j] > target)
break;
int sum = target - nums[i] - nums[j];
int left = j+1;
int right = nums.length-1;
while(left < right){
if(nums[left]+nums[right]==sum){
res.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
while(left<right && nums[left]==nums[left+1]) left++;
while(left<right && nums[right]==nums[right-1]) right--;
left++;right--;
}
else if(nums[left] + nums[right] < sum)
left ++;
else
right--;
}
}
}
return res;
}
}
19. Remove Nth Node From End of List
用一个指针先往前走n步，然后两个指针同时行动，当前面的指针走到最后的时候，后面的指针所指向的位置就是倒数第n个节点的位置。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
if(head==null)
return head;
ListNode dummy = new ListNode(-999);
dummy.next = head;
ListNode p = dummy;
ListNode q = dummy;
int i = 0;
while(p!=null && i<n){
p = p.next;
I++;
}
if(p==null)
return dummy.next;
while(p.next!=null){
p = p.next;
q = q.next;
}
q.next = q.next.next;
return dummy.next;
}
}
20. Valid Parentheses
经典的栈的问题
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<Character>();
for (char c : s.toCharArray()) {
if (c == '(')
stack.push(')');
else if (c == '{')
stack.push('}');
else if (c == '[')
stack.push(']');
else if (stack.isEmpty() || stack.pop() != c)
return false;
}
return stack.isEmpty();
}
}
