算法笔记1
2020-09-24 10:33:45 # 算法

投票算法

​ 在面试题中经常会出现这样一个题目，给一个数组，其中含有N个非负元素，让你求出数组中出现次数超过一半的数字。

​ 看到这个问题我们首先想到的可能是暴力的解法，那就是将数组排个序，输出中间的元素就行了，因为如果出现次数超过一半的话排完序后中间的那个元素肯定是我们需要求的值。

​ 这样做的话排序的时间复杂度一般来说是O(NlogN)，那么有没有时间复杂度为n的算法呢？

​ 投票算法。核心就是对拼消耗。

​ 玩一个诸侯争霸的游戏，假设你方人口超过总人口一半以上，并且能保证每个人口出去干仗都能一对一同归于尽。最后还有人活下来的国家就是胜利。那就大混战呗，最差所有人都联合起来对付你（对应你每次选择作为计数器的数都是众数），或者其他国家也会相互攻击（会选择其他数作为计数器的数），但是只要你们不要内斗，最后肯定你赢。最后能剩下的必定是自己人。（在某乎上看到的通俗解释）

​ 下面进行举例，找出数组中的主要元素，数组中占比超过一半的元素称之为主要元素。给定一个整数数组，找到它的主要元素。若没有，返回-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int majorityElement(int[] nums) {
        int ans = nums[0]; //假设第一个数即为核心元素
        int account = 1;  //设定一个计数器
        for(int i=1;i<nums.length;i++){
            if(nums[i]==ans){
                account++; //如果相等，计数器加一
            }else{
                account--;   //如果不相等，计数器减一
            }

            if(account == 0){   //若计数器等于零，则从下一个数从新开始
                ans = nums [i+1];
                i++;
                account = 1;
            }
        }
        return ans;
    }
}

位运算

1、位运算右移一位可代替除以2，左移一位可代替乘2。

2、对n做右移运算时，一定要考虑到n为负数时的特殊情况。

3、判断一个数的最后一位是不是1，只需与1做位与运算，若结果为1则最后一位是1，若结果为0则最后一位为0

4、判断n的奇偶性可以将n和1做位与运算，若结果为1则n为奇数，若结果为0，则n为偶数。

链表

双指针

设置一个pre和cur分别指向前一个节点和当前节点(例如反转链表)

876. 链表的中间结点

由于不能直接获取长度,从而需要遍历才能知道链表的长度,确定哪个是中间节点.

但是可以转为数学问题,一个快指针,一个慢指针,快指针每次移动两步,慢指针每次移动一步,这样当快指针遍历完之后,慢指针一定指向的是中间节点

*设置标记,遍历过的节点添加tag属性为true(如判断链表是否有环)

Prev
2020-09-24 10:33:45 # 算法
Next