2018年8月 leetcode刷題(初級(jí)算法數(shù)組)

  1. 從排序數(shù)組中刪除重復(fù)項(xiàng)

給定一個(gè)排序數(shù)組匠楚,你需要在原地刪除重復(fù)出現(xiàn)的元素画机,使得每個(gè)元素只出現(xiàn)一次盛卡,返回移除后數(shù)組的新長(zhǎng)度矗钟。

不要使用額外的數(shù)組空間唆香,你必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成。

自己?jiǎn)栴}代碼(及正解):

PS:自己的問(wèn)題出在吨艇,沒(méi)有看清楚題目躬它,并且將賦值語(yǔ)句混亂為移動(dòng)。
細(xì)節(jié)在于i++處秸应,當(dāng)相等的時(shí)候i下標(biāo)先向后移動(dòng)虑凛,在進(jìn)行比較碑宴。

// 在一個(gè)數(shù)組中只能是賦值操作,不能修改長(zhǎng)度桑谍。 length是靜態(tài)常量
// 此方法為自己的方法延柠,只能用于統(tǒng)計(jì)不重復(fù)的個(gè)數(shù)

 public static int removeDuplicates(int[] nums) {
    int b = nums.length;
    for (int i = 0; i < nums.length - 1; i++) {
        if (nums[i] == nums[i + 1]) {
            b--;
        }
    }
    return b;
}

*******正解********

 public static int remove(int[] nums) {
     if (nums.length == 0)
        return 0;
    int i = 0;
    for (int j = 1; j < nums.length; j++) {
        if (nums[j] != nums[i]) {
            i++;                // 這一步很關(guān)鍵,請(qǐng)注意锣披。
            nums[i] = nums[j];
            System.out.println(nums[i]);
        }
    }
    return i + 1;
}

2.旋轉(zhuǎn)數(shù)組

給定一個(gè)數(shù)組贞间,將數(shù)組中的元素向右移動(dòng)k 個(gè)位置,其中k 是非負(fù)數(shù)雹仿。

輸入:[1,2,3,4,5,6,7]和k= 3 輸出:[5,6,7,1,2,3,4]

解釋?zhuān)?/p>

    向右旋轉(zhuǎn) 1 步:[7,1,2,3,4,5,6]

    向右旋轉(zhuǎn) 2 步:[6,7,1,2,3,4,5]

    向右旋轉(zhuǎn) 3 步:[5,6,7,1,2,3,4]

說(shuō)明:

盡可能想出更多的解決方案增热,至少有三種不同的方法可以解決這個(gè)問(wèn)題。

要求使用空間復(fù)雜度為 O(1) 的原地算法胧辽。

正解(自己結(jié)合網(wǎng)友的解法寫(xiě)的):

public static void rotate(int nums [] , int k ){
    int len = nums.length;
    if(len<=1) return;
    int a [] = new int [len];
    for(int i =0 ; i<len ; i++){
        a[i] = nums[i];
    }
    k = k%len; //去重
    for(int i = 0 ; i<len ; i++){
        int s = k+i;
        s = s %len;
        nums [s] = a[i];
    }
}

注:以下解法并沒(méi)有完全滿(mǎn)足題目要求
解法(一):
ps:在增加數(shù)組的操作上要注意:傳值引用問(wèn)題峻仇。 (使用了數(shù)組返回修改原引用)

public static int []  rotate1(int nums [] ,int k) {
    int len = nums.length;
    int a[] = new int[len];
    for (int i = 0; i < len; i++) {
        int s = k + i;
        if (s >= len) {
            s = s % len;
            a[s] = nums[i];
        } 
        a[s] = nums[i];
    }
    nums = a;
    return nums;
}

解法(二):
ps:時(shí)間復(fù)雜度過(guò)高。

public static void rotate3(int[] nums, int k) {
    int len = nums.length;
    if (len > 1) {
        for (int i = 0; i < k; i++) {
            int temp = nums[0];
            nums[0] = nums[len - 1];
            for (int j = len - 1; j > 1; j--) {
                nums[j] = nums[j - 1];
            }
            nums[1] = temp;
        }
    }
}

