翻转字符串里的单词
题目：给定一个字符串，逐个翻转字符串中的每个单词。
示例 1：
输入: "the sky is blue"
输出: "blue is sky the"
示例 2：
输入: " hello world! "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3：
输入: "a good example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
说明：
无空格字符构成一个单词。
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
进阶：
请选用 C 语言的用户尝试使用 O(1) 额外空间复杂度的原地解法。
思路：讲真，这个题像是初级难度的啊，进阶要求是C语言的才有的，，我是java，哈哈。然后单纯的实现其实真的很简单，trim去前后空格，然后空格拆分字符串，然后双指针调换位置，然后stringBuffer加上。就酱，我去实现下
好了，思路没问题，而且很简单，性能超过百分之九十八，我都不敢去看评论了，恐怕再说我不应该用啥。。我先贴代码：
class Solution {
public String reverseWords(String s) {
s = s.trim();
String[] arr = s.split(" ");
StringBuffer sb = new StringBuffer();
for(int i = arr.length-1;i>=0;i--){
if(arr[i].equals(" ") || arr[i].equals("") ) continue;
sb.append(arr[i]+" ");
}
return sb.toString().trim();
}
}
算了，伸头一刀缩头一刀，我去瞅瞅评论说啥了。
额，评论没说啥啊，而且性能排行第一的代码也是这个套路，所以这个题就过了吧！
寻找旋转排序数组中的最小值
题目：假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。请找出其中最小的元素。你可以假设数组中不存在重复元素。
示例 1:
输入: [3,4,5,1,2]
输出: 1
示例 2:
输入: [4,5,6,7,0,1,2]
输出: 0
思路：这个题我感觉题目肯定是少条件了。不然不能是中等难度啊，不就是一个遍历的事么？应该是时间复杂度logn？常量级是不可能的，，我去按照我想的时间复杂度做了。
第一版本出来了，我先贴出来：
class Solution {
public int findMin(int[] nums) {
int l = 0;
int r = nums.length-1;
while(l<r){
if(nums[l]<nums[r]) return nums[l];
if(nums[l]>nums[l+1]) return nums[l+1];
if(nums[r]<nums[r-1]) return nums[r];
l++;
r--;
}
return nums[0];
}
}
这个时间复杂度是n。不太满足我的要求，我再去试试logn实现的。
好了，二分法实现了，我贴下代码：‘
class Solution {
public int findMin(int[] nums) {
if(nums.length == 1) return nums[0];
//说明已经是升序了
if(nums[0]<nums[nums.length-1]) return nums[0];
int l = 0;
int r = nums.length-1;
while(l<r){
int mid = (r-l)/2+l;
if(nums[mid]<nums[r]){//后半段是排好序的。说明旋转点在前半段
r = mid;
}else if(nums[mid]>nums[r]){//旋转点在后半段
l = mid +1;
}else{
return nums[mid];
}
}
return nums[l];
}
}
然后这道题就这样了，不算难，难点就是二分法区间了。没啥好说的，多看看就好了，直接下一题了。
乘积最大子序列
题目：给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。
示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
思路：这道题怎么说呢，乍一看我甚至想到了动态规划，但是仔细瞅了瞅，其实逻辑好处理多了。也可以用dp。第一个数作为开始值，挨个和后面乘，保存其中的最大乘积，第二个数开始，挨个和后面乘，保存最大乘积，反正取最大的就行。我去实现啦。
哎，我自己实现了，然后性能贼可怜，但是我还是要发出来，毕竟是自己想出来的：
class Solution {
public int maxProduct(int[] nums) {
int max = Integer.MIN_VALUE;
for(int i = 0;i<nums.length;i++){
int count = nums[i];
max = Math.max(max,count);
for(int j = i+1;j<nums.length;j++){
count *= nums[j];
max = Math.max(max,count);
}
}
return max;
}
}
咳咳，无脑但是一看就懂，我觉得挺好的，但是性能太不给力啊~~~
其实有这个感觉，毕竟做了很多无用功，我去看看怎么能优化一下。
好了，接下来去看性能排行第一的代码了！对，我凭实力优化不出来了。。。膜拜大佬吧
class Solution {
public int maxProduct(int[] nums) {
/*求最大值，看被0拆分的各个子数组的最大值
1.负数为偶数：全部乘积
2.负数为奇数：最左或最右的负数不在内，从左到右和从右到左分别计算，求最大
3.存在0，则从1重新开始
*/
int m=1;
int max=nums[0];
for(int num:nums){
m=m*num;
max=Math.max(max,m);
if(num==0){
m=1;
}
}
m=1;
for(int i=nums.length-1;i>=0;i--){
m=m*nums[i];
max=Math.max(max,m);
if(nums[i]==0){
m=1;
}
}
return max;
}
}
这个思路怎么说呢，代码复杂了点，因为两遍循环。但是比我的n方的时间复杂度好太多。。。我只能说记住了，下次争取自己写也这样写。
今天的笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注哟~！然后顺便祝大家工作顺顺利利！生活健健康康！
网友评论