lc题目总结

Easy

205. 同构字符串

• 使用嵌套数组同样可以实现map映射

  67. 二进制求和

Integer.toBinaryString(Integer.parseInt(a, 2) + Integer.parseInt(b, 2));

a，b为字符串二进制，toBinaryString可以直接讲int转化为二进制字符串形式，但数据量太大时，应该使用位移计算

public String addBinary(String a, String b) {
    StringBuilder ans = new StringBuilder();
    int ca = 0;
    for(int i = a.length() - 1, j = b.length() - 1;i >= 0 || j >= 0; i--, j--) {
        int sum = ca;
        sum += i >= 0 ? a.charAt(i) - '0' : 0;
        sum += j >= 0 ? b.charAt(j) - '0' : 0;
        ans.append(sum % 2);
        ca = sum / 2;// 进位
    }
    ans.append(ca == 1 ? ca : "");
    return ans.reverse().toString();
}

Mid

179. 最大数

• fast

public String largestNumber(int[] nums) {
        String[] numstr = new String[nums.length];
        for(int i=0;i<nums.length;i++){
            numstr[i] = String.valueOf(nums[i]);
        }
        quickSort(numstr,0,nums.length-1);
        // System.out.println(Arrays.toString(numstr));
        StringBuffer sb = new StringBuffer();
        if(numstr[0].charAt(0)=='0'){
            return "0";
        }
        for(String num:numstr){
            sb.append(num);
        }
        return sb.toString();
    }
    int compare(String a,String b){
        int l1 = a.length();
        int l2 = b.length();
        int l = l1+l2;
        int i=0;
        for(;i<l;i++){
            char ac = a.charAt(i%l1);
            char bc = b.charAt(i%l2);
            if(ac==bc){
                continue;
            }
            return ac-bc;
        }
        return 0;
        // System.out.println("a:"+a+",b:"+b+",cp:"+cp);
        // return cp;
    }
    void quickSort(String[] nums,int start,int end){
        if(start>=end){
            return;
        }
        int index = getIndex(nums,start,end);
        quickSort(nums,start,index-1);
        quickSort(nums,index+1,end);
    }
    int getIndex(String[]nums,int low,int high){
        String tmp = nums[low];
        while(low<high){
            while(low<high&&compare(nums[high],tmp)<=0){
                high--;
            }
            nums[low] = nums[high];
            while(low<high&&compare(nums[low],tmp)>=0){
                low++;
            }
            nums[high] = nums[low];
        }
        nums[low] = tmp;
        return low;
    }

• mine

public String largestNumber(int[] nums) {
    String[] ans = new String[nums.length];
    for (int i = 0; i < nums.length; i++) ans[i] = String.valueOf(nums[i]);
    Arrays.sort(ans, new NumComparator());
    StringBuffer sb = new StringBuffer();
    if (ans[0].charAt(0) == '0') {
        return "0";
    }
    for (String num : ans) {
        sb.append(num);
    }
    return sb.toString();
}


public class NumComparator implements Comparator<String> {
    @Override
    public int compare(String o1, String o2) {
        int l1 = o1.length();
        int l2 = o2.length();
        int l = l1 + l2;
        int i = 0;
        for (; i < l; i++) {
            char ac = o1.charAt(i % l1);
            char bc = o2.charAt(i % l2);
            if (ac == bc) {
                continue;
            }
            return  bc - ac;
        }
        return 0;
    }
}

• lambda

public String largestNumber(int[] nums) {
    String result = IntStream.of(nums).mapToObj(String::valueOf).sorted(((o1, o2) -> (o2 + o1).compareTo(o1 + o2))).collect(Collectors.joining());
    return result.startsWith("0") ? "0" : result;
}

面试题57 - II. 和为s的连续正数序列-滑动窗口

138. 复制带随机指针的链表-空间的迭代

Hard