Leetcode-389-390

Posted by Jerry on November 28, 2017

Leetcoode Weekly Contest 2总共有三道题

题目389 Find the Difference

问题描述

Given two strings s and t which consist of only lowercase letters.

String t is generated by random shuffling string s and then add one more letter at a random position.

Find the letter that was added in t.

Example:

Input:
s = "abcd"
t = "abcde"

Output:
e

Explanation:
'e' is the letter that was added.

解题思路

给定两个字符串s,t只包括小写字母,t是字符串s的字符重排而且在随机的位置上还多了一个字母,要求找到该字母。

  • 方法一 第一反应就是用两个for循环,外层为s字符串,内层在t中寻找,找到的话将其替换成字符A(原字符串全是小写字母,所以不存在大写字符。然后再遍历一遍t,如果不为A字符则该字符为所求字符。
  • 方法二 hash表原理,统计两个字符串中每个字符个数,然后找出两个字符串哈希表的不同,返回那个不同的字符即可。
  • 方法三这是我在写这个文章的时候想出来的)将两个字符串中所有字符转换为整数相加,最后将总数相减即为所求字符(在Leetcode上能通过,好开心),这应该是最简单的方法吧。

    代码

方法一


方法二

public char findTheDifference(String s, String t) {
        int[] hash1 = new int[256];//哈希表
        int[] hash2 = new int[256];
        for(int i = 0; i<s.length();i++){
            hash1[s.charAt(i)]++;
        }
        for(int i =0; i<t.length();i++){
            hash2[t.charAt(i)]++;
        }
        for(int i=0;i<256;i++){
            if(hash1[i]!=hash2[i]){
                return (char) i;
            }
        }
        return '\0';
    }

方法三

public char findTheDifference(String s, String t) {
    long s1=0,t1=0;
        for(int i =0;i<s.length();i++)
            s1+=(int)s.charAt(i);
        for (int i=0;i<t.length();i++)
            t1+=(int)t.charAt(i);
        return (char) (t1-s1);
}

题目390 Elimination Game

问题描述

There is a list of sorted integers from 1 to n. Starting from left to right, remove the first number and every other number afterward until you reach the end of the list.

Repeat the previous step again, but this time from right to left, remove the right most number and every other number from the remaining numbers.

We keep repeating the steps again, alternating left to right and right to left, until a single number remains.

Find the last number that remains starting with a list of length n.

Example

Input:
n = 9,
1 2 3 4 5 6 7 8 9
2 4 6 8
2 6
6

Output:
6

解题思路

题目大意是指给定一个已排序的整数从1到n,首先从左到右,移除第一个数,而后每隔一个数字移除一个,直到表的最后位置,重复之前的步骤,不过这回是从右往左开始,移除最右边的数,然后每隔一个数移除一个,直到最左边。 重复上述操作,直至表中只有一个元素。

  • 方法一 用数组,两个数组,一个用来保存未被删除的。但是该方法容易内存超过限制,不能通过leetcode。
  • 方法二 根据题设要求的数字移除过程,可以发现每执行完一趟数字移除操作,列表中剩余相邻数字之间的差都会加倍。(参考别人的)

代码

方法一

    public static int lastRemaining2(int n) {
        int[] a = new int [n];
        int[] b = new int [n];
        for(int i = 0;i<n;i++)
            a[i]=i+1;
        int k = n;
        while(k>1){
            int i =0,j=0;
            while(i<k-1){//正向删除
                b[j++]=a[i+1];//复制
                i+=2;
            }
            k=k/2;
            if(k!=1){
            for(j=k-1,i=0;j>=0;j-=2){//逆向删除
                b[j]=0;//直接将其改为0
            }}
            for(i=0,j=0;i<k;i++){
                if(b[i]!=0){
                    a[j++]=b[i];//复制
                }
            }
            k=k/2;
        }
        return a[0];
    }

方法二

参考了书影

public static int lastRemaining3(int n) {
    int a=1,p=1,cnt=0;
    while (n>1){
        n/=2;
        cnt++;//执行的cnt趟
        p*=2;//数字间的间隔
        if(cnt%2==1){
            a += p/2 + p*(n-1);
        }else {
            a -= p/2 + p*(n-1);
        }
    }
    return a;
}