3.只出現(xiàn)一次的數(shù)字
給定一個(gè)非空整數(shù)數(shù)組邑商,除了某個(gè)元素只出現(xiàn)一次以外摄咆,其余每個(gè)元素均出現(xiàn)兩次。找出那個(gè)只出現(xiàn)了一次的元素人断。

說(shuō)明:

你的算法應(yīng)該具有線性時(shí)間復(fù)雜度吭从。 你可以不使用額外空間來(lái)實(shí)現(xiàn)嗎?

示例 1:

輸入: [2,2,1]
輸出: 1
示例 2:

輸入: [4,1,2,1,2]
輸出: 4

使用Java語(yǔ)言恶迈,想了很久通過(guò)下標(biāo)來(lái)實(shí)現(xiàn)涩金,但是沒(méi)成功。在網(wǎng)上找到結(jié)果暇仲,利用異或來(lái)實(shí)現(xiàn)步做。細(xì)想一下這題主要考位運(yùn)算符中的 ^ (異或) 運(yùn)算符。 知識(shí)欠缺所致熔吗!

public int singleNumber(int[] nums) {
    int res = 0 ;
    for(int i = 0 ; i<nums.length ; i++){
        res = res^nums[i] ;
    }
    return res;
}

轉(zhuǎn)載:位運(yùn)算符知識(shí)補(bǔ)充 .
https://blog.csdn.net/xiaopihaierletian/article/details/78162863

  1. 兩個(gè)數(shù)組的交集 II
    給定兩個(gè)數(shù)組辆床,編寫(xiě)一個(gè)函數(shù)來(lái)計(jì)算它們的交集佳晶。
    示例 1:
    輸入: nums1 = [1,2,2,1], nums2 = [2,2]
    輸出: [2,2]

思路:最開(kāi)始想到的是用最傳統(tǒng)的下標(biāo)來(lái)進(jìn)行解決桅狠,發(fā)現(xiàn)寫(xiě)出的代碼太過(guò)于復(fù)雜,可讀性很差轿秧,而且時(shí)間復(fù)雜度太高了中跌。
于是百度出正解。(對(duì)于Java中對(duì)于一些復(fù)雜數(shù)組的問(wèn)題菇篡,應(yīng)該結(jié)合類(lèi)集中的底層數(shù)據(jù)結(jié)構(gòu)來(lái)進(jìn)行求解會(huì)更好漩符。)

   public int[] intersect(int[] nums1, int[] nums2) {
        List<Integer> tmp = new ArrayList<>();
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
              
        for(int i = 0 ;i<nums1.length;i++){
            Integer temp = map.get(nums1[i]);
            map.put(nums1[i],(temp == null? 0:temp)+1);
        }
    
        for(int i=0;i<nums2.length;i++){
           if(map.containsKey(nums2[i])&&map.get(nums2[i])!=0){
             
               tmp.add(nums2[i]);
               map.put(nums2[i],map.get(nums2[i])-1);
           }
        }
        int[] result = new int[tmp.size()];
        int i = 0;
        for(Integer in : tmp){
            result[i++] = in;
        }
        return result;
    }

5.兩數(shù)之和
給定一個(gè)整數(shù)數(shù)組和一個(gè)目標(biāo)值,找出數(shù)組中和為目標(biāo)值的兩個(gè)數(shù)驱还。
你可以假設(shè)每個(gè)輸入只對(duì)應(yīng)一種答案嗜暴,且同樣的元素不能被重復(fù)利用凸克。

示例:
給定 nums = [2, 7, 11, 15], target = 9

因?yàn)?nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

思路:最開(kāi)始想的是將數(shù)組裝到集合中在進(jìn)行值的判斷,因?yàn)檫@樣可以將已經(jīng)獲得的元素進(jìn)行刪除闷沥,不用在寫(xiě)刪除元素的底層代碼萎战,也實(shí)現(xiàn)了,但是這樣的方式增加了時(shí)間復(fù)雜度舆逃。后來(lái)用數(shù)組就可以直接解決蚂维,雖然時(shí)間復(fù)雜度下降了,但是離標(biāo)準(zhǔn)還是偏高路狮。

