1.数组中重复的数字
【题目】
?【思路】
- 排序法：调用JDK中的排序算法，然后遍历数组，两两进行比较，遇到重复，返回结果（时间复杂度：O(nlogn)用在排序上，空间复杂度O(1)）空间复杂度O(1)意为算法执行所需要的临时空间不随着某个变量n的大小而变化
- 哈希表：准备一个哈希表，将数组中的第一个元素存入此表，后来的元素依次与哈希表进行判断，不过不存在那就存入该表，如果存在，那就返回该值(时间复杂度：O(n),空间复杂度O(n))
- 下标法1（用到了题目中给到的条件）：通过不断的交换元素，使得元素和它所对应的下标相等，因为有多个相同元素，所以会有多个元素对应同一个下标。
- 下标法2：建立一个新的数组长度为n，初始化所有元素，将第一个元素对应下标加一，后面的每一个元素对应的下标先进行判断，如果是0，那么加一，如果非0，那么返回该元素
?【代码】
下标法1
?class Solution {
public int findRepeatNumber(int[] nums) {
int sw;
for(int i=0;i<nums.length;i++){
while(nums[i]!=i){
if(nums[i]==nums[nums[i]])
return nums[i];
sw=nums[i];
nums[i]=nums[sw];
nums[sw]=sw;
}
}
return -1;
}
}下标法2
class Solution {
public int findRepeatNumber(int[] nums) {
int[] arr = new int[nums.length];
for(int i = 0; i < nums.length; i++){
arr[nums[i]]++;
if(arr[nums[i]] > 1) return nums[i];
}
return -1;
}
}2.二位数组中的查找
【思路】
-
暴力法：两层循环遍历寻找
-
二分查找：利用题目中有序这个条件，每行进行二分查找（时间复杂度：O(nlogn)用在排序上，空间复杂度O(1)）
-
换位思考，从左下角向右上角看，是一个二叉树
【代码】
换位思考
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
if(matrix==null||matrix.length<=0||matrix[0].length<=0)
return false;
int cols=matrix.length;
int rows=matrix[0].length;
int col=cols-1;
int row=0;
while(col>=0&&row<rows){
if(target<matrix[col][row]){
col--;
}else if(target>matrix[col][row]){
row++;
}else{
return true;
}
}
return false;
}
}书写注意：
- 查找前先排除极端条件（数组为空，行为空，列为空）
- 注意数组的长度的数字和数组的下标的数字细节描写（数组的长度是从1开始，数组下标是从0开始）
3.替换空格
【题目】
【思路】
- Java：String类
- C++：原地扩容
【代码】
Java：
class Solution {
public String replaceSpace(String s) {
StringBuilder stringBuilder=new StringBuilder();
for(int i=0;i<s.length();i++){
if(s.charAt(i)==' ')
stringBuilder.append("%20");
else{
stringBuilder.append(s.charAt(i));
}
}
return stringBuilder.toString();
}
}C++
class Solution {
public String replaceSpace(String s) {
int count=0;
for(int i=0;i<s.length();i++){
if(s.charAt(i)==' ')
count++;
}
//创建数组
char[] chars=new char[s.length()+count*2];
//进行倒序遍历
int n=s.length()+count*2-1;
for(int i=s.length()-1;i>=0;i--){
if(s.charAt(i)==' '){
chars[n--]='0';
chars[n--]='2';
chars[n--]='%';
}
else{
chars[n--]=s.charAt(i);
}
}
return new String(chars);
}
}4.从头到尾打印链表
【题目】
?【思路】
- 栈：利用栈先进后出的性质，对链表进行正向的遍历，反向的存储。
- 反转：将该链表进行反转
- 递归方法
- 原地反转
- 反向数组存贮：将链表进行正向的遍历，在数组中的存储从后向前。
?【代码】
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public int[] reversePrint(ListNode head) {
if(head==null)
return new int[0] ;
int count=0;
ListNode point=head;
while(point!=null){
count++;
point=point.next;
}
int[] nums=new int[count];
int k= count - 1;
while(head!=null||k>0){
nums[k--]=head.val;
head=head.next;
}
return nums;
}
}