LeetCode 2018面试高频算法

发表于 更新于 分类于 评论数：
本文字数： 9k 阅读时长 ≈ 11 分钟

简单题

开始之前

136 只出现一次的数字

https://leetcode-cn.com/problems/single-number/

169 求众数

https://leetcode-cn.com/problems/two-sum/solution/qiu-zhong-shu-by-leetcode-2/

1
int major = nums.length/2;//求众数的条件

方法一 暴力搜索法

不建议，时间复杂度O(n2),空间复杂度O(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) {
        if(nums.length <= 0){
            return -1;
        }

        for(int i=0;i<nums.length;i++){
             int count = 0;//注意初始化位置，每次检查完i位置的数后需要把count清0，重新计数
            for(int j=0;j<nums.length;j++){//count初始为0.所以仍从第一个位置开始
                if(nums[j] == nums[i]){
                    count++;
                }
            }
            if(count > nums.length/2){
                return nums[i];
            }
        }
        return -1;
    }
}

方法二 Map遍历法

Map常用于计数方面的算法，要牢记其初始化和遍历方法

时间复杂度O(n),空间复杂度O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int majorityElement(int[] nums) {
    int major = nums.length/2;
		Map<Integer,Integer> map = numsMap(nums);//map初始化
		if(nums.length<=0) {
			return -1;
		}
		for(Integer num:map.keySet()) {//Map遍历的方式之一
			if(map.get(num)>major) {
				return num;
			}
		}
		return -1;
    }

    public Map<Integer,Integer> numsMap(int[] nums){//map初始化方法
		Map<Integer,Integer> map = new HashMap<Integer, Integer>();
		for(int num:nums) {
			if(!map.containsKey(num)) {
				map.put(num, 1);
			}else {
				map.put(num, map.get(num)+1);
			}
		}
		return map;
	}
}

方法三 Boyer-Moore 投票算法

想法: 如果我们把众数记为 +1 ，把其他数记为 -1 ，将它们全部加起来，显然和大于 0 ，从结果本身我们可以看出众数比其他数多。

（竖线用来划分每次计数器归零的情况）
[7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7]

首先，下标为 0 的 7 被当做众数的第一个候选。在下标为 5 处，计数器会变回0 。所以下标为 6 的 5 是下一个众数的候选者。由于这个例子中 7 是真正的众数，所以通过忽略掉前面的数字，我们忽略掉了同样多数目的众数和非众数。因此， 7 仍然是剩下数字中的众数。

1
2
3
4
5
6
7
8
9
10
11
12
//计数法，相同就+1；不同就-1
	public static int majorEle2(int[] nums) {
		int count = 0;
		int candidate = nums[0];
		for(int num:nums) {
			if(count == 0) {
				candidate = num;
			}
			count += (candidate == num)? 1:-1;
		}
		return candidate;
	}

88. 合并两个有序数组

https://leetcode-cn.com/problems/merge-sorted-array/
给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。

说明:

初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
示例:

1
2
3
4
5
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

输出: [1,2,2,3,5,6]

此处考虑到若从前往后 比较并排序需要把后面的数字挪动，为避免挪动增大空间复杂度，从后往前比较并填充

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p = m+n-1;//合并后的最大下标
		m--;//最大下标
		n--;
		while(n>=0) {
			if(m>=0 && nums1[m]>nums2[n]) {//注意判断次序， 需要先判断m再判断数组
				nums1[p] = nums1[m];
				m--;
				p--;
			}else {
				nums1[p] = nums2[n];
				n--;
				p--;
			}
		}
    }
}

简化后

1
2
3
4
5
6
public void merge(int[] nums1, int m, int[] nums2, int n) {
    int p = m-- + --n;
    while(n>=0){
      nums1[p--] = m>=0 && nums1[m]>nums2[n] ? nums1[m--]:nums2[n--];
    }
}

字符串

125. 验证回文串

https://leetcode-cn.com/problems/valid-palindrome/

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串。

示例 1:

1
2
输入: "A man, a plan, a canal: Panama"
输出: true

示例 2:

1
2
输入: "race a car"
输出: false

双指针，一个从头开始，一个从尾开始

要求不区分大小写，就可以把字符串转为小写
一定要区分好if和while

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public static boolean isPalindrome(String s) {
	if (s == null) {
		return true;
	}
	s = s.toLowerCase();// 都转为小写
	int i = 0, j = s.length() - 1;
	while (i < j) {
		while (!isLawful(s.charAt(i))) {
			i++;
			if (i == s.length())
				return true;// 空字符串
		}
		while (!isLawful(s.charAt(j))) {
			j--;
		}
		//char ichar = s.charAt(i);//debug用
		//char jchar = s.charAt(j);

		if (s.charAt(i) != s.charAt(j)) return false;
		i++;
		j--;
	}
	return true;
}

private static boolean isLawful(char c) {
	if (c >= '0' && c <= '9' || c >= 'a' && c <= 'z') {
		return true;
	} else {
		return false;
	}
}

387. 字符串中的第一个唯一字符

https://leetcode-cn.com/problems/first-unique-character-in-a-string/
给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

案例:

1
2
3
4
5
s = "leetcode"
返回 0.

s = "loveleetcode",
返回 2.

方法一 Map存储遍历

和出现次数有关的，不要犹豫，hash

此类技术方法均可用map记录出现次数并遍历的方法。本题中不同点在于遍历时使用原先数组的索引进行遍历，因为题目要求的是找到第一个不重复的字符(value=1的key)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int firstUniqChar(String s) {
  Map<Character,Integer> map = new HashMap<Character, Integer>();
	char[] chars = s.toCharArray();
	for(char ch:chars) {
		if(map.containsKey(ch)) {
			map.put(ch,map.get(ch)+1);
		}else {
			map.put(ch,1);
		}
	}
	for(int i=0;i<s.length();i++) {
		if(map.get(chars[i]) == 1) return i;//利用字符 串索引
	}
	return -1;
}

