一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 756|回复: 13
收起左侧

[CareerCup] 一个软件测试的刷题记录

[复制链接] |试试Instant~ |关注本帖
davidsuger 发表于 2015-9-1 14:21:11 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 davidsuger 于 2015-9-1 16:38 编辑

想换工作了,之前上学就没学过算法和数据结构,后来自己看了下书,然后一直在外企混(混了太久),之前换工作也拿过百度的offer,(基本没考算法,哈哈)性价比不高选的别家。现在打算准备一下试试看能不能找个国外的工作,到国外混混,看来以前偷的懒还是得还。为什么从CareerCup开始,个人这个比较有条理,分类也比较好,解答也清楚。现在开始刷CareerCup!加油
欢迎大家来讨论,指导。


补充内容 (2015-9-2 11:14):
帖子不能编辑了,有点麻烦。
 楼主| davidsuger 发表于 2015-9-1 15:33:07 | 显示全部楼层
本帖最后由 davidsuger 于 2015-9-1 16:33 编辑

1.1 Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?
怎么判断一个字符串所有的字符都是唯一的。不使用其他数据结构帮助。
我的思路:
1. 如果用别的数据结构帮忙。用hashmap,字符串走一遍,以字符作为key,字符出现的次数作为value,如果有value大于1了就说明字符串的字符不唯一。
2. 不用其他数据结构。char 是2 bytes
相关知识: ASCII String 和 Unicode string:
在查。。。
“字节”是byte,“位”是bit ; 1 byte = 8 bit ;char 在java中是2个字节。java采用unicode,2个字节(16位)来表示一个字符。 2字节无符号,范围 \u0000 to \uFFFF, 0-65535。可以存放中文。
java基本类型(内置类型)取值范围
例1:
  • public class PrimitiveTypeTest {   
  •     public static void main(String[] args) {   
  •         // byte   
  •         System.out.println("基本类型:byte 二进制位数:" + Byte.SIZE);   
  •         System.out.println("包装类:java.lang.Byte");   
  •         System.out.println("最小值:Byte.MIN_VALUE=" + Byte.MIN_VALUE);   
  •         System.out.println("最大值:Byte.MAX_VALUE=" + Byte.MAX_VALUE);   

运行结果:
  • 基本类型:byte 二进制位数:8
  • 包装类:java.lang.Byte
  • 最小值:Byte.MIN_VALUE=-128
  • 最大值:Byte.MAX_VALUE=127
  • 补充基本类型:short 二进制位数:16
  • 包装类:java.lang.Short
  • 最小值:Short.MIN_VALUE=-32768
  • 最大值:Short.MAX_VALUE=32767
  • 基本类型:int 二进制位数:32
  • 包装类:java.lang.Integer
  • 最小值:Integer.MIN_VALUE=-2147483648
  • 最大值:Integer.MAX_VALUE=2147483647
  • 基本类型:long 二进制位数:64
  • 包装类:java.lang.Long
  • 最小值:Long.MIN_VALUE=-9223372036854775808
  • 最大值:Long.MAX_VALUE=9223372036854775807
  • 基本类型:float 二进制位数:32
  • 包装类:java.lang.Float
  • 最小值:Float.MIN_VALUE=1.4E-45
  • 最大值:Float.MAX_VALUE=3.4028235E38
  • 基本类型:double 二进制位数:64
  • 包装类:java.lang.Double
  • 最小值:Double.MIN_VALUE=4.9E-324
  • 最大值:Double.MAX_VALUE=1.7976931348623157E308
  • 基本类型:char 二进制位数:16
  • 包装类:java.lang.Character
  • 最小值:Character.MIN_VALUE=0
  • 最大值:Character.MAX_VALUE=65535

解答1:



补充内容 (2015-9-2 11:27):
补充 ASCII String 和 Unicode string的知识:
ASCII 字符用8位来表示,只有256个。
Unicode 有16位, 有65535个。
char 类型是16位,可以有65535个。
回复 支持 反对

使用道具 举报

 楼主| davidsuger 发表于 2015-9-2 12:13:50 | 显示全部楼层
解答1:
        // 思路,使用hashset,存入字符串的每个字符,遍历一遍字符串,set里不存在就放进去,存在的话字符串的字符就是有相同的。
        public static boolean isUniqueChar1(String str) {
                Set<Character> set = new HashSet<>();

                // 检查输入是不是null,是的话就返回false
                if (str == null) {
                        return false;
                }
                for (int i = 0; i < str.length(); i++) {
                        if (set.contains(str.charAt(i))) {
                                return false;
                        } else {
                                set.add(str.charAt(i));
                        }
                }

                return true;

        }

        // 思路,使用hashmap,用字符串的每个字符作为key,遍历一遍字符串,字符在map里不存在就加进去,已经存在就返回false
        public static boolean isUniqueChar11(String str) {
                Map<Character, Integer> map = new HashMap<>();

                // 检查输入是不是null,是的话就返回false
                if (str == null) {
                        return false;
                }
                for (int i = 0; i < str.length(); i++) {
                        if (map.containsKey(str.charAt(i))) {
                                return false;
                        } else {
                                map.put(str.charAt(i), 1);
                        }
                }

                return true;

        }
回复 支持 反对

使用道具 举报

 楼主| davidsuger 发表于 2015-9-2 12:24:44 | 显示全部楼层
解法2: 不使用额外数据结构。

        // 先问问面试官是ASCII字符串还是Unicode字符串,因为不同的字符串程序使用的空间大小不一样。这里假设输入是ASCII字符串
        public static boolean isUniqueChar2(String str) {

                // 检查输入是不是null,是的话就返回false
                // ASCII字符用8位表示,只有256个,如果输入大于256,肯定就不是都不相同的了。
                if (str == null || str.length() > 256) {
                        return false;
                }

                char[] chars = new char[256];
                for (int i = 0; i < str.length(); i++) {
                        chars[str.charAt(i)]++;
                        if (chars[str.charAt(i)] > 1) {
                                return false;
                        }
                }

                return true;

        }
回复 支持 反对

使用道具 举报

 楼主| davidsuger 发表于 2015-9-2 12:49:45 | 显示全部楼层
本帖最后由 davidsuger 于 2015-9-2 13:33 编辑

1.2 Implement a function void reverse(char* str) in C or C++ which reverses a null-terminated string. 反转一个以null结尾的字符串。
用Java解吧,C++已经九霄云外了。遍历到中间位置,第一个和最后一个交换,第二个和第倒数第二个交换,以此类推。

        public static String reverseString(String str) {
                // 检查 输入
                if (str == null) {
                        return null;
                }

                char[] chars = str.toCharArray();
                for (int i = 0; i < chars.length / 2; i++) {
                        char temp = chars;
                        chars = chars[chars.length - i - 1];
                        chars[chars.length - i - 1] = temp;
                }

                return String.valueOf(chars);
        }
回复 支持 反对

使用道具 举报

 楼主| davidsuger 发表于 2015-9-2 13:21:14 | 显示全部楼层
1.3 Given two strings, write a method to decide if one is a permutation of the other. 给定两个字符串,确定其中一个字符串的字符重新排列后,能否变成另一个字符串。
解法:满足条件的话,1. 两个长度肯定要相等,2. 每个字符出现的次数也应该一样。

解法1:
                // 满足条件的字符串重新排序后应该相等
        public static boolean twoStringsAreAnagrams(String str1, String str2) {

                //检查输入
                if (str1 == null || str2 == null || str1.length() != str2.length()) {
                        return false;
                }

                String newStr1 = sortString(str1);
                String newStr2 = sortString(str2);
                if (newStr1.equals(newStr2)) {
                        return true;
                } else {
                        return false;
                }
        }

        public static String sortString(String str) {
                char[] charArray = str.toCharArray();
                java.util.Arrays.sort(charArray);

                return String.valueOf(charArray);
        }
回复 支持 反对

使用道具 举报

 楼主| davidsuger 发表于 2015-9-2 13:56:06 | 显示全部楼层
解法2:
        //遍历一遍第一个字符串,以字符为key,字符出现次数为value,然后遍历一遍另外一个字符串,将对应字符出现次数减1,如果有map里没有的返回false,出现次数小于0返回false
        public static boolean twoStringsAreAnagrams2(String str1, String str2) {
                if (str1 == null || str2 == null || str1.length() != str2.length()) {
                        return false;
                }

                Map<Character, Integer> map = new HashMap<>();

                for (int i = 0; i < str1.length(); i++) {
                        if (map.containsKey(str1.charAt(i))) {
                                map.put(str1.charAt(i), map.get(str1.charAt(i)) + 1);
                        } else {
                                map.put(str1.charAt(i), 1);
                        }
                }

                for (int i = 0; i < str2.length(); i++) {
                        if (map.containsKey(str2.charAt(i))) {
                                map.put(str2.charAt(i), map.get(str2.charAt(i)) - 1);
                                if (map.get(str2.charAt(i)) < 0) {
                                        return false;
                                }
                        } else {
                                return false;
                        }
                }

                return true;

        }
回复 支持 反对

使用道具 举报

 楼主| davidsuger 发表于 2015-9-2 14:01:01 | 显示全部楼层
本帖最后由 davidsuger 于 2015-9-2 14:21 编辑

解法3: 同理        public static boolean twoStringsAreAnagrams3(String str1, String str2) {
                if (str1 == null || str2 == null || str1.length() != str2.length()) {
                        return false;
                }

                int[] chars = new int[256];

                for (int i = 0; i < str1.length(); i++) {
                        chars[str1.charAt(i)]++;
                }
                for (int i = 0; i < str2.length(); i++) {
                        chars[str2.charAt(i)]--;
                        if (chars[str2.charAt(i)] < 0) {
                                return false;
                        }
                }
                return true;
        }

回复 支持 反对

使用道具 举报

 楼主| davidsuger 发表于 2015-9-2 14:21:42 | 显示全部楼层
本帖最后由 davidsuger 于 2015-9-2 15:37 编辑

1.4 Write a method to replace all spaces in a string with'%20'. You may assume that the string has sufficient space at the end of the string to hold the additional characters, and that you are given the "true" length of the string. (Note: if implementing in Java, please use a character array so that you can perform this operation in place.)
EXAMPLE
Input: "Mr John Smith
Output: "Mr%20Dohn%20Smith"
将字符串的空格全部替换为%20,如果用java,用字符数组做,直接在数组上操作。解法1: 实际工作中我肯定用StringBuilder,方便。
        public static String replaceBlank(char[] string, int length) {
                if (string==null) {
                        return null;
                }
               
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < string.length; i++) {
                        if (string != ' ') {
                              sb.append(string);
                        } else {
                                sb.append("%20");
                        }
                }
                return sb.toString();
        }


解法2: 转换的数组最大是之前的3倍(不用计算遍历字符串算新数组的大小了,最后的string要trim())。然后从前面的向后遍历字符串,用index记录新数组的下标,逐个拷贝。
        public static String replaceBlank2(char[] string, int length) {
                if (string == null) {
                        return null;
                }

                int index = 0;
                char[] newString = new char[3 * length];
                for (int i = 0; i < string.length; i++) {
                        if (string != ' ') {
                                newString[index] = string;
                        } else {
                                newString[index] = '%';
                                index++;
                                newString[index] = '2';
                                index++;
                                newString[index] = '0';
                        }
                        index++;
                }
                return String.valueOf(newString).trim();
        }

解法3: 先算出需要多大的数组,然后从后遍历字符串,逐个拷贝。
public static String replaceBlank3(char[] string, int length) {
                if (string==null) {
                        return null;
                }
               
                int newLength = 0;
                for (int i = 0; i < string.length; i++) {
                        if (string != ' ') {
                                newLength++;
                        } else {
                                newLength += 3;
                        }
                }

                char[] newString = new char[newLength];
                int index = newLength - 1;
                for (int i = string.length - 1; i >= 0; i--) {
                        if (string != ' ') {
                                newString[index] = string;
                        } else {
                                newString[index] = '0';
                                index--;
                                newString[index] = '2';
                                index--;
                                newString[index] = '%';
                        }
                        index--;
                }
                return String.valueOf(newString);

        }

回复 支持 反对

使用道具 举报

 楼主| davidsuger 发表于 2015-9-2 16:51:10 | 显示全部楼层
1.5 Implement a method to perform basic string compression using the counts of repeated characters. For example, the string aabcccccaaa would become a2blc5a3. If the "compressed" string would not become smaller than the original string, your method should return the original string.
利用字符重复出现的次数,实现一个压缩算法。如果没有缩小返回原来的字符串。

解法1: 用StringBuilder。
public static String compressString1(String str) {
                if (str == null) {
                        return null;
                }
                StringBuilder sb = new StringBuilder();
                char current = str.charAt(0);
                int count = 0;

                for (int i = 0; i < str.length(); i++) {
                        if (str.charAt(i) == current) {
                                count++;
                        } else {
                                sb.append(current);
                                sb.append(count);
                                current = str.charAt(i);
                                count = 1;
                        }
                }
                sb.append(current);
                sb.append(count);

                if (sb.toString().length() < str.length()) {
                        return sb.toString();
                } else {
                        return str;
                }
        }
回复 支持 反对

使用道具 举报

 楼主| davidsuger 发表于 2015-9-3 08:06:06 | 显示全部楼层
本帖最后由 davidsuger 于 2015-9-3 08:15 编辑

解法2:
//先算出转换后的长度,建一个新数组,然后再转换
        public static String compressString2(String str) {
                if (str == null) {
                        return null;
                }
                if (str.isEmpty()) {
                        return str;
                }

                int newLenth = countCompression(str);
                if (newLenth > str.length()) {
                        return str;
                }

                char[] newStr = new char[newLenth];
                int index = 0;
                char current = str.charAt(0);
                int count = 0;
                for (int i = 0; i < str.length(); i++) {
                        if (str.charAt(i) == current) {
                                count++;
                        } else {
                                newStr[index] = current;
                                // 把数量变成字符加在新字符串后面
                                char[] countCharArray = String.valueOf(count).toCharArray();
                                for (int j = 0; j < countCharArray.length; j++) {
                                        index++;
                                        newStr[index] = countCharArray[j];
                                }
                                index++;
                                current = str.charAt(i);
                                count = 1;
                        }
                }
               
                //放最后一组
                newStr[index] = current;
                // 把数量变成字符加在新字符串后面
                char[] countCharArray = String.valueOf(count).toCharArray();
                for (int j = 0; j < countCharArray.length; j++) {
                        index++;
                        newStr[index] = countCharArray[j];
                }

                return String.valueOf(newStr);

        }
        //算转换后的字符串长度
        public static int countCompression(String str) {
                if (str == null || str.isEmpty()) {
                        return 0;
                }

                int length = 0;
                int count = 0;
                char current = str.charAt(0);
                for (int i = 0; i < str.length(); i++) {
                        if (str.charAt(i) == current) {
                                count++;
                        } else {
                                length += 1 + String.valueOf(count).length();
                                current = str.charAt(i);
                                count = 1;
                        }
                }
                length += 1 + String.valueOf(count).length();
                return length;
        }
回复 支持 反对

使用道具 举报

 楼主| davidsuger 发表于 2015-9-3 08:16:04 | 显示全部楼层
解法3:
//最坏的情况就是转换后的长度增加一倍,建一个两倍长度的数组,然后再转换,然后trim()
                public static String compressString3(String str) {
                        if (str == null) {
                                return null;
                        }
                        if (str.isEmpty()) {
                                return str;
                        }

                        char[] newStr = new char[2*str.length()];
                        int index = 0;
                        char current = str.charAt(0);
                        int count = 0;
                        for (int i = 0; i < str.length(); i++) {
                                if (str.charAt(i) == current) {
                                        count++;
                                } else {
                                        newStr[index] = current;
                                        // 把数量变成字符加在新字符串后面
                                        char[] countCharArray = String.valueOf(count).toCharArray();
                                        for (int j = 0; j < countCharArray.length; j++) {
                                                index++;
                                                newStr[index] = countCharArray[j];
                                        }
                                        index++;
                                        current = str.charAt(i);
                                        count = 1;
                                }
                        }
                       
                        //放最后一组
                        newStr[index] = current;
                        // 把数量变成字符加在新字符串后面
                        char[] countCharArray = String.valueOf(count).toCharArray();
                        for (int j = 0; j < countCharArray.length; j++) {
                                index++;
                                newStr[index] = countCharArray[j];
                        }

                        return String.valueOf(newStr).trim();

                }
回复 支持 反对

使用道具 举报

 楼主| davidsuger 发表于 2015-9-3 08:43:46 | 显示全部楼层
1.6 Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?
给定一幅由NxN矩阵表示的图像,其中每个像素的大小为4字节,编写一个方法,将图像旋转90度。不占用额外内存空间能否做到?
回复 支持 反对

使用道具 举报

 楼主| davidsuger 发表于 2015-9-3 09:19:18 | 显示全部楼层
解法1:
        // 先每行左右翻转,然后对角线翻转
        public static void rotate(int[][] matrix) {
                for (int i = 0; i < matrix.length; i++) {
                        for (int j = 0; j < matrix[i].length / 2; j++) {
                                int temp = matrix[i][j];
                                matrix[i][j] = matrix[i][matrix[i].length - j - 1];
                                matrix[i][matrix[i].length - j - 1] = temp;
                        }
                }
                for (int i = 0; i < matrix.length; i++) {
                        for (int j = 0; j < matrix[i].length - i; j++) {
                                int temp = matrix[i][j];
                                matrix[i][j] = matrix[matrix.length - j - 1][matrix[i].length - i
                                                - 1];
                                matrix[matrix.length - j - 1][matrix[i].length - i - 1] = temp;
                        }
                }
        }
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 10:06

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表