题目

Palindrome Partitioning III
You are given a string s containing lowercase letters and an integer k. You need to :

First, change some characters of s to other lowercase English letters.
Then divide s into k non-empty disjoint substrings such that each substring is palindrome.
Return the minimal number of characters that you need to change to divide the string.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

Example 1:

Input: s = "abc", k = 2
Output: 1
Explanation: You can split the string into "ab" and "c", and change 1 character in "ab" to make it palindrome.
Example 2:

Input: s = "aabbc", k = 3
Output: 0
Explanation: You can split the string into "aa", "bb" and "c", all of them are palindrome.
Example 3:

Input: s = "leetcode", k = 8
Output: 0

Constraints:

1 <= k <= s.length <= 100.
s only contains lowercase English letters.

问题

1. 遍历二叉树
2. O(1)的时间复杂度
3. 二叉树的形状不能破坏

题目

Median of Two Sorted Arrays
There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

1
2
3
4

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

1
2
3
4

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

题目

Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.

Example 1:

1
2
3

Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

1
2
3

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

1
2
3
4

Input: "pwwkew"
Output: 3
Explanation: 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.

题目

AddTwoNumbers
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.

Example:

1
2
3

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

题目

MajorityElementII
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Note: The algorithm should run in linear time and in O(1) space.

• Example 1:

  1 2	Input: [3,2,3] Output: [3]

• Example 2:

  1 2	Input: [1,1,1,3,3,2,2,2] Output: [1,2]

背景

最近做的项目需要对C++对象进行序列化和反序列化，最主要的目的是将JSON和C++对象互转。

题目

TwoSum
Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

1
2
3
4

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

题目

TwoSum
Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

1
2
3
4

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

贪心策略

一. 常见贪心方法归类

朴素贪心（通过确定性的贪心步骤得出最优解）

1. 最优化策略： 每次都选当前最优策略

• 适用条件

1.1. 有明确的阶段，切每个阶段的决策都很清晰

可以分成多个轮，每轮都是一个阶段，每个阶段做的事情是个原子事件，做的事情还都类似 （一个选择，一个操作，一个切割…），阶段一定似乎按顺序执行

1

对于 `K（1≤K≤N）`个阶段，前 K 轮的最优决策集合成为局部最优解，当 `K = N` 时，成为全局最优解

1.2 一个阶段的局部最优解，一定是前面阶段局部最优解得到的 (最优子结构)

1.3 后面阶段的决策，不会影响到掐面阶段的决策 （无后效性）

• 解题步骤

1.4 划分问题的决策和阶段

1.5 验证最优子结构和无后效性

2. 构造法: 通过归纳总结找到规律，直接推导答案

3. 二分答案： 通过答案反推，验证合法性从而确定最优解