## leetcode Wiggle Subsequence

A sequence of numbers is called a

wiggle sequenceif the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence.For example,

`[1,7,4,9,2,5]`

is a wiggle sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast,`[1,4,7,2,5]`

and`[1,7,4,5,5]`

are not wiggle sequences, the first because its first two differences are positive and the second because its last difference is zero.Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence. A subsequence is obtained by deleting some number of elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.

Examples:

12345678910 Input: [1,7,4,9,2,5]Output: 6The entire sequence is a wiggle sequence.Input: [1,17,5,10,13,15,10,5,16,8]Output: 7There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].Input: [1,2,3,4,5,6,7,8,9]Output: 2

Follow up:

Can you do it in O(n) time?

# Leetcode

本博客所有的leetcode 题解见： https://www.hrwhisper.me/leetcode-algorithm-solution/

## leetcode Guess Number Higher or Lower II

## leetcode Guess Number Higher or Lower II

We are playing the Guess Game. The game is as follows:

I pick a number from

1ton. You have to guess which number I picked.Every time you guess wrong, I’ll tell you whether the number I picked is higher or lower.

However, when you guess a particular number x, and you guess wrong, you pay

$x. You win the game when you guess the number I picked.

Example:

123456789 n = 10, I pick 8.First round: You guess 5, I tell you that it's higher. You pay $5.Second round: You guess 7, I tell you that it's higher. You pay $7.Third round: You guess 9, I tell you that it's lower. You pay $9.Game over. 8 is the number I picked.You end up paying $5 + $7 + $9 = $21.Given a particular

n ≥ 1, find out how much money you need to have to guarantee awin.

Hint:

- The best strategy to play the game is to minimize the maximum loss you could possibly face. Another strategy is to minimize the expected loss. Here, we are interested in the
firstscenario.- Take a small example (n = 3). What do you end up paying in the worst case?
- Check out this article if you’re still stuck.
- The purely recursive implementation of minimax would be worthless for even a small n. You MUST use dynamic programming.
- As a follow-up, how would you modify your code to solve the problem of minimizing the expected loss, instead of the worst-case loss?

## leetcode Guess Number Higher or Lower

## leetcode Guess Number Higher or Lower

We are playing the Guess Game. The game is as follows:

I pick a number from

1to. You have to guess which number I picked.nEvery time you guess wrong, I’ll tell you whether the number is higher or lower.

You call a pre-defined API

`guess(int num)`

which returns 3 possible results (`-1`

,`1`

, or`0`

):

123 -1 : My number is lower1 : My number is higher0 : Congrats! You got it!

Example:

123 n = 10, I pick 6.Return 6.

## leetcode Find K Pairs with Smallest Sums

## leetcode Find K Pairs with Smallest Sums

You are given two integer arrays

nums1andnums2sorted in ascending order and an integerk.Define a pair

(u,v)which consists of one element from the first array and one element from the second array.Find the k pairs

(uwith the smallest sums._{1},v_{1}),(u_{2},v_{2}) …(u_{k},v_{k})

Example 1:

123456 Given nums1 = [1,7,11], nums2 = [2,4,6], k = 3Return: [1,2],[1,4],[1,6]The first 3 pairs are returned from the sequence:[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

Example 2:

123456 Given nums1 = [1,1,2], nums2 = [1,2,3], k = 2Return: [1,1],[1,1]The first 2 pairs are returned from the sequence:[1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]

Example 3:

123456 Given nums1 = [1,2], nums2 = [3], k = 3Return: [1,3],[2,3]All possible pairs are returned from the sequence:[1,3],[2,3]

## leetcode Super Pow

## leetcode Super Pow

Your task is to calculate

a^{b}mod 1337 whereais a positive integer andbis an extremely large positive integer given in the form of an array.

Example1:

1234 a = 2b = [3]Result: 8

Example2:

1234 a = 2b = [1,0]Result: 1024

## leetcode Sum of Two Integers

## leetcode Sum of Two Integers

Calculate the sum of two integers

aandb, but you arenot allowedto use the operator`+`

and`-`

.

Example:

Givena= 1 andb= 2, return 3.

## leetcode Largest Divisible Subset

## leetcode Largest Divisible Subset

Given a set of

distinctpositive integers, find the largest subset such that every pair (S_{i}, S_{j}) of elements in this subset satisfies: S_{i}% S_{j}= 0 or S_{j}% S_{i}= 0.If there are multiple solutions, return any subset is fine.

Example 1:

123 nums: [1,2,3]Result: [1,2] (of course, [1,3] will also be ok)

Example 2:

123 nums: [1,2,4,8]Result: [1,2,4,8]

## leetcode Valid Perfect Square

## leetcode Valid Perfect Square

Given a positive integer

num, write a function which returns True ifnumis a perfect square else False.

Note:Do notuse any built-in library function such as`sqrt`

.

Example 1:

12 Input: 16Returns: True

Example 2:

12 Input: 14Returns: False

## leetcode Water and Jug Problem

## leetcode Water and Jug Problem

You are given two jugs with capacities

xandylitres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactlyzlitres using these two jugs.Operations allowed:

- Fill any of the jugs completely.
- Empty any of the jugs.
- Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.

Example 1:

12 Input: x = 2, y = 6, z = 4Output: True

Example 2:

12 Input: x = 2, y = 6, z = 5Output: False

## leetcode Max Sum of Rectangle No Larger Than K

## leetcode Max Sum of Rectangle No Larger Than K

Given a non-empty 2D matrix

matrixand an integerk, find the max sum of a rectangle in thematrixsuch that its sum is no larger thank.

Example:

12345 Given matrix = [[1, 0, 1],[0, -2, 3]]k = 2The answer is

`2`

. Because the sum of rectangle`[[0, 1], [-2, 3]]`

is 2 and 2 is the max number no larger than k (k = 2).

Note:

- The rectangle inside the matrix must have an area > 0.
- What if the number of rows is much larger than the number of columns?