资讯专栏INFORMATION COLUMN

[LintCode/LeetCode] First Unique Character in a S

Xufc / 3367人阅读

Problem

Given a string, find the first non-repeating character in it and return it"s index. If it doesn"t exist, return -1.

Example

Given s = "lintcode", return 0.

Given s = "lovelintcode", return 2.

Tags

Amazon Microsoft Bloomberg

Solution
a fast way
class Solution {
    public int firstUniqChar(String s) {
        int[] dict = new int[26];
        for (int i = 0; i < s.length(); i++) {
            dict[s.charAt(i)-"a"]++;
        }
        for (int i = 0; i < s.length(); i++) {
            if (dict[s.charAt(i)-"a"] == 1) return i;
        }
        return -1;
    }
}
a dumb way...
public class Solution {
    public int firstUniqChar(String s) {
        //store string in an array
        char[] str = s.toCharArray();
        //use HashMap to check each character"s frequency
        Map map = new HashMap<>();
        for (int i = 0; i < str.length; i++) {
            char ch = str[i];
            //reset duplicate chars to "#"
            if (map.containsKey(ch)) {
                str[map.get(ch)] = "#";
                str[i] = "#";
            } else {
                map.put(ch, i);
            }
        }
        int index = str.length;
        for (int i = 0; i < str.length; i++) {
            //find the first character that is not "#" and return its index
            if (str[i] != "#") {
                return i;
            }
        }
        //if no unique character, return -1
        return -1;
    }
}

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/68097.html

相关文章

  • [LintCode/LeetCode] Unique Paths II

    摘要:和完全一样的做法,只要在初始化首行和首列遇到时置零且即可。对了,数组其它元素遇到也要置零喏,不过就不要啦。 Problem Follow up for Unique Paths: Now consider if some obstacles are added to the grids. How many unique paths would there be? An obstacle...

    firim 评论0 收藏0
  • [LintCode/LeetCode] Minimum Window Substring

    Problem Given a string source and a string target, find the minimum window in source which will contain all the characters in target. Notice If there is no such window in source that covers all charac...

    Corwien 评论0 收藏0
  • [LintCode/LeetCode] 3Sum

    摘要:双指针法的解法。然后用和夹逼找到使三数和为零的三数数列,放入结果数组。对于这三个数,如果循环的下一个数值和当前数值相等,就跳过以避免中有相同的解。 Problem Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplet...

    Sunxb 评论0 收藏0
  • [LintCode/LeetCode] Unique Paths

    摘要:简单的动规题目,建立数组。坐标为矩阵的坐标,值为从左上角到这一格的走法总数。赋初值,最上一行和最左列的所有格子的走法都只有一种,其余格子的走法等于其左边格子走法与上方格子走法之和。最后,返回即可。 Problem A robot is located at the top-left corner of a m x n grid (marked Start in the diagram ...

    Gu_Yan 评论0 收藏0
  • [LintCode/LeetCode] Two Strings are Anagrams/Valid

    摘要:建立一个长度为的数组,统计所有个字符在出现的次数,然后减去这些字符在中出现的次数。否则,循环结束,说明所有字符在和中出现的次数一致,返回。 Program Write a method anagram(s,t) to decide if two strings are anagrams or not. Example Given s=abcd, t=dcab, return true....

    vslam 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<