LeetCode 16 17 19 23
16 最接近的三数之和
func threeSumClosest(nums []int, target int) int {
minDiscount := math.MaxInt64
result := target
for i := 0; i < len(nums); i++ {
for j := 0; j < len(nums); j++ {
if j == i {
continue
}
for k := 0; k < len(nums); k++ {
if k == i || k == j {
continue
}
discount := int(math.Abs(float64(nums[i] + nums[j] + nums[k] - target)))
if discount < minDiscount {
minDiscount = discount
result = nums[i] + nums[j] + nums[k]
}
}
}
}
return result
}
暴力也通过了
17. 电话号码的字母组合
class Solution {
public List<String> letterCombinations(String digits) {
if(digits.length()==0||digits==null) return new ArrayList<String>();
Map<Integer,String> map = new HashMap<>();
map.put(2,"abc");
map.put(3,"def");
map.put(4,"ghi");
map.put(5,"jkl");
map.put(6,"mno");
map.put(7,"pqrs");
map.put(8,"tuv");
map.put(9,"wxyz");
return letterCombinations(digits,map);
}
public List<String> letterCombinations(String digits,Map<Integer,String> map){
List<String> now = new ArrayList<>();
if(digits.length() == 1){
String s = map.get(Integer.parseInt(digits));
for(int i=0;i<s.length();i++){
now.add(""+s.charAt(i));
}
return now;
}
List<String> pre = letterCombinations(digits.substring(1),map);
String head = map.get(Integer.parseInt(digits.substring(0,1)));
for(String s : pre){
for(int j=0;j<head.length();j++){
now.add(head.charAt(j)+s);
}
}
return now;
}
}
19 删除链表的倒数第N个节点
type Stack struct {
l []interface{}
maxSize int
nowSize int
}
func InitStack(size int) *Stack {
defaultSize := 10
if size <= 0 {
size = defaultSize
}
return &Stack{make([]interface{}, defaultSize), defaultSize, 0}
}
func (stack *Stack) IsEmpty() bool {
return stack.l == nil || stack.nowSize == 0
}
func (stack *Stack) Put(e interface{}) {
if stack.nowSize < stack.maxSize {
stack.l[stack.nowSize] = e
stack.nowSize++
} else {
stack.Dilatation()
stack.Put(e)
}
}
func (stack *Stack) Top() interface{} {
return stack.l[stack.nowSize-1]
}
func (stack *Stack) Pop() interface{} {
p := stack.Top()
stack.l[stack.nowSize-1] = nil
stack.nowSize--
return p
}
func (stack *Stack) Dilatation() {
newMaxSize := stack.maxSize * 2
newList := make([]interface{}, newMaxSize)
copy(newList, stack.l)
stack.l = newList
stack.maxSize = newMaxSize
}
func removeNthFromEnd(head *ListNode, n int) *ListNode {
if head == nil {
return head
}
if n <= 0 {
return head
}
stack := InitStack(10)
temp := head
for ; temp != nil; {
stack.Put(temp)
temp = temp.Next
}
var end *ListNode = nil
for i := 1; i <= n; i++ {
node := stack.Pop().(*ListNode)
if i == n-1 {
end = node
}
}
lastEnd := stack.Pop().(*ListNode)
lastEnd.Next = end
return head
}
给个牛逼的递归解法
class Solution {
//递归做法
int i;
public ListNode removeNthFromEnd(ListNode head, int n) {
if(head == null){
i=0;
return null;
}
head.next = removeNthFromEnd(head.next,n);
i++;
if(i==n) return head.next;
return head;
}
}
22 括号生成
func generateParenthesis(n int) []string {
if n == 0 {
return make([]string, 0)
}
r := make([]string, 0)
if n == 1 {
return append(r, "()")
}
for i := 0; i < n; i++ {
s1 := generateParenthesis(i)
s2 := generateParenthesis(n - 1 - i)
if len(s1) == 0 {
s1 = append(s1, "")
}
if len(s2) == 0 {
s2 = append(s2, "")
}
for j := 0; j < len(s1); j++ {
for k := 0; k < len(s2); k++ {
ns := "(" + s1[j] + ")" + s2[k]
r = append(r, ns)
}
}
}
return r
}
23 合并K个排序链表
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func mergeKLists(lists []*ListNode) *ListNode {
if len(lists) == 0 {
return nil
}
var r *ListNode = nil
var re *ListNode = nil
for ; ; {
var min *ListNode = nil
var hitI int = 0
for i := 0; i < len(lists); i++ {
if lists[i] == nil {
continue
}
if min == nil {
min = lists[i]
hitI = i
}
if min != nil && lists[i].Val <= min.Val {
min = lists[i]
hitI = i
}
}
if min == nil {
break
}
lists[hitI] = lists[hitI].Next
if re == nil {
}
if r == nil {
r = &ListNode{min.Val, nil}
re = r
} else if re != nil {
re.Next = &ListNode{min.Val, nil}
re = re.Next
}
}
return r
}