笔经整理1

Leetcode 笔试题1

题目来源：LeetCode

easy

1. Two Sum

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].

public int[] twoSum(int[] nums, int target) {
	Map<Integer,Integer> map = new HashMap<Integer, Integer>();
	int[] result = new int[2];
	for(int i=0;i<nums.length;++i){
		if(map.containsKey(nums[i])){
			result[0] = map.get(nums[i]);
			result[1] = i;
			return result;
		}else{
			map.put(target - nums[i],i);
		}
	}
	return result;
}

7. Reverse Integer

Given a 32-bit signed integer, reverse digits of an integer.

Example 1:

Input: 123
Output: 321

Example 2:

Input: -123
Output: -321

Example 3:

Input: 120
Output: 21

Note:
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

public static void main(String[] args) {
	System.out.println(new Solution().reverse(-123010));

}
static class Solution {
	public int reverse(int x) {
		boolean flag = false;// 默认正数
		boolean carry = true;
		int[] num = new int[21];
		if(x<0){
			x = -x;
			flag = true;
		}
		int result = 0;

		if(x == 0){
			return result;
		}
		int i =0;
		while(x>0){
			num[i++] = x%10;
			x/=10;
		}
		for(int j =0;j<i;++j){
			if(num[j]==0 && carry){
				// 首位是零
				continue;
			}
			carry = false;
			if(result>Integer.MAX_VALUE/10 || result < Integer.MIN_VALUE/10){
			//判断溢出
				result = 0;
				break;
			}
			result = 10*result + num[j];

		}
		if(flag)
			result = -result;

		return result;
	}
}

13. Roman to Integer

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.
Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

Example 1:

Input: “III”
Output: 3

Example 2:

Input: “IV”
Output: 4

Example 3:

Input: “IX”
Output: 9

Example 4:

Input: “LVIII”
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 5:

Input: “MCMXCIV”
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

class Solution {
    public int romanToInt(String s) {

			int sum = 0,count = 0,pre = 0;
			for(int i = 0;i<s.length();++i){
				char c = s.charAt(i);
				switch (c){
					case 'I':
						count = 1;
						break;
					case 'V':
						count = 5;
						break;
					case 'X':
						count = 10;
						break;
					case 'L':
						count = 50;
						break;
					case 'C':
						count = 100;
						break;
					case 'D':
						count = 500;
						break;
					case 'M':
						count = 1000;
						break;
				}
				sum += count;
				// 如果后一位大于前一位，说明要扣掉双倍的 pre
				if(count > pre){ 
					sum -= 2 * pre;
				}
				pre = count;

			}
			return sum;        
    }
}

说明：每一位比如 X、L、C、D、M都可以独立存在的，即可以独立表示为500这种，所以直接按位读取即可。

14. Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: [“flower”,”flow”,”flight”]
Output: “fl”

Example 2:

Input: [“dog”,”racecar”,”car”]
Output: “”
Explanation: There is no common prefix among the input strings.

Note:

All given inputs are in lowercase letters a-z.

public class study0112_1 {
	public static void main(String[] args) {
//		String[] strs = {"flower","flow","flight"};
		String[] strs = {"dog","racecar","car"};
		System.out.println(new Solution().longestCommonPrefix(strs));

	}
	static class Solution {
		public Solution(){

		}
		public String longestCommonPrefix(String[] strs) {
			if(strs.length == 0){
				return "";
			}
			String result = strs[0];
			for(int i = 0;i<strs.length-1;++i){
				result = getPrefix(result,strs[i+1]);
				if(result.equals(""))
					return "";
			}
			return result;
		}
		// 两两比较，拿相同前缀，使用StringBuilder缩短时间
		public String getPrefix(String A,String B){
			int i=0;
			StringBuilder common = new StringBuilder("");
			while(i<A.length() && i<B.length()){
				if(A.charAt(i) == B.charAt(i)){
					common.append(A.charAt(i));
					i++;
				}else{
					break;
				}
			}
			return common==null?"":common.toString();
		}
	}
}

38.Count and Say

The count-and-say sequence is the sequence of integers with the first five terms as following:

1. 1
   

2. 11
   

3. 21
   

4. 1211
   

5. 111221
   

1 is read off as “one 1” or 11.
11 is read off as “two 1s” or 21.
21 is read off as “one 2, then one 1” or 1211.

Given an integer n where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence.

Note: Each term of the sequence of integers will be represented as a string.

