1两字符串和两字符串和
给定两个仅含数字的字符串，你需要返回一个由各个位之和拼接的字符串
样例:
示例1: 输入: A = "99" B = "111" 输出: "11010" 解释: 因为 9 + 1 = 10, 9 + 1 = 10, 0 + 1 = 1,连接
解法：
public String SumofTwoStrings(String A, String B) {
// write your code here
String result = "";
int lenA = A.length(), lenB = B.length();
int Aindex = lenA - 1, Bindex = lenB - 1;
while(Aindex >= 0 && Bindex >= 0){
//计算出各个位上的和的值。
int temp = (A.charAt(Aindex) - '0') + (B.charAt(Bindex) - '0');
//利用字符串 + 的拼接，使各个位上的和相互拼接。
result = String.valueOf(temp) + result;
//向上移动一位
Aindex--; Bindex--;
}
//判断A和B那个数的位数更大，再与结果直接相加。
if(Aindex >= 0) result = A.substring(0, Aindex + 1) + result;
if(Bindex >= 0) result = B.substring(0, Bindex + 1) + result;
return result;
}
2.旋转数组
给定一个数组，将数组向右移动k步，其中k为非负数。
样例 :
输入: [1,2,3,4,5,6,7], k = 3 输出: [5,6,7,1,2,3,4] 解释: 向右旋转1步: [7,1,2,3,4,5,6] 向右旋转2步: [6,7,1,2,3,4,5] 向右旋转3步: [5,6,7,1,2,3,4]
一个结论：rotate之前数组中位置i的元素在rotate之后位于位置(i+k) % nums.length.
思路1：观察初始数组和结果数组
可以发现如果把数组的[1,2,3,4]视为一块，把[5,6,7]视为另一块，要得到结果就只要把这两块互换一下位置即可，即原来在数组左边的现在放到右边，原来在右边的放到左边。而块的边界是由k和数组的长度唯一确定的。
怎么实现这样的操作？有个技巧就是三次翻转——先分别翻转左、右两边的块，再翻转整个数组。
这个做法不容易想到，算是针对该问题的特定方法。
public int[] rotate(int[] nums, int k) {
if (nums == null || k == 0) {
return nums;
}
k = (k % nums.length);
//对数组分别进行反转。
reverse(nums, 0, nums.length-k-1);
reverse(nums, nums.length-k, nums.length-1);
//整体进行反转，即将两部分数组交换顺序。
reverse(nums, 0, nums.length-1);
return nums;
}
//构建方法，使数组进行反转。
private void reverse(int[] nums, int st, int ed) {
for (int i = st, j = ed; i < j; i++, j--) {
int tmp = nums[j];
nums[j] = nums[i];
nums[i] = tmp;
}
思路2：用辅助数组
public int[] rotate(int[] nums, int k) {
if (nums == null || k == 0) {
return nums;
}
k = (k % nums.length);
int[] helper = new int[nums.length];
//巧妙利用结论，运用辅助数组进行旋转。
for (int i = 0; i < nums.length; ++i) {
helper[(i+k)%nums.length] = nums[i];
}
return helper;
}
3.回文数
判断一个非负整数 n 的二进制表示是否为回文数
样例1：
输入: n = 3 输出: True 解释: 3 的二进制表示为：11。
样例2：
输入: n = 4 输出: False 解释: 4 的二进制表示为：100。
思路：笨方法，暴力解
public boolean isPalindrome(int n) {
// 先算出二进制 再判断是否回文
if(n==0 || n==1)
return true;
Stack stack = new Stack();
//化为二进制：
while(n/2!=0) {
stack.add(n%2);
n = n/2;
}
stack.add(1);
int size = stack.size();
// size 即二进制的位数是 基数或者偶数都可以统一下面处理
for(int i = 0;i
4.移动零
给一个数组 nums 写一个函数将 0 移动到数组的最后面，非零元素保持原数组的顺序
样例：
输入: nums = [0, 1, 0, 3, 12],
输出: [1, 3, 12, 0, 0].
输入: nums = [0, 0, 0, 3, 1],
输出: [3, 1, 0, 0, 0].
思路：利用双指针，left代表新数组，right代表老数组
public void moveZeroes(int[] nums) {
// Write your code here
int left = 0, right = 0;
while (right < nums.length) {
if (nums[right] != 0) {
//利用双指针进行便利，使不为零的数值移动到数组的前面。
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
//left为新数组，反转后上面一定不为零，储存为新数组，指针移动到下一位。
left++;
}
//每次循环移动旧数组指针进行遍历。
right++;
}
}
5.数组第二大数
在数组中找到第二大的数。
样例：
输入：[1,3,2,4]
输出：3
输入：[1,1,2,2]
输出：2
思路1： 维护最大数和此大数即可
public int secondMax(int[] nums) {
//定义时简单判断0.1位上的大小关系。
int max = Math.max(nums[0], nums[1]);
int second = Math.min(nums[0], nums[1]);
for (int i = 2; i < nums.length; i++) {
//遍历数组，若出现更大的值，使第二大值变成上一个最大值，并更换最大值。
if (nums[i] > max) {
second = max;
max = nums[i];
//若出现比第二大值大而比最大值小的，交换第二大值。
} else if (nums[i] > second) {
second = nums[i];
}
}
return second;
}
思路2：利用库，先排序，再取倒数第二个。
public int secondMax(int[] nums) {
//默认排序从小到大
Arrays.sort(nums);
return nums[nums.length-2];
}
6.最长单词
给一个词典，找出其中所有最长的单词。
样例 1:
输入: {
"dog",
"google",
"facebook",
"internationalization",
"blabla"
}
输出: ["internationalization"]
样例 2:
输入: {
"like",
"love",
"hate",
"yes"
}
输出: ["like", "love", "hate"]
思路：简单模拟，使用一个list记录单词，如果遇见更长的单词就讲list清空并保存新的字符串。
public List longestWords(String[] dictionary) {
// write your code here
List list = new ArrayList<>();
if (dictionary.length == 0) {
return list;
}
list.add(dictionary[0]);
for (int i = 1; i < dictionary.length; i++) {
if(dictionary[i].length() > list.get(list.size() - 1).length()) {
list.clear();
list.add(dictionary[i]);
} else if (dictionary[i].length() == list.get(list.size() - 1).length()) {
list.add(dictionary[i]);
} else {
continue;
}
}
return list;
}
7.最后一个单词的长度
给定一个字符串， 包含大小写字母、空格 ' '，请返回其最后一个单词的长度。
如果不存在最后一个单词，请返回 0
样例 ：
输入："Hello World"
输出：5
思路
public int lengthOfLastWord(String s) {
int length = 0;
char[] chars = s.toCharArray();
for (int i = s.length() - 1; i >= 0; i--) {
if (length == 0) {
//不存在，返回length = 0；
if (chars[i] == ' ') {
continue;
} else {
length++;
}
} else {
if (chars[i] == ' ') {
break;
} else {
length++;
}
}
}
return length;
}
8.打印X
输入一个正整数N， 你需要按样例的方式返回一个字符串列表。
输入：
n = 1
输出：
["X"]
X
输入：
n = 2
输出：
["XX", "XX"]
XX
XX
输入：
n = 3
输出：
["X X", " X ", "X X"]
X X
X
X X
输入：
n = 4
输出：
["X X", " XX ", " XX ", "X X"]
X X
XX
XX
X X
输入：
n = 5
输出：
["X X", " X X ", " X ", " X X ", "X X"]
X X
X X
X
X X
X X
思路：
public List printX(int n) {
ArrayList res=new ArrayList<>();//创建一个存放String类型属性的ArrayList，名称为res
char[] line=new char[n];//创建一个长度为n的字符型数组line
for(int i=0;i
9.最大字母
给定字符串S，找到最大的字母字符，其大写和小写字母均出现在S中，则返回此字母的大写，若不存在则返回"NO"。
样例：
输入: S = "admeDCAB"
输出: "D"
输入: S = "adme"
输出: "NO"
思路：先找到大写字母最大值的ASCII码然后放起来，再继续遍历一次有没有它的小写字母，通过ASCII码找。
public String largestLetter(String s) {
// write your code here
int temp=0;
//遍历找到最大的大写字母。
for (int i = 0; i ='A' && s.charAt(i)>temp) {
temp = s.charAt(i);
}
}
//寻找有没有其小写字母。
for (int i = 0; i < s.length(); i++) {
if(s.charAt(i)==temp+32) {
return String.valueOf((char)(temp));
}
}
return "NO";
}
10.主元素
给定一个整型数组，找出主元素，它在数组中的出现次数大于数组元素个数的二分之一。
输入：
数组 = [1, 1, 1, 1, 2, 2, 2]
输出：
1
思路：保存当前出现次数最多的元素 currentMajor 和一个 count，循环遍历 nums 所有元素，当 count 为 0 的时候把 currentMajor 设为当前遍历到的元素。
public int majorityNumber(List nums) {
int currentMajor = 0;
int count = 0;
//对集合中的每一个数进行遍历。
for(Integer num : nums) {
//用于交换当前的数值，因为大于二分之一，最后currentMajor一定为主元素。
if(count == 0) {
currentMajor = num;
}
//是就加，不是就减
if(num == currentMajor) {
count++;
} else {
count--;
}
}
return currentMajor;
}
11.字符串查找
对于一个给定的 source 字符串和一个 target 字符串，你应该在 source 字符串中找出 target 字符串出现的第一个位置(从0开始)。如果不存在，则返回 -1。
输入：
source = "abcdabcdefg"
target = "bcd"
输出：
1
解释：
如果source里包含target的内容，返回target在source里第一次出现的位置
思路：
-
先进行特判，若target长度为0，则返回0；若target的长度大于source，则表示不可能匹配，返回-1
-
枚举匹配source的起始位置，从0到sourceLen-targetLen
-
对于一个起始位置，比对之后的targetLen位是否相同，若遇到不相同直接退出判断，尝试下一个起始位置
-
当成功比对完targetLen位后，说明全部相同，则返回起始位置
public int strStr(String source, String target) {
//获取两个字符串的长度
int sourceLen = source.length();
int targetLen = target.length();
//注意特判，若target长度为0则答案为0
if(targetLen == 0){
return 0;
}
//若target长度大于source，则不可能匹配
if(targetLen > sourceLen){
return -1;
}
for(int i = 0; i < sourceLen-targetLen+1; i++){
//k表示比对时source中所指向的字符
int k = i;
for(int j = 0; j < targetLen; j++){
if(source.charAt(k) == target.charAt(j)){
//最后一个字符匹配完成，输出答案
if(j == targetLen - 1){
return i;
}
k++;
}
//其中一个字符无法匹配，直接退出做下一次循环
else{
break;
}
}
}
return -1;
}
12.加一
给定一个非负数，表示一个数字数组，在该数的基础上+1，返回一个新的数组。
该数字按照数位高低进行排列，最高位的数在列表的最前面。
输入：[1,2,3]
输出：[1,2,4]
输入：[9,9,9]
输出：[1,0,0,0]
思路：考虑0 - 9. 只有9要2 operations. Time = 10/9 = O(1). 如果跑完digits，extra还是1，
则结果是100..0. 所以只要result[0] = 1就好了。
public int[] plusOne(int[] digits) {
// write your code here
int extra = 1;
for (int i = digits.length - 1; i >= 0; i--) {
int sum = digits[i] + extra;
//保留一位数。
digits[i] = sum % 10;
//若出现进位，则保留进位。
extra = sum / 10;
//不进位直接跳出循环。
if (extra == 0) {
break;
}
}//最后一位没进位直接放回值。
if (extra == 0) {
return digits;
}//进位则让最前一位变成1.
int[] result = new int[digits.length + 1];
result[0] = 1;
return result;
}
13.翻转字符串
给定一个字符串，逐个翻转字符串中的每个单词。
输入：
s = "the sky is blue"
输出：
"blue is sky the"
思路1：运用String split。
public String reverseWords(String s) {
// write your code here
if(s.length() == 0 || s == null) {
return "";
}
//按照空格将s切分
String[] array = s.split(" ");
StringBuilder sb = new StringBuilder();
//从后往前遍历array，在sb中插入单词
for(int i = array.length - 1; i >= 0; i--) {
if(!array[i].equals("")) {
if (sb.length() > 0) {
sb.append(" ");
}
sb.append(array[i]);
}
}
return sb.toString();
}
思路2：通过左右指针找到每个word，然后reverse it。
public String reverseWords(String s) {
char cs[] = s.trim().toCharArray();
StringBuilder sb = new StringBuilder();
reverse(cs, 0, cs.length-1);
int l = 0, r = 0;
while(r < cs.length){
while(r < cs.length && cs[r] == ' '){
r++;
}
while(l < r && cs[l] == ' '){
l++;
}
while(r < cs.length && (cs[r] != ' ' || r == cs.length-1)){
r++;
}
reverse(cs, l, r-1);
for(int i = l; i <= r-1; i++){
sb.append(cs[i]);
}
sb.append(' ');
l=r;
}
if(sb.length() > 0){
sb.deleteCharAt(sb.length()-1);
}
return sb.toString();
}
public void reverse(char cs[], int begin, int end){
int l = begin, r = end;
while(l < r){
char t = cs[l];
cs[l] = cs[r];
cs[r] = t;
l++;
r--;
}
}
14.数组剔除元素后的乘积（还未懂）
给定一个整数数组A。
定义B[i] = A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1]B[i]=A[0]∗...∗A[i−1]∗A[i+1]∗...∗A[n−1]， 计算B的时候请不要使用除法。请输出B。
输入：
A = [1,2,3]
输出：
[6,3,2]
解释：
B[0] = A[1] * A[2] = 6; B[1] = A[0] * A[2] = 3; B[2] = A[0] * A[1] = 2
思路：先遍历一遍数组，每一个位置上存之前所有数字的乘积。那么一遍下来，最后一个位置上的数字是之前所有数字之积;
这时候再从后往前扫描，每个位置上的数在乘以后面所有数字之积.对于最后一个位置来说，由于后面没有数字了，所以乘以1就行。
public class Solution {
public List productExcludeItself(List nums) {
long[] res = new long[nums.size()];
long left = 1;
res[0] = 1;
for(int i = 1 ; i < nums.size(); i++ ) {
left = left * (long)nums.get(i - 1);
res[i] = left;
}
long right = 1;
for(int i = nums.size() - 2; i >= 0 ; i-- ) {
right = right * nums.get(i + 1);
res[i] = res[i] * right;
}
List result = new ArrayList<>();
for(long num : res) {
result.add(num);
}
return result;
