Leecode题型笔记（一）

布满荆棘的人生 2022-03-11 10:22 160阅读 0赞

*  一、给定一个整数 *n*，返回 *n*! 结果尾数中零的数量。

**示例 1:**

输入: 3
    输出: 0
    解释: 3! = 6, 尾数中没有零。

**示例 2:**

输入: 5
    输出: 1
    解释: 5! = 120, 尾数中有 1 个零.

**说明:** 你算法的时间复杂度应为 *O*(log *n*)* *。

> 2\*5会产生10.
> 
> 算n里有几个5！！！！有五一定会有2的。比如1，2，3，4，5，6，7，8，9，10中。5中有2，10中有8

*  二、有的时候关于两个数组或链表的关系，是不是可以把他们合并起来试试看
 *  三、快慢指针可以求终点
 *  哈希表可以用在求重复的问题上
 *  有的时候想想看是不是可以用数学公式解决问题。例如

爱丽丝和鲍勃有不同大小的糖果棒：`A[i]` 是爱丽丝拥有的第 `i` 块糖的大小，`B[j]` 是鲍勃拥有的第 `j` 块糖的大小。

因为他们是朋友，所以他们想交换一个糖果棒，这样交换后，他们都有相同的糖果总量。*（一个人拥有的糖果总量是他们拥有的糖果棒大小的总和。）*

返回一个整数数组 `ans`，其中 `ans[0]` 是爱丽丝必须交换的糖果棒的大小，`ans[1]` 是 Bob 必须交换的糖果棒的大小。

如果有多个答案，你可以返回其中任何一个。保证答案存在。

**示例 1：**

输入：A = [1,1], B = [2,2]
    输出：[1,2]

**示例 2：**

输入：A = [1,2], B = [2,3]
    输出：[1,2]

方法：方程求解

**思路**

如果爱丽丝交换糖果 `x`，她将会期待交换一些特定量的糖果 `y` 回来。

**算法**

设爱丽丝和鲍勃分别总计有 SA,SBS\_A, S\_BSA,SB 的糖果。

如果爱丽丝给了糖果 xxx，并且收到了糖果 yyy，那么鲍勃收到糖果 xxx 并给出糖果 yyy。那么，我们一定有

SA−x+y=SB−y+x

对于公平的糖果交换。这意味着

我们的策略很简单。对于爱丽丝拥有的每个糖果 xxx，如果鲍勃有糖果 y=x+(SB−SA)2，我们就返回 \[x，y\]。我们在常量时间内使用`集 Set` 结构来检查Bob是否拥有所需的糖果 yyy。

*  有的时候整体做不出来，不妨试试一步一步分开来做。比如求岛屿长度。

### [摩尔投票法][Link 1] ###

### [杨辉三角,][Link 2] ###

[算排列组合分分钟超范围啊，不要随意产生贼大的中间结果！！如果确定结果不会溢出的话，可以使用long类型做中间计算，然后再强转。][Link 2]

### 添加字符 ###

如果经常需要为字符串添加字符的时候，StringBuilder类的效率会高一些

### 使用队列实现栈 ###

额。。。就是访问的时候弹出前n-1个值，相当于对队尾操作，（好愚蠢）

### 给定一个整数，编写一个函数来判断它是否是 2 的幂次方。 ###

class Solution {
        public boolean isPowerOfTwo(int n) {
            if(n<=0){return false;}
            else{
                if((n&(n-1))==0){return true;}
                else
                    return false;
            }
        }
    }

> sqrt()算法的实现：牛顿迭代法,求a的平方根
> 
> Xn+1=(Xn+a/Xn)/2;
> 
> 还有一种方法，直接暴力得到最接近平方根的数，不用那么多习迭代。

float InvSqrt(float x)
    {
        float xhalf = 0.5f*x;
        int i = *(int*)&x; // get bits for floating VALUE 
        i = 0x5f375a86- (i>>1); // gives initial guess y0
        x = *(float*)&i; // convert bits BACK to float
        x = x*(1.5f-xhalf*x*x); // Newton step, repeating increases accuracy
        x = x*(1.5f-xhalf*x*x); // Newton step, repeating increases accuracy
        x = x*(1.5f-xhalf*x*x); // Newton step, repeating increases accuracy
    
        return 1/x;
    }

