LeetCode 557. Reverse Words in a String III

Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.

Example 1:
Input: “Let’s take LeetCode contest”
Output: “s’teL ekat edoCteeL tsetnoc”
Note: In the string, each word is separated by single space and there will not be any extra space in the string.

题目大意:将一个字符串的每个单词反转~
分析:将每个单词放入栈中,当遇到空格或者最后一个字符的时候,说明当前栈内为一个完整的单词,那么就将栈内的单词按字符一个个出栈加入result字符串中,根据flag的值判断是否是第一个单词,如果不是第一个单词就要在result的后面加一个空格~

 

LeetCode 524. Longest Word in Dictionary through Deleting

Given a string and a string dictionary, find the longest string in the dictionary that can be formed by deleting some characters of the given string. If there are more than one possible results, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.

Example 1:
Input:
s = “abpcplea”, d = [“ale”,”apple”,”monkey”,”plea”]

Output:
“apple”
Example 2:
Input:
s = “abpcplea”, d = [“a”,”b”,”c”]

Output:
“a”
Note:
All the strings in the input will only contain lower-case letters.
The size of the dictionary won’t exceed 1,000.
The length of all the strings in the input won’t exceed 1,000.

题目大意:给一个string s和一个string字典d,找字典中的某个string,寻找s的子串(满足可以通过删除s中某些元素后得到该string),寻找满足条件的字符串中最长的一个,如果有多个长度相等的就返回字典序中最小的那个,如果一个都没有满足条件的string,就返回一个空字符串~
分析:遍历字典中的某一个字符串,设当前字符串的下标为index,对于当前字符串d[index],使用两个指针i和j分别从头到尾遍历s和d[index],随着i指针的增加,如果j指针所指元素和i指针所指元素相同就向后移动一位,当i指针都指完的时候,j如果也指完了说明满足条件,当前d[index]是s的子串,如果当前d[index]的长度比保存的result字符串长度长,就更新result,或者一样长但是字典序排列中d[index]比result小,也要更新result,最后返回result~

 

LeetCode 530. Minimum Absolute Difference in BST

Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.

Example:

Input:

1
\
3
/
2

Output:
1

Explanation:
The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).
Note: There are at least two nodes in this BST.

题目大意:给一棵二叉搜索树,结点的值都为非负,找到两个元素值之差的绝对值的最小值~
分析:二叉搜索树,用中序遍历后得到的结果是从小到大的元素,遍历这个中序遍历后的结果数组,就可以得到两个元素值之差的绝对值的最小值~

 

LeetCode 526. Beautiful Arrangement

526. Beautiful Arrangement
Suppose you have N integers from 1 to N. We define a beautiful arrangement as an array that is constructed by these N numbers successfully if one of the following is true for the ith position (1 ≤ i ≤ N) in this array:

The number at the ith position is divisible by i.
i is divisible by the number at the ith position.
Now given N, how many beautiful arrangements can you construct?

Example 1:
Input: 2
Output: 2
Explanation:

The first beautiful arrangement is [1, 2]:

Number at the 1st position (i=1) is 1, and 1 is divisible by i (i=1).

Number at the 2nd position (i=2) is 2, and 2 is divisible by i (i=2).

The second beautiful arrangement is [2, 1]:

Number at the 1st position (i=1) is 2, and 2 is divisible by i (i=1).

Number at the 2nd position (i=2) is 1, and i (i=2) is divisible by 1.
Note:
N is a positive integer and will not exceed 15.

题目大意:N个数1~N,求它有多少种排列方式,满足:对于每一位,i位上的数字能被i整除,或者i能被i位上的数字整除~
分析:深度优先搜索,从N开始一直到0,用visit标记当前元素是否访问过,当当前下标为1的时候表示当前深度优先的一条路径满足条件,result+1,否则遍历visit数组看有没有没被访问过的元素,如果满足(i % index == 0 || index % i == 0)就标记为已经访问过,然后继续向下遍历dfs(index-1)~最后返回result的结果~

 

LeetCode 525. Contiguous Array

525. Contiguous Array
Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

Example 1:
Input: [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.
Example 2:
Input: [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.
Note: The length of the given binary array will not exceed 50,000.

题目大意:给一个二进制数组,找最长的连续子数组,要求子数组里面的0和1的个数相等~
分析:0和1数组,可以考虑把0换成-1,变成-1和0数组,那么本质上就是找是否有下标从i~j的总和为0的子数组~
令map保存sum和sum对应的下标的值,遍历数组每次计算数组当前的sum,如果当前sum之前已经出现过,比如说之前有过一个sum = 2,现在又sum = 2了,说明在第一次sum等于2的时候,它前面所有元素加起来总和是2,那么在它前面去掉2个元素1就能满足0,同理当前的sum = 2也可以通过去掉最前面的2个元素1使sum = 0,所以看看i – m[sum]是否比之前的最大值大,如果比之前最大值大就更新最大值~

 

LeetCode 520. Detect Capital

520. Detect Capital
Given a word, you need to judge whether the usage of capitals in it is right or not.

We define the usage of capitals in a word to be right when one of the following cases holds:

All letters in this word are capitals, like “USA”.
All letters in this word are not capitals, like “leetcode”.
Only the first letter in this word is capital if it has more than one letter, like “Google”.
Otherwise, we define that this word doesn’t use capitals in a right way.
Example 1:
Input: “USA”
Output: True
Example 2:
Input: “FlaG”
Output: False

题目大意:判断一个字母是否大小写正确:要么全是大写,要么全是小写,或者首字母大写其他小写,否则不满足题意~
分析:判断word[0]和word[1]的大小写,如果word[0]是小写,那后面必须是小写,如果word[0]是大写word[1]是小写,那后面也必须是小写,如果word[0]是大写word[1]也是大写那么后面必须都是大写~