17.10. 主要元素
数组中占比超过一半的元素称之为主要元素。给你一个 整数 数组，找出其中的主要元素。若没有，返回 -1 。请设计时间复杂度为 O(N) 、空间复杂度为 O(1) 的解决方案。
示例 1：
输入：[1,2,5,9,5,9,5,5,5]
输出：5
示例 2：
输入：[3,2]
输出：-1
示例 3：
输入：[2,2,1,1,1,2,2]
输出：2
class Solution {
public int majorityElement(int[] nums) {
int v=0,a=-1;
for(int x:nums)
{
if(v==0)
{
a=x;
v++;
}else
{
if(a==x)
v++;
else
v--;
}
}
if(v==0) return -1;
int n=0;
for(int x:nums)
{
if(x==a)
n++;
if(n>nums.length/2)
return a;
}
return -1;
}
}
个人总结： 学会了投票算法。
01.05. 一次编辑
字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。 给定两个字符串，编写一个函数判定它们是否只需要一次(或者零次)编辑。
示例 1:
输入:
first = “pale”
second = “ple”
输出: True
示例 2:
输入:
first = “pales”
second = “pal”
输出: False
class Solution {
public boolean oneEditAway(String first, String second) {
if(first.equals(second))
return true;
if(first.length()1)
return false;
int b=0,e=n1-1;
for(;b=0;i--)
{
if(f[e]!=s[i]) break;
else
e--;
}
return b==e?true:false;
}
}
个人总结： 思路不是很灵活。