public  int [] twoSum(int [] nums , int target){
    int result []  = new int [2];
    for(int i = 0 ; i<nums.length ; i++){
        for(int j = i+1 ; j<nums.length ; j++){
            if(nums[i] + nums[j] == target){
                result[0] = i;
                result[1] = j;
                break;
            }
        }
    }
    return  result;
}
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末虫啥,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子奄妨,更是在濱河造成了極大的恐慌涂籽,老刑警劉巖,帶你破解...
    沈念sama閱讀 217,657評(píng)論 6 505
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件砸抛,死亡現(xiàn)場(chǎng)離奇詭異又活,居然都是意外死亡,警方通過(guò)查閱死者的電腦和手機(jī)锰悼,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,889評(píng)論 3 394
  • 文/潘曉璐 我一進(jìn)店門(mén)茄蚯,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái),“玉大人辰晕,你說(shuō)我怎么就攤上這事顽分。” “怎么了丝里?”我有些...
    開(kāi)封第一講書(shū)人閱讀 164,057評(píng)論 0 354
  • 文/不壞的土叔 我叫張陵曲初,是天一觀的道長(zhǎng)。 經(jīng)常有香客問(wèn)我杯聚,道長(zhǎng)臼婆,這世上最難降的妖魔是什么? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 58,509評(píng)論 1 293
  • 正文 為了忘掉前任幌绍,我火速辦了婚禮颁褂,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘傀广。我一直安慰自己颁独,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,562評(píng)論 6 392
  • 文/花漫 我一把揭開(kāi)白布伪冰。 她就那樣靜靜地躺著誓酒,像睡著了一般。 火紅的嫁衣襯著肌膚如雪贮聂。 梳的紋絲不亂的頭發(fā)上靠柑,一...
    開(kāi)封第一講書(shū)人閱讀 51,443評(píng)論 1 302
  • 那天寨辩,我揣著相機(jī)與錄音,去河邊找鬼歼冰。 笑死捣染,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的停巷。 我是一名探鬼主播耍攘,決...
    沈念sama閱讀 40,251評(píng)論 3 418
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼畔勤!你這毒婦竟也來(lái)了蕾各?” 一聲冷哼從身側(cè)響起,我...
    開(kāi)封第一講書(shū)人閱讀 39,129評(píng)論 0 276
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤庆揪,失蹤者是張志新(化名)和其女友劉穎式曲,沒(méi)想到半個(gè)月后,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體缸榛,經(jīng)...
    沈念sama閱讀 45,561評(píng)論 1 314
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡吝羞,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,779評(píng)論 3 335
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了内颗。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片钧排。...
    茶點(diǎn)故事閱讀 39,902評(píng)論 1 348
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖均澳,靈堂內(nèi)的尸體忽然破棺而出恨溜,到底是詐尸還是另有隱情,我是刑警寧澤找前,帶...
    沈念sama閱讀 35,621評(píng)論 5 345
  • 正文 年R本政府宣布糟袁,位于F島的核電站,受9級(jí)特大地震影響躺盛,放射性物質(zhì)發(fā)生泄漏项戴。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,220評(píng)論 3 328
  • 文/蒙蒙 一槽惫、第九天 我趴在偏房一處隱蔽的房頂上張望周叮。 院中可真熱鬧,春花似錦躯枢、人聲如沸则吟。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 31,838評(píng)論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至水慨,卻和暖如春得糜,著一層夾襖步出監(jiān)牢的瞬間敬扛,已是汗流浹背。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 32,971評(píng)論 1 269
  • 我被黑心中介騙來(lái)泰國(guó)打工朝抖, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留啥箭,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 48,025評(píng)論 2 370
  • 正文 我出身青樓治宣,卻偏偏與公主長(zhǎng)得像急侥,于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子侮邀,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,843評(píng)論 2 354

推薦閱讀更多精彩內(nèi)容