Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

package leetcode

import "fmt"

func lengthOfLongestSubstring(s string) int {
	l := len(s)
	i := 0
	j := 0
	ans := 0
	set := make(map[byte]bool)
	for i < l && j < l {
		if !set[s[j]] {
			set[s[j]] = true
			j += 1
			if j-i > ans {
				ans = j - i
			}
		} else {
			delete(set, s[i])
			i += 1
		}
	}
	return ans
}

func TestLengthOfLongestSubstring() {
	fmt.Println(lengthOfLongestSubstring("abcabcdefabcdedght"))
}

Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
package leetcode

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

func AddTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	dummyHead := &ListNode{0, nil}
	p := l1
	q := l2
	carry := 0
	curr := dummyHead
	for p != nil || q != nil {
		x := 0
		if p != nil {
			x = p.Val
		}
		y := 0
		if q != nil {
			y = q.Val
		}
		sum := x + y + carry
		carry = sum / 10
		curr.Next = &ListNode{sum % 10, nil}
		curr = curr.Next
		if p != nil {
			p = p.Next
		}
		if q != nil {
			q = q.Next
		}
	}
	if carry > 0 {
		curr.Next = &ListNode{carry, nil}
	}
	return dummyHead.Next
}

func TestAddTwoNumbers() {
	node12 := ListNode{1, nil}
	node11 := ListNode{9, &node12}

	node22 := ListNode{9, nil}
	node21 := ListNode{9, &node22}

	n := AddTwoNumbers(&node11, &node21)
	for n != nil {
		fmt.Print(n.Val)
		n = n.Next
	}
	fmt.Println("")
}

Array Partition I

Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), …, (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.

Example 1:
Input: [1,4,3,2]

Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).

Note:
n is a positive integer, which is in the range of [1, 10000].
All the integers in the array will be in the range of [-10000, 10000].

package leetcode

import "sort"

func ArrayPairSum(nums []int) int {
	sort.Ints(nums)
	r := 0
	for i := 0; i < len(nums); i = i + 2 {
		r += nums[i]
	}
	return r
}

Merge Two Binary Trees

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.

You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.

Example 1:
Input: 
	Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
Output: 
Merged tree:
	     3
	    / \
	   4   5
	  / \   \ 
	 5   4   7
Note: The merging process must start from the root nodes of both trees.
package leetcode

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func MergeTrees(t1 *TreeNode, t2 *TreeNode) *TreeNode {
	if t1 == nil {
		return t2
	}
	if t2 == nil {
		return t1
	}
	t1.Val += t2.Val
	t1.Left = MergeTrees(t1.Left, t2.Left)
	t1.Right = MergeTrees(t1.Right, t2.Right)
	return t1
}

Hamming Distance

Hamming Distance

package leetcode

import "fmt"
import "math/big"

func HammingDistance(x int, y int) int {
	bin, diff := fmt.Sprintf("%b", x^y), 0
	for i := 0; i < len(bin); i++ {
		if string(bin[i]) == "1" {
			diff++
		}
	}
	return diff
}

func HammingDistance2(x int, y int) int {
	var count int
	z := x ^ y
	d := big.NewInt(int64(z))
	for _, x := range d.Bits() {
		for x != 0 {
			x &= x - 1
			count++
		}
	}
	return count
}

出梁庄记

读完<<出梁庄记>>想到的两句话:

我年纪还轻,阅历不深的时候,我父亲教导过我一句话,我至今还念念不忘。 “每逢你想要批评任何人的时候, ”他对我说,“你就记住,这个世界上所有的人,并不是个个都有过你拥有的那些优越条件。” ——菲茨杰拉德 了不起的盖茨比

他十几岁出去打工,我十几岁出去上学,我们的生活越来越远……想起他时,只是故乡回忆中的美好风景,至于那风景中真实的人和人生,我其实是不关心的。是的,很多时候,当风景中的人走出来,向你伸出求援之手,或者,只是到你的家里坐一坐,你真的如你想象中的那么热情吗?——梁鸿《出梁庄记》