[java 需要转义的一些特殊符号。][java]

> 字符串一旦初始化之后不能改变。replace函数什么的都不能改变自身。都是返回一个新值。
> 
> String str=new String("abc")
> 
> str.replace("a","c");
> 
> 这样是没有作用的。

## 696、计数的二进制串 ##

给定一个字符串 `s`，计算具有相同数量0和1的非空(连续)子字符串的数量，并且这些子字符串中的所有0和所有1都是组合在一起的。

重复出现的子串要计算它们出现的次数。

**示例 1 :**

输入: "00110011"
    输出: 6
    解释: 有6个子串具有相同数量的连续1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。
    
    请注意，一些重复出现的子串要计算它们出现的次数。
    
    另外，“00110011”不是有效的子串，因为所有的0（和1）没有组合在一起。

//一个简单的思路：用last来记录之前一种数字的个数， cur来记录当前数字的个数； 当last >= cur的时候， //res ++; 具体代码如下
    
    class Solution {
    public:
        int countBinarySubstrings(string s) {
            int last, cur, res; last = res = 0; cur = 1;
            for(int i=1; i<s.size(); i++){
                if(s[i] == s[i-1]) cur ++;
                else{last = cur; cur = 1;}
                if(last >= cur) res++;
            }
            return res;
        }
    };

## HashMap和数组谁快 ##

> 做题目感觉数组比hashmap读取速度快好多，一用hashmap就贼慢
> 
> [hashmap和数组哪个快][hashmap]

##  LinkList使用remove()时报错。 ##

> 是因为有两个remove
> 
>  *  如果想要删除指定元素，就要封箱成Object才行
>     
>      *  <table> 
>          <tbody> 
>           <tr> 
>            <td><code><a rel="nofollow">E</a></code></td> 
>            <td><code><a rel="nofollow">remove</a>(int&nbsp;index)</code> <p>删除该列表中指定位置的元素。</p> </td> 
>           </tr> 
>          </tbody> 
>         </table>
>      *   *  <table> 
>              <tbody> 
>               <tr> 
>                <td><code>boolean</code></td> 
>                <td><code><a rel="nofollow">remove</a>(<a rel="nofollow">Object</a>&nbsp;o)</code> <p>从列表中删除指定元素的第一个出现（如果存在）。</p> </td> 
>               </tr> 
>              </tbody> 
>             </table>

## 蓄水池抽样 ##

[蓄水池抽样][Link 3]

## 0-1背包 ##

[0-1背包][0-1]

## 重写compare方法 ##

[重写compare（Comparator）][compare_Comparator]

## 字典树 ##

[字典树][Link 4]

## 正则表达式 ##

[正则表达式][Link 5]

## split用法 ##

[split用法][split]

## 正则表达式入门 ##

[正则表达式用法][Link 6]

## 将整数转化为二进制串 ##

Integer.toBinaryString

## 数组赋值 ##

[数组赋值][Link 7]

[Link 1]: https://mabusyao.iteye.com/blog/2223195
[Link 2]: https://blog.csdn.net/baidu_37107022/article/details/72853001
[java]: https://blog.csdn.net/bamboo_cqh/article/details/51066396
[hashmap]: https://blog.csdn.net/Chasel_s/article/details/77678300
[Link 3]: https://blog.csdn.net/huagong_adu/article/details/7619665
[0-1]: https://www.cnblogs.com/Christal-R/p/Dynamic_programming.html
[compare_Comparator]: https://blog.csdn.net/xiaxl/article/details/72568587
[Link 4]: https://www.cnblogs.com/xujian2014/p/5614724.html
[Link 5]: https://blog.csdn.net/qq_19865749/article/details/77478489
[split]: https://www.cnblogs.com/mingforyou/archive/2013/09/03/3299569.html
[Link 6]: https://www.jb51.net/article/126553.htm
[Link 7]: https://blog.csdn.net/qq_35580883/article/details/79115707