Tag: leetcode

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"))
}

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("")
}

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
}

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

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
}

Given an array S of n integers, are there elements a, b, c in S such that
a + b + c = 0?
Find all unique triplets in the array which gives the sum of zero.

Note:

Elements in a triplet (a,b,c) must be in non-descending order.
(ie, a ≤ b ≤ c)
The solution set must not contain duplicate triplets.

For example, given array S = {-1 0 1 2 -1 -4},

A solution set is:
(-1, 0, 1)
(-1, -1, 2)

package leetcode

import (
	"fmt"
	"sort"
	"sync/atomic"
)

var arrLen int
var ops uint64 = 0
var sortArr []int

func getArr() []int {
	inputArr := []int{-7, -8, -1, -2, -4, 1, 4, 9, 3, 6}
	return inputArr
}

func ThreeSum() {
	// call get array func
	inputArr := getArr()
	//make sure are sorted
	fmt.Println(inputArr)
	if !sort.IntsAreSorted(inputArr) {
		// sort inputArr
		sort.Ints(inputArr)
		fmt.Println(inputArr)
		sortArr = inputArr
	}
	//get this array length
	arrLen = len(sortArr)
	for i := 0; i < arrLen-2; i++ {
		fmt.Println("loop time : ", i)
		if i > 0 && sortArr[i-1] == sortArr[i] {
			//if near equal ,skip this time loop
			continue
		}
		currNum := sortArr[i]
		low := i + 1
		high := arrLen - 1
		for low < high {
			lowNum := sortArr[low]
			highNum := sortArr[high]
			sumNum := currNum + lowNum + highNum
			if sumNum == 0 {
				//2d array use
				atomic.AddUint64(&ops, 1)
				opsFinal := atomic.LoadUint64(&ops)
				//print result
				fmt.Println("--------------Begin--------------")
				fmt.Println("counter : ", opsFinal)
				fmt.Println("first Number : ", currNum)
				fmt.Println("second Number : ", lowNum)
				fmt.Println("third Number : ", highNum)
				fmt.Printf("[%d,%d,%d]", currNum, lowNum, highNum)
				fmt.Println("")
				fmt.Println("---------------End---------------")
				low++
			} else if sumNum > 0 {
				for high > 0 && sortArr[high] == sortArr[high-1] {
					high--
				}
				high--
			} else {
				for low < arrLen && sortArr[low] == sortArr[low+1] {
					low++
				}
				low++
			}
		}
	}
}