01.01判断字符串是否唯一

面试题 01.01. 判定字符是否唯一 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

解法一： 使用map

这个方法虽然很简单，但是面试不推荐的话不推荐使用这个方法

func isUnique(astr string) bool {
   // 使用map暂存
   unique:=make(map[int32]bool)
   for _,v:=range astr{
      if unique[v] {
         return false
      }
      unique[v] = true
   }
   return true
}

解法二： bool数组

因为这个题目的范围已经定死了，在a-z这个范围内，所以我们可以使用一个bool数组来存储，当然了，这方法也不是很推荐

func isUnique(astr string) bool {
   unique:=make([]bool,26)
   for i := 0; i < len(astr); i++ {
      if unique[astr[i]-'a'] {
         return false
      }
      unique[astr[i]-'a'] = true
   }
   return true
}

解法三：位运算

我们使用bool数组还是太浪费了，为了最大化的压缩空间，我们可以使用一个bit来表示。因为题目里的范围在0-26，所以我们可以使用int类型，int类型是4个字节，4*8=32位。

但是这个有个难点，那就是怎么判断这个字符是否出现了呢，可以使用与运算来判断重复，用或运算来进行赋值

go代码如下：

func isUnique(astr string) bool {
   mask:=0
   for i := 0; i < len(astr); i++ {
      bitMove:=astr[i]-'a'
      if mask & (1<<bitMove) != 0 {
         return false
      } else {
         mask|=1<<bitMove
      }
   }
   return true
}

java代码如下：

public boolean isUnique(String astr) {
    int mask = 0;
    byte[] data= astr.getBytes();
    for(byte a:data){
        int bitMove = a-'a';
        if ( (mask & (1<<bitMove)) != 0 ){
            return false;
        } else {
            mask |= 1<<bitMove;
        }
    }
    return true;
}

01.02 判定是否为字符重排

面试题 01.02. 判定是否互为字符重排 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

解法一： 字符统计

我们使用一个数组来存储每个字母出现的次数，当然也可以使用map（但是更推荐用数组）

func CheckPermutation(s1 string, s2 string) bool {
   // 使用data来存储数据
   data:=make([]int,26)
   // 首先遍历s1，统计一下
   for _,v:=range s1{
      data[v-'a']++
   }
   // 然后遍历s2，每个字符减1
   for _,v:=range s2{
      data[v-'a']--
   }
   // 最后我们遍历数据表，如果不为0直接返回false
   for _,v:=range data{
      if v != 0 {
         return false
      }
   }
   return true
}

解法二：使用字符串处理函数来进行处理

这个思路也很简单，我们可以先对字符串进行分割，然后我们简单进行排序，最后再拼接字符串，如果结果相等，那么我们就返回真

func CheckPermutation(s1 string, s2 string) bool {
	if len(s1) != len(s2) {
		return false
	}
	tmp1:=strings.Split(s1,"")
	tmp2:=strings.Split(s2,"")
	sort.Strings(tmp1)
	sort.Strings(tmp2)
	return strings.Join(tmp1,"") == strings.Join(tmp2,"")
}

01.03URL化

面试题 01.03. URL化 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

解法一：字符串替换

这个是能想到最简单的方法了，我们直接使用Go的strings包来进行字符串替换。注意我们这里需要注意一下字符串的长度，不能直接替换。

func replaceSpaces(S string, length int) string {
	return strings.Replace(S[:length]," ","%20",-1)
}

解法二：按照题意直接替换

我们使用两个指针来进行替换操作，

func replaceSpaces(S string, length int) string {
   // 先把S转换为字符数组
   data := []rune(S)
   // 使用两个指针
   i := length - 1
   j := len(S)-1
   for i>=0 {
      // 如果i位置为空格，那么我们就替换为02%
      if data[i] == ' ' {
         data[j] = '0';j--
         data[j] = '2';j--
         data[j] = '%';j--
      } else {
         data[j] = data[i];j--
      }
      i--
   }
   // 截取字符串
   return string(data[j+1:])
}

01.03回文排列

说一下这题的核心思想，其实我们只需要判断字符串里相同的字符串个数里，奇数只能有一个，偶数可以有多个

解法一：使用map来实现

func canPermutePalindrome(s string) bool {
   // 创建一个map来暂存数据
   tmp:=make(map[rune]bool)
   // 遍历字符串
   for    _,c:=range s{
      // 判断字符串是否存在，如果存在我们就删除，不存在我们就添加
      if tmp[c] {
         delete(tmp,c)
      } else {
         tmp[c] = true
      }
   }
   // 最后我们要确保奇数个数只能为1
   return len(tmp) <= 1
}

解法二：位运算

上面那个map还是优点浪费零空间，这里我们使用位运算来压缩空间。这个解法非常巧妙，使用位运算，把所有的数据信息全部存入到我们的result数组中。

func canPermutePalindrome(s string) bool {
   // 我们使用result数组来存储最终结果
   var result [4]int
   // 遍历字符串s来把我们的值放入到这个数组中
   for _, v := range s {
      atoi := int(v)
      // 这里的作用就是使用异或运算，相同置0，不同置1
      result[atoi/32] ^= 1 << (atoi % 32)
   }

   var cnt int

   for i := 0; i < 4; i ++ {
      // 判断result[i]这部分位数是否只有一个bit为1
      if (result[i] & -result[i]) == result[i] {
         if result[i] != 0 {
            cnt ++
         }
      } else { // 如果这段bit不止一个1, 直接判断false
         return false
      }
   }

   // 只有一个置位或者没有则是回文字符串
   return cnt <= 1
}