[日常刷题]leetcode D34

65 阅读 0 评论 43 点赞

我是靠谱客的博主有魅力玫瑰，最近开发中收集的这篇文章主要介绍[日常刷题]leetcode D34，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

文章目录

- 441. Arranging Coins
- 443. String Compression
- 小结
- - 知识点

441. Arranging Coins

You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins.

Given n, find the total number of full staircase rows that can be formed.

n is a non-negative integer and fits within the range of a 32-bit signed integer.

Example 1:

n = 5

The coins can form the following rows:
¤
¤ ¤
¤ ¤

Because the 3rd row is incomplete, we return 2.

Example 2:

n = 8

The coins can form the following rows:
¤
¤ ¤
¤ ¤ ¤
¤ ¤

Because the 4th row is incomplete, we return 3.

Solution in C++：

关键点：

数列求和公式

思路：

题目很明显就是一个求和公式的逆运用，这里我主要出的问题可能是因为数据类型写的有点问题，然后sqrt的结果居然是nan，思索好久不懂情况，然后自己拆分之后OK，但是看到别人的写法和我的类似但是AC，所以可能还是自己对于类型转换这样的问题掌握的还不够。

int arrangeCoins(int n) {
        // x * (x + 1) / 2 = n => x = -1/2 + sqrt(2*n+1/4)
        return sqrt(2.0 * double(n) + 0.25) - 0.5;
    }

443. String Compression

Given an array of characters, compress it in-place.

The length after compression must always be smaller than or equal to the original array.

Every element of the array should be a character (not int) of length 1.

After you are done modifying the input array in-place, return the new length of the array.

Follow up:
Could you solve it using only O(1) extra space?

Example 1:

Input:
["a","a","b","b","c","c","c"]

Output:
Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]

Explanation:
"aa" is replaced by "a2". "bb" is replaced by "b2". "ccc" is replaced by "c3".

Example 2:

Input:
["a"]

Output:
Return 1, and the first 1 characters of the input array should be: ["a"]

Explanation:
Nothing is replaced.

Example 3:

Input:
["a","b","b","b","b","b","b","b","b","b","b","b","b"]

Output:
Return 4, and the first 4 characters of the input array should be: ["a","b","1","2"].

Explanation:
Since the character "a" does not repeat, it is not compressed. "bbbbbbbbbbbb" is replaced by "b12".
Notice each digit has it's own entry in the array.

Note:

All characters have an ASCII value in [35, 126].
1 <= len(chars) <= 1000.

Solution in C++：

关键点：

扫描

思路：

思路很简单就是扫描，然后计数，添加到result字符串中，这里当然写也可以通过变量当指针的作用使用。主要需要注意的就是控制变量的合法性。

int compress(vector<char>& chars) {
        
        size_t size = chars.size();
        
        if (size == 0)
            return 0;
        string result(1, chars[0]);
        
        for(int i = 1; i < size; ++i){
            int tmp = 1;
            
            while(chars[i] == chars[i-1] && i < size){
                ++i;
                ++tmp;
            }
            if (tmp > 1)
                result += to_string(tmp);
            if (i < size)
                result += chars[i];
        }
        
        for(int i = 0; i < result.size(); ++i)
            chars[i] = result[i];
            
        return result.size();
    }