数组&字符串
9 回文数
public boolean isPalindrome(int x) {
if(x < 0) return false;
String str = Integer.toString(x);
char[] charArr = str.toCharArray();
for(int i = 0; i < charArr.length/2; i++){
if(charArr[i] != charArr[charArr.length-1-i]){
return false;
}
}
return true;
}
方法2：
public boolean isPalindrome(int x) {
if(x<0) return false;
if(x % 10 == 0 && x != 0) return false; //末位是0，不可能是回文数
int halfReserve = 0;
while((x - halfReserve) > 0){
halfReserve = halfReserve*10 + x%10;
x = x/10;
}
System.out.println(halfReserve+" "+ x);
if(x == halfReserve) return true;
if(x == halfReserve/10) return true;//121
return false;
}
26 从排序数组中删除重复项
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
很简单，直接上代码：
class Solution {
public int removeDuplicates(int[] nums) {
int index=0;
for(int i =1 ; i < nums.length ; i++){
if ( nums[i] != nums[index]){
index ++;
nums[index] = nums[i];
}
}
return ++index;
}
}
27 移除元素
原地移除所有=val的值,返回新数组的长度[3,2,2,3] 3 --> [2,2]
public int removeElement(int[] nums, int val) {
if(nums == null || nums.length == 0) return 0;
int index = 0;
for(int i = 0; i < nums.length; i++){
if(nums[i] != val){
nums[index] = nums[i];
index++;
}
}
return index;
}
mid 80 从排序数组中删除重复项II
/*
- 给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。
*/
扩展 最多出现n次 repeat
public int removeDuplicatesII(int[] nums) {
if(nums == null || nums.length == 0) return 0;
int repeat = 2;
int slow = repeat;
for(int fast = repeat; fast < nums.length; fast++){
if(nums[fast] != nums[slow-repeat]){
nums[slow] = nums[fast];
slow++;
}
}
return slow;
}
public class DeleteRepeatedItemsII {
public static void main(String[] args) {
DeleteRepeatedItemsII d = new DeleteRepeatedItemsII();
int[] nums = {0,0,1,1,1,1,2,3,3,4};
int length = d.removeDuplicates(nums);
for(int i = 0; i < length; i++) {
System.out.println(nums[i]);
}
}
public int removeDuplicates(int[] nums) {
if(nums.length == 0 || nums == null) return 0;
int i = 1;
for(int j = 2; j < nums.length; j++) {
if(nums[j] != nums[i-1]) {
i += 1;
nums[i] = nums[j];
}
}
return i+1;
}
}
mid-旋转数组
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
先将数组的前len-k个元素反转，后k个元素反转，然后再将整个数组反转。注意先让k对len取模。
class Solution {
public void rotate(int[] nums, int k) {
int len = nums.length;
k = k%len;
if(len<2||k==0)return;
swap(nums, 0, len-k-1);
swap(nums, len-k, len-1);
swap(nums, 0, len-1);
}
public void swap(int[] nums, int left, int right){
while(left<right){
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right–;
}
}
}
存在重复元素
给定一个整数数组，判断是否存在重复元素。
如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。
方案一：利用HashSet。
class Solution {
public boolean containsDuplicate(int[] nums) {
int len = nums.length;
if(len<2)return false;
HashSet hashSet = new HashSet<>();
for(int num:nums)
if(!hashSet.add(num))return true;
return false;
}
}
方案二：利用Arrays.sort()方法先对数组进行排序，然后判断。
class Solution {
public boolean containsDuplicate(int[] nums) {
int len = nums.length;
if(len<2)return false;
Arrays.sort(nums);
for(int i=0;i+1<len;i++){
if(nums[i]==nums[i+1])return true;
}
return false;
}
}
136 只出现一次的数字 位运算
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
异或，出现偶数次的元素会被清零，于是留下来的就是那个只出现一次的数字。
public int singleNumber(int[] nums) {
int res = 0;
for(int i = 0; i < nums.length; i++){
res = res ^ nums[i];
}
return res;
}
137 只出现一次的数字II
给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
方法1：map
执行用时：5 ms, 在所有 Java 提交中击败了30.98%的用户
内存消耗：41 MB, 在所有 Java 提交中击败了18.70%的用户
public int singleNumberII(int[] nums) {
Map<Integer,Integer> map = new HashMap<Integer, Integer>();
int res = 0;
for(int i = 0; i < nums.length; i++){
if(!map.containsKey(nums[i])){
map.put(nums[i],1);
}else{
Integer v = map.get(nums[i]);
map.put(nums[i],v+1);//对于已有的key，新的value会覆盖之前的
}
}
//用迭代器遍历map
Set entrySet = map.entrySet();
Iterator<Map.Entry> it = entrySet.iterator();
while(it.hasNext()){
Map.Entry entry = it.next();
if(entry.getValue().equals(1)){
res = (Integer)entry.getKey();
}
}
return res;
}
方法2：位运算
260 只出现一次的数字III 多个出现一次
给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
public int singleNumberIII(int[] nums) {
Map<Integer,Integer> map = new HashMap<Integer, Integer>();
List reslist = new ArrayList();
for(int i = 0; i < nums.length; i++){
if(!map.containsKey(nums[i])){
map.put(nums[i],1);
}else{
Integer v = map.get(nums[i]);
map.put(nums[i],v+1);
}
}
Set entrySet = map.entrySet();
Iterator<Map.Entry> it = entrySet.iterator();
while(it.hasNext()){
Map.Entry entry = it.next();
if(entry.getValue().equals(1)){
reslist.add((Integer)entry.getKey());
}
}
int[] resarr = new int[reslist.size()];
for(int i = 0 ; i < reslist.size(); i++){
resarr[i] = reslist.get(i);
}
return resarr;
}
位运算：
两个数组的交集 II
给定两个数组，写一个方法来计算它们的交集。
先排序，再比较。
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
int len1 = nums1.length;
int len2 = nums2.length;
if(len10||len20)return new int[0];
Arrays.sort(nums1);
Arrays.sort(nums2);
List list = new ArrayList<>();
int i=0;
int j=0;
while(i<len1&&j<len2){
if(nums1[i]==nums2[j]){
list.add(nums1[i]);
i++;
j++;
continue;
}
else if(nums1[i]>nums2[j])j++;
else i++;
}
int[] res = new int[list.size()];
for(int k=0;k<list.size();k++)res[k] = list.get(k);
return res;
}
}
加一
给定一个非负整数组成的非空数组，在该数的基础上加一，返回一个新的数组。
最高位数字存放在数组的首位， 数组中每个元素只存储一个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
注意进位的处理。
class Solution {
public int[] plusOne(int[] digits) {
int len = digits.length;
if(len==0)return new int[0];
int[] res = new int[len+1];
res[len] = (digits[len-1]+1)%10;
int carry = (digits[len-1]+1)/10;
for(int i=len-2;i>=0;i–){
res[i+1] = (digits[i]+carry)%10;
carry = (digits[i]+carry)/10;
}
res[0] = carry;
if(carry!=0)return res;
int[] res1 = new int[len];
System.arraycopy(res, 1, res1, 0, len);
return res1;
}
}
移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
class Solution {
public void moveZeroes(int[] nums) {
int len = nums.length;
if(len<2)return;
int index = 0;
for(int i=0;i<len;i++){
if(nums[i]!=0)nums[index++] = nums[i];
}
for(int i=index;i<len;i++)nums[i] = 0;
}
}
有效的数独
判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
- 数字 1-9 在每一行只能出现一次。
- 数字 1-9 在每一列只能出现一次。
- 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
使用一个二维数组seat保存所有数字的位置，遍历输入的数独，遇见数字则先判断该位置是否与seat中相同数字的位置冲突，若冲突则返回false，否则将当前数字的位置保存至seat中。
class Solution {
public boolean isValidSudoku(char[][] board) {
boolean[][] seat=new boolean[9][27];
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
if(board[i][j]==‘.’)continue;
int num=board[i][j]-‘0’;
int grid=(i/3)*3+(j/3);
if(seat[num-1][i]||seat[num-1][j+9]||seat[num-1][grid+18])return false;
else{
seat[num-1][i]=true;
seat[num-1][j+9]=true;
seat[num-1][grid+18]=true;
}
}
}
return true;
}
}
mid-旋转图像
给定一个 n × n 的二维矩阵表示一个图像。
将图像顺时针旋转 90 度。
你必须在原地旋转图像。
先按主对角线翻转，再按垂直对称轴翻转。
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
for(int i=0;i<n;i++)
for(int j=0;j<i;j++)
swap(matrix, i, j);
for(int i=0;i<n;i++)swap(matrix, i);
}
public void swap(int[][] matrix, int i, int j){
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
public void swap(int [][] matrix, int i){
int left = 0;
int right = matrix[i].length-1;
while(left<right){
int temp = matrix[i][left];
matrix[i][left] = matrix[i][right];
matrix[i][right] = temp;
left++;
right–;
}
}
}
反转字符串
编写一个函数，其作用是将输入的字符串反转过来。
注意不要想得太复杂了就好。
class Solution {
public String reverseString(String s) {
int len = s.length();
if(len<2)return s;
char[] chars = s.toCharArray();
int left = 0;
int right = len-1;
while(left<right){
char temp = chars[left];
chars[left] = chars[right];
chars[right] = temp;
left++;
right–;
}
return new String(chars);
}
}
mid-反转整数
给定一个 32 位有符号整数，将整数中的数字进行反转。
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [?231, 231 ? 1]。根据这个假设，如果反转后的整数溢出，则返回 0。
不能使用long！！！
class Solution {
public int reverse(int x) {
int res = 0;
while (x != 0){
int temp = res;
res = res * 10 + x % 10;
if (res/10 != temp) return 0;//校验溢出
x /= 10;
}
return res;
}
}
mid-字符串中的第一个唯一字符
给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回-1。
方案一：利用HashMap存下每个字符和其索引的键值对，若该字符重复出现则将HashMap中的key为该字符的value设为-1，最后遍历HashMap中所有的value，找到最小值。
class Solution {
public int firstUniqChar(String s) {
int len = s.length();
if(len0)return -1;
HashMap<Character, Integer> map = new HashMap<>();
for(int i=0;i<len;i++){
char curr = s.charAt(i);
if(map.containsKey(curr))map.put(curr,-1);
else map.put(curr,i);
}
int index = Integer.MAX_VALUE;
Iterator it = map.values().iterator();
while(it.hasNext()){
int i = (int)it.next();
if(i!=-1)index = Math.min(index,i);
}
return indexInteger.MAX_VALUE?-1:index;
}
}
方案二：使用一个256大小的数组来存放每个字符出现的次数，然后再遍历字符串中的每个字符，如果该字符出现的次数为1则返回。
class Solution {
public int firstUniqChar(String s) {
int len = s.length();
if(len==0)return -1;
int[] charTable = new int[256];
for(int i=0;i<len;i++){
int index = s.charAt(i)-‘0’;
charTable[index]++;
}
for(int i=0;i<len;i++){
int index = s.charAt(i)-‘0’;
if(charTable[index]==1)return i;
}
return -1;
}
}
有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的一个字母异位词。
如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
class Solution {
public boolean isAnagram(String s, String t) {
int lens = s.length();
int lent = t.length();
if(lens!=lent)return false;
HashMap<Character, Integer> map = new HashMap<>();
for(int i=0;i<lens;i++){
char curr = s.charAt(i);
if(map.containsKey(curr))map.put(curr, map.get(curr)+1);
else map.put(curr, 1);
}
for(int i=0;i<lent;i++){
char curr = t.charAt(i);
if(!map.containsKey(curr)||map.get(curr)==0)return false;
map.put(curr, map.get(curr)-1);
}
Iterator it = map.values().iterator();
while(it.hasNext()){
if((int)it.next()!=0)return false;
}
return true;
}
}
验证回文字符串
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。
注意小写字符比大写字符大32！
class Solution {
public boolean isPalindrome(String s) {
int len = s.length();
if(len<2)return true;
int left = 0;
int right = len-1;
while(left<right){
while(left<right&&letter(s.charAt(left))==null)left++;
while(left<right&&letter(s.charAt(right))==null)right–;
if(left<right&&letter(s.charAt(left))!=letter(s.charAt(right)))return false;
left++;
right–;
}
return true;
}
public Character letter(char c){
if(c>=‘a’&&c<=‘z’||c>=‘0’&&c<=‘9’)return c;
else if(c>=‘A’&&c<=‘Z’)return (char)(c+32);
else return null;
}
}
字符串转整数 (atoi)
实现 atoi，将字符串转为整数。
在找到第一个非空字符之前，需要移除掉字符串中的空格字符。如果第一个非空字符是正号或负号，选取该符号，并将其与后面尽可能多的连续的数字组合起来，这部分字符即为整数的值。如果第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
字符串可以在形成整数的字符后面包括多余的字符，这些字符可以被忽略，它们对于函数没有影响。
当字符串中的第一个非空字符序列不是个有效的整数；或字符串为空；或字符串仅包含空白字符时，则不进行转换。
若函数不能执行有效的转换，返回 0。
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [?231, 231 ? 1]。如果数值超过可表示的范围，则返回 INT_MAX (231 ? 1) 或 INT_MIN (?231) 。
public class Solution {
public int myAtoi(String str) {
str = str.trim();
if (str.isEmpty()) return 0;
int sign = 1, base = 0, i = 0, n = str.length();
if (str.charAt(i) == ‘+’ || str.charAt(i) == ‘-’) {
sign = (str.charAt(i++) == ‘+’) ? 1 : -1;
}
while (i < n && str.charAt(i) >= ‘0’ && str.charAt(i) <= ‘9’) {
if (base > Integer.MAX_VALUE / 10 || (base == Integer.MAX_VALUE / 10 && str.charAt(i) - ‘0’ > 7)) {
return (sign == 1) ? Integer.MAX_VALUE : Integer.MIN_VALUE;
}
base = 10 * base + (str.charAt(i++) - ‘0’);
}
return base * sign;
}
}
实现strStr()
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回-1。如果needle是空字符串，则返回0 。
class Solution {
public int strStr(String haystack, String needle) {
int len1 = haystack.length();
int len2 = needle.length();
if(len2==0)return 0;
if(len1<len2)return -1;
int i = 0;
int j = 0;
while(i<len1&&j<len2){
if(haystack.charAt(i)needle.charAt(j)){
j++;
i++;
}else{
i = i-j+1;
j = 0;
}
}
if(jlen2)return i-j;
else return -1;
}
}
数数并说
报数序列是指一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：
- 1
- 11
- 21
- 1211
- 111221
1 被读作 “one 1” (“一个一”) , 即 11。
11 被读作 “two 1s” (“两个一”）, 即 21。
21 被读作 “one 2”, “one 1” （“一个二” , “一个一”) , 即 1211。
给定一个正整数 n ，输出报数序列的第 n 项。
注意：整数顺序将表示为一个字符串
class Solution {
public String countAndSay(int n) {
String countSequence=“1”;
if(n==1)return countSequence;
for(int i=2;i<=n;i++){
StringBuffer sb=new StringBuffer();
for(int j=0;j<countSequence.length()😉{
char current=countSequence.charAt(j);
int num=0;
while(j<countSequence.length()&&countSequence.charAt(j)==current){
num++;
j++;
}
sb.append(String.valueOf(num));
sb.append(current);
}
countSequence=sb.toString();
}
return countSequence;
}
}
mid-最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。
使用startsWith()方法判断一个字符串是不是另一个字符串的前缀。
class Solution {
public String longestCommonPrefix(String[] strs) {
int count=strs.length;
String prefix=“”;
if(count!=0){
prefix=strs[0];
}
for(int i=0;i<count;i++){
while(!strs[i].startsWith(prefix)){
prefix=prefix.substring(0,prefix.length()-1);
}
}
return prefix;
}
}
1 两数之和
给定一个整数数组和一个目标值，找出数组中和为目标值的两个数，返回它们的坐标。
你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
用HashMap！！！
class Solution {
public int[] twoSum(int[] nums, int target) {
int len = nums.length;
if(len<2)return null;
HashMap<Integer, Integer> map = new HashMap<>();
for(int i=0;i<len;i++){
if(map.containsKey(target-nums[i])){
return new int[]{i, map.get(target-nums[i])};
}
map.put(nums[i], i);
}
return null;
}
}
mid-15 三数之和 双指针
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
先对数组进行排序，然后遍历数组中小于等于0的部分，每次将当前元素设为三数中的其中一个，然后对数组剩余的部分运用两数之和的算法。
public List<List> threeSum(int[] nums) {
List<List> res = new ArrayList<List>();
if(nums == null || nums.length <= 2) return res;
Arrays.sort(nums);
for(int i = 0; i < nums.length; i++){
if(nums[i] > 0) break;
if(i > 0 && nums[i] == nums[i-1]) continue; //去重
int target = -nums[i];
int left = i+1;
int right = nums.length-1;
while(left < right){
if(nums[left] + nums[right] == target){
List sublist = new ArrayList();
sublist = Arrays.asList(nums[i],nums[left],nums[right]);
res.add(sublist);
left++;
right–;
while (nums[left] == nums[left-1] && left < right) left++;
while (nums[right] == nums[right+1] && left < right) right–;
}else if(nums[left] + nums[right] < target){
left++;
}else{
right–;
}
}
}
return res;
}
class Solution {
public List<List> threeSum(int[] nums) {
List<List> res = new ArrayList<>();
int len = nums.length;
if(len<3)return res;
Arrays.sort(nums);
int i = 0;
while(i<len&&nums[i]<=0){
int target = 0-nums[i];
int left = i+1;
int right = len-1;
while(left<right){
if(nums[left]+nums[right]==target){
res.add(Arrays.asList(nums[i], nums[left], nums[right]));
int l = nums[left];
while(left<right&&nums[left]==l)left++;
int r = nums[right];
while(left<right&&nums[right]==r)right–;
}else if(nums[left]+nums[right]>target)right–;
else left++;
}
int temp = nums[i];
while(i<len&&nums[i]==temp)i++;
}
return res;
}
}
mid-16 最接近的三数之和 双指针
三数之和最接近target，返回三数之和。假定存在一个解
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int res = nums[0]+nums[1]+nums[2];
for(int i = 0; i < nums.length-2; i++){
int left = i+1;
int right = nums.length-1;
while (left < right){
int sum = nums[i]+nums[left]+nums[right];
int dev = Math.abs(sum-target);
if(Math.abs(res-target) > dev){
res = sum;
}
if(sum < target){
left++;
}else{
right--;
}
}
}
return res;
}
mid-18 四数之和 双指针+双循环
/*
给定一个包含 n 个整数的数组 nums 和一个目标值 target，
判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？
找出所有满足条件且不重复的四元组。
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
满足要求的四元组集合为：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
使用双循环固定两个数，用双指针找另外两个数，通过比较与target 的大小（3数之和），移动指针。
？？如何跳过重复值
方法一：使用set：不能存重复值
方法二：当有重复值，改变索引（例如sum3）
*/
public class Sum4 {
public List<List> fourSum(int[] nums, int target) {
List<List> resList = new ArrayList<List>();
Arrays.sort(nums);
Set<List> set = new HashSet<List>();
int l = nums.length;
for(int i = 0; i < l-3; i++) {
if(nums[i] > target && target > 0) break;
for(int j = i+1; j < l-2; j++) {
int start = j+1;
int end = l-1;
while(start < end) {
int sum = nums[i]+nums[j]+nums[start]+nums[end];
if(sum == target) {
set.add(Arrays.asList(nums[i],nums[j],nums[start],nums[end]));
start++;
end–;
}else if(sum < target) {
start++;
}else {
end–;
}
}
}
}
for(List list : set) {
resList.add(list);
}
return resList;
}
}
mid-11盛最多水的容器 双指针
public int maxArea(int[] height) {
if(height == null || height.length <= 1) return 0;
int left = 0;
int right = height.length-1;
int res = 0;
while(left < right){
res = Math.max(res, (right-left)*Math.min(height[right],height[left]));
if(height[left] < height[right]){
left++;
}else{
right--;
}
}
return res;
}
mid-31 下一个排列 双指针
必须 原地 修改，只允许使用额外常数空间。
思路：
从右往左遍历，找到num[i-1]<nums[i]的位置i-1，然后遍历第二次，找到比num[i-1]数字大的数，二者交换，然后对i-1之后的元素进行翻转
时间复杂度：O(N)O(N)，其中 NN 为给定序列的长度。我们至多只需要扫描两次序列，以及进行一次反转操作。
空间复杂度：O(1)O(1)，只需要常数的空间存放若干变量
public void nextPermutation(int[] nums) {
int left = -1;
int right = 0;
for(int i = nums.length - 1; i > 0; i–) {
if(nums[i-1] < nums[i]) {
left = i-1;
break;
}
}
if(left >= 0) { //对于321，其下一个排列是第一个123，所以第二次循环和交换不需要做
for(int i = nums.length - 1; i > left; i–) {
if(nums[i] > nums[left]){
right = i;
break;
}
}
int tmp = nums[left];
nums[left] = nums[right];
nums[right] = tmp;
}
reserve(left + 1, nums);
}
public void reserve(int begin, int[] nums){
int end = nums.length - 1;
while(begin < end){
int tmp = nums[begin];
nums[begin] = nums[end];
nums[end] = tmp;
begin ++;
end --;
}
}
88 合并两个有序数组 逆向 双指针
逆向
//非递减数组，合并后仍保持非递减
//输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
//输出：[1,2,2,3,5,6]
public void merge(int[] nums1, int m, int[] nums2, int n) {
int last = m+n; //逆向
while(n > 0){
if(m > 0 && nums1[m-1] > nums2[n-1]){
nums1[–last] = nums1[–m];
}else{
nums1[–last] = nums2[–n];
}
}
}
mid-四数相加
/*
-
给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。 -
遍历 A 和 B 所有元素和的组合情况，并记录在 ab_map 中，ab_map 的 key 为两数和，value 为该两数和出现的次数
遍历 C 和 D 所有元素和的组合情况，取和的负值判断其是否在 ab_map 中，若存在则取出 ab_map 对应的 value 值，count = count + value
*/
public class Sum4_2 { public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
int count = 0;
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
int len = A.length;
for(int i = 0; i < len; i++) {
for(int j = 0; j < len; j++) {
int val = 0;
if(map.containsKey(A[i]+B[j])) {
val = (A[i]+B[j])+1;
}else {
val = 1;
}
map.put(A[i]+B[j], val);
}
} for(int m = 0; m < len; m++) {
for(int n = 0; n < len; n++) {
int sum = -(C[m]+D[n]);
int val = 0;
if(map.containsKey(sum)) {
val = sum;
}
count += val;
}
}
return count;
}
}
mid-矩阵置零
给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。
你能想出一个常数空间的解决方案吗？
用第一行的元素表示每一列是否存在0，第一列的元素表示每一行是否存在0，再使用额外两个变量firstRowIsZero，firstColIsZero判断第一行以及第一列本身是否存在0。
class Solution {
public void setZeroes(int[][] matrix) {
int row = matrix.length;
if(row0)return;
int col = matrix[0].length;
if(col0)return;
boolean firstRowIsZero = false;
boolean firstColIsZero = false;
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
if(i!=0&&j!=0&&matrix[i][j]0){
matrix[i][0] = 0;
matrix[0][j] = 0;
}else if(matrix[i][j]0){
firstRowIsZero = i0 ? true:firstRowIsZero;
firstColIsZero = j0 ? true:firstColIsZero;
}
}
}
for(int i=1;i<row;i++){
if(matrix[i][0]==0){
for(int j=1;j<col;j++)matrix[i][j] = 0;
}
}
for(int j=1;j<col;j++){
if(matrix[0][j]==0){
for(int i=1;i<row;i++)matrix[i][j] = 0;
}
}
if(firstRowIsZero){
for(int j=0;j<col;j++)matrix[0][j] = 0;
}
if(firstColIsZero){
for(int i=0;i<row;i++)matrix[i][0] = 0;
}
}
}
mid-字谜分组
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串
说明：
● 所有输入均为小写字母。
● 不考虑答案输出的顺序
创建一个HashMap<String, List>，将每个词中的字母重新排序，把排好序之后的词作为key存入HashMap中，对每次词都进行同样的排序操作，然后将这个词放入对应的键值对中，最后返回HashMap中value的集合。
class Solution {
public List<List> groupAnagrams(String[] strs) {
int len = strs.length;
if(len==0)return new ArrayList<List>();
Map<String, List> map = new HashMap<>();
for(String str:strs){
char[] chars = str.toCharArray();
Arrays.sort(chars);
String keyStr = String.valueOf(chars);
if(!map.containsKey(keyStr))map.put(keyStr, new ArrayList());
map.get(keyStr).add(str);
}
return new ArrayList<List>(map.values());
}
}
|