leetcode 算法

1.Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

(译:给定一个整数数组,返回两个数字的索引,使它们相加得到一个特定目标值。
您可以假设每个输入都只有一个解决方案,而您可能不会使用相同的元素两次。)
Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
实现:用hashmap实现是比较方便的,可以用函数直接找出是否包含某一数值

import java.util.HashMap;
import java.util.Map;
 
public class twoSum {
    public static int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        Map<Integer,Integer> map = new HashMap();
        for(int i=0; i<nums.length; i++){
            if(map.containsKey(target - nums[i])){
                if(map.get(target - nums[i]) > i){
                    result[0] = i;
                    result[1] = map.get(target - nums[i]);
                }else{
                    result[1] = i;
                    result[0] = map.get(target - nums[i]);
                }
                return result;
            }
            map.put(nums[i], i);
        }
        return result;
    }
    
    public static void main(String[] args) {
        int[] nums = {3,2,4};
        int target = 6;
        int[] result = new int[2];
        result = twoSum(nums,target);
        System.out.println(result[0] + " " + result[1]);
    }
}

2.删除排序数组中的重复项 Remove Duplicates from Sorted Array
Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

Given nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.

It doesn’t matter what you leave beyond the returned length.

mode: easy
tag: array(数组)

Python

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if len(nums)<2:
            return len(nums);
        // idx记录已经找到的非重复数值 
        idx=0
        for i in range(len(nums)):            
            if nums[idx]!=nums[i]:
                idx+=1
                nums[idx]=nums[i]               
        return index+1

C++

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int nums_size=nums.size();
        // Corner case
        if(nums_size<2)
            return nums_size;
        int idx=0;
        for(int i=1; i<nums_size; i++)
        {
            if(nums[idx]!=nums[i])
            {
                idx++;
                nums[idx]=nums[i];
            }
        }
        return idx+1;
    }
};

3.题目:

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后,链表变为 1->2->3->5.
说明:

给定的 n 保证是有效的。

进阶:

你能尝试使用一趟扫描实现吗?

我们可以使用两个指针而不是一个指针。第一个指针从列表的开头向前移动 n+1 步,而第二个指针将从列表的开头出发。现在,这两个指针被 n个结点分开。我们通过同时移动两个指针向前来保持这个恒定的间隔,直到第一个指针到达最后一个结点。此时第二个指针将指向从最后一个结点数起的第n个结点。我们重新链接第二个指针所引用的结点的 next 指针指向该结点的下下个结点。

var removeNthFromEnd = function(head, n) {
  let first = head; // 慢指针
  for (let i = 0; i < n; i++) {
    first = first.next;
  }
  if (!first) return head.next; // 当链表长度为n时,删除第一个节点
 
  let second = head; // 快指针
  while (first.next) {
    first = first.next;
    second = second.next;
  }
  second.next = second.next.next;
  return head;
};

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4题目理解:把两个排好序的linkedlist merge起来,然后返回merge好的linkedlist的头节点。关于linkedlist的题目一般都要准备好双指针,然后通过双指针的“速度”“方向”“遍历”来完成.这道题也是需要使用双指针:题目给了一个很关键的提示:两个linkedlist都是排好序的,那么我们可以得到以下的结论:1. let s1 = head of list 1, s2 = head of list 22. if s1 < s2 and s1 -> next < s2, then there does not exist any element e such that s1 < e < s2.因为我们只有两个linkedlist,所以这个结论我们可以很容易通过contradiction来证明。在实施起来也非常容易. 这里需要使用一个dummy 和curr节点分别在每次遍历的时候更新和用作返回值。解法1:

 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
12     {
13         ListNode *dummy = new ListNode(-1), *curr = dummy;
14         while (l1 && l2) {
15             if (l1->val < l2->val) {
16                 dummy->next = l1;
17                 l1 = l1->next;
18             } else { // if l1 and l2 are equal, then choose l2 (you can also choose l1)
19                 dummy->next = l2;
20                 l2 = l2->next;
21             }
22             dummy = dummy->next;
23         }
24         if (l1)
25             dummy->next = l1;
26         else if (l2)
27             dummy->next = l2;
28         return curr->next;
29     }
30 };

jiefa2

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //require 
        ListNode fake=new ListNode(0);
        ListNode cur=fake;
        //invariant
        while(true){
            if(l1==null){cur.next=l2;break;}
            if(l2==null){cur.next=l1;break;}
            if(l1.val>l2.val){
                cur.next=l2;
                l2=l2.next;
            }else{
                cur.next=l1;
                l1=l1.next;
            }
            cur=cur.next;
        }
        //ensure
        return fake.next;
    }
}

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 218,284评论 6 506
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 93,115评论 3 395
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 164,614评论 0 354
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 58,671评论 1 293
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 67,699评论 6 392
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 51,562评论 1 305
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 40,309评论 3 418
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 39,223评论 0 276
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,668评论 1 314
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,859评论 3 336
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,981评论 1 348
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,705评论 5 347
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 41,310评论 3 330
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,904评论 0 22
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 33,023评论 1 270
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 48,146评论 3 370
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,933评论 2 355