1.两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> res;
        unordered_map<int,int> m;
        for (int i = 0; i < nums.size(); i ++ )
        {
            int another = target - nums[i];
            if (m.count(another))
            {
                res = vector<int>({m[another], i});
                break;
            }
            m[nums[i]] = i;
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
func twoSum(nums []int, target int) []int {
    m := make(map[int]int)
    for i := 0; i < len(nums); i++ {
        res := target - nums[i]
        if _, ok := m[res]; ok {
			return []int{m[res], i}
		}
		m[nums[i]] = i
    }
    return nil
}

2.两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *res = new ListNode(-1);   //添加虚拟头结点，简化边界情况的判断
        ListNode *cur = res;
        int carry = 0;  //表示进位
        while (l1 || l2)
        {
            int n1 = l1 ? l1->val : 0;
            int n2 = l2 ? l2->val : 0;
            int sum = n1 + n2 + carry;
            carry = sum / 10;
            cur->next = new ListNode(sum % 10);
            cur = cur->next;
            if (l1) l1 = l1->next;
            if (l2) l2 = l2->next;
        }
        if (carry) cur->next = new ListNode(1);
        return res->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    res := &ListNode{Val: -1};
    cur := res;
    n1, n2, carry := 0, 0, 0;
    for l1 != nil || l2 != nil {
        if l1 == nil {
			n1 = 0
		} else {
			n1 = l1.Val
		}
		if l2 == nil {
			n2 = 0
		} else {
			n2 = l2.Val
		}
        sum := n1 + n2 + carry
        carry = sum / 10;
        cur.Next = &ListNode{Val: sum % 10}
        cur = cur.Next
        if l1 != nil {
            l1 = l1.Next
        }
        if l2 != nil {
            l2 = l2.Next;
        }
    }
    if carry != 0 {
        cur.Next = &ListNode{Val: 1}
    }
    return res.Next
}

3.无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.size() == 0) return 0;
        unordered_set<char> cnt;
        int res = 0;
        for(int i = 0, j = 0; j < s.size(); j++) {
            while(cnt.find(s[j]) != cnt.end()) {
                cnt.erase(s[i]);
                i++;
            }
            res = max(res, j - i + 1);
            cnt.insert(s[j]);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func lengthOfLongestSubstring(s string) int {
    m := make(map[byte]int)
    res := 0
    for i, j := 0, 0; j < len(s); j++ {
          if idx, ok := m[s[j]]; ok && idx >= i {
			i = idx + 1
		}
        m[s[j]] = j
        res = max(res, j - i + 1)
    }
    return res
}

func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

4.寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int tot = nums1.size() + nums2.size();
        if (tot % 2 == 0) {
            int left = find(nums1, 0, nums2, 0, tot / 2);
            int right = find(nums1, 0, nums2, 0, tot / 2 + 1);
            return (left + right) / 2.0;
        } else {
            return find(nums1, 0, nums2, 0, tot / 2 + 1);
        }
    }

    int find(vector<int> &a, int i, vector<int> &b, int j, int k)
    {
        if(a.size() - i > b.size() - j) return find(b, j, a, i, k);
        if (k == 1) {
            if (a.size() == i) return b[j];
            else return min(a[i], b[j]);
        }
        if(a.size() == i) return b[j + k - 1];
        int si = min((int)a.size(), i + k / 2);
        int sj = j + k - k / 2;
        if (a[si - 1] > b[sj - 1])
            return find(a, i, b, sj, k - (sj - j));
        else
            return find(a, si, b, j, k - (si - i));
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    tot := len(nums1) + len(nums2)
    if tot % 2 == 1 {
        return float64(find(nums1, nums2, 0, 0, tot / 2 + 1))
    } else {
        return float64(find(nums1, nums2, 0, 0, tot / 2 + 1) + find(nums1, nums2, 0, 0, tot / 2)) / 2.0
    }
}

func find(nums1 []int, nums2 []int, i, j, k int) int {
    if len(nums1) - i > len(nums2) - j {
        return find(nums2, nums1, j, i, k)
    }
    if k == 1 {
        if len(nums1) == i {
            return nums2[j]
        } else {
            return min(nums1[i], nums2[j])
        }
    }
    if len(nums1) == i {
        return nums2[j + k - 1];
    }
    si := min(len(nums1), i + k / 2)
    sj := j + k - k / 2;
    if nums1[si - 1] > nums2[sj - 1] {
        return find(nums1, nums2, i, sj, k - (sj - j))
    } else {
        return find(nums1, nums2, si, j, k - (si - i))
    }
}

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

5.最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    string longestPalindrome(string s) {
        int res = 0;
        string str;
        for (int i = 0; i < s.size(); i ++ )
        {
            for (int j = 0; i - j >= 0 && i + j < s.size(); j ++ )
                if (s[i - j] == s[i + j])
                {
                    if (j * 2 + 1 > res)
                    {
                        res = j * 2 + 1;
                        str = s.substr(i - j, j * 2 + 1);
                    }
                }
                else break;

            for (int j = i, k = i + 1; j >= 0 && k < s.size(); j -- , k ++ )
                if (s[j] == s[k])
                {
                    if (k - j + 1 > res)
                    {
                        res = k - j + 1;
                        str = s.substr(j, k - j + 1);
                    }
                }
                else break;
        }
        return str;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func longestPalindrome(s string) string {
    if s == "" {
        return ""
    }
    start, end := 0, 0
    for i := 0; i < len(s); i++ {
        left1, right1 := expandAroundCenter(s, i, i)
        left2, right2 := expandAroundCenter(s, i, i + 1)
        if right1 - left1 > end - start {
            start, end = left1, right1
        }
        if right2 - left2 > end - start {
            start, end = left2, right2
        }
    }
    return s[start:end+1]
}

func expandAroundCenter(s string, left, right int) (int, int) {
    for ; left >= 0 && right < len(s) && s[left] == s[right]; left, right = left-1 , right+1 { }
    return left + 1, right - 1
}

6.Z 字形变换