LeetCode算法题（31-35）

第31题
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。

例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。

必须 原地 修改，只允许使用额外常数空间。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/next-permutation

思路
对于数组nums：
1.先从尾部开始寻找满足nums[i]<nums[i+1]的第一个坐标i，如果找不到，则不存在下一个字典序更大的排列，将数组重排为字典序最小的排列；
2.从尾部开始寻找满足nums[j] > nums[i]的第一个坐标j;
3.交换nums[i]和nums[j]的值，然后将数组i+1到numsSize-1的值逆置。

void nextPermutation(int* nums, int numsSize){
    int i, j, k, tmp;
    for( i = numsSize-2; i >= 0; i--)
    {
        if(nums[i] < nums[i+1]) break;
    }
    if(i == -1)
    {
        for(i = 0; i < numsSize/2; i++)
        {
            tmp = nums[i];
            nums[i] = nums[numsSize-i-1];
            nums[numsSize-i-1] = tmp;
        }
    }
    
    else
    {
        for(j = numsSize-1; j > i; j--)
        {
            if(nums[j] > nums[i]) break;
        }
        tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
        j = i+1;
        k = numsSize-1;
        while(j < k)
        {
            tmp =nums[j];
            nums[j] = nums[k];
            nums[k] = tmp;
            j++;
            k--;
        }
    }
    return nums;
}

第32题：最长有效括号
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
来源：LeetCode
链接：32. 最长有效括号 - 力扣（LeetCode） (leetcode-cn.com)

int longestValidParentheses(char * s){
    int max = 0;
    int tmp = 0;
    int len = strlen(s);
    if(len < 2)  return 0;
    int left = 0, right = 0;
    int i;
    for(i = 0; i < len; i++)    //从头开始遍历字符串
    {
       
        if(s[i] == '(' )       //每遇到一个左括号
        {
            left++;
        }
        if(s[i] == ')')       //每遇到一个右括号
        {
            right++;
        }

        if(left == right && s[i+1] == ')')       //当前子串完全匹配，且长度不能再增加了
        {
            
            max = (tmp + 2*left)>max ? (tmp + 2*left) :max;
            tmp = 0;
            left = 0;
            right = 0;
            
        }
        if(left == right && s[i+1] == '(')     //当前子串完全匹配，但是长度有增加的可能
        {
            tmp = tmp +  left + right;
            left = 0;
            right = 0;
        }
        if(left < right)
        {
            right = 0;
            left = 0;
        }
        
    }
    if(left == right)      //最后一部分子串完全匹配
    {
        max = (tmp + 2*left)>max ? (tmp + 2*left) :max;
        return max;
    }
    else                 //最后一部分子串中左括号多余右括号
    {
        max = tmp > max ? tmp : max;
        tmp = 0;
        int r= 0;
        int l= 0;
        for(i = len-1; i > len-left-right; i--)       //从尾部开始遍历最后一部分子串
        {
            if(s[i] == ')')
            {
                r++;
            }
            else l++;
            if(r == l && s[i-1] == '(')
            {
                max = (tmp + 2*l)>max ? (tmp + 2*l) :max;
                r = 0;
                l = 0;
                tmp = 0;
            } 
            if(r == l && s[i-1] == ')')
            {
                tmp = tmp + r + l;
                r = 0;
                l = 0;
            }
            if(l > r)
            {
                l = 0;
                r = 0;
            }
        }
        return max;
    }
    
    
}

第33题：搜索旋转排序数组
整数数组 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 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array

int search(int* nums, int numsSize, int target){     
    int i;
    for(i = 0; i < numsSize; i++)
    {
        
        if(nums[i] == target)  return i;
    }        
    return -1;
}```
**第34题：在排序数组中查找元素的第一个和最后一个位置**
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array

/**

  • Note: The returned array must be malloced, assume caller calls free().
    /
    int     searchRange(int* nums, int numsSize, int target, int* returnSize){
    int *ans = (int *)malloc(sizeof(int) * 2);
    *returnSize = 2;
    ans[0] = -1;
    ans[1] = -1;
    if( numsSize == 0 || target < nums[0])
    {

     return ans;

    }
    int i;
    while(i < numsSize && nums[i] != target) i++;
    if(i != numsSize)
    {
    ans[0] = i;
    while(i < numsSize && nums[i] == target) i++;
    ans[1] = i-1;
    }
    return ans;
    }

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-insert-position

int searchInsert(int* nums, int numsSize, int target){
if(target <= nums[0]) return 0;
if(target > nums[numsSize-1]) return numsSize;
if(target == nums[numsSize-1]) return numsSize-1;
int mid, high, low;
low = 0;
high = numsSize-1;
while(low < high) //二分搜索
{
mid = (low+high)/2;
if(low == mid) return high;
if(target == nums[mid]) return mid;
if(target < nums[mid])
{
high = mid;
}
if(target > nums[mid])
{
low = mid;
}

}

return 0;
}

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容