方法二 桶存储

当全是字母字符时，可以考虑用大小为26的整型数组存储每个字母的频次，索引为ch-'a', 相当于一个简化的Map，原理与Map存储相同

此处还应注意数组初始化大小之后，整型默认值均为0

1
2
3
4
5
6
7
8
9
10
public int firstUniqChar(String s) {
  int[] freq = new int[26];//初始化数组后默认值均为0,值为频次，索引为ch-'a'
  for(int i=0;i<s.length();i++) {
  	freq[s.charAt(i)-'a']++;
  }
  for(int i=0;i<s.length();i++) {
  	if(freq[s.charAt(i)-'a']==1) return i;
  }
  return -1;
}

344. 反转字符串

https://leetcode-cn.com/problems/reverse-string/
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例 1：

1
2
输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例 2：

1
2
输入：["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

两个指针自增自减，相遇退出就完事了

1
2
3
4
5
6
7
8
public void reverseString(char[] s) {
  int i=0,j=s.length-1;
	while(j>i) {
		char temp = s[i];
		s[i++] = s[j];
		s[j--] = temp;
	}
}

数组

189. 旋转数组

https://leetcode-cn.com/problems/rotate-array/

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。要求使用空间复杂度为 O(1)的原地算法。

示例 1:

1
2
3
4
5
6
输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]

示例 2:

1
2
3
4
5
输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释:
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]

方法一 暴力法

理清旋转一次的算法，再重复k次即可。时间复杂度：O(n∗k) 。每个元素都被移动 1 步O(n)） k次O(k)

注意在变换时每次都是第j位和第 j-1 位的数值进行交换，并不是直接交换数值中的值，所以此处选取了prev来存储第j-1位的数值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public void rotate(int[] nums, int k) {
		for(int i=0;i<k;i++) {
		/**
		 * 每次循环变换一次,共变换k次
		 */
			rotOnce(nums);
		}
    }

    public void rotOnce(int[] nums) {

		int prev = nums[nums.length-1];//选取一个哨兵变量用于交换
		for(int j=0;j<nums.length;j++) {//每次都是第j位和第j+1位的数值进行交换，j递增
			int temp = nums[j];
			nums[j] = prev;
			prev = temp;//prev每次都是nums[j]的前一个数值
		}
	}
}

方法二 环状替换

未看

217. 存在重复元素

https://leetcode-cn.com/problems/contains-duplicate/
给定一个整数数组，判断是否存在重复元素。

如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。
示例 1:

1
2
输入: [1,2,3,1]
输出: true

示例 2:

1
2
输入: [1,2,3,4]
输出: false

示例 3:

1
2
输入: [1,1,1,3,3,4,3,2,4,2]
输出: true

方法一 Map存储法

刚开始想用数组桶的方法来存储每个数字出现的频次，但这种方法就忽略了负数的情况，造成了数组越界，故仍要用map

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
*考虑不足的代码，弃用
*/
public boolean containsDuplicate(int[] nums) {
	int[] freq = new int[10];//没有考虑负数的情况
	for(int i=0;i<nums.length;i++) {
		freq[nums[i]]++;
	}
	for(int f:freq) {
		if(f>1) return true;
	}
	return false;
}

AC代码如下,也是常规map，和出现次数有关

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean containsDuplicate(int[] nums) {
       Map<Integer,Integer> map = new HashMap<Integer, Integer>();
		for(int num:nums) {
			if(map.containsKey(num)) {
				map.put(num,map.get(num)+1);
			}else {
				map.put(num, 1);
			}
		}

		for(Integer num:map.keySet()) {
			if(map.get(num)>1) return true;
		}
		return false;
    }
}

Boolean数组法

没看懂
TODO

283. 移动零(TODO)

https://leetcode-cn.com/problems/move-zeroes/
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

1
2
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

说明: 必须在原数组上操作，不能拷贝额外的数组

参考别人的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//思路：设置一个index，表示非0数的个数，循环遍历数组，
// 如果不是0，将非0值移动到第index位置,然后index + 1
//遍历结束之后，index值表示为非0的个数，再次遍历，从index位置后的位置此时都应该为0
public void moveZeroes(int[] nums) {
   if (nums == null || nums.length <= 1) {
       return;
   }
   int index = 0;
   for (int i = 0; i < nums.length; i++) {
       if (nums[i] != 0) {
           nums[index] = nums[i];
           index++;
       }
   }

   for (int i = index; i < nums.length; i++) {
       nums[i] = 0;
   }
}

最后补零的操作其实可以替代为 直接交换nums[index]和nums[i]，因为index所经过的数组值都是非零项。如果是0，则index没有变，直接把i+1的非0值替换过来即可。 代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
public void moveZeroes(int[] nums) {
  int index = 0;
	for (int i = 0; i < nums.length; i++) {
		if(nums[i]!=0) {
			int temp = nums[index];
			nums[index] = nums[i];
			nums[i] = temp;

			index++;

		}
	}
}

350. 两个数组的交集 II

https://leetcode-cn.com/problems/intersection-of-two-arrays-ii

给定两个数组，编写一个函数来计算它们的交集。
示例 1:

1
2
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]

示例 2:

1
2
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]

说明：
输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。可以不考虑输出结果的顺序

堆、栈、队列

链表

哈希与映射

树

排序与搜索

动态规划

图论

数学、位运算

中等题

数组

堆、栈、队列

链表

哈希与映射

树

排序与搜索

动态规划

图论

数学、位运算

0%