Example 1:

Input: 1
Output: “1”

Example 2:

Input: 4
Output: “1211”

public static void main(String[] args) {
		System.out.println(new Solution().countAndSay(5));
	}

	static class Solution {
		public String countAndSay(int n) {
			String result = "1";
			String temp = "";
			for (int i = 1; i < n; ++i) {
				// 迭代 n-1 次
				int count = 1;
				for (int j = 0; j < result.length(); ++j) {
					if (j == result.length() - 1) {
						// 如果是最后一位，把 count 结果和最后一位字符加在末尾
						temp += String.valueOf(count) + result.charAt(j);
					}else {
						// 如果 j+1 位与 j 位相同，计数器+1
						// 如果不同，把 count 结果，和 j 位字符一起加在末尾
						if (result.charAt(j) == result.charAt(j + 1)) {
							++count;
						} else {
							temp += String.valueOf(count) + result.charAt(j);
							count = 1;
						}
					}
				}
				result = temp;
				temp = "";
			}
			return result;
		}
	}

Medium

2. Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

class Solution {
		public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
			ListNode T1 = l1,T2 = l2,tail = new ListNode(-1),temp = tail;
			int carry = 0;
			while(T1!= null && T2!= null){
				int sum = T1.val + T2.val + carry;
				if(sum>9){
					carry = 1;
					sum-=10;
				}else{
					carry = 0;
				}
				ListNode node = new ListNode(sum);
				tail.next = node;
				tail = node;
				T1 = T1.next;
				T2 = T2.next;
			}
			if(T1 == null && T2 == null){
				// 传入 carry 和尾指针
				dealWithCarry(carry,tail);
			}else if(T1 == null){
				while(T2 != null){
					int sum = T2.val + carry;
					if(sum>9){
						carry = 1;
						sum-=10;
					}else{
						carry = 0;
					}
					ListNode node = new ListNode(sum);
					tail.next = node;
					tail = node;
					T2 = T2.next;
					if(T2 == null){
						dealWithCarry(carry,tail);
					}
				}
			}else{
				while(T1 != null){
					int sum = T1.val + carry;
					if(sum>9){
						carry = 1;
						sum-=10;
					}else{
						carry = 0;
					}
					ListNode node = new ListNode(sum);
					tail.next = node;
					tail = node;
					T1 = T1.next;
					if(T1 == null){
						dealWithCarry(carry,tail);
					}
				}
			}
			ListNode result = temp.next; // 排除首节点
			return result;
		}
	}

	public void dealWithCarry(int carry,ListNode tail){
		// 两个链的尾部都没有结点，但要处理 carry 的情况
		if(carry == 0) {
			tail.next = null;
		}else{
			ListNode node = new ListNode(carry);
			tail.next = node;
			node.next = null;
		}
	}

	public class ListNode {
		int val;
		ListNode next;
		ListNode(int x) {
			val = x;
		}
    }

3. Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.

Example 2:

Input: “bbbbb”
Output: 1
Explanation: The answer is “b”, with the length of 1.

Example 3:

Input: “pwwkew”
Output: 3
Explanation: The answer is “wke”, with the length of 3.
Note that the answer must be a substring, “pwke” is a subsequence and not a substring.

	public static void main(String[] args) {
//		String s = "abcabcbb";
//		String s = "bbbbbbb";
//		String s = "pwwkew";
//		String s = "dvdf";
//		String s = "aabaab!bb";
		String s ="asljlj";
		System.out.println(new Solution().lengthOfLongestSubstring(s));
	}
	static class Solution {
		public int lengthOfLongestSubstring(String s) {
			int max = 0;
			Map<String,Integer> map = new HashMap<String, Integer>();
			Map<Integer,String> reverseMap = new HashMap<Integer, String>();

			for(int i = 0;i<s.length();++i){
			 	String str = s.substring(i,i+1);
				if(map.containsKey(str)){
					// 找到重复char，把char及前面的全部从map中删除，后面的重新编号
					int idx = map.get(str);
					int temp = idx;
					int size = map.size();
					int value = temp;
					for(;value>0;--value){
						String key = reverseMap.get(value);
						map.remove(key);
						reverseMap.remove(value);
					}
					temp++;
					for(;temp<=size;++temp){
						String key = reverseMap.get(temp);
						int k = map.get(key) - idx;
						map.put(key,k);
						reverseMap.remove(temp);
						reverseMap.put(k,key);
					}
					map.put(str,map.size()+1);
					reverseMap.put(reverseMap.size()+1,str);
				}else{
					 map.put(str,map.size()+1);
					 reverseMap.put(reverseMap.size()+1,str);
				 }
				if(map.size() > max){
					max = map.size();
				}
			 }
			 return max;
		}
	}

