第16天--算法（Leetcode 14,15,17,19,20,21）
14.最长公共前缀
public String longestCommonPrefix(String[] strs) {
String first = strs[0];
char f[] = first.toCharArray();
int res = first.length();
for(int i = 0;i < strs.length;i ++) {
char s[] = strs[i].toCharArray();
int index = 0;
while(index < f.length && index < s.length) {
if(f[index] != s[index]) {
break;
}
index ++;
}
if(index == 0) {
return "";
}
res = Math.min(res,index);
}
return strs[0].substring(0,res);
}
15.三数之和
public List> threeSum(int[] nums) {
List> res = new ArrayList<>();
if(nums == null || nums.length < 3) {
return res;
}
Arrays.sort(nums);
for(int i = 0;i < nums.length - 2 && nums[i] <= 0;i ++) {
if(i == 0 || nums[i] != nums[i - 1]) {
List> two = twoSum(nums,i + 1,0 - nums[i]);
for(List l : two) {
l.add(nums[i]);
res.add(l);
}
}
}
return res;
}
public List> twoSum(int[] nums,int begin,int target) {
List> res = new ArrayList<>();
int L = begin;
int R = nums.length - 1;
while(L < R) {
if(nums[L] + nums[R] < target) {
L ++;
}else if(nums[L] + nums[R] > target) {
R --;
}else {
if(L == begin || nums[L] != nums[L - 1]) {
List ls = new ArrayList<>();
ls.add(nums[L]);
ls.add(nums[R]);
res.add(ls);
}
L ++;
R --;
}
}
return res;
}
17.电话号码的字母组合
char phone[][] = {
{'a','b','c'},
{'d','e','f'},
{'g','h','i'},
{'j','k','l'},
{'m','n','o'},
{'p','q','r','s'},
{'t','u','v'},
{'w','x','y','z'}
};
public List letterCombinations(String digits) {
List ans = new ArrayList<>();
if(digits == null || digits.length() == 0) {
return ans;
}
char s[] = digits.toCharArray();
char path[] = new char[s.length];
process(s,0,path,ans);
return ans;
}
public void process(char s[],int index,char[] path,List ans) {
if(index == s.length) {
ans.add(String.valueOf(path));
}else {
char res[] = phone[s[index] - '2'];
for(char c : res) {
path[index] = c;
process(s,index + 1,path,ans);
}
}
}
19.删除链表的倒数第N个节点
stack = new Stack<>();
char s1[] = s.toCharArray();
for(int i = 0;i < s1.length;i ++) {
if(s1[i] == '(' || s1[i] == '[' || s1[i] == '{') {
stack.push(s1[i]);
}
if(s1[i] == ')' || s1[i] == ']' || s1[i] == '}') {
if(stack.isEmpty()) {
return false;
}else {
char c = stack.pop();
if((s1[i] == ')' && c == '(') || (s1[i] == ']' && c == '[') || (s1[i] == '}' && c == '{')) {
}else {
return false;
}
}
}
}
return stack.isEmpty();
}
21.合并两个有序链表
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if(list1 == null) {
return list2;
}else if(list2 == null) {
return list1;
}else {
ListNode head = new ListNode();
ListNode cur = head;
while(list1 != null && list2 != null) {
if(list1.val <= list2.val) {
cur.next = list1;
list1 = list1.next;
cur = cur.next;
}else {
cur.next = list2;
list2 = list2.next;
cur = cur.next;
}
}
if(list1 != null) {
cur.next = list1;
}
if(list2 != null) {
cur.next = list2;
}
return head.next;
}
}
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode l1 = new ListNode(0,head);
ListNode l2 = head;
ListNode l3 = head;
for(int i = 0;i < n - 1;i ++) {
l3 = l3.next;
}
if(l3.next == null) {
head = l2.next;
}
while(l3.next != null) {
l3 = l3.next;
l1 = l1.next;
l2 = l2.next;
}
l1.next = l2.next;
return head;
}
20.有效的括号 public boolean isValid(String s) { if(s == null || s.length() == 0) { return false; } if((s.length() & 1) != 0) { return false; } Stack