菜鸟刷题Day5

描述

给你一个数组 nums 。数组「动态和」的计算公式为：runningSum[i] = sum(nums[0]…nums[i]) 。

请返回 nums 的动态和。

示例：

输入：nums = [1,2,3,4]
输出：[1,3,6,10]
解释：动态和计算过程为 [1, 1+2, 1+2+3, 1+2+3+4] 。

解题思路

1.通过观察示例可以发现，其实runningSum[0]和nums[0]相等，runningSum[1]=runningSum[0]+nums[1];所以我们可以得到这样一个结论：当 i > 0时：runningSum[i]=runningSum[i-1]+nums[i];

我可以新开辟一个数组（大小和nums一样大），将累加的结果存放到这个新开的数组中，再返回这个新开辟的数组。

int* runningSum(int* nums, int numsSize, int* returnSize)
{	
    int*tmp=(int*)malloc(sizeof(int)*numsSize);
    tmp[0]=nums[0];
    
    for(int i=1;i<numsSize;i++)
    {
        tmp[i]=tmp[i-1]+nums[i];
    }
    *returnSize=numsSize;
    
    return tmp;
}

2.直接在原地改变，除了第一项不用改变以外，后面的每一项元素都是前面元素累加的结果。

int* runningSum(int* nums, int numsSize, int* returnSize)
{
    for(int i=1;i<numSize;i++)
    {
         nums[i]+=nums[i-1];
    }
    
    *returnSize=numsSize;
    
    return nums;
}

描述

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

解题思路

看到说时间复杂度位O（log n）就让人想起二分查找算法，二分查找虽然强大，但是有一个很大的缺陷就是要求被查找的数据必须要有序。正好题目说了是一个排序数组，那还不二分走起

int searchInsert(int* nums, int numsSize, int target)
{
    int begin=0;
    int end=numsSize-1;
    int mid=0;
    
    while(begin<=end)
    {
        mid=(begin+end)/2;
        
        if(nums[mid]<target)
        {
            begin=mid+1;
        }
        else if(nums[mid]>target)
        {
            end=mid-1;
        }
        else//相等
        {
            return mid;
        }
        

    }
   return begin;
}

关于最后的返回值：位于begin左边的数一定小于目标值，而在end右边的数一定是大于end的，也就是说目标值要么在begin和end的中间，要么就在begin和end之间的某个位置插入，而最后的结束条件是begin>end，也就是说这中间只有begin是一直在改变的，因此如果最后在数组中找不到这个元素，那么它的插位置一定是begin位置

描述

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

解题思路

首先映入眼帘的还是O(log n)，那么用二分查找吗？一看是升序排序数组，但是这里又说了，会在某个位置旋转一下。好像不能用二分

但是（我知道你在等但是），在k位置旋转以后，仍然是局部有序的。如果中间的数小于最右边的数，则右半段是有序的，若中间数大于最右边数，则左半段是有序的，我们只要在有序的半段里用首尾两个数组来判断目标值是否在这一区域内，这样就可以确定保留哪一半了

这里只要通过控制下标就可以实现在一个数组内分割出两个数组的目的

int search(int* nums, int numsSize, int target)
{
    //核心在于只是局部有序

    int begin=0,end=numsSize-1;
    while(begin<=end)
    {
        int mid=(begin+end)/2;

        if(nums[mid]==target)
            return mid;

        //二分查找只能在有序数列中进行，所以要判断有序范围，一定是局部有序
        if(nums[mid]<nums[end])//说明右边数组有序
        {
            //判断一下目标值是否在右边数组中,既然在右边数组，那么就要重新调整一下mid的值
            if(nums[mid]<target&&nums[end]>=target)
                 begin=mid+1;
            else
                end=mid-1;      
        }
        else
        {
            //左边数组有序,还要判断一下是否在左边数组中
            if(nums[mid]>target&&nums[begin]<=target)
                end=mid-1;
            else
                begin=mid+1;
        }

    }
    //到这里就是找不到
    return -1;
}

描述

给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。请你返回该链表所表示数字的 十进制值
链表不为空; 链表的结点总数不超过 30; 每个结点的值不是0就是 1

示例：

输入：head = [1,0,1]
输出：5
解释：二进制数 (101) 转化为十进制数 (5）

解题思路

1.建立一个数组，然后遍历链表，将链表中的值存取到数组中，将数组的内容转换成十进制，在size-1位置的反而是于二的零次方相乘，所以可以得到如下代码

	int getDecimalValue(struct ListNode* head)
 {

    int arr[31];
    int i=0;
    int flag=0;//做标记，如果数组中没有1，无论链表多长结果都是0
    while(head!=NULL)
    {
        arr[i]=head->val;
        i++;
        if(head->val==1)
        {
            flag=1;
        }
        head=head->next;
    }
    //将链表中的数值全部提取到数组中,必须要拿到数组的有效长度
    int sum=0;
    int sz=i;

    if(flag==0)
        return 0;
    else
    {
        for(i=0;i<sz;i++)
        {
           if(arr[i]!=0)
           {
                sum+=pow(2,sz-1-i);
           }
        }
    }

    return sum;
}

2.此外还可以利用位运算，第一次就从链表中拿到的那个数其实是二的size-1次方，而左移一位就有乘二的效果

int getDecimalValue(struct ListNode* head)
{
    int sum=0;
    
    while(head!=NULL)
    {
        sum=(sum<<1)+head->val;
        
        head=head->next;
    }
    
    return sum;
}

人们总是高估短期努力能带来的提升，而忽略长期坚持带来的改变。今天是第五天，也是第二十题了，你还在坚持吗？