每日一题

面试题 10.02. 变位词组

编写一种方法，对字符串数组进行排序，将所有变位词组合在一起。变位词是指字母相同，但排列不同的字符串

示例：

1
2
3
4
5
6
7

输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

说明：

• 所有输入均为小写字母。
• 不考虑答案输出的顺序

题解：

1. 思路：计数法。

   计算每个字符串中所有字符出现的个数，将相同的放在同一个list中，完成分类

2. 代码：

   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 33 34 35 36 37 38 39 40 41 42

   public class Solution { public IList<IList<string>> GroupAnagrams(string[] strs) { IList<IList<string>> vs = new List<IList<string>>(); // 用字典储存相同的字符串 Dictionary<string, IList<string>> pairs = new Dictionary<string, IList<string>>(); // 用list储存出现过的key IList<string> keysss = new List<string>(); //循环计算所有字符串中出现字符的次数，并通过key将字符串添加到相应的pairs中，最终结果key也添加到keysss列表中 foreach(var str in strs) { string key = new string('0', 26); foreach(var val in str) { var keys = key.ToCharArray(); keys[val - 'a']++; key = new string(keys); } if (pairs.ContainsKey(key)) { pairs[key].Add(str); } else { IList<string> temp = new List<string>(); temp.Add(str); pairs.Add(key, temp); } if (!keysss.Contains(key)) { keysss.Add(key); } } //取出字典中的数据，存到list中 foreach(var key in keysss) { vs.Add(pairs[key]); } return vs; } }

1877. 数组中最大数对和的最小值

题解：

1. 分析：

   最大与最小相加产生的数对和最小，即第k大的数和第k小的数相加，所得的最大数对和最小.

   所以先将数组进行排序，然后依次下相加比较，即得出结果

2. 代码：

   1 2 3 4 5 6 7 8 9 10

   public int MinPairSum(int[] nums) { int n = nums.Length; Array.Sort(nums); int maxSum = 0; for(int i = 0; i < n/2; i++) { maxSum = Math.Max(maxSum, nums[i] + nums[n - i - 1]); } return maxSum; }

1893. 检查是否区域内所有整数都被覆盖

题解：

1. 分析：

   暴力解法，用一个 right-left+1 大小的数组来记录，直接通过二重循环，依次判断ranges中的每个[start,end]中是否包含[left,right]中的任意数字，如果包含，则对应的数组的值加一，循环完毕后再次循环判断数组中是否有0，有则为false，没有返回true。

2. 代码：

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

   public bool IsCovered(int[][] ranges, int left, int right) { int[] ltr = new int[right - left + 1]; for (int i = 0; i < ranges.Length; i++) { for (int j = ranges[i][0]; j <= ranges[i][1]; j++) { if(j <= right && j >= left) { ltr[j - left]++; } } } for (int i = 0; i < right - left + 1; i++) { if(ltr[i] == 0) { return false; } } return false; }

1743. 从相邻元素对还原数组

题解：

1. 分析：

   将数组中的数对用字典储存，则数组头或尾中字典的list的长度只有1，然后在通过字典，一次查找下一个

2. 代码：

   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 33 34 35 36 37 38 39

   public int[] RestoreArray(int[][] adjacentPairs) { Dictionary<int, List<int>> pairs = new Dictionary<int, List<int>>(); foreach(int[] pair in adjacentPairs) { if (!pairs.ContainsKey(pair[0])) { pairs.Add(pair[0], new List<int>()); } if (!pairs.ContainsKey(pair[1])) { pairs.Add(pair[1], new List<int>()); } pairs[pair[0]].Add(pair[1]); pairs[pair[1]].Add(pair[0]); } int n = adjacentPairs.Length + 1; int[] nums = new int[n]; foreach(var pair in pairs) { int key = pair.Key; if(pair.Value.Count == 1) { nums[0] = key; break; } } nums[1] = pairs[nums[0]][0]; for (int i = 2; i < n; i++) { List<int> vs = pairs[nums[i - 1]]; nums[i] = nums[i - 2] == vs[0] ? vs[1] : vs[0]; } return nums; } }

704. 二分查找 2021/9/7

题解：

1. 分析：

   经典二分题，将数组分成两个部分，通过判断中间数字和目标数字的大小比较，然后进入目标数字存在的部分再次进行二分查找

   在进行中间下标的计算时，若直接用 (left + right)/2 会导致一些特殊情况出现问题，所以使用 (right - left)/2 + left， 或直接使用位移运算 left + right >> 1。

2. 代码：

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

   public int Search(int[] nums, int target) { int left = 0; int right = nums.Length - 1; while(left <= right) { int middle = left + right >> 1; if (nums[middle] == target) return middle; else if (nums[middle] < target) left = middle + 1 ; else right = middle - 1; } return -1; }

470. 用 Rand7() 实现 Rand10() 2021/9/6

题解：

1. 分析：

   Rand7() 有 1~7 共7种数字，49种情况，所以从1-10依次分布如下

   ​

2. 代码：

   1 2 3 4 5 6 7 8 9 10 11

   public int Rand10() { int ra = Rand7(); int rb = Rand7(); int idx; do{ ra = Rand7(); rb = Rand7(); idx = ra + (rb - 1) * 7; }while(idx > 40); return (idx) % 10 + 1; }

1221. 分割平衡字符串 2021/9/7

题解：

1. 分析：

   循环计算字符串中的L和R的字符个数，当两个个数相等时就表示出现一个平衡字符串，则计数器加一。

1. 代码：

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

   public int BalancedStringSplit(string s) { int i = 0; int len = s.Length; int L = 0, R = 0, sum = 0; while(i < len) { if (s[i].Equals('L')) L++; else R++; if (L == R) { L = 0; R = 0; sum++; } i++; } return sum; }

678. 有效的括号字符串 2021/9/12

题解：

1. 分析：

   • 堆栈法：

     对字符串s逐个字符进行判断，有如下三种情况

     • 如果字符是左括号，则将其下标压入左括号栈
     • 如果字符是星号，则将其下表压入星号栈
     • 如果字符是右括号，则
       • 如果左括号栈中元素不为空，则将左括号栈中顶部元素出栈
       • 如果左括号栈中元素为空，星号栈中元素不为空，则将星号栈中顶部元素出栈
       • 如果两个栈中元素都为空，则此右括号无匹配元素，返回false
     • 字符串遍历完后，如果两个栈中元素都不为空，则依次将两个栈中的栈顶元素出栈，然后比较两个元素的大小，如果左括号栈的出栈下标比星号栈的出栈下标大，则表示左括号在星号的后面，无法匹配，返回false
     • 最后判断左括号栈中的所有元素是否全部出栈，即所有左括号均有匹配，则返回true（星号可以为空字符，所以星号栈不需要做判断）

   • 动态规划：

   • 贪心：

1. 代码：

   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

   public bool CheckValidString(string s) { int length = s.Length; Stack<int> left = new Stack<int>(); Stack<int> aster = new Stack<int>(); int i = 0; while(i < length) { if (s[i].Equals('(')) left.Push(i); else if (s[i].Equals('*')) aster.Push(i); else { if (left.Count > 0) left.Pop(); else if (aster.Count > 0) aster.Pop(); else return false; } i++; } while(left.Count > 0 && aster.Count > 0) { int leftIndex = left.Pop(); int asterIndex = aster.Pop(); if (leftIndex > asterIndex) return false; } return left.Count == 0; }

447. 回旋镖的数量 2021/9/12

题解：

1. 分析：

   • 直接三重循环依次判断三个点是否组成等边三角形，然后返回值。（严重超时）

   • 一个回旋镖可以看作三个点组成的一个等边三角形，所以要判断是否可以放置回旋镖即判断是否可以组成等边三角形，即找到两个点到同一个点的距离相同。每多一个点到顶点的距离相同，就会多两个可摆放的回旋镖（存在位置差异，n>=2），即为n的排列组合。

     An = n * (n - 1)

     所以我们可以采用枚举的方法，依次判断所有点到其他点的距离，并用字典储存,再在最后进行判断。

2. 代码：

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

   public static int NumberOfBoomerangs(int[][] points) { //三重循环直接超时 int sum = 0; foreach(int[] p in points) { Dictionary<int, int> cnt = new Dictionary<int, int>(); foreach(int[] q in points) { int dis = (p[1] - q[1]) * (p[1] - q[1]) + (p[0] - q[0]) * (p[0] - q[0]); if (!cnt.ContainsKey(dis)) cnt.Add(dis, 1); else cnt[dis]++; } foreach(KeyValuePair<int, int> pair in cnt) { int m = pair.Value; sum += m * (m - 1); } } return sum; }

524. 通过删除字母匹配到字典里最长单词 2021/9/14

题解：

1. 分析：

   题目描述不清楚，应为在第二个参数dictionary中找到最长的s的，且相同长度下字典序靠前的子字符串。

   所以先将字典中的字符串按长度和字典序进行排序，然后依次判断是否为s的子串。

   排序时需要先将 IList 转化为 List var list = new List(dictionary);

   然后使用List的Sort方法

   1 2 3 4 5 6 7 8

   list.Sort((x, y) => { if(x.Length == y.Length) { return x.CompareTo(y); } return y.Length.CompareTo(x.Length); });

1. 代码：

   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

   public string FindLongestWord(string s, IList<string> dictionary) { var list = new List<string>(dictionary); list.Sort((x, y) => { if(x.Length == y.Length) { return x.CompareTo(y); } return y.Length.CompareTo(x.Length); }); foreach (string str in list) { int i = 0, j = 0; while (i < str.Length && j < s.Length) { if (str[i] == s[j]) i++; j++; } if (i == str.Length) return str; } return ""; }

162. 寻找峰值 2021/9/15

题解：

1. 分析：

   该题需要时间复杂度为O(log n)，所以直接循环查找行不通。

   因此需要使用二分法进行查找。

   在二分查找时有四种情况

   • nums[mid - 1] < nums[mid] < nums[mid + 1]，此时右边一定存在一个峰值
   • nums[mid - 1] > nums[mid] > nums[mid + 1]，此时左边一定存在一个峰值
   • nums[mid - 1] > nums[mid] < nums[mid + 1]，此时左边和右边都存在峰值
   • nums[mid - 1] < nums[mid] > nums[mid + 1]，此时mid 本生就为一个峰值

   对上述四种情况进行优化，可以分为两种情况，峰值在左边（右边）和峰值在右边（左边）和中间

2. 代码：

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

   public int FindPeakElement(int[] nums) { int n = nums.Length; int mid; int l = 0, r = n - 1; while(l < r) { mid = l + (r - l) / 2; if(nums[mid] < nums[mid + 1]) { l = mid + 1; } else { r = mid; } } return l; }