LeetCode 16 17 19 23

发表信息: by

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
}