LeetCode简单题(一)
题目一：
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
分析：这是一个求数组和的题目，数组求和问题。
方法一：暴力法
1、我们设置两层循环遍历数组，找出数组所有的两数之和可能，将其相加找到目标值
2、将找得到值得索引下标返回，return new int[] {i,j};
3、如果没有所求值，则抛出一个异常，throw new IllegalAugementException("No sum");
class Solution {
public int[] twoSum(int[] nums, int target) {
for(int i=0;i<nums.length;i++)
for(int j=i+1;j<nums.length;j++)
{
if(nums[i]+nums[j]==target)
{
return new int[] {i,j};
}
}
throw new IllegalArgumentException("No sum");
}
}
方法二：哈希表法
1、首先将数组的元素和下标存放在一个哈希表中，因为我们要返回的是下标。
哈希表定义：Map<Interger,Interger> map=new HashMap<>();
循环存储数组元素：for(int i=0;i<nums.lengh,i++) map.put(nums[i],i);
2、循环进行目标值计算，这一步最重要的是设置变量存储要求得值 int com=targer-nums[i]
3、进行判断，if(map.containKey(com)&&map.get(com)!=i)，然后将其返回 return new int[] {i,map.get(com)};
4、抛出异常 throw new IllegalAugementException("No sum");
整体代码：
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> map=new HashMap();
for(int i=0;i<nums.length;i++)
{
map.put(nums[i], i);
}
for(int i=0;i<nums.length;i++)
{
int com=target-nums[i];
if(map.containsKey(com)&& map.get(com)!=i)
{
return new int[] {i,map.get(com)};
}
}
throw new IllegalArgumentException("No sum");
}
}
方法三、一次遍历哈希表
其实遍历和哈希表存储可以循环一次进行，一边遍历，一边将元素插入到哈希表，具体代码如下：
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> map=new HashMap();
for(int i=0;i<nums.length;i++)
{
int com=target-nums[i];
if(map.containsKey(com))
{
return new int[] {i,map.get(com)};
}
map.put(nums[i], i)
}
throw new IllegalArgumentException("No sum");
}
}
题目二：
判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
示例 1:输入: 121输出: true
分析：判断回文将整数反转，然后判断反转后的整数和之前的整数是否相同。
1、如果整数小于0或者其余数等于0，则返回false，if(x<0||x%10==0) return false;
2、接下就是整数的反转，当x!=0，m=x%10; result=result*10+m;x=x/10;
完整代码：
class Solution {
public boolean isPalindrome(int x) {
if(x<0||(x%10==0&&x!=0))
return false;
int s=x;
int result=0;
while(x!=0)
{
int MeResult=x%10;
result=result*10+MeResult;
x=x/10;
}
if(s==result)
return true;
else {
return false;
}
}
}
题目三：
给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
示例 1:
输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。
分析：这道题难点在于如何实现进位
1、遍历数组可以从最后一位开始，digit[digit.lenght]++；
2、对上式进行判断，如果其和等于10，选择进位，先将现在这一位赋值为0，将上一位加一；
3、遍历这样的一个循环；
4、如果相加之后小于10，直接返回digit；
5、上面可以实现大部分的测试用例，但对于9,99并不能通过，需要将数组长度加一，并将第一位设置为1，其他默认为0；
具体代码：
class Solution {
public int[] plusOne(int[] digits) {
for(int i=digits.length-1;i>=0;i--)
{
digits[i]++;
digits[i]=digits[i]%10;
if(digits[i]!=0)
return digits;
}
digits=new int[digits.length+1];
digits[0]=1;
return digits;
}
}
题目四：
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
示例 1：
输入: haystack = "hello", needle = "ll"
输出: 2
方法一：
1、设置两个指针，一个用于指向原始字符串，另一个指向匹配字符串；
2、如果字符值相同，i++，j++；
3、如果字符值不同，j=0,i=i-j+1，对其进行回溯；
4、最后如果j=a2.length，说明匹配成功，将其下标进行返回
5、否则返回-1；
具体代码：
class Solution {
public int strStr(String haystack, String needle) {
char[] a1=haystack.toCharArray();
char[] a2=needle.toCharArray();
int i=0,j=0;
while(i<a1.length&&j<a2.length)
{
if(a1[i]==a2[j])
{
i++;
j++;
}
else {
i=i-j+1;
j=0;
}
}
if(j==a2.length)
return i-j;
else {
return -1;
}
}
}
方法二：
public int strStr(String haystack, String needle) {
return haystack.indexOf(needle);
}
题目五：
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"
方法一：
1、这是一道求解所有字符串的公共前缀，而不是子字符串；
2、先比较前两个字符串的公共前缀，得到前缀再与第三个字符串进行比较，逐步进行；
3、将数组第一个元素设置为前缀，prefix=strs[0]；
4、循环接下来数组的其他元素，for(int i=1;i<strs.lenght;i++)；
5、比较前两元素的公共前缀，while(strs[i].indexof(prefix)！=0)，将前缀将前推一位，直到前缀是第一个字符串的子字符；
6、prefix=prefix.substring(0,prefix.lenght)；
7、如果前缀为isempty()，return " "；
具体代码：
class Solution {
public String longestCommonPrefix(String[] strs) {
if(strs.length==0) return "";
String prefix=strs[0];
for(int i=1;i<strs.length;i++)
{
while(strs[i].indexOf(prefix)!=0)
{
prefix=prefix.substring(0,prefix.length()-1);
if(prefix.isEmpty()) return "";
}
}
return prefix;
}
}
题目六：
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例 1:
给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
你不需要考虑数组中超出新长度后面的元素。
方法一：
1、采用双指针，一个慢指针，一个快指针，快指针循环整个数组；
2、i=0；if(nums[i]!=nums[j]) i++;nums[i]=nums[j]；
具体代码：
class Solution {
public int removeDuplicates(int[] nums) {
int i=0;
for(int j=1;j<nums.length;j++)
{
if(nums[i]!=nums[j])
{
i++;
nums[i]=nums[j];
}
}
return i+1;
}
}
题目7：
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
方法1：迭代
1、两个链表的合并，链表是个很奇怪的，不需要设置链表长度，只需要设置一个节点，再设置一个节点指针，将指针指向节点；
2、对指针进行修改其实就是对这个链表进行修改，比较神奇；
3、遍历两个链表，不管遍历哪一个，pre.next=l1，就表示指针发生了变化，指针发生发变化也就是链表发生了变化；
4、最后判断链表是否为空，pre.next=l1==null?l2:l1；
5、返回节点的指针就是整个链表了；
具体代码：
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode result=new ListNode(0);
ListNode rListNode;
rListNode=result;
while(l1!=null&&l2!=null)
{
if(l1.val<=l2.val)
{
rListNode.next=l1;
l1=l1.next;
}
else
{
rListNode.next=l2;
l2=l2.next;
}
rListNode=rListNode.next;
}
rListNode.next=l1==null?l2:l1;
return result.next;
}
}
方法二：递归
1、先找到递归出口，l1或l2=0；
2、递归实在太简单了；
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1==null)
return l2;
else if (l2==null) {
return l1;
}
else if (l1.val<l2.val) {
l1.next=mergeTwoLists(l1.next, l2);
return l1;
}
else {
l2.next=mergeTwoLists(l1, l2.next);
return l2;
}
}
}
题目八：
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
输入: [1,3,5,6], 5
输出: 2
分析：
1、通过有序数组查找目标值，就应该想到用二分查找；
2、这是一种思维，具体二分查找的过程，先设定数组首位的索引值和末尾索引值，l=0,r=len，这个长度应该是数组长度加一；
3、进行判断mid=(left+right)/2，nums[mid]==target，这个判断过程比较巧妙；
4、if(nums[mid]<target)，left=mid+1；否则，right=mid；因为mid可能包括了等于target的情况；
5、我们的目标是获取相同值的下标，对于返回left还是right会有所考虑，我们只需要设置循环while(left<right)，这样一定是left=right的时候跳出循环，不管返回那个都一样；
6、在求中间索引mid时，可能存在整数溢出的问题，解决方法是mid=(left+right)>>>1，这样实现无符号右移，得到不溢出结果；
具体代码：
class Solution {
public int searchInsert(int[] nums, int target) {
int len=nums.length;
if(len==0)
return 0;
int left=0,right=len;
while(left<right)
{
int mid=left+right>>>1;
if(nums[mid]<target)
{
left=mid+1;
}
else {
right=mid;
}
}
return left;
}
}
题目九：
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
方法：
1、这道题思路很奇怪，我们什么时候应舍弃，从下个节点开始遍历是问题的关键；
2、先定义求和sum=0，ans=nums[0]；
3、遍历数组，只要sum>0，就将nums[i]加进去，如果sum<0，从新开始遍历sum=nums[i]；
4、求ans和sum的最大值；
具体代码：
class Solution {
public int maxSubArray(int[] nums) {
int ans=nums[0];
int sum=0;
for(int i=0;i<nums.length;i++)
{
if(sum>0)
{
sum=sum+nums[i];
}
else {
sum=nums[i];
}
ans=Math.max(ans, sum);
}
return ans;
}
}
题目十：
给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
说明:
初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
示例:
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
方法一：
1、将一个数组复制到另一个数组中；
2、复制好的数组进行排序；
如何复制数组？ java中给定了一个系统函数：System.arraycopy(要复制的数组，从第几位，目标数组，从第几位，复制几位)；
数组如何排序？ java中Arrays.sort(要排序的数组)；
具体代码：
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
System.arraycopy(nums2, 0, nums1, m, n);
Arrays.sort(nums1);
}
}
方法二：
1、因为要返回num1，先将num1复制到一个数组num1_copy，System.arraycopy(nums1,0,num1_copy,0,m)；
2、设置双指针分别从前到后遍历num1_copy和num2，i,j；为num1也设置一个指针p，用于往后推进；
3、while(i<m&&j<n) num1[p++]=(nums1_copy[i]<nums2[j]) ?nums1_copy[i++]：nums2[j++]；
4、处理两个数组其中一个剩下的元素；
具体代码：
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int[] nums1_copy=new int[m];
System.arraycopy(nums1, 0, nums1_copy, 0, m);
int i=0,j=0,p=0;
while(i<m&&j<n)
{
nums1[p++]=(nums1_copy[i]<nums2[j])? nums1_copy[i++]:nums2[j++];
}
if(i<m)
System.arraycopy(nums1_copy, i, nums1, i+j, m+n-i-j);
if(j<m)
System.arraycopy(nums2, j, nums1, i+j, m+n-i-j);
}
}
方法三：
1、同样设置三个指针，但是不需要复制num1；
2、从后往前进行遍历，思想有点巧妙；
具体代码：
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int p1=m-1;
int p2=n-1;
int p=m+n-1;
while(p1>=0&&p2>=0)
{
nums1[p--]=(nums1[p1]<nums2[p2])?nums2[p2--]:nums1[p1--];
}
System.arraycopy(nums2, 0, num1, 0, p2+1);
}
}
最新文章
- mysql 大表拆分成csv导出
- Linux下不同机器之间拷贝文件
- VS2013 GIT 克隆远程仓库
- MySQL 调优基础(五) Linux网络
- Oracle的thin驱动和oci驱动有什么不同？哪个性能好些？
- extjs 一些杂碎的技术问题
- MSSQL导入导出数据
- 配置iDempiere源码开发环境
- merge into的用法
- poj1673EXOCENTER OF A TRIANGLE
- Eclipse安装插件的方式
- spoj 364
- 错误代码: 1005 Can't create table 'hibernate.bill' (errno: 150)
- jquery validate.addMethod 正则表达式 (自定义验证方法)
- javascript有用小技巧—实现分栏显示
- Mac_OS_Sierra_10.12.6编译OpenJDK9
- javascript入门篇（五）
- 剑指Offer_编程题_23
- Winform 关闭按钮
- POJ2112 Optimal Milking