11. 盛最多水的容器【中】
11.盛最多水的容器 一:双指针
- 时间复杂度 O(N);
- 空间复杂度 O(1): 变量 i ,j,S,temp使用常数额外空间。
class Solution {
public int maxArea(int[] height) {
int left = 0, right = height.length - 1;
int S = 0, temp = 0;;
while(left < right) {
if(height[left] < height[right]) {
temp = height[left]*(right - left);
left++;
} else {
temp = height[right]*(right - left);
right--;
}
S = Math.max(S, temp);
}
return S;
}
}
15. 三数之和【中】
15.三数之和 方法一:双指针
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums);
for(int i = 0; i < nums.length - 1; i++) {
int left = i + 1, right = nums.length - 1;
if(nums[i] > 0) {
break;
}
if(i > 0 && nums[i] == nums[i - 1]) {
continue;
}
while(left < right) {
int sum = nums[i] + nums[left] + nums[right];
if(sum == 0) {
list.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(sum < 0) {
left++;
} else {
right--;
}
}
}
return list;
}
}
17. 电话号码的字母组合【中】
17.电话号码的字母组合 方法一:回溯
class Solution {
List<String> result = new ArrayList<>();
StringBuilder res = new StringBuilder();
String[] ss = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public List<String> letterCombinations(String digits) {
if(digits.length() == 0) return result;
backTracking(digits, 0);
return result;
}
public void backTracking(String digits, int index) {
if(index == digits.length()) {
result.add(res.toString());
return ;
}
String tmp = ss[digits.charAt(index) - '0'];
for(int i = 0; i < tmp.length(); i++) {
res.append(tmp.charAt(i));
backTracking(digits, index + 1);
res.deleteCharAt(res.length() - 1);
}
}
}
19. 删除链表的倒数第N个结点【中】
19.删除链表的倒数第N个结点 方法一:遍历 先统计总的结点数count,删除倒数第N个结点也就是删除第(count - n + 1)个结点
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
ListNode pre = dummy;
pre.next = head;
ListNode cur = head;
int count = 0;
while(cur != null) {
cur = cur.next;
count++;
}
for(int i = 0; i < count - n; i++) {
pre = pre.next;
}
pre.next = pre.next.next;
return dummy.next;
}
}
方法二:双指针
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode fast = dummy,slow = dummy;
while(n != 0) {
fast = fast.next;
n--;
}
while(fast.next != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummy.next;
}
}
20. 有效的括号【易】
20.有效的括号 方法一:辅助栈
class Solution {
public boolean isValid(String s) {
if(s.isEmpty())
return true;
Stack<Character> stack = new Stack<>();
for(char c : s.toCharArray()){
if(c == '('){
stack.push(')');
}else if(c == '['){
stack.push(']');
}else if(c == '{'){
stack.push('}');
}else if(stack.isEmpty() || c != stack.pop()){
return false;
}
}
return stack.isEmpty();
}
}
|