数组和字符串
88 合并两个有序数组
思路中，正序考虑的东西很多，可以倒序插入
因为nums1在后面的数组为空
具体思路：
设定nums1 的index 为 m-1即数组一中最大值
设定nums2 的index为n-1即数组二中最大值
设定一个总的index为了插入数字
循环开始
因为要合并到nums1中，
就要确定nums2是否全部放入nums1中
比较nums1 和nums2的值的大小，谁大谁就在最后
在放nums1值时要确定index1是否大于0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int index1 = m - 1;
int index2 = n - 1;
int index = nums1.length - 1;
while(index2 >= 0){
if (index1 >= 0 && nums1[index1] > nums2[index2]){
nums1[index--] = nums1[index1--];
} else {
nums1[index--] = nums2[index2--];
}
}
}
}
|
27 移除元素
左右指针，不需要确定右指针是不是val，或者利用while loop确定右指针指到第一个不是val的值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public int removeElement(int[] nums, int val) {
int left = 0;
int right = nums.length - 1;
while (left <= right){
if (nums[left] == val){
nums[left] = nums[right--];
} else {
left++;
}
}
return left;
}
}
|
26 删除有序数组中的重复项
注意快慢指针的变化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int removeDuplicates(int[] nums) {
int slowIndex = 0;
int fastIndex = 0;
while (fastIndex < nums.length){
if (nums[fastIndex] != nums[slowIndex]){
nums[++slowIndex] = nums[fastIndex];
}
fastIndex++;
}
return slowIndex + 1;
}
}
|
80. 删除有序数组中的重复项 II
利用快慢指针
在快指针还没有到终点时
快指针和慢指针一起走，一起经历一个if循环，查看当前快指针，和前一个慢指针的点是否一致，一致则通过该点，此时快指针应移到不等于慢指针的前一个节点的点上
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int removeDuplicates(int[] nums) {
if (nums.length < 3) return nums.length;
int slowIndex = 0;
int fastIndex = 0;
while (fastIndex < nums.length){
nums[slowIndex++] = nums[fastIndex++];
if (fastIndex < nums.length && nums[fastIndex] == nums[slowIndex - 1])
nums[slowIndex++] = nums[fastIndex++];
while (fastIndex< nums.length && nums[fastIndex] == nums[slowIndex - 1]) fastIndex++;
}
return slowIndex;
}
}
|
169 多数元素
此题主要熟悉map的用法
利用map统计元素出现次数
利用for loop查看所有元素的次数
for(Map.Entry<Integer, Integer> entry : map.entrySet()){
}
entry.getValue()
entry.getKey();
具体代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int majorityElement(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
for (int i : nums){
map.put(i, map.getOrDefault(i, 0) + 1);
}
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
if (entry.getValue() > nums.length / 2) {
return entry.getKey();
}
}
return 0;
}
}
|
189 旋转数组
此题和反转字符串是一个思路，
首先整体反转
之后再局部反转
如果K=3， 前三个翻转，后面的翻转
唯一需要注意的是k值的转化，k值可能大于数组长度，所以需要去k%num.length的余数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public void rotate(int[] nums, int k) {
k %= nums.length;
reverseArray(nums, 0, nums.length - 1);
reverseArray(nums, 0, k - 1);
reverseArray(nums, k, nums.length - 1);
}
private void reverseArray(int[] nums, int start, int end){
while (start <= end){
int temp = nums[start];
nums[start++] = nums[end];
nums[end--] = temp;
}
}
}
|
121 购入股票最好时机
此题贪心算法，累加到是负值，清空重新计算，中间记录最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length <= 1) return 0;
int sum = 0;
int max = Integer.MIN_VALUE;
for (int i = 1; i < prices.length; i++){
sum += prices[i] - prices[i - 1];
if (sum < 0){
sum = 0;
} else {
max = Math.max(max, sum);
}
}
return max == Integer.MIN_VALUE ? 0 : max;
}
}
|
122 购入股票的最好时机II
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length <= 1) return 0;
int sum = 0;
for (int i = 1; i< prices.length; i++){
if (prices[i] - prices[i - 1] > 0){
sum += prices[i] - prices[i - 1];
}
}
return sum;
}
}
|
55 跳跃游戏
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length <= 1) return 0;
int sum = 0;
for (int i = 1; i< prices.length; i++){
if (prices[i] - prices[i - 1] > 0){
sum += prices[i] - prices[i - 1];
}
}
return sum;
}
}
|
45 跳跃游戏II
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public int jump(int[] nums) {
if (nums == null || nums.length <= 1) return 0;
int count = 0;
int maxLen = 0;
int curLen = 0;
for (int i = 0; i < nums.length; i++){
maxLen = Math.max(maxLen, i + nums[i]);
if (maxLen >= nums.length - 1) return ++count;
if (i == curLen){
curLen = maxLen;
count++;
}
}
return count;
}
}
|
274 H-index
利用binary search，所有数值，数出每一组mid的count值，进行比较，多了，就取右边，少了就取左边，最后输出一个值
不能用位运算
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public int hIndex(int[] c) {
int low=0 , high = c.length;
while(low < high){
int mid = (low+high+1)/2;
int cnt=0;
for(int i=0 ; i<c.length ; i++) if(c[i] >= mid) cnt++;
if(cnt >= mid) low = mid;
else high = high=mid-1;
}
return low;
}
}
|