说明：

1. 维持一个最大值，遍历整个字符串，遍历经过的那个字符作为 subString 的末尾，将重复的char及更前面的全部删掉（使用 map和反map进行编号与定位）。
2. 将重复处到遍历点之间重新编号（从1 开始）。

5. Longest Palindromic Substring

Input: “babad”
Output: “bab”

Note: “aba” is also a valid answer.

思路：最长回文子串：

1. 维护一个二维数组dp[i][j]，保存的是i、j的长度。
2. 如果不是回文串，保存的是0.
3. 先对1位、2位进行存入数组，之后就可以叠加了。

package com.examination.learn;


import java.util.Scanner;

public class Solution {

	public static int[][] dp;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String str = sc.nextLine();
		dp = new int[str.length()][str.length()];
		String result = longestPalindrome(str);
		System.out.println(result);
	}

	public static String longestPalindrome(String s) {
		int resultX = 0;
		int resultY = 0; // 直接用resultX、Y来保存最大的角标。
		if(s.isEmpty()){
			return "";
		}
		for (int i = 0; i < s.length(); ++i) {
			dp[i][i] = 1;
			resultX = i;
			resultY = i;
		}
		for (int i = 0; i < s.length() - 1; ++i) {
			int j = i + 1;
			if (s.charAt(i) == s.charAt(j)) {
				dp[i][j] = 2;
				resultX = i;
				resultY = j;
			}
		}

		for (int step = 3; step <= s.length(); step++) {

			for (int i = 0; i <= s.length() - step; ++i) {
				int j = i + step - 1; //i、j 分别是首末两位
				if (dp[i + 1][j - 1] == 0) {
					dp[i][j] = 0;
				} else {
					if (s.charAt(i) == s.charAt(j)) {
						dp[i][j] = dp[i + 1][j - 1] + 2;
						resultX = i;
						resultY = j;
					} else {
						dp[i][j] = 0;
					}
				}


			}

		}
		String result = s.substring(resultX, resultY + 1);
		return result;
	}
}

12. Integer to Roman

阿拉伯数字转罗马数字

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000

For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.
Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.

Example 1:

Input: 3
Output: “III”

Example 2:

Input: 4
Output: “IV”

Example 3:

Input: 9
Output: “IX”

Example 4:

Input: 58
Output: “LVIII”
Explanation: L = 50, V = 5, III = 3.

Example 5:

Input: 1994
Output: “MCMXCIV”
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

public static void main(String[] args) {
	System.out.println(new Solution().intToRoman(58));

}
static class Solution {
	public String intToRoman(int num) {
		int[] values = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
		String[] strs = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
		StringBuilder result = new StringBuilder();
		for(int i =0;i<values.length;++i){
			while(num>=values[i]){
				num -= values[i];
				result.append(strs[i]);
			}
		}
		return result.toString();
	}
}

15. 3Sum

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]

public static void main(String[] args) {
	int[] nums = {-1, 0, 1, 2, -1, -4};
	System.out.println(new Solution().threeSum(nums));

}

static class Solution {

	public List<List<Integer>> threeSum(int[] nums) {
		Arrays.sort(nums);
		List<List<Integer>> list = new ArrayList<>();
		for (int i = 0; i < nums.length - 2; ++i) {
			if (i > 0 && nums[i] == nums[i - 1]) {
				continue;
			}
			for (int j = i + 1, k = nums.length - 1; j < k; ) {
				if (nums[i] + nums[j] + nums[k] == 0) {
					list.add(Arrays.asList(nums[i], nums[j], nums[k]));
					++j;
					--k;
					while (j < k && nums[j] == nums[j - 1]) ++j;
					while (j < k && nums[k] == nums[k + 1]) --k;

				} else if (nums[i] + nums[j] + nums[k] > 0) {
					--k;
				} else {
					++j;
				}
			}
		}
		return list;
	}
}

33.Search in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e.,[0,1,2,4,5,6,7]might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm’s runtime complexity must be in the order of O(log n).

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

class Solution {
    	public Solution(){

		}
		// 为满足题设要求，将四个参数的方法包装成两个参数的方法
		public int search(int[] nums,int target){
			return search(0,nums.length-1,nums,target);
		}
		public int search(int i,int j,int[] nums, int target) {
			int mid = (i+j)/2;
			if(i>j){
				return -1;
			}
			if(i == j){
				return nums[i] == target ? i : -1;
			}
			if(nums[i]<nums[mid]){
				// 前半部分有序
				int result = binarySearch(i,mid,nums,target);
				if(result!=-1){
					return result;
				}else{
					return search(mid+1,j,nums,target);
				}

			}else{
				// 后半部分有序
				int result = binarySearch(mid+1,j,nums,target);
				if(result != -1){
					return result; // 二分
				}else{
					return search(i,mid,nums,target); // 递归 search 方法
				}
			}
		}
		public int binarySearch(int i,int j,int[] nums,int target){
			int mid;
			while(i<=j){
				if(i == j && nums[i]!=target)
					return -1;
				mid=(i+j)/2;
				if(nums[mid]<target){
					i = mid+1;
					return binarySearch(i,j,nums,target);
				}else if(nums[mid]>target){
					j = mid;
					return binarySearch(i,j,nums,target);
				}else{
					return mid;
				}
			}
			return -1;
		}
	}
	
	<!--评价-->
Runtime: 11 ms, faster than 80.79% of Java online submissions for Search in Rotated Sorted Array.

说明：对于循环数组的二分查找，要求时间复杂度为O(logN)。

思路（分治、递归）：

• 实现一个方法A：将数组第一个元素与mid比较，如果小于 mid ，说明数组的前一半有序；如果大于mid，说明数组后一半有序。
• 那么有序的一半采用常规二分，无序的一半依然是循环数组，将递归方法A。

hard

4. Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

说明：

1. 标准答案居然是直接 sort ！！！ hard 界的耻辱！
2. 所以我留下了不同的解法，如下
3. 以下代码虽然没有 AC ，但我解决的是找中位数的问题，表示解决的很满意。

public static void main(String[] args) {

	int[] nums1 = {1, 2, 3};
	int[] nums2 = {4, 5, 6, 7};
	System.out.println(new Solution().findMedianSortedArrays(nums1, nums2));
}

static class Solution {
	public double findMedianSortedArrays(int[] nums1, int[] nums2) {
		// 考虑到某个数组为空的场景
		if (nums1.length == 0) {
			return findMid(nums1);
		} else if (nums2.length == 0) {
			return findMid(nums2);
		}
		return findMedianSortedArrays(0, nums1.length - 1, 0, nums2.length - 1, nums1, nums2);
	}

	public double findMedianSortedArrays(int i, int j, int m, int n, int[] nums1, int[] nums2) {
		double result = 0.0;
		if (i == j || m == n) {
			// 如果某个数组仅有一个元素，直接排序找中位数
			result = sort(i, j, m, n, nums1, nums2);
		} else {
			if (nums1[(i + j) / 2] < nums2[(m + n) / 2]) {
			// 砍掉nums1 的左边一半和 nums2 的右边一半
			// 考虑数组中剩下的元素个数，给予不同的策略
				return findMedianSortedArrays((j - i) % 2 == 0 ? (i + j) / 2 : (i + j) / 2 + 1, j, m, (m + n) / 2, nums1, nums2);
			} else if (nums1[(i + j) / 2] > nums2[(m + n) / 2]) {
				return findMedianSortedArrays(i, (i + j) / 2, (n - m) % 2 == 0 ? (m + n) / 2 : (m + n) / 2 + 1, n, nums1, nums2);
			} else {
				return findMid(nums1);
			}
		}
		return result;
	}

	public double sort(int i, int j, int m, int n, int[] nums1, int[] nums2) {
		// 将两个数组直接 sort 排序后返回中位数
		int size = j - i + n - m + 2;
		int[] xx = new int[size];
		int u = 0;
		for (int t = i; t <= j; ++t) {
			xx[u++] = nums1[t];
		}
		for (int t = m; t <= n; ++t) {
			xx[u++] = nums2[t];
		}
		Arrays.sort(xx);
		return findMid(xx);

	}

	public double findMid(int[] num) {
	// 传入一个数组，根据奇偶，返回中位数或者计算后的结果
		int size = num.length;
		if (size % 2 == 0) {
			return 1.0 * (num[size / 2 - 1] + num[size / 2]) / 2;
		} else {
			return 1.0 * num[size / 2];
		}
	}

}