力扣算法题目(每日一道)_力扣每日一题

一. 两数求和（2022.9.25）

1.1 题目

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案

示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
 
提示：
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案
进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

1.2 解法
1.2.1 暴力求解(M)

class Solution {
    public int[] twoSum(int[] nums, int target) {
        
        for(int i=0;i<nums.length;i++)
        {
            for(int j=0;j<nums.length;j++)
            {
                if((i!=j)&& ((nums[i]+nums[j])==target))
                {
                    result[0]=i;
                    result[1]=j;
                    return new int[]{i,j};
                }
            }
        }
       return null;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

1.2.2 查找表法

在遍历的时候记录一些信息，省去一次循环，空间换时间。
需要记录已经遍历过的数值和下标，可以用查找表来实现，
查找表有两种方法：
1.哈希表
2.平衡二叉搜索树
由于这里不需要维护顺序，哈希表就够了。

class Solution {
    public int[] twoSum(int[] nums, int target) {

        int len =nums.length;
        Map<Integer,Integer> hashMap=new HashMap<Integer,Integer>(len-1);

        hashMap.put(nums[0],0);
        for(int i=1;i<nums.length;i++)
        {
            if(hashMap.containsKey(target-nums[i]))
                return new int[]{hashMap.get(target-nums[i]),i}; 
            hashMap.put(nums[i],i);
        }

        return null;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

1.3 拓展
1.3.1平衡二叉树

二. 两数相加（2022.9.26）

1.1 题目

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]
 
提示：
每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

1.2 解法

       public delegate ListNode _ListNode(int number, int strLen);

        static void Main(string[] args)
        {
            //342 + 465 = 807.
            int nume1 = 942;
            int nume2 = 9465;

            ListNode l1;
            ListNode l2;

            _ListNode delegateList = CreateNode;

            l1 = delegateList(nume1, nume1.ToString().Length);
            l2 = delegateList(nume2, nume2.ToString().Length);

            Action<ListNode> PintListNode = Pint;
            PintListNode(l1);
            PintListNode(l2);
            
            PintListNode(AddTwoNumbers_My)(l1,l2));//算法代码
            PintListNode(AddTwoNumbers(l1,l2));//算法代码
        }


        public class ListNode
        {
            public int val;
            public ListNode next;
            public ListNode(int val = 0, ListNode next = null)
            {
                this.val = val;
                this.next = next;
            }
        }

        public static ListNode AddTwoNumbers_My(ListNode l1, ListNode l2)
        {
            ListNode resultListNode = l1;
            ListNode pro=l1;

            int bit = 0;

            while (l1 != null && l2 != null) 
            {
                int temp= (l1.val + l2.val+bit) % 10;
                bit = (l1.val + l2.val+bit) / 10;
                l1.val = temp;
                pro = l1;
                l1 = l1.next;
                l2 = l2.next;
            }

            if (l1 != null)
            {
                while (l1 != null&&bit==1) 
                {
                    int temp = (l1.val +  bit) % 10;
                    bit = (l1.val + bit) / 10;
                    l1.val = temp;
                    pro = l1;
                    l1 = l1.next;
                   
                }
            }
            else if (l2 != null)
            {
                l1 = pro;
                while (l2 != null && bit == 1) 
                {
                    int temp = (l2.val + bit) % 10;
                    bit = (l2.val + bit) / 10;
                    ListNode list = new ListNode(temp, null);
                    l1.next = list;
                    l1 = l1.next;
                    pro = l1;
                    l2 = l2.next;
                }

                while(l2!=null)
                {
                    ListNode list = new ListNode(l2.val, null);
                    l1.next = list;
                    l1 = l1.next;
                    pro = l1;
                    l2 = l2.next;
                }
            }

            if (bit != 0)
            {
                ListNode list = new ListNode(1, null);
                pro.next = list;
            }


            return resultListNode;
        }

        public static ListNode AddTwoNumbers(ListNode l1, ListNode l2)
        {
            ListNode head = null, tail = null;
            int carry = 0;
            while (l1 != null || l2 != null)
            {
                int n1 = l1 != null ? l1.val : 0;
                int n2 = l2 != null ? l2.val : 0;
                int sum = n1 + n2 + carry;
                if (head == null)
                {
                    head = tail = new ListNode(sum % 10);
                }
                else
                {
                    tail.next = new ListNode(sum % 10);
                    tail = tail.next;
                }
                carry = sum / 10;
                if (l1 != null)
                {
                    l1 = l1.next;
                }
                if (l2 != null)
                {
                    l2 = l2.next;
                }
            }
            if (carry > 0)
            {
                tail.next = new ListNode(carry);
            }
            return head;
        }

        public static ListNode CreateNode(int number, int strLen)
        {
            ListNode listNode = new ListNode();
            ListNode result = listNode;

            for (int i = 0; i < strLen; i++)
            {
                ListNode temp = new ListNode();
                int tempNume = number % 10;
                number = number / 10;
                temp.val = tempNume;
                temp.next = null;
                listNode.next = temp;
                listNode = temp;
            }

            return result.next;
        }

        public static void Pint(ListNode listNode)
        {
            ListNode p = listNode;
            while (p != null)
            {
                if (p.next == null)
                    Console.Write(p.val);
                else
                    Console.Write(p.val + "-->");
                p = p.next;
            }
            Console.WriteLine("\n");
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167

1.2.1 解法
1.2.2 解法
1.2.3 解法
1.3 拓展