11. 盛最多水的容器
//通过反证法可以证明这个方法是对的
class Solution {
public int maxArea(int[] height) {
int left = 0;
int max = 0;
int right = height.length - 1;
while(left < right) {
int temp = (right - left) * (Math.min(height[left],height[right]));
if(max < temp) {
max = temp;
}
if(height[left] > height[right]) {
right--;
}else {
left++;
}
}
return max;
}
}12. 整数转罗马数字
//模拟
class Solution {
public String intToRoman(int num) {
int[] values = new int[] {
1000,
900, 500, 400, 100,
90, 50, 40, 10,
9, 5, 4, 1
};
String[] reps = new String[] {
"M",
"CM", "D", "CD", "C",
"XC", "L", "XL", "X",
"IX", "V", "IV", "I"
};
StringBuilder res = new StringBuilder();
for (int i = 0; i < 13; i++) {
while(num >= values[i]) {
res.append(reps[i]);
num -= values[i];
}
}
return res.toString();
}
}13. 罗马数字转整数
class Solution {
public int romanToInt(String s) {
Map<Character,Integer> map = new HashMap();
map.put('I', 1);
map.put('V', 5);
map.put('X', 10);
map.put('L', 50);
map.put('C', 100);
map.put('D', 500);
map.put('M', 1000);
int res = 0;
for (int i = 0; i < s.length(); i++) {
//先考虑特殊情况
if (i < s.length() - 1 && map.get(s.charAt(i)) < map.get(s.charAt(i + 1))) {
res -= map.get(s.charAt(i));
} else {
res += map.get(s.charAt(i));
}
}
return res;
}
}14. 最长公共前缀
class Solution {
public String longestCommonPrefix(String[] strs) {
// 判空
if (strs.length == 0) {
return "";
}
StringBuilder builder = new StringBuilder();
int i = 0;
while(true) {
//
if (i >= strs[0].length()) {
break;
}
char c = strs[0].charAt(i);
for (String s : strs) {
//从数组取或者从字符里面取一定要进行范围的判断
if (i >= s.length() || s.charAt(i) != c) {
return builder.toString();
}
}
builder.append(c);
i++;
}
return builder.toString();
}
}15. 三数之和
双指针做法一定要有序。
判断单调性
import java.util.*;
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> list = new ArrayList();
for (int i = 0; i < nums.length; i++) {
if (i != 0 && nums[i] == nums[i - 1]) {
continue;
}
for (int j = i + 1, k = nums.length - 1; j < k; j++) {
if(j != i + 1 && nums[j] == nums[j - 1]) {
continue;
}
while(k > j + 1 && nums[k] + nums[j] + nums[i] > 0) {
k--;
}
if (nums[k] + nums[j] + nums[i] == 0) {
list.add(Arrays.asList(new Integer[]{nums[i], nums[j], nums[k]}));
}
}
}
return list;
}
}16. 最接近的三数之和
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int res = Integer.MAX_VALUE;
int finsum = 0;
for (int i = 0; i < nums.length; i++) {
for(int j = i + 1, k = nums.length - 1; j < k; j++) {
while (k > j + 1 && nums[k] + nums[i] + nums[j] > target) {
k--;
}
int sum = nums[i] + nums[j] + nums[k];
if(res > Math.abs(sum - target)) {
res = Math.abs(sum - target);
finsum = sum;
}
if (k < nums.length - 1) {
sum = nums[i] + nums[j] + nums[k+1];
if(res > Math.abs(sum - target)) {
res = Math.abs(sum - target);
finsum = sum;
}
}
}
}
return finsum;
}
}17. 电话号码的字母组合
class Solution {
String[] strs;
List<String> res;
public List<String> letterCombinations(String digits) {
strs = new String[] { "", "", "abc", "def",
"ghi", "jkl", "mno",
"pqrs", "tuv", "wxyz"};
res = new ArrayList();
if (digits.equals("")) {
return res;
}
dfs(digits, 0 ,new StringBuilder());
return res;
}
private void dfs(String digits, int index, StringBuilder builder) {
// 这里就进行一个结尾的工作就好，重复行的操作放在下面，在这里不要做下面的工作。
if (index == digits.length()) {
res.add(builder.toString());
return ;
}
//在这里进行重复的操作添加等等。
for (char c : strs[digits.charAt(index) - '0'].toCharArray()) {
builder.append(c);
dfs(digits, index + 1,new StringBuilder(builder));
builder.deleteCharAt(builder.length() - 1);
}
}
}18. 四数之和
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList();
for (int i = 0; i < nums.length; i++) {
if (i != 0 && nums[i] == nums[i - 1]) {
continue;
}
for (int j = i + 1; j < nums.length; j++) {
if (j != i + 1 && nums[j] == nums[j - 1]) {
continue;
}
for (int k = j + 1, p = nums.length - 1; k < p; k++) {
if (k != j + 1 && nums[k] == nums[ k - 1]) {continue;}
while (p > k + 1 && (nums[k] + nums[p] + nums[i] + nums[j]) > target) {
p--;
}
if (nums[i] + nums[j] + nums[p] + nums[k] == target) {
res.add(Arrays.asList(new Integer[]{nums[i], nums[j], nums[k], nums[p]}));
}
}
}
}
return res;
}
}19.删除链表的倒数第N个节点
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
int num = 0;
//头节点可能也需要变化的时候就需要创建虚拟的头节点
ListNode dummy = new ListNode(-1);
dummy.next = head;
while (head != null) {
head = head.next;
num++;
}
ListNode cur = dummy;
for (int i = 1; i <= num - n; i++) {
cur = cur.next;
}
cur.next = cur.next.next; //仅仅将上一个节点的next指向了该节点的next，属于不完全删除
return dummy.next;
}
}20. 有效的括号
class Solution {
public boolean isValid(String s) {
Deque<Character> deque = new LinkedList();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '{' || s.charAt(i) == '[' || s.charAt(i) == '(') {
deque.offerFirst(s.charAt(i));
}else {
//如果直接加进去}])就会报错， 先判断是否为空【取的时候先判断是否为空】
if (!deque.isEmpty() && Math.abs(s.charAt(i) - deque.peekFirst()) <= 2) { //通过ascil码进行判断
deque.pollFirst();
} else {
return false;
}
}
}
//最后判断是否为空 有可能都是[{(的加进去
if (deque.isEmpty()) {
return true;
}
return false;
}
}
京公网安备 11010502036488号