有空就看看的leetcode10——搜索插入位置&&外观数列（c++版）

野性酷女 2023-06-27 12:49 3阅读 0赞

### 有空就看看的leetcode10——搜索插入位置&&外观数列（c++版） ###

*  学习前言
 *  题目
 *   *  1、搜索插入位置
     *  2、外观数列
 *  解法
 *   *  1、搜索插入位置
     *  2、外观数列

# 学习前言 #

明天就要考试啦，考神保佑。  
![在这里插入图片描述][20190723170158884.jpg_pic_center]

# 题目 #

## 1、搜索插入位置 ##

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

你可以假设数组中无重复元素。

示例 1:

输入: \[1,3,5,6\], 5  
输出: 2  
示例 2:

输入: \[1,3,5,6\], 2  
输出: 1  
示例 3:

输入: \[1,3,5,6\], 7  
输出: 4  
示例 4:

输入: \[1,3,5,6\], 0  
输出: 0

## 2、外观数列 ##

「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。前五项如下：

1.      1
2.      11
3.      21
4.      1211
5.      111221

1 被读作 “one 1” (“一个一”) , 即 11。  
11 被读作 “two 1s” (“两个一”）, 即 21。  
21 被读作 “one 2”, “one 1” （“一个二” , “一个一”) , 即 1211。

给定一个正整数 n（1 ≤ n ≤ 30），输出外观数列的第 n 项。

注意：整数序列中的每一项将表示为一个字符串。

示例 1:

输入: 1  
输出: “1”  
示例 2:

输入: 4  
输出: “1211”

# 解法 #

## 1、搜索插入位置 ##

class Solution {
        
    public:
        int searchInsert(vector<int>& nums, int target) {
        
            int index=0;
            for(int i = 0; i<nums.size(); i++){
        
                if(nums[i]<target){
        
                    index++;
                }else if(nums[i]>=target){
        
                    return i;
                }
            }
            return index;
        }
    };

思路：  
**由于原数组是顺序的，所以当我们的目标大于原数组中的某个数时，表示已到达插入的位置。找到相等的则直接返回位置。**

## 2、外观数列 ##

class Solution {
        
    public:
        string countAndSay(int n) {
        
            string temp;
            string out="1";
            for(int i = 1; i<n; i++){
        
                temp = out;
                out = "";
                for(int j = 0; j<temp.length();){
        
                    int count = 0;
                    int k = j;
                    while(temp[j]==temp[k] && k<temp.length()){
        
                        k++;
                        count++;
                    }
                    out += to_string(count) + temp[j];
                    j = k;
                }
            }
            return out;
            
        }
    };

思路：  
**对上一个数的每一位进行计数。当所计数的对象发生变化时，到out进行记录。**

[20190723170158884.jpg_pic_center]: https://img-blog.csdnimg.cn/20190723170158884.jpg